Broadcast - 120 PTS
You stumbled upon a group Message. Can you figure out what they were sending? The string sent is ascii encoded as a hex number (submit the ascii string as the flag)

```
e = 3
c1 = 261345950255088824199206969589297492768083568554363001807292202086148198540785875067889853750126065910869378059825972054500409296763768604135988881188967875126819737816598484392562403375391722914907856816865871091726511596620751615512183772327351299941365151995536802718357319233050365556244882929796558270337
n1 = 1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627
c2 = 147535246350781145803699087910221608128508531245679654307942476916759248311896958780799558399204686458919290159543753966699893006016413718139713809296129796521671806205375133127498854375392596658549807278970596547851946732056260825231169253750741639904613590541946015782167836188510987545893121474698400398826
n2 = 405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309
c3 = 633230627388596886579908367739501184580838393691617645602928172655297372145912724695988151441728614868603479196153916968285656992175356066846340327304330216410957123875304589208458268694616526607064173015876523386638026821701609498528415875970074497028482884675279736968611005756588082906398954547838170886958
n3 = 1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723
```

Another RSA challenge. This time we have number of group messages, encrypted with the same small exponent (e). After doing a little bit of googling, I've found that Hastad's Broadcast Attack is able to break this encryption. You can read more about it here , at chapter 4.2.

If three parties participating in the same system encrypt the same message m using the same public exponent e=3, although perhaps different modulus n1, n2, and n3, then one can easily compute m from the three cipher texts.

Now we can look at the equations:

c1 = m^3 modulo n1

c2 = m^3 modulo n2

c3 = m^3 modulo n3

But what now? This amazing piece of code will perform the attack for us. Let's take a look at it.

import sys
import binascii
from Crypto.PublicKey import RSA
from base64 import b64decode
if ( len ( sys . argv ) < 7 ):
print " \t\n\n Arg error: python rsaHastad.py <n0 File> <n1 File> <n2 File> <c0 File> <c1 File> <c2 File> [--decimal/--hex/--b64] [-v/--verbose] \n\n "
exit ()
print " \n "
print " \t ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print " \t RSA Hastad Attack "
print " \t JulesDT -- 2016 "
print " \t License GNU/GPL "
print " \t ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
def chinese_remainder ( n , a ):
sum = 0
prod = reduce ( lambda a , b : a * b , n )
for n_i , a_i in zip ( n , a ):
p = prod / n_i
sum += a_i * mul_inv ( p , n_i ) * p
return sum % prod
def mul_inv ( a , b ):
b0 = b
x0 , x1 = 0 , 1
if b == 1 : return 1
while a > 1 :
q = a / b
a , b = b , a % b
x0 , x1 = x1 - q * x0 , x0
if x1 < 0 : x1 += b0
return x1
def find_invpow ( x , n ):
high = 1
while high ** n < x :
high *= 2
low = high / 2
while low < high :
mid = ( low + high ) // 2
if low < mid and mid ** n < x :
low = mid
elif high > mid and mid ** n > x :
high = mid
else :
return mid
return mid + 1
def parseC ( argv , index , verbose ):
import string
file = open ( argv [ index ], 'r' )
cmd = ' ' . join ( argv )
fileInput = '' . join ( file . readlines ()) . strip ()
if '--decimal' in cmd :
if verbose :
print "##"
print "##" , fileInput
print "## Considered as decimal input"
print "##"
return long ( fileInput )
elif '--hex' in cmd :
if verbose :
print "##"
print "##" , fileInput
print "## Considered as hexadecimal input"
print "##"
return long ( fileInput , 16 )
elif '--b64' in cmd :
if verbose :
print "##"
print "##" , fileInput
print "## Considered as base64 input"
print "##"
return long ( binascii . hexlify ( binascii . a2b_base64 ( fileInput )), 16 )
else :
try :
fileInput = long ( fileInput )
if verbose :
print "##"
print "##" , fileInput
print "## Guessed as decimal input"
print "##"
return long ( fileInput )
except ValueError :
if all ( c in string . hexdigits for c in fileInput ):
if verbose :
print "##"
print "##" , fileInput
print "## Guessed as hexadecimal input"
print "##"
return long ( fileInput , 16 )
else :
if verbose :
print "##"
print "##" , fileInput
print "## Guessed as base64 input"
print "##"
return long ( binascii . hexlify ( binascii . a2b_base64 ( fileInput )), 16 )
pass
def parseN ( argv , index ):
file = open ( argv [ index ], 'r' )
fileInput = '' . join ( file . readlines ()) . strip ()
try :
fileInput = long ( fileInput )
return fileInput
except ValueError :
from Crypto.PublicKey import RSA
return long ( RSA . importKey ( fileInput ) . __getattr__ ( 'n' ))
pass
if __name__ == '__main__' :
e = 3
cmd = ' ' . join ( sys . argv )
if '-v' in cmd or '--verbose' in cmd :
verbose = True
else :
verbose = False
n0 = parseN ( sys . argv , 1 )
n1 = parseN ( sys . argv , 2 )
n2 = parseN ( sys . argv , 3 )
c0 = parseC ( sys . argv , 4 , verbose )
c1 = parseC ( sys . argv , 5 , verbose )
c2 = parseC ( sys . argv , 6 , verbose )
n = [ n0 , n1 , n2 ]
a = [ c0 , c1 , c2 ]
result = ( chinese_remainder ( n , a ))
resultHex = str ( hex ( find_invpow ( result , 3 )))[ 2 : - 1 ]
print ""
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print "Decoded Hex : \n " , resultHex
print "---------------------------"
print "As Ascii : \n " , resultHex . decode ( 'hex' )
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

Shoutout to JulesDT !

And now it's time to finally crack this message. Firstly let's create files that will hold our ciphertext and modulus n values.

[email protected] ~> echo "261345950255088824199206969589297492768083568554363001807292202086148198540785875067889853750126065910869378059825972054500409296763768604135988881188967875126819737816598484392562403375391722914907856816865871091726511596620751615512183772327351299941365151995536802718357319233050365556244882929796558270337" >> c0
[email protected] ~> echo "1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627" >> n0
[email protected] ~> echo "147535246350781145803699087910221608128508531245679654307942476916759248311896958780799558399204686458919290159543753966699893006016413718139713809296129796521671806205375133127498854375392596658549807278970596547851946732056260825231169253750741639904613590541946015782167836188510987545893121474698400398826" >> c1
[email protected] ~> echo "405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309" >> n1
[email protected] ~> echo "633230627388596886579908367739501184580838393691617645602928172655297372145912724695988151441728614868603479196153916968285656992175356066846340327304330216410957123875304589208458268694616526607064173015876523386638026821701609498528415875970074497028482884675279736968611005756588082906398954547838170886958" >> c2
[email protected] ~> echo "1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723" >> n2

Now we can use provided code to break the crypto, and get the message.

[email protected] ~> python2 hastad.py n0 n1 n2 c0 c1 c2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
RSA Hastad Attack
JulesDT -- 2016
License GNU/GPL
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Decoded Hex :
62726f6164636173745f776974685f736d616c6c5f655f69735f6b696c6c65725f3430333332333030313931
---------------------------
As Ascii :
broadcast_with_small_e_is_killer_40332300191
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Amazing crypto challenge, and we have another flag!

Keep learning and stay safe!

~ W3ndige