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!

# The challenge

We're given, in a zip file:

- A `cipher.txt` file which contains a big number (the cipher, supposedly)
- 101 public keys

And that's it, we have to decipher it. Oof, that's not a whole lot of information.

# Examining the data

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:

- Every file has a different modulus
- Every file has the same exponent

# Trying to solve it

## Options options options

So I had to figure out what was up with all these files. I had a few possibilities to explore:

- All of these were all public keys derivated from the same private key and I had to somehow find the private key from all these files
- The ciphertext had been encrypted using all of these public keys
- A single one of those keys was used to encrypt the plaintext and I somehow have to find which one

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.

## Common factor attack

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:

```py
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:

```py
# 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:

```py
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!

Original writeup (https://atomheartother.github.io/cybersecurity/2019/03/24/SecurinetsPrequalz2019Maze.html).