Find the flag
data
Summary: Coppersmith’s short pad attack
In this challenge we are given a python script and a set of files generated by it. Here’s the main part:
r = generate_random_number_bytes(1024) p = get_prime(r % (2**512)) q = get_prime((r << 512) % (2**512)) n = p*q open('out/n1','w').write(str(n)) e=3 flag_index = random.getrandbits(10) for i in range(0, 1024): if i <> flag_index: encryptedFlag = pow(FLAG * 2**32 + random.getrandbits(32), e, n) open('out/flag'+str(i),'w').write(str(encryptedFlag)) r = generate_random_number_bytes(1024) p = get_prime(r % (2**512)) q = get_prime((r >> 512) % (2**512)) |
Flag is also encrypted under another random modulus (n2) but it is not relevant for this challenge (the author confirmed it was added to make the tasks rsa1 and rsa2 look similar).
Here we have 1023 messages encrypted. Each message is the flag padded with 32 random least significant bits. There is a classic attack for this setting – Coppersmith’s Short Pad attack. The description on Wikipedia is enough to implement the attack in Sage, though there is a little problem: Sage doesn’t want to compute the so called resultant of two polynomials modulo composite number:
ValueError: Resultants require base fields or integer base ring. |
We can overcome this issue by switching the ring to ZZ and back.
The first phase of the attack is to take some two of the encrypted messages and recover the small difference between them:
from sage.all import * n1 = long(open("out/n1").read()) e = 3 C1 = long(open("out/flag0").read()) C2 = long(open("out/flag1").read()) PRxy.<x,y> = PolynomialRing(Zmod(n1)) PRx.<xn> = PolynomialRing(Zmod(n1)) PRZZ.<xz,yz> = PolynomialRing(Zmod(n1)) g1 = x**e - C1 g2 = (x + y)**e - C2 q1 = g1.change_ring(PRZZ) q2 = g2.change_ring(PRZZ) h = q2.resultant(q1) # need to switch to univariate polynomial ring # because .small_roots is implemented only for univariate h = h.univariate_polynomial() # x is hopefully eliminated h = h.change_ring(PRx).subs(y=xn) h = h.monic() roots = h.small_roots(X=2**40, beta=0.3) assert roots, "Failed1" diff = roots[0] if diff > 2**32: diff = -diff C1, C2 = C2, C1 print "Difference:", diff |
The second stage is to apply Franklin-Reiter related messages attack to recover the message:
x = PRx.gen() # otherwise write xn g1 = x**e - C1 g2 = (x + diff)**e - C2 # gcd while g2: g1, g2 = g2, g1 % g2 g = g1.monic() assert g.degree() == 1, "Failed 2" # g = xn - msg msg = -g[0] # convert to str h = hex(int(msg))[2:].rstrip("L") h = "0" * (len(h) % 2) + h print `h.decode("hex")` |
The flag: Drgns{She’s_playin’_dumb_all_the_timeJust_to_keep_it_funTo_get_you_on_like_ahh!Be_careful_amigoShe_talkin’_and_walkin}
