Sepertinya tidak ada yang aneh dari source code tersebut , jadi selanjutnya kami coba cek keynya dan ternyata nilai e yang diberikan besar.
Dari sini kami coba lakukan common attack pada rsa dengan public exponent besar yaitu menggunakan wiener attack dan ternyata berhasil. Berikut script yang kami gunakan
continued_fractions.py
defrational_to_contfrac(x,y):# Converts a rational x/y fraction into a list of partial quotients [a0, ..., an] a = x // y pquotients = [a]while a * y != x: x, y = y, x - a * y a = x // y pquotients.append(a)return pquotientsdefconvergents_from_contfrac(frac):# computes the list of convergents using the list of partial quotients convs = [];for i inrange(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))return convsdefcontfrac_to_rational (frac):# Converts a finite continued fraction [a0, ..., an] to an x/y rational.iflen(frac)==0:return (0,1) num = frac[-1] denom =1for _ inrange(-2, -len(frac) -1, -1): num, denom = frac[_]* num + denom, numreturn (num, denom)
test_rsa.py
from continued_fractions import*from Crypto.Util.number import*n = 136375679787927244696289795885005648815108289212464497859431615538673042375946778524473848398525037451190261199521819004739278031645357897677734698610951953541404381824146329328624288281641905271183010840974530269547547895439947481142131892305619548317029068789911069885321453469718238390495448090075373321029
e = 9934026283243447335784142672216496968427437150405829331521710602854826988915623834828401428975156770075612396739682567963382915587369749409382765177454083732327254135875299330600089331382217653825675232007843740755445444239391851451767573941155945865534339871956773517088821953019398585021686663749551991183
tmp =open('flag.enc', 'r').read()c =bytes_to_long(tmp[::-1])defegcd(a,b):if a ==0:return (b,0,1) g, x, y =egcd(b % a, a)return (g, y - (b // a) * x, x)defmod_inv(a,m): g, x, _ =egcd(a, m)return (x + m) % mdefisqrt(n): x = n y = (x +1) //2while y < x: x = y y = (x + n // x) //2return xdefcrack_rsa(e,n): frac =rational_to_contfrac(e, n) convergents =convergents_from_contfrac(frac)for (k, d) in convergents:if k !=0and (e * d -1) % k ==0: phi = (e * d -1) // k s = n - phi +1# check if x*x - s*x + n = 0 has integer roots D = s * s -4* nif D >=0: sq =isqrt(D)if sq * sq == D and (s + sq) %2==0:return dd =crack_rsa(e, n)print(long_to_bytes(int(str(pow(c,d,n)),8))[::-1])
Flag : MDT4.0{small_d__i_mean_d_as_RSA_private_key}