Algorithme RSA

To the non-french speaker, note that you can translate the articles using the Google Trad widget situated at the bottom of all pages.


Aujourd’hui on va s’attaquer à un poids lourd dans le monde de la cryptographie : l’algorithme RSA ! Cet algorithme a été développé par trois mathématiciens (Ronald Rivest, Adi Shami et Leonard Adleman) durant les années 70 et a finalement été décrit en 1977.

Il a été inventé à l’époque afin de résoudre les problématiques liés au chiffrement des données ainsi que les problèmes liés à l’authenticité d’un message. En effet avec RSA nous allons pouvoir chiffrer un message mais aussi s’assurer que seuls les destinataires finaux pourront le déchiffrer (donc garantir sa confidentialité).

Aujourd’hui RSA est toujours très utilisé que ce soit dans les protocoles TLS ou SSH et est même devenu une entreprise spécialisée dans la vente de token OTP :

Capture d’écran du 2019-04-24 11-14-53.png

Sans plus tarder let’s ding into the wonderful world of cryptology !

I/ RSA, comment ça marche ?

Prenons deux communicants : Alice et Bob. Les zones en orange représentent les espaces privés d’Alice et Bob tandis que la zone en bleu représente l’Internet publique :

Capture d’écran du 2019-04-24 11-31-40.png

Tout au long de cet article nous allons créer la paire de clé privée/publique d’Alice. La clé privée restera entre les mains d’Alice tandis que la clé publique pourra être émise librement sur Internet.

Pour commencer nous allons choisir deux nombres entiers premiers. Pour rappelle un nombre premier et un nombre qui n’est divisible que par lui même ou 1. Pour simplifier les calculs nous prendrons deux nombres petits : 3 et 11. Dans la réalité les nombres utilisées sont extrêmement grands.

Capture d’écran du 2019-04-24 11-38-17.png

Puis nous allons calculer une première valeur : le module de chiffrement (n). Tous les calculs de chiffrements/déchiffrements se feront modulo le module de chiffrement (mais nous y reviendrons plus tard). Ce module de chiffrement est calculé ainsi :

n = p * q

Capture d’écran du 2019-04-24 11-41-40.png

Ensuite nous allons calculer une nouvelle valeur : l’indicatrice d’Euler via cette formule :

Φ(n) = (p - 1)(q - 1)

Capture d’écran du 2019-04-24 11-47-09.png

Puis on va choisir un nombre « e » (l’exposant de chiffrement), strictement inférieur et premier avec notre indicatrice d’Euler (par exemple 3).

Capture d’écran du 2019-04-24 11-50-28.png

Enfin on va calculer le nombre « d » (l’exposant de déchiffrement), l’inverse de « e » modulo 20. Pour cela on devra se servir de l’algorithme d’Euclide étendu que je ne détaillerai pas ici. Tout ce que nous avons besoin de savoir c’est que l’inverse de 3 module 20 c’est 7 :

Capture d’écran du 2019-04-24 11-53-10.png

Voilà, avec les valeurs que nous venons de calculer nous pouvons créer la paire de clé privée/publique d’Alice. La clé privée sera composée du module de chiffrement et de l’exposant de déchiffrement :

Cpriv = (n, e)
soit
Cpriv = (33, 3)

Tandis que la clé publique sera composée du module de chiffrement et de l’exposant de chiffrement :

Cpub = (n, d)
soit
Cpub = (33, 7)

Une fois les clés établies, Alice pourra envoyer sa clé publique à Bob afin que celui-ci puisse chiffrer ses futures communications :

Capture d’écran du 2019-04-24 12-13-25.png

Pour chiffrer un message clair M on se servira de la formule suivante :

C = M^e % n

Et pour déchiffrer le message C on utilisera celle-ci :

M = C^d % n

Comme je vous l’ai dis plus haut, l’ensemble des calculs sont effectués modulo le module de chiffrement. On notera aussi que l’exposant utilisé pour chiffrer un message est l’exposant de chiffrement tandis que l’exposant utilisé pour déchiffrer un message et l’exposant de déchiffrement (ils portent bien leurs noms 😉 ) !

Du coup on pourra chiffrer/déchiffrer le message « 2 » de cette manière :

Capture d’écran du 2019-04-24 12-21-52.png

A partir de maintenant Bob pourra communiquer de manière sécurisée avec Alice mais l’inverse n’est pas vrai. En effet pour que les deux communicants puissent communiquer de manière sécurisée il faudra que Bob génère lui aussi une paire de clé publique/privée.

Et non, pour ceux qui se posent la question, Alice ne devra JAMAIS chiffrer ses messages à l’aide de sa clé privée puisque n’importe qui (c’est à dire toute personnes se situant dans la zone bleue) pourra utiliser la clé publique d’Alice pour déchiffrer le messages.

Les clés publiques sont utilisées pour chiffrer tandis que les clés privées sont utilisées pour déchiffre 😉 !

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s