PicoCTF - SmallRSA
April 19, 2017

You intercepted a single message. However, it appears to be encrypted. Can you decrypt it? Message

Hint: Normally, you pick e and generate d from that. What appears to have happened in this case? What is likely about the size of d?

```
e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141
n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069
c = 84740524770381403153622925447792920959815469600692319965596776738431504244164788253920072346154965475345520986566261139605189850053220984036986688956922312943484012082747435674795128749623149324459566588589685250817942108728364336944750553593289462772627326115549452684668188298340307743571301091011089977112
```

Okay, they're giving us a hint about a size of a d . The one thing that comes to my mind is that, if d < 1/3 * N^(1/4) , Wiener's attack would be a great option to break this crypto. It uses the continued fraction method to expose the private key d , but only when d is small. You can read more about it in this paper .

In the RSA Cryptosystem, Bob might tend to use a small value of d, rather than a large random number to improve the RSA decryption performance. However, Wienerâ€™s attack shows that choosing a small value for d will result in an insecure system in which an attacker can recover all secret information, i.e., break the RSA system.

Now we have to apply these information to our message values. I've found this piece of code made by pablocelayes . Thanks!

I'm presenting here code used for only attacking, Arithmetic and ContinuedFractions modules are loaded from external files, so make sure to check out the Github Repository to get all the essential code.

import ContinuedFractions , Arithmetic
def hack_RSA ( e , n ):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
frac = ContinuedFractions . rational_to_contfrac ( e , n )
convergents = ContinuedFractions . convergents_from_contfrac ( frac )
for ( k , d ) in convergents :
#check if d is actually the key
if k != 0 and ( e * d - 1 ) % k == 0 :
phi = ( e * d - 1 ) // k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s * s - 4 * n
if ( discr >= 0 ):
t = Arithmetic . is_perfect_square ( discr )
if t !=- 1 and ( s + t ) % 2 == 0 :
print ( "Hacked!" )
return d
# TEST functions
def test_hack_RSA ():
print ( "Testing Wiener Attack" )
times = 5
while ( times > 0 ):
e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141
n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069
print ( "(e,n) is (" , e , ", " , n , ")" )
hacked_d = hack_RSA ( e , n )
print ( "Hacked_d = " , hacked_d )
print ( "-------------------------" )
times -= 1
if __name__ == "__main__" :
test_hack_RSA ()

With our values, we can now run this, to get desired value.

[email protected] ~/rsa-wiener> python wiener-attack.py
Testing Wiener Attack
( e,n) is ( 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141 , 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069 )
Hacked!
Hacked_d = 3223594586826657550897063711914171740995144768727978698812620148084071525621

As we now have d , we can now calculate the message.

w3ndige @W3ndige ~> python
Python 3.6 . 0 ( default , Jan 16 2017 , 12 : 12 : 55 )
[ GCC 6.3 . 1 20170109 ] on linux
Type "help" , "copyright" , "credits" or "license" for more information .
>>> d = 3223594586826657550897063711914171740995144768727978698812620148084071525621
>>> e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141
>>> n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069
>>> c = 84740524770381403153622925447792920959815469600692319965596776738431504244164788253920072346154965475345520986566261139605189850053220984036986688956922312943484012082747435674795128749623149324459566588589685250817942108728364336944750553593289462772627326115549452684668188298340307743571301091011089977112
>>> pow ( c , d , n )
3338241147602298443253582134580600952121701496335419787655403775061762704160368620726916691837

And lastly, decrypt it.

>>> hex ( 3338241147602298443253582134580600952121701496335419787655403775061762704160368620726916691837 )
'0x666c61677b4172655f616e795f5253415f76616c735f676f6f645f31353837383537303537377d'
>>> txt = '666c61677b4172655f616e795f5253415f76616c735f676f6f645f31353837383537303537377d'
>>> '' . join ([ chr ( int ( '' . join ( c ), 16 )) for c in zip ( txt [ 0 :: 2 ], txt [ 1 :: 2 ])])
'flag{Are_any_RSA_vals_good_15878570577}'

Great, we have another flag!

Contact
If you have any suggestions regarding this post or just want to chat together check out these ways to reach out to me.