Table of contents
- How does RSA work
- Public and private key
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
Before seeing the mathematical aspect, here are some examples of keys.
-----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0 FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/ 3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB -----END PUBLIC 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.
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)
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]
>>> pow(m, e, n) x
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 
>>> pow(10, 5, 85) 40
So x = 40 is our encrypted message
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
We are going to try to decrypt the previous message that we have encrypted previously:
x = 40 m ≡ 4013 
>>> pow(40, 13, 85) 10
m = 10
Yeah! We retrieved our plaintext.