TAMUctf – lowered_expectations – Crypto

Snowden RSA encrypted the contained message, but he made a fatal flaw in choosing keys.
He underestimated your hacking skills. Can you figure out the message?

[File]

We’re given a file with the contents C, e, and N. These are quickly recognized as RSA encryption where, with P = Plaintext, \( C=P^{e} \left ( modN \right ) \).

Because the given exponent, e = 3, is small and the given modulus is many orders of magnitude above the cipher text, it can be assumes that during encryption, the value never rose above the value N. This means we can simply knock off the “mod N” part of the encryption, leaving us with \(C=P^{e}\). Solving for P, we get \( P=C^{1/e}\) -or- \( P=\sqrt[e]{C}\). This is also known as the “Low Public Exponent Attack.”

While writing a python program to decrypt the flag, I did run into an issue of precision. Vanilla python decimals are not precise enough to fully decrypt the flag. This is however, easily fixed by using the decimal module which allows setting the desired precision.

Finally, the code worked and upon running it we get our flag!
gigem{get_L0W__d8d93c7ec9e56348}

If you do have to choose a low public exponent due to some technological limitation, make sure you pad your messages to a “full” message length. This will ensure that the modulus takes effect. If you have no such limitation, still pad your messages, but also make the exponent \(e=2^{16}+1\). These measures will ensure your message is adequately encrypted.

Python Code

~T