The problem was called “Broadcast” and we got some big integer variables named e,c1,n1,c2,n2,c3,n3. However I know that it is a RSA stuff  but I didn’t understand how we could decrypt the message. At the first time, i tried to factorize the number using but i got nothing, the number is too big. When i went back to the problems page,  there was a hint said that this problem is about RSA attack on small public exponent. I did my best on google and i found that this problem is about Håstad’s Broadcast Attack.

Basically, as I know (yup, i do not know much about this kind of stuff), Håstad’s Broadcast Attack is a mathematical approach to recover secret message that encrypted using RSA with multiple different moduli numbers known as n1, n2, n3,…, ni and a single small public exponent e. This attack is based on Chinese Reminder Theorem(CRT) that said if all the moduli are relatively prime, we can compute x such as x ≡ y1 (mod n1), x ≡ y2 (mod n2), x ≡ y3 (mod n3). In this case we know that x is our secret message raised to e and yi is our ciphertexts. So, we could recover the secret message by computing x using CRT and then the e-th root of x.

I did python to solve this problem.

import gmpy2
import binascii
e = 3
c1 = gmpy2.mpz("261345950255088824199206969589297492768083568554363001807292202086148198677263604958247638518239089545015544140878441375704999371548235205708718116265184277053405937898051706510050325657424248032017194168466912140157665066494528590260879287464030275170787644749401275343677539640347609231708327119700420050952")
n1 = gmpy2.mpz("1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627")
c2 = gmpy2.mpz("147535246350781145803699087910221608128508531245679654307942476916759248448374688671157343167317710093065456240596223287904483080800880319712443044372346198448258006286828355244986776657425121775659144630571637596283100201930037799979864768887420615134036083295810488407488056595808231221356565664602262179441")
n2 = gmpy2.mpz("405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309")
c3 = gmpy2.mpz("633230627388596886579908367739501184580838393691617645602928172655297372282390454586345936209841638502749645277206386289490247066959822668419069562380546618337543323956757811325946190976649051724173510367477564435069180291575386473277111391106753472257905377429144209593931226163885326581862398737742032667573")
n3 = gmpy2.mpz("1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723")

M = n1*n2*n3
m1 = M/n1
m2 = M/n2
m3 = M/n3

t1 = c1*(m1)*gmpy2.invert(m1,n1)
t2 = c2*(m2)*gmpy2.invert(m2,n2)
t3 = c3*(m3)*gmpy2.invert(m3,n3)

x = (t1+t2+t3) % M # chinese reminder theorem
m, exact = gmpy2.iroot(x,e) # recover m
if exact:
    print binascii.unhexlify(gmpy2.digits(m,16)) # convert int -> hex -> ascii

Run the script and we got the flag : broadcast_with_small_e_is_killer_76217934106

Unfortunately, I am still new to cryptography, that’s why i couldn’t explain much about this problem. There are a lot of good explanation about cryptography and number theory on the Net and that things help me a lot when i play CTF.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s