# DiceCTF baby-rsa writeup

novafacing · February 7, 2022

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

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}'`