This was an RSA challenge, but DiceGang are always creative and they mixed it up quite a
bit! The general gist is that we are given an RSA encrypted ciphertext whose `e`

value is not
coprime with its `phi [(p-1)(q-1)]`

value. In RSA, non-coprime `phi`

and `e`

don’t actually make the encryption non-secure, they make it
non-invertible
which means we can’t *uniquely* decrypt the ciphertext.

## Challenge

We are given two files:

```
# generate.py
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
def getAnnoyingPrime(nbits, e):
while True:
p = getPrime(nbits)
if (p-1) % e**2 == 0:
return p
nbits = 128
e = 17
p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)
flag = b"dice{???????????????????????}"
N = p * q
cipher = pow(bytes_to_long(flag), e, N)
print(f"N = {N}")
print(f"e = {e}")
print(f"cipher = {cipher}")
```

```
# data.txt
N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971
```

## RSA Refresher

Recall that RSA is an asymmetric encryption scheme that relies
on the fact that factoring is hard. This challenge utilizes so-called *textbook* RSA, which isn’t typically used in the
real world. In *textbook* RSA, we define a few values:

### RSA Parameters

`p`

: a large prime number (private key component)`q`

: another large prime number (private key component)`n`

:`p * q`

(public key)`phi`

:`(p - 1) * (q - 1)`

`d`

:`inv(e, phi)`

(The decryption key, derived from the private`p`

and`q`

)`e`

: public exponent (usually 3, 17, 65537, but technically can be any prime number)`m`

: plaintext (in Python, we can use`Crypto.Util.number.bytes_to_long(b"your_message_here")`

from`pycrypto`

)`c`

: ciphertext

### RSA Encryption

We encrypt by performing:

`c === m^e (mod n)`

This creates the ciphertext `c`

, and is done by the provided script in the line:

`cipher = pow(bytes_to_long(flag), e, N)`

### RSA Decryption

We decrypt by performing:

`c^d === (m^e)^d === m (mod n)`

This creates the plaintext `m`

back from the ciphertext.

## Solution

The problem is straightforward RSA, and we know off the bat that we need `d`

to be able to have a shot at decrypting
this ciphertext. Luckily for us `n`

is in factordb.

### Easy Part

So we find the prime factors of `n`

are:

```
p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
```

We can compute `phi`

:

```
phi = (p - 1)(q - 1)
phi = 57996511214023134147551927572747727073750608765342311271929088892243932625120
```

Now, we should ostensibly be able to take:

```
d = inverse(e, phi)
plain = pow(cipher, d, N)
print(plain)
```

and be done, but due to the prime generation function `getAnnoyingPrime`

this doesn’t work! Why? The modular inverse `d`

actually ends up being `1`

! This is where the trick comes in. If we examine the “rules” for RSA, we notice that one of
them is that `1 < e < phi`

and `gcd(e, phi) == 1`

. The second condition ensures that `e`

and `phi`

are coprime. If we
do this with our `e`

and `phi`

however:

```
gcd(e, phi)
>>> 17
```

So they are actually not coprime, `e`

is a factor of `phi`

…this is bad! It means that we can’t correctly decrypt the
ciphertext…or can we?

### Hard Part

The hard part really comes down to Google. If we search “possible private keys when e and phi not coprime”, we’ll find
a 2-year old paper from Microsoft Research that explains an algorithm for
recovering all possible plaintexts for RSA performed in exactly this incorrect way given `phi`

. Perfect!

There is an implementation of `Algorithm 1`

and `Algorithm 2`

given in the paper online
but I don’t really like their code, so I implement them here.

```
from itertools import permutations, chain
from sage.all import mod, crt, Integer
from Crypto.Util.number import long_to_bytes
N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
# http://factordb.com/index.php?query=57996511214023134147551927572747727074259762800050285360155793732008227782157
p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971
# Solution mostly taken from
# https://github.com/danshumow-msft/FixBadRsaEncryption/blob/master/script/RSAOAEPPlaintextSearch.py
for pr, qr in permutations(
chain(
mod(cipher, p).nth_root(e, all=True),
mod(cipher, q).nth_root(e, all=True),
),
2,
):
print(long_to_bytes(int(crt([Integer(pr), Integer(qr)], [p, q]))))
```

And we can just run: `python3 solve.py | grep dice`

`b'dice{cado-and-sage-say-hello}'`