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
1 ping
[…] http://leetmore.ctf.su/wp/plaidctf-2012-…-guessing/ […]