## How does RSA work#

RSA is an asymetric encryption system, it means that the key which encrypt the message is not the same as the key which decrypt the message, there is a public key and a private key. The public key can be shared with other to encrypt messages unlike the private key which has to be completely secret because it allows to decrypt encrypted message. These key are really long integers and are mathematically connected.

## Public and private key#

### Examples#

Before seeing the mathematical aspect, here are some examples of keys.

Public key:

``````-----BEGIN PUBLIC KEY-----
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----
``````

Private key:

``````-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----
``````

Those keys are the integers quoted in the introduction, but base 64 encoded.

### Keys computing#

To compute those keys, we have to choose 2 prime numbers p and q.

After that, we are going to multiply p and q to get a part of our public key: `n = p * q`, then find Euler’s totient of n named phi(n).

For prime numbers: `phi(n) = (p -1) * (q -1)`

The last step to build our public key is to choose an integer e such that `1 < e < phi(n)` and `gcd(e, phi(n)) = 1`.

So, we have our public key: (n, e).

The last step to get our key couple is to compute the private key named d. It corresponds to the modular inverse of e mod phi(n).

We can easily make this calculus with Python:

``````>>> pow(e, -1, phi(n))
d
``````

So we have our key couple: d as our private key and (n, e) as our public key.

### Key computing example#

Let’s make a concrete example.

For example, p = 5 and q = 17. These numbers are prime numbers so we can use them to encrypt our messages.

``````n = 5 * 17 = 85
phi(n) = (5 -1) * (17 - 1) = 64
``````

So we just need our exponent e, let’s take 5 which is coprime with phi(n).

So we have our public key, n = 85 et e = 5.

Let’s compute the private key!

d is the modular inverse of e mod phi(n). So `d = inv(5 )`

``````>>> pow(5, -1, 64)
13
``````

So we have our key couple: d = 13 et (n, e) = (85, 5)

## Encryption#

Let’s interest to data encryption.

### How does encryption work#

Data encryption required only one calculus. x is the encrypted message and m the plaintext.

x ≡ me [n]

In python:

``````>>> pow(m, e, n)
x
``````

### Encryption example#

Let’s encrypt a message with our previous keys: 10 for example

Reprenons les clefs que nous avons calculé plus haut et chiffrons le message 10 par exemple:

x ≡ 105 

Computing:

``````>>> pow(10, 5, 85)
40
``````

So x = 40 is our encrypted message

## Decryption#

### How does decryption work#

Data decryption is only with one calculus too:

m ≡ xd [n]

It can be executed in python for example:

``````>>> pow(x, d, n)
m
``````

### Decryption example#

We are going to try to decrypt the previous message that we have encrypted previously:

x = 40 m ≡ 4013 

Calculus:

``````>>> pow(40, 13, 85)
10
``````

m = 10

Yeah! We retrieved our plaintext.