Photo by Parsoa Khorsand on Unsplash

CTF Generator: Low private exponent (d) in RSA … the Wiener attack

I am working on a set of automated Cipher CTF (Capture The Flag) challenges, and part of this is to create methods which aim to break RSA. If you are interested, here are the RSA -related ones I’ve already completed:

• CTF Generator: Cracking RSA with Chinese Remainder Theory — Håstad’s Broadcast Attack. CRT. In this example, an RSA cipher has used the same message and with three different moduli.
• CTF: RSA Challenge Generator. RSA. This provides values for e and N, and gives the cipher, and you must crack it by finding d.
• CTF Generator: Low exponent in RSA (for public exponent). Low public exponent in RSA.

So, this morning, I implemented the Wiener attack [1] on RSA keys which have a relatively low private exponent (d):

In RSA, we select two prime numbers of equal length (p and q), and then multiply these to give a modulus:

We then compute the ciphertext as:

and where we decrypt with:

With this, we have a public exponent of e, and a private exponent of d. The value of d is computed from: