Mar 13

0CTF 2016 Quals – RSA? (Crypto 2 pts)

It seems easy, right?
rsa.zip
Tip: openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc

Summary: factoring 300-bit modulus into 3 primes, extracting cube roots.

$ openssl rsa -in public.pem -pubin -text
Public-Key: (314 bit)
Modulus:
    02:ca:a9:c0:9d:c1:06:1e:50:7e:5b:7f:39:dd:e3:
    45:5f:cf:e1:27:a2:c6:9b:62:1c:83:fd:9d:3d:3e:
    aa:3a:ac:42:14:7c:d7:18:8c:53
Exponent: 3 (0x3)
writing RSA key
-----BEGIN PUBLIC KEY-----
MEEwDQYJKoZIhvcNAQEBBQADMAAwLQIoAsqpwJ3BBh5Qflt/Od3jRV/P4Seixpti
HIP9nT0+qjqsQhR81xiMUwIBAw==
-----END PUBLIC KEY-----

314 bits only! Let’s factor it! For example, using CADO-NFS. It takes only 30 minutes on my laptop.

Interestingly, there are three factors:

N = 32581479300404876772405716877547 x 27038194053540661979045656526063 x 26440615366395242196516853423447.

Moreover, $gcd(3, \phi(N)) = 3$, meaning that we can’t invert the decryption! We have to compute all possible cube roots of the ciphertext. All such algorithms work modulo prime, but that is not a problem, since we have the factorization: we will compute all cube roots modulo each prime and then use Chinese Remainder Theorem to reconstruct the answer modulo $N$. There are some algorithms described in the following paper: New Cube Root Algorithm Based on Third Order Linear Recurrence Relation in Finite Field. The shortest one is the Cipolla-Lehmer algorithm, so I decided to implement it. Here’s Sage function:

def cube_root(a, q):
    F = GF(q)
    R.<x> = PolynomialRing(F)
    while 1:
        a = F.random_element()
        b = F.random_element()
        fx = x**3 - a*x**2 + b*x - c
        fc = list(factor(fx))
        if len(fc) <= 1:
            root = pow(x, (q**2+q+1)/3, fx)
            root %= x
            return int(root)

Note that it yields some cube root. We need to get all of them (at most 3) modulo each prime. We can either extract random cube roots with cube_root until we get all of them, or we can simply multiply a single root by 3rd roots of unity. We can get these roots by finding a multiplicative generator and raising it to power $(p-1)/3$.

Here’s the code:

p = 26440615366395242196516853423447
q = 27038194053540661979045656526063
r = 32581479300404876772405716877547
 
c = int(open("flag.enc").read().encode("hex"), 16)
 
mods = [p, q, r]
rems = []
for mod in mods:
    rems.append([])
    if gcd(mod - 1, 3) == 1:
        d = inverse_mod(3, mod - 1)
        rems[-1].append( int(pow(c, d, mod)) )
    else:
        g = GF(mod).multiplicative_generator()
        u = int(g ** ((mod-1)/3))
        r1 = int(cube_root(c, mod))
        for i in xrange(3):
            rems[-1].append( int(r1 * pow(u, i, mod) % mod) )
    print rems[-1]
 
from itertools import product
for testrems in product(*rems):
    m = crt(list(testrems), mods)
    assert pow(m, 3, p*q*r) == c % (p*q*r)
    h = hex(m)
    if len(h) & 1:
        h = "0" + h
    print `h.decode("hex")`

And result:

[13374868592866626517389128266735L, 7379361747422713811654086477766L, 5686385026105901867473638678946L]
[19616973567618515464515107624812L]
[13028011585706956936052628027629L, 6149264605288583791069539134541L, 13404203109409336045283549715377L]
'\x01\x93\x83\x7f\xc1\xe6/\xadr{B\x07\x16\x9ev\x13\xb5"$?S%\x96\xea\xc6}?>0^\x87+\x05~\tk\\\xe8R<'
'\x01c\xb9;\x0c\x87\r\x00\xf3/X\x90\xf2\xec\xa7o[\xb4\xf2\xaao9\x97\xe6\x87~\x1a`i~\xd8\xcc\x19PtP920H'
'\x01\xbf4\xa0O\xe0\x01Z\xd8\xcb\x00\xf1\t\xb6\xc0\x83\x04\x82\xa22\xa2\x02\x88"\x19\xd5\xf2\xb4+\xf3\x1f\x03\x8b\x1d\x90l\xd3\xc9e\xa5'
"\x02BRD:\xd703\xf3\xbe\xc7\xf4\x85\xc7\x88nf\x9a\xc9'f\xbb\xb4\xd3\x1b\xeb\x0e\xe9\x04\x0f\x15\xad f\xaa\x02y\x04\x04\xfc"
'\x02\x12\x87\xff\x85x\r\x87tr\xde~b\x15\xb9\xca\r-\x97\x92\x82\xcf\xb5\xce\xdc\xeb\xea\x0b=/gN49\x14\xe7UM\xe3\x08'
'\x02n\x03d\xc8\xd1\x01\xe1Z\x0e\x86\xdex\xdf\xd2\xdd\xb5\xfbG\x1a\xb5\x98\xa6\noC\xc2^\xff\xa3\xad\x85\xa6\x061\x03\xef\xe5\x18e'
'\x02\xd1^\xcb\x84\x84RC\xf3J\x000ctf{HahA!Thi5_1s_n0T_rSa~}\n'
'\x02\x9d\xb0\xda\xb3\xe6g\xc4\x15%\xbc\tF\x8f\x89\x07\x81\xab\x10\xfa\xff\xfb\xf0\xc6F\xba7\xf0\xe9\xbej\x0c\x14s\xf1\xb5\x14\xe0\xe7i'
'.\x82\x7fY~U\xff\xaaC\x08\xea#{\xbe\xd5\xca\xa8\xdf[\x8f\xfeE\x9f\xbc\x8e\x12\xa7n\xf4\x06\x08\xd9\xfe\xf9T\xd8_\x90s'

Don’t miss the flag! 0ctf{HahA!Thi5_1s_n0T_rSa~}

hellman

Leave a Reply

Your email address will not be published.