Table of contents

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-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
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 [85])

>>> 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 [85]

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 [85]

Calculus:

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

m = 10

Yeah! We retrieved our plaintext.