一题多解：结构相似 RSA 的参数回收与多路径收尾
from math import gcd
from gmpy2 import isqrt
from Crypto.Util.number import *
from sympy.ntheory.modular import crt
e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
N1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
N2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
c1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865
class ContinuedFraction():
def __init__(self, numerator, denumerator):
self.numberlist = []
self.fractionlist = []
self.GenerateNumberList(numerator, denumerator)
self.GenerateFractionList()
def GenerateNumberList(self, numerator, denumerator):
while numerator != 1:
quotient = numerator // denumerator
remainder = numerator % denumerator
self.numberlist.append(quotient)
numerator = denumerator
denumerator = remainder
def GenerateFractionList(self):
self.fractionlist.append([self.numberlist[0], 1])
for i in range(1, len(self.numberlist)):
numerator = self.numberlist[i]
denumerator = 1
for j in range(i):
temp = numerator
numerator = denumerator + numerator * self.numberlist[i - j - 1]
denumerator = temp
self.fractionlist.append([numerator, denumerator])
a = ContinuedFraction(N1, N2)
for (_, solve) in enumerate(a.fractionlist):
if solve[0].bit_length() == 256 and solve[1].bit_length() == 256:
a2, k = solve
if gcd(a2, k) == 1:
inve = inverse(k, e)
_phi = int(crt([a2, e], [0, -inve%e])[0])
M = a2*e
for i in range(-10,10):
phi = (N1//M)*M+i*M+_phi
s = N1-phi+1
delta = s*s-4*N1
if delta > 0:
t = isqrt(delta)
if t*t == delta:
p = (s+t)//2
q = (s-t)//2
d = inverse(e, (p-1)*(q-1))
m = pow(c1, d, N1)
print(long_to_bytes(m).decode())
