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 an RSA stuff but I didn’t understand how we could decrypt the message. At the first time, I tried to factorize the number using factordb.com 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 the 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 the 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 Remainder 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 the 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.

Advertisements

2 thoughts on “Håstad’s Broadcast Attack [PICO CTF Level 3 Crypto]

    1. Sorry for a late reply. If you are using python3, you need to install gmpy2 for python3. With Ubuntu in your machine, you just install the library using apt install python3-gmpy2.
      Unfortunately, there is a problem when I tried it on Python 3.
      Here is the problem :

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

      My code didn’t work because of the function gmpy2.invert() needs gmpy2.mpz as data type on both parameters. So, I parsed the data type of m1, m2, and m3 using gmpy2.mpz() function, but it couldn’t find the iroot.
      I don’t understand why this problem appears. When I run the code on python 2, the data type of m1, m2, and m3 is gmpy2.mpz. However, in python3 M/n1, M/n2, and M/n3 return gmpy2.mpfr as the data type of the result which is data type for real numbers, not integers. I think because M/n1 is a division, the code automatically parses the result to mpfr. I called gmpy2.mpz() on purpose to change the datatype to mpz but the value of m1,m2, and m3 are changed. Because the value of m1 is not the real value of M/n1 and so on, it couldn’t find the iroot of x.
      In python2, the value of m1=M/n1 is equal to n2*n3 since M=n1*n2*n3, and the data type is gmpy2.mpz. In python 3 I just made a little change. For m1,m2, and m3 I changed the operation directly into multiplication instead of the division so that m1 = n2*n3, m2=n1*n3, and m3=n1*n2. Since it didn’t do division, the data type of m1, m2, m3 didn’t change to mpfr. The code runs perfectly and prints the result.
      For more information about Chinese Reminder Theorem, you could read it on https://brilliant.org/wiki/chinese-remainder-theorem/#theorem-and-proof.

      Like

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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