babyRSA - 200 points
Writeup by Valar_Dragon
- Cryptography
- 200 points
- Message intercepted. Break it.
- 72 Solves
We're given the output of
from Crypto.PublicKey import RSA
key = RSA.generate(4096, e=5)
msg = "welcome to uiuctf!\nyour super secret flag is: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
m = int(msg.encode("hex"), 16)
c = pow(m, key.e, key.n)
f = open("babyrsa.txt", "w")
print >> f, "n = {}".format(key.n)
print >> f, "e = {}".format(key.e)
print >> f, "c = {}".format(c)
That's a short message, and tiny exponent! I wonder if it even wraps around the modulus! len(msg) = 96
Size of ciphertext with no modular reduction is
So our ciphertext didn't even wrap around the modulus, so we can just take the 5th root of it!
>>> import gmpy
>>> e = 5
>>> c = 199037898049081148054548566008626493558290050160287889209057083223407180156125399899465196611255722303390874101982934954388936179424024104549780651688160499201410108321518752502957346260593418668796624999582838387982430520095732090601546001755571395014548912727418182188910950322763678024849076083148030838828924108260083080562081253547377722180347372948445614953503124471116393560745613311509380885545728947236076476736881439654048388176520444109172092029548244462475513941506675855751026925250160078913809995564374674278235553349778352067191820570404315381746499936539482369231372882062307188454140330786512148310245052484671692280269741146507675933518321695623680547732771867757371698350343979932499637752314262246864787150534170586075473209768119198889190503283212208200005176410488476529948013610803040328568552414972234514746292014601094331465138374210925373263573292609023829742634966280579621843784216908520325876171463017051928049668240295956697023793952538148945070686999838223927548227156965116574566365108818752174755077045394837234760506722554542515056441166987424547451245495248956829984641868331576895415337336145024631773347254905002735757
>>> m = gmpy.root(c,e)
>>> m = int(m[0].digits())
>>> m
724081006093103073870411844755532358755197342008573377061438844308314214677217990779288710263091538385722490992008161940721129371454559070484736279173692896173427956436750374207114456505619477221672052481060102010477488477517411197
>>> import binascii
>>> binascii.unhexlify(hex(m)[2:])
b'welcome to uiuctf!\nyour super secret flag is: flag{c4n_w3_get_s0m3b0dy_t0_sm1th_some_c0pper_pls}'
Flag: flag{c4n_w3_get_s0m3b0dy_t0_sm1th_some_c0pper_pls}
Nice and quick problem!