PicoCTF - SmallRSA


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!

Keep learning and stay safe! ~ W3ndige