# Understanding RSA keys

RSA (Rivest, Shamir, Adleman) is a public key cryptographic system used to make communications secure. As in all public key system, there exists a public key, used to encrypt the messages, and a private key, used to decrypt those messages:

Both keys are just very large numbers. Of course, they must be mathematically linked someway so the encryption/decryption process works. The question is: how are they generated?

## Public key

First, two large random prime numbers must be selected: `p`

and `q`

. Then, we get `N`

by multiplying them:

`N = p * q`

Then, a public exponent `e`

is selected so great common divisor between `e`

and Euler's totient function of `N`

equals 1:

`gcd(e, euler_phi(N)) = 1`

The tuple `(N, e)`

is the public key (`p`

and `q`

must be secret). You share this so others can send encrypted messages to you. We will see later how encryption works.

## Private key

To get the private key, we need to get the value of `d`

by solving the modular equation below:

`d = e^(-1) (mod euler_phi(N))`

`d`

is the modular inverse of `e`

(public exponent) module `euler_phi(N)`

.

The tuple `(N, d)`

is the private key. You will use this to decrypt messages sent to you and it must kept secret.

## How to encrypt messages with the public key?

Given a plaintext message `m`

and a public key `(N, e)`

, getting the ciphered text `c`

is quite straightforward:

`c = m^e (mod N)`

## How to decrypt messages with the private key?

Given a ciphered message `c`

and a private key `(N, d)`

, getting the plaintext message `m`

is quite straightforward:

`m = c^d (mod N)`

## Example

I will omit the process of keys pair creation. In this case, for simplicity, I will use small numbers.

- Public key: (N = 77, e = 3)
- Private key: (N = 77, d = 43)

We want to encrypt the plaintext message `m = 57`

using the public key, so:

```
c = m^e (mod N)
c = 57^7 (mod 77)
c = 29
```

Now, to decrypt the ciphered message using the private key:

```
m = c^d (mod N)
m = 29^43 (mod 77)
m = 57
```

We have encrypted and decrypted the message and the result seems correct.

## Conclusions

RSA system's security relies on the difficulty of getting the factors of `N`

(`p`

and `q`

). If an attacker can guess `p`

and `q`

, he will obtain the private key and the process won't be secure anymore. When `p`

and `q`

are small numbers, it is easy to guess them from `N`

. However, if they are large (say 2048 or 4096 bits, for example), it can take thousands of years to guess them using the most powerful computer.