DiceCTF baby-rsa writeup

novafacing · February 7, 2022

CTF   Writeups

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

Twitter, Facebook