Tags: common-factor crypto rsa
Rating:
Maze was a fun cryptography challenge which wasn't all that challenging once i figured out what I had to do. That took me a while though!
We're given, in a zip file:
cipher.txt
file which contains a big number (the cipher, supposedly)And that's it, we have to decipher it. Oof, that's not a whole lot of information.
I decided to look at the modulus and exponents in each file, moved all the decoded files to a clear/
folder with this command:
for file in pub*; do openssl rsa -pubin -inform PEM -text -noout < $file > "./clear/$file"; done
Ok so now I have 101 files that look like:
RSA Public-Key: (2048 bit)
Modulus:
00:dd:a2:f9:b5:2c:68:3f:35:bc:41:da:f5:26:b2:
49:6e:da:c0:59:ed:04:90:71:49:a9:71:8c:33:72:
71:50:64:20:7e:24:fa:b0:6c:33:d0:eb:c2:5a:d5:
4f:fa:48:e7:cf:e1:5f:54:b5:97:1a:0f:f0:be:3d:
0d:a8:b1:10:0a:d1:77:88:87:a1:9c:9e:29:49:bd:
5f:82:4f:b2:1f:4d:68:85:c8:14:52:6f:27:23:f5:
56:ce:29:b3:06:bf:59:bd:43:cc:a1:1d:ea:fe:20:
d0:db:b8:46:ce:ed:18:44:09:74:cd:8b:f4:94:5d:
f1:fb:5c:01:f7:91:ac:63:1a:19:b2:8d:d1:67:2a:
cd:ea:08:ce:7d:e9:65:e9:95:bb:06:3c:61:38:15:
98:f9:3f:81:6e:dc:b6:26:8e:e5:a2:92:43:a0:3b:
e7:39:74:60:b2:3a:74:44:eb:00:fc:42:00:bc:95:
d1:17:d9:30:a3:13:1c:fa:8d:95:22:60:a1:bc:bb:
46:af:4c:52:a6:7c:5c:df:d3:4b:09:66:c8:d6:9f:
82:0f:4f:25:bd:e5:04:46:b4:c8:c0:70:8c:2a:39:
3a:04:67:d4:e3:51:b6:66:2d:46:25:99:54:a2:5e:
21:2a:44:65:be:a7:ed:a9:f9:51:1c:b1:f4:69:c4:
e7:29
Exponent: 65537 (0x10001)
I wasted way too much time establishing these few basic facts:
So I had to figure out what was up with all these files. I had a few possibilities to explore:
Option #1 was basically impossible, and wouldn't have helped me anyway. I was pretty set on option #2 but before doing my script I decided to ask an admin since the math involved might lose me a lot of time. He told me I was on the wrong track. So... It has to be #3.
I hadn't known of Common Factor Attack before this chall, I don't know how I didn't! It's really powerful, though not very applicable to real-world keys. The idea is that if you have a bunch of keys that were generated by the same source, that was using really bad values for its prime generation for p
and q
, then there's a chance both keys have one of those prime numbers in common. And that's really good news because we can calculate gcd
between large integers very fast! So, first of all, write a sagemath script that reads all of the modulus and puts them in a file:
vals = []
cipher = 12225682126551187619399843891561465899608952498495120851070778192443023261485900560363269700242510941697365921981918056191408738905974825435324679841994232057252389709580959723999122054844144379187848417389566267322902673441312265008128249280701778727420570269893119286011513549800540500264752909082405313097299590601819529975638766522951170517766409850156769569563924473524368177233982270360715976884639307240445794551655637991803019693125040126171348043927410721121473304998359286936518573367417946711868112216965614586268606230443139176878435753744068734717043992817907788262531021387616180516736397859628481024223
e = 65537
for n in range(101):
f = open("pub{}.pem".format(n), 'r')
lines=[x.rstrip().lstrip() for x in f.readlines()[2:-1]]
hexa = ''
for part in lines:
hexa += part.replace(":", "")
val = Integer(int(hexa, 16))
if cipher < val:
vals.append(val)
# vals now contains all modulus
Ok cool, now to check if 2 modulus have common factors:
# Find keys that share common factors
for x in range(len(vals)):
for y in range(x+1, len(vals)):
if x == y:
continue
valX = vals[x]
valY = vals[y]
g = gcd(valX, valY)
if g == 1:
continue
print("{} and {} share a common factor: {}".format(x, y, g))
And the output:
38 and 44 share a common factor: 168736462866079204789584058199620418225526506348478399447895958829038354002285480486576728303147995561507709511105490546002439968559726489519296139857978907240880718150991015966920369123795034196767754935707681686046233424449917085120027639055362329862072939086970892956139024391556483288415208981014264336691
Boom! Now we have a p
value, we can compute q
for both moduli and that's it, we've broken both private keys. All we need now is to decipher the ciphertext with both private keys and see which of the two make sense:
p = Integer(168736462866079204789584058199620418225526506348478399447895958829038354002285480486576728303147995561507709511105490546002439968559726489519296139857978907240880718150991015966920369123795034196767754935707681686046233424449917085120027639055362329862072939086970892956139024391556483288415208981014264336691)
for i in [38, 44]:
n = vals[i]
# Find q
q = n // p
# Comute Lambda(n):
l = lcm(p-1, q-1)
# Compute d
d = inverse_mod(e, l)
# Calculate (cipher^d) % n
R = IntegerModRing(n)
plaintext = R(cipher)
plaintext = plaintext ^ d
print(hex(Integer(plaintext)))
One of the two outputted values looks a LOT like ASCII, so I convert it and:
securinets{rs4_1s_g00d_s0m3t1m3s!}
That's it!
Nice writeup.