ciscn2024

Crypto

OvO

$e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1$ $e = 65537 + kk * p + (kk+2) * ((p+1) * (q+1)) + 1$ $e = 65537 + kk * p + (kk+2) *n+(kk+2) * p+(kk+2) * q + 1$

因为k为128位，p,q为512位，e近似（kk+2）*n,所以

$k=e//n-2$

等式两边同乘以p

$e*p = 65537*p + kk * p^2 + (kk+2) *n*p+(kk+2) * p^2+(kk+2) * n + p$

所以存在

$e_h*p_h = 65537*p_h + kk * n + (kk+2) *n*p_h+(kk+2) * n+(kk+2) * p_h^2 + p_h$

解方程可得到p的高位，然后就是已知p的高位求解，直接套板子

from Crypto.Util.number import * 
 
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823

k = e // n - 2 

R.<x> = PolynomialRing(RealField(1024)) 

f=e*x-(65538*x+k*x^2+(k+2)*n*x+(k+2)*x^2+(k+2)*n)

res = f.roots() 
 
for i in res: 
    p_h = int(i[0]) 
    PR.<x> = PolynomialRing(Zmod(n)) 
    f1 = x + p_h
    roots = f1.monic().small_roots(X=2^200,beta=0.4) 
    if roots: 
        p = int(roots[0]) + p_h
        #print(p,n%p)
        if p and n%p==0:
            q= n // p
            e = 65537 + k * p + (k+2) * ((p+1) * (q+1)) + 1 
            d = inverse(e,(p-1)*(q-1)) 
            m = pow(c,d,n) 
            print(long_to_bytes(int(m)))
            
#b'flag{b5f771c6-18df-49a9-9d6d-ee7804f5416c}'