Textbook RSA

This is a tutorial on how to do RSA key generation, encrypt and decrypt message and hack an insecure RSA public key. I am assuming that you have already had an introduction to RSA and need to do something like what I will show you for homework or a project. The purpose of this article is to give you a better understanding of RSA — not to teach it to you.

It's called textbook RSA because it's used to teach the basics of asymmetric encryption. Don't try to implement something like this for an application, it's not secure! For real life applications something like RSA-OAEP should be used.

Key Generation

To calculate the modulo, choose two random primes p and q. Multiplying them gives you n, which is our modulo.

To calculate the public and secret key multiply (p - 1) with (q - 1). This gives us phi, now choose a random prime that is smaller than phi, this is our public exponent e.

For the secret exponent d we just need to find a number that fulfills e * d mod phi = 1.

That's it, now we have our public key (n,e) and our secret key (n,d).

Encryption and Decryption

To encrypt a plaintext we just need to use the following formula. plaintext ^ e mod n or pow(plaintext,e,n) in Python.

For decryption we simply need to switch the plaintext with our ciphertext and e with our secret exponent d. So ciphertext ^ d mod n or pow(ciphertext,d,n) in Python.

Example

Say we choose the primes 17 and 23, this means 17 * 23 = 391, so n = 391.

For phi we get (17 - 1) * (23 - 1) = 352. Lets choose 173 for our e, remembering that e has to be smaller than phi.

Having chosen e = 173 we get d = 213. I use SageMathCell with the function inverse_mod(173, 391) to calculate d.

Now we have our two keys:

Encryption

To encrypt a plaintext 15 we do the calculation 15 ^ 173 mod 391 or pow(15,173,391) in Python. This gives us the ciphertext 71.

Decryption

To decrypt our ciphertext 71 we do the calculation 71 ^ 213 mod 391 or pow(71,213,391) in Python. This gives us the original plaintext of 15.

Hacking the RSA key

The keys we have come up with for this example are completely insecure. Lets see how you would go about hacking them.

The public key is — as the name suggests — public. This means that n is known. If we can factor n then it gives us our two primes p and q. Once we have the primes we can calculate the secret exponent d.

To get d we calculate phi by doing (p - 1) * (q - 1). Once we have phi we can calculate d just like we would for key generation.

The security of RSA is based on the hardness of factoring. If p and q are large enough numbers, then n becomes so large that it's unrealistic to factor. Hence, safe.

Example

Let's say we want to find the secret key for our public key (391,173).

First we need to factor n. Here we can use SageMathCell with the function factor(391). The result is 17 * 23 — our two primes!

Now that we know p = 17 and q = 23 we can calculate (17 - 1) * (23 - 1) which gives us phi = 352. With phi we have the last piece of the puzzle. We can use it together with e to calculate d. Again I use SageMathCell with the function inverse_mod(173, 352) which gives us 293 — our secret exponent d!

I hope that has helped you better understand RSA. Try to go through the process of generating the keys, encrypting/decrypting a message and then hacking the public key using your own numbers.