Low Exponent Attack
Magic RSA Nahamcon CTF 2024
INTRODUCTION
In this blog, we will be discussing about the RSA cryptosystem and a flaw in its implementation that arises when the value of the exponent is set very low. This attack is referred to as the Low Exponent Attack or the Cube-Root Attack.
BACKGROUND
RSA (Rivest-Shamir-Adleman) is one of the most used asymmetric modern cryptosystems. It utilizes two distinct keys: a public key and a private key. In this scheme, the public key is widely distributed, while the private key remains confidential to its owner. The algorithm hinges on the computational complexity of factoring large integers. The public key, typically composed of two large prime numbers multiplied together, forms the foundation for encryption. Conversely, the private key, derived from the same primes, enables decryption.
To better understand RSA, lets comprehend it in steps. Let’s explore the components required to complete the process of encryption and decryption in RSA.
1. Select Primes p and q:
Choose two distinct prime numbers, for instance (p=11) and (q=13).
2. Calculate Modulus ( n ):
Calculate the modulus (n = p * q = 143).
3. Calculate Totient Φ(n):
Calculate the totient Φ(n) = (p-1) * (q-1) = 120.
4. Choose Public Key Exponent e:
Choose a public key exponent e such that 1 < e < Φ(n) and e is coprime to Φ(n). In this example, (e = 7).
5. Calculate Private Key Exponent d:
Calculate the private key exponent d using the Extended Euclidean Algorithm, such that d*e = 1 mod Φ(n). In this example, (d=103).
6. Encryption:
To encrypt a message M with public key (n, e) , which is (143, 7).
Ciphertext, C = M^e mod n
Substituting, (M = 9), (e = 7), and (n = 143):
C = 9⁷ mod 143 = 48. The cipher text is 48.
7. Decryption:
To decrypt the ciphertext C with private key (d, n):
Message, M = C^d mod n
Substituting, ( C = 48 ), ( d = 103 ), and ( n = 143 ):M = 48¹⁰³ mod 143 = 9. The message is 9.
Now that we’ve mathematically explored how the RSA cryptosystem works, let’s examine a flaw that arises when the public exponent is set to a very low value. The security of RSA encryption depends heavily on the size of the keys; larger keys significantly enhance the difficulty of decryption. While RSA keys typically range from 1024 to 2048 bits in length, concerns about the feasibility of breaking shorter keys persist.
Low Exponent Attack
The Low Exponent Attack occurs when the public exponent is very low, and decryption becomes viable or possible without the need for the private key. This attack on RSA encryption arises when the plaintext message m raised to the public exponent e is smaller than the modulus n . In this scenario, the modulo operation text mod n becomes irrelevant because the result of m^e is already within the range of acceptable ciphertext values.
For the demonstration of the Low Exponent Attack, I will be solving a CTF challenge from Nahamcon CTF 2024 named Magic RSA. The challenge provides us with python file containing the encryption process and the encrypted text.
From the Python file, it is understood that the code is for the encryption process where the p and q are randomly generated and the public exponent is set to 3. Also, in another file we are provided with the value of N and the Ciphertext. From the image below, we can understand that the value of N is very huge. On the other hand, the value of e is only 3.
Now, let’s mathematically compile all the findings to compute the RSA equation. Here, for decryption we must compute M, so from the RSA’s equation, we have, C = M^e mod n , which in our case becomes M³ mod n , here since we have M³ < n , we finally get, M = C³ .
Now, by computing the cube root of C (C³), we can directly retrieve the original message M. This attack is efficient when e is relatively small, making it a significant vulnerability in certain RSA implementations where 𝑒 is set to a low value like 3. Now, let's try to compute the plaintext in accordance with the above equation.
So, this piece of Python script stores the ciphertext in a list. Then, a loop is run, which sums up the cube root for each item in the list. Compiling this finally gives out the flag.
In this blog, we successfully learned about RSA and the Low Exponent Attack. This particular scenario was a Cube-Root Attack, as we computed the cube root of the ciphertext to retrieve the message without needing the private key.
