crypto-PellRSA(2022 ISG CTF)

RSA新套路，记录一下。

题目源码：

from secret import flag, x, y
from Crypto.Util.number import *

D = 0x1337
assert x**2 - D*y**2 == 1

p, q = [getPrime(1024) for _ in range(2)]
n = p * q
e = 0x10001
m = bytes_to_long(flag)
c = pow(m, e, n)
hint = x*p+y*q

print(f"c = {c}")
print(f"n = {n}")
print(f"hint = {hint}")

# c = 3005210900274062028245064763681985171865732477888576575723787090796927451576980061053851866237955581217514145765632113368490115032450199985758227732632048361191007646408276913089831906329971437230559530448171301727266374997545370123383402726558627115715475862029561278423823518444820977264751303044302265493708799121168143462311965945091467240934532001260635332451496021570344953585558566967953242376305314361254897583062914601586502797581537297696760063459202795730665696764263768365841709190449166538288878080889669665026312901303009296451551464554389754163788816398944455459009524861984572615424670639254030151054
# n = 15718757517521251374958179320446142283106866234677555962716669310992898890185071974665307763506272733881181355624859739900598443787336490077978994566789053663418590696159044391330241067187081512182824631894647418510875405615745967831095900926071879310908555025126167350062806600612989286959517901360623166342258230751843299825036857599702420000410748900477339859195343125679909303239140523015164436167732911014179093209512745136065705348000005927264077855404829601870427156494640300513831498305781704787224695635843906200844830814368296185775476464094439535093160507307060825299000779102353898638521855718963250126411
# hint = 25554225946418820739932963199267565143249197331792582934680530259781352338033809894486636299663276720660161274600116944243562621815071872332713982731906833226185925332402882590577780931343494988584492568662132160373007142250538311414299314391751747130332966573464023483628487169137147382668830758422851921134062566813674606680584569364070329996014784761466853704469300230627289640396078029124024721492689780252172435786800400687554721418435802505512555196774950296179670031042084572223128748401

题目一开始是佩尔方程$x^2-D{y}^2=1$
其中x和y都未知需要进行枚举。参考连分数法解佩尔方程特解

又根据关系式$hint=xp+yq=a+b$
有$$a^2-a\times hint=x^2{p}^2-x^2{p}^2-xypq=-xypq$$
同理$$b^2-b\times hint=y^2{q}^2-y^2{q}^2-xypq=-xypq$$
即a,b是一元二次方程
$$z^2-z\times hint+xyn=0,z\in \mathbb{Z}$$的解；
由于 hint,x,y,n 已知，则利用韦达定理求解该方程，若解为整数即可进一步推出p,q ；最后老套路RSA解密即可。

最终exp：

#sage
from Crypto.Util.number import *
from gmpy2 import iroot

def solve_pell(N, numTry = 100):
    cf = continued_fraction(sqrt(N))    
    for i in range(numTry):
        denom = cf.denominator(i)
        numer = cf.numerator(i)        
        if numer^2 - N * denom^2 == 1:            
            return numer, denom    
    return None, None

def gen_pell(D):
    x, y = solve_pell(D)
    xs = [x]
    ys = [y]    
    while True:        
        yield xs[-1], ys[-1]
        x_i = xs[0] * xs[-1] + D * ys[0] * ys[-1]
        y_i = xs[0] * ys[-1] + ys[0] * xs[-1]
        xs.append(x_i)
        ys.append(y_i)


c = 3005210900274062028245064763681985171865732477888576575723787090796927451576980061053851866237955581217514145765632113368490115032450199985758227732632048361191007646408276913089831906329971437230559530448171301727266374997545370123383402726558627115715475862029561278423823518444820977264751303044302265493708799121168143462311965945091467240934532001260635332451496021570344953585558566967953242376305314361254897583062914601586502797581537297696760063459202795730665696764263768365841709190449166538288878080889669665026312901303009296451551464554389754163788816398944455459009524861984572615424670639254030151054
n = 15718757517521251374958179320446142283106866234677555962716669310992898890185071974665307763506272733881181355624859739900598443787336490077978994566789053663418590696159044391330241067187081512182824631894647418510875405615745967831095900926071879310908555025126167350062806600612989286959517901360623166342258230751843299825036857599702420000410748900477339859195343125679909303239140523015164436167732911014179093209512745136065705348000005927264077855404829601870427156494640300513831498305781704787224695635843906200844830814368296185775476464094439535093160507307060825299000779102353898638521855718963250126411
hint = 25554225946418820739932963199267565143249197331792582934680530259781352338033809894486636299663276720660161274600116944243562621815071872332713982731906833226185925332402882590577780931343494988584492568662132160373007142250538311414299314391751747130332966573464023483628487169137147382668830758422851921134062566813674606680584569364070329996014784761466853704469300230627289640396078029124024721492689780252172435786800400687554721418435802505512555196774950296179670031042084572223128748401
e = 0x10001
N = 0x1337

for (x, y) in gen_pell(N):
    z = var('z')
    delta = hint**2 - 4*x*y*n    
    if iroot(delta, 2)[1] == True:
        sol = solve(z**2-hint*z+x*y*n==0, z, solution_dict=True)
        a, b = int(z.subs(sol[0])), int(z.subs(sol[1]))
        a, b = [a, b] if a > b else [b, a]
        p, q = a // x, b // y        
        break
assert p * q == n
        
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = int(pow(c, d, n))
print(long_to_bytes(m))