# 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:

• Public key: `(391,173)`
• Secret key: `(391,213)`

#### 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.