CTF Generator: RSA Cracking With the Different Public Exponents But The Same Modulus
I love cracking ciphers, and I believe it is great exercise for your brain. And, so, I see so many of our students undertaking CTF (Capture The Flag) challenges. Often there is a range of RSA ciphers in some of the more challenging ones, and one of them is related to the usage of different public exponents, but with the same public modulus. So let’s create a challenge generator for this.
In RSA, Bob generates two random prime numbers (p and q), and creates a public modulus:
Bob will then use a public exponent (e_1) to cipher a message (M) with:
and cipher the same message with another public exponent (e_2):
This could have happened because of an error on the system. Now, Eve can take the two ciphers, and then can recover the plaintext if:
and:
With Bezout’s Theorem we can find two integer values (x and y) for two integer values of a and b:
If gcd(e₁, e₂)=1, we can determine the values for x and y for:
Next we can use the Extended Euclidean algorithm to determine x and y. With these values, we can then compute the message with:
and which is:
