NPST 07. Alle gode ting er tre: small RSA exponent

Task description

Alveresepsjonen fant en mystisk lapp i postboksen til Nissens verksted i dag tidlig. Vanligvis er dette noe Ronny, Shahana og Ada fra alvdeling for kryptografi ville tatt seg av. Dessverre er alle tre bortreist på en viktig konferanse i San Francisco for å høre om den siste utviklingen innen eksponenter og modulær aritmetikk. Kan du steppe inn for dem og finne ut av hva denne beskjeden egentlig er for noe?

- Mellomleder

msg.txt

N = 0x5993c05eac819aa17ae7e4e4b9f75b2d6fdbaec913e0b2d6f4ba585a991b62279ed9ac53aeadee3327321e02c0c06ecda184952df5d1cc8b3024643c0afdd9bbd52bf2d830f54d6e59e76844394eb0ffc498995dd270b9b95bf1614984472a3ef12d8c1bad64529be7b638c5d0fccf61c5ac2ab4564e5215748eb2533d4d949afd9486426dbf0c06a07c2c0f6d482e4f8cf3052e6ab9df20878b747936d590c3b8bb0219a378cbec03baee4ea8d0641c57bcc18706bbe92c3f2d7569c424062d9b79464958419b4000e3e31c077bba27ef2fc6ed15b7ebdcdb41d1cbf7708737e200904015d341ef94c537a916f1fec61e0b1bf64762e5a97bafdde290b939c3
e = 3
C = 0x755040806d1d699c76cf2b3fffc28ad8831a8667e1b064297a43733b89f6272483a5a728b725d02b069f8fc65eb51d89ce9133df8f5f2d5e13f63c5423021eb2b56eeb91b11d78717528dfce169450a08d40f5ab451c8ac1f8c6875cffbd4d70259d436ed70baeae37b9bdafc5965

Notes

This is a simple RSA challenge. Ronny, Shahana and Ada from cryptography is a hint at Rivest, Shamir and Adleman, the people who came up with the public-key encryption algorithm known as RSA (their initials)

In msg.txt, the variables are:

  • N - Public key (N = p * q)
  • e - Public exponent (usually 65537, i.e. 2 ** 2 ** 4 + 1)
  • C / ct - Ciphertext (encrypted message) (ct = (m ** e) % N)

There are a few more variables in the algorithm:

  • m - The original plaintext message
  • p - Private prime #1 (around 1024 bits to be considered secure enough)
  • q - Private prime #2 (around 1024 bits to be considered secure enough)
  • phi - Euler’s totient (phi = (p - 1) * (q - 1)), used to generate the private key from the two private primes
  • d - Private key (the modular inverse of e modulo phi, i.e. d = pow(e, -1, phi)). Used to decrypt the ciphertext: m = (ct ** d) % N

Now, to determine the number of bits of N, we can convert it to binary and count the number of 1s and 0s. It turns out to be 2049.

In [8]: N = 0x5993c05eac819aa17ae7e4e4b9f75b2d6fdbaec913e0b2d6f4ba585a991b62279ed9ac53aeadee3327321e02c0c06ecda184952df5d1cc8b3024643c0afdd9bbd52bf2d830f54d6e59e76844394eb0ffc498995dd270b9b95bf1614984472a3ef12d8c1bad64529be7b638c5d0fccf61c5ac2ab4564e5215748eb2533d4d949afd9486426dbf0c06a07c2c0f6d482e4f8cf3052e6ab9df20878b747936d590c3b8bb0219a378cbec03baee4ea8d0641c57bcc18706bbe92c3f2d7569c424062d9b79464958419b4000e3e31c077bba27ef2fc6ed15b7ebdcdb41d1cbf7708737e200904015d341ef94c537a916f1fec61e0b1bf64762e5a97bafdde290b939c3

In [7]: len(bin(N))
Out[7]: 2049

RSA relies on the difficulty of factoring a large number composed of primes. Usually there are only two primes (p and q), each being roughly 1024 bits in size. When multiplied they create a public key (N) (usually) of size 2048-bit.

However, there are many ways to mess up the encryption causing it to break very easily. You can learn more about that in the links below

Solution

The public exponent (e) is too small, it should be minimum 65537.

Side note. Here’s why 65537 is a good number: https://en.wikipedia.org/wiki/Coppersmith%27s_attack

In order to reduce encryption or signature verification time, it is useful to use a small public exponent (e). In practice, common choices for e are 3, 17 and 65537 (2 ** 16 + 1). These values for e are Fermat primes, sometimes referred to as F0, F2 and F4 respectively (Fx = 2**2**x + 1). They are chosen because they make the modular exponentiation operation faster. Also, having chosen such e, it is simpler to test whether gcd(e, p - 1) = 1 gcd(e, q - 1) = 1 while generating and testing the primes in step 1 of the key generation. Values of p or q that fail this test can be rejected there and then.

When encrypting a message “abc” (m) we run it through an exponentiation and a modulo, like so:

ciphertext = (message ** public_exponent) % public_key

# or in a simpler form:
ct = pow(m, e, N)

Now, N is very large and e is very small, do you see where we’re going? m to the power of e isn’t really all that big. It may even be so small that it doesn’t have to “wrap around” (modulo) N. Depending on the message size, the ciphertext may just be equal to m ** e. To get m back again, we just need to take the cube root of C (or ct, whichever you prefer). Let’s try it out.

from Crypto.Util.number import long_to_bytes

e = 3
C = 0x755040806d1d699c76cf2b3fffc28ad8831a8667e1b064297a43733b89f6272483a5a728b725d02b069f8fc65eb51d89ce9133df8f5f2d5e13f63c5423021eb2b56eeb91b11d78717528dfce169450a08d40f5ab451c8ac1f8c6875cffbd4d70259d436ed70baeae37b9bdafc5965

# C to the power of 1/e is the same as nth root of C, where n is 3.
m = long_to_bytes(int(pow(C, 1/e)))
print(m)

# > b'NSM{ae8\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

We get a small part of the flag. After reading unblvr’s solution, I figured it had to be something odd with Python versus Sagemath, even though Sagemath is based on Python

NB: I was informed that the issue above is due to rounding errors caused by converting a float to an int. By using nroot from the libnum library instead of int(pow(C, 1/e)) it will work correctly in Python.

The same solution works correctly in sage:

sage: from Crypto.Util.number import long_to_bytes
....:
....: e = 3
....: C = 0x755040806d1d699c76cf2b3fffc28ad8831a8667e1b064297a43733b89f6272483a5a728b725d02b069f8fc65eb51d89ce9133df8f5f2d5e13f63c5423021eb2b56eeb91b11d78717528dfce169450a08d40f5ab451c8ac1f8c6875cffbd4d70259d436ed70baeae37b9bdafc5965
....:
....: # C to the power of 1/e is the same as nth root of C, where n is 3.
....: m = long_to_bytes(int(pow(C, 1/e)))
....: print(m)

b'NSM{af0dbd13cee45990593c182b213f978d}'

Flag: NSM{af0dbd13cee45990593c182b213f978d}