PlaidCTF 2012 – RSA [200] (Password Guessing)

We recently intercepted a plethora of robot transmissions but they are all encrypted with some strange scheme we just can’t quite figure out. Can you crack it?

Summary: small public exponent: 3

We are given just two files: enc.dat and id-rsa.pub. Let’s extract RSA public key:

$ openssl rsa -pubin -in id-rsa.pub -text
Public-Key: (4096 bit)
Modulus:
    00:b0:a1:f3:90:ac:d3:d4:3b:47:d3:9f:13:26:62:
    f6:9c:15:89:25:d9:28:71:e4:78:69:e2:84:1a:91:
    7c:20:d5:10:24:31:b9:a9:78:14:58:d8:40:fd:29:
    57:78:15:a4:16:12:d6:87:a3:48:7d:26:fb:ae:25:
    6f:15:d4:74:0c:34:59:1b:64:6a:bc:cc:b1:a2:7a:
    cd:e2:99:b3:e7:16:00:85:7b:45:5c:28:36:60:e0:
    45:5c:68:ff:45:c0:64:4c:fe:c2:11:d7:f5:1a:16:
    c8:2e:91:d7:86:d9:2c:79:9f:b3:cb:48:f9:2d:e3:
    42:ba:70:dd:82:13:05:6b:31:4a:8d:51:da:94:93:
    cf:1b:86:ec:15:fd:f0:3e:04:6e:76:d3:f1:a1:ad:
    0a:ab:b6:84:ce:5d:15:7e:39:98:28:a6:3a:5a:f5:
    92:02:28:bb:5e:a1:e6:6b:8f:ea:a3:cc:bb:af:f5:
    55:e3:46:79:77:30:dd:fc:1c:4c:f4:a9:dd:40:65:
    88:62:93:48:c4:c2:92:65:df:9e:2c:3d:02:55:8b:
    e5:e3:5c:b2:77:f4:e7:ac:7b:51:58:ef:39:03:a3:
    96:48:63:71:02:9e:54:a3:45:29:2a:ba:47:49:9f:
    1c:26:7e:68:0a:e7:38:19:5f:d5:af:2a:80:75:93:
    98:90:f5:d6:9e:6b:3e:94:e3:e5:60:86:1a:a6:c6:
    c6:9d:a8:24:05:db:a2:18:2e:66:ec:ff:6a:8a:9c:
    df:5a:d5:22:6f:07:3e:7d:52:5e:05:0f:dd:77:e0:
    bb:18:91:a4:9e:fe:c2:d3:67:a6:93:d2:a6:79:9d:
    0d:46:67:95:3d:4f:3d:de:c1:6a:c1:5b:b4:cf:60:
    25:ea:58:ec:b6:df:a5:72:31:6d:a0:8d:31:06:07:
    39:73:32:2a:e7:59:74:46:f2:fd:30:43:df:6e:1d:
    60:4c:6a:1f:0e:59:47:3d:9b:c1:82:d4:ec:6f:c4:
    58:8f:1c:6b:2a:a4:76:87:6a:84:b2:d4:e0:d4:59:
    10:39:91:18:d7:e1:e2:0d:cc:27:70:3f:2b:d3:e9:
    af:72:2f:37:a7:67:3b:15:d6:74:92:28:62:c8:4d:
    00:fc:2f:c7:dd:dd:c9:15:c4:69:3f:cb:0b:17:89:
    e9:dc:bd:72:ac:04:65:9e:7c:18:dc:f3:62:54:76:
    00:40:40:2b:fc:ef:11:b8:a3:ef:9c:8b:dd:ba:aa:
    8d:14:c6:e8:f5:18:a7:0b:03:6d:20:6b:80:9c:d9:
    b3:b5:1a:1e:c0:13:2d:ac:e9:6d:ca:94:51:f3:4c:
    38:ab:84:ed:47:5e:7d:94:fb:e9:ff:c0:07:f2:d1:
    48:60:bd
Exponent: 3 (0x3)

Oh, the exponent is very small – 3. If the message is rather small and it wasn’t padded correctly, we can decrypt it! Let’s see:

$$c \equiv m^3 \pmod{N} \iff m^3 = c + k*N$$

Bigger m -> bigger k. Let’s bruteforce k until $c + k*N$ is a cube. Then the secret message will be a cuberoot of that:

import gmpy
from libnum import *
 
N = long('00b0...0bd', 16)
orig = s2n(open("enc.dat").read().rstrip())
 
c = orig
while True:
    m = gmpy.root(c, 3)[0]
    if pow(m, 3, N) == orig:
        print "pwned", n2s(m)
        break
    c += N
$ time py rsa.py 
pwned 
Didn't I tell you everything would work out in the end? Brixby gave me the password to the secure server: 56c812da9a3955e3c81453eb035b3d37b3f1bfe407ef701d09cf68dd4bb335b1
 
 
real	0m44.679s
user	0m44.615s
sys	0m0.008s

The flag: 56c812da9a3955e3c81453eb035b3d37b3f1bfe407ef701d09cf68dd4bb335b1

Leave a Reply

Your email address will not be published.