Table des matières

Fonctionnement global de RSA

RSA est une méthode de chiffrement dite asymétrique, c’est à dire que la clef qui va chiffrer le message n’est pas la même que celle qui le déchiffre, on parle de clef publique et de clef privée. La clef publique est par définition la clef qui peut être partagée, elle servira pour chiffrer les messages. La clef privée quant à elle doit rester secrète car elle permet de déchiffrer les messages chiffrés. Ces clefs sont des nombres entiers composées de plusieurs centaines de chiffres qui sont mathématiquement liés.

Clef publique et clef privée

Exemples de clefs publiques et privées

Avant de rentrer dans le dur du sujet voyons quelques exemples.

Clef publique:

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

Clef privée:

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

Ces clefs sont les nombres entiers abordés dans l’intro, mais encodés en base64.

Calcul de ces clefs

Pour calculer les clefs nous devons d’abord choisir deux nombres premiers notés p et q.

Par la suite, il nous faudra les multiplier pour obtenir une partie de notre clef publique, n = p * q.

Puis nous devrons calculer l’indicatrice d’Euler de n, qui correspond à la quantité de nombres premiers avec n allant de 1 à n. Je ne rentrerai pas plus dans les détails, il faut juste savoir que dans le cas de nombres premiers, phi(n) = (p - 1) * (q -1).

La dernière étape de la création de la clef publique est le choix d’un exposant de chiffrement noté e. IL doit être inférieur à phi(n) et e doit être premier avec phi(n).

On a donc une clef publique qui correspond à (n, e)

Il nous reste plus qu’à calculer la clef privée pour obtenir notre couple clef publique clef privée. La clef privée notée d correspond à l’inverse modulaire de e modulo phi(n).

Ce calcul peut s’effectuer en python:

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

On finit donc nos calculs avec une clef privée d, et une clef publique (n, e).

Exemple de calcul de clefs

Passons à un exemple concret.

Prenons p = 5 et q = 17, les deux nombres sont premiers donc peuvent être utilisés pour notre chiffrement. J’ai volontairement pris des nombres petits pour pouvoir faire les calculs à la main.

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

Prenons un exposant de chiffrement e = 5 qui est bien premier avec phi(n).

On a donc notre clef publique, n = 85 et e = 5.

Passons maintenant au calcul de la clef privée. d est l’inverse modulaire de e modulo phi(n). Donc d = inv(5 [85])

Calcul:

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

On a donc enfin notre couple de clefs: d = 13 et (n, e) = (85, 5)

Chiffrement

Intéressons nous maintenant au chiffrement des données.

Fonctionnement du chiffrement

Le chiffrement des messages se fait en un seul calcul. Notons x le message chiffré et m le message en clair:

x ≡ me [n]

En python:

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

Exemple de chiffrement

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

x ≡ 105 [85]

On effectue le calcul:

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

Donc x = 40 constitue notre message chiffré

Déchiffrement

Fonctionnement du déchiffrement

Le déchiffrement se fait également avec seulement un calcul:

m ≡ xd [n]

Ce calcul peut également se faire en python:

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

Exemple de déchiffrement

Essayons donc de déchiffrer le message que nous avons chiffré précédemment. x = 40 m ≡ 4013 [85]

Calcul:

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

m = 10

Bingo ! On retrouve notre message en clair.