Le cryptosystème RSA

Chapitre: XV. Cryptographie moderne Prérequis: -

L'implémentation fut achevée en 1978 par Rivest, Shamir et Adleman. Depuis, ce système de chiffrement est appelé RSA, qui sont les initiales de ces trois chercheurs.

Fonctionnement du cryptosystème RSA

On appellera Alice la personne qui désire recevoir un message chiffré, et Bob la personne qui envoie le message.

1. Choix de la clef



Alice choisit deux grands entiers naturels premiers p et q (d'environ 100 chiffres chacun ou plus) et fait leur produit n = p·q. Puis elle choisit un entier e premier avec (p-1)·(q-1). Enfin, elle publie dans un annuaire, par exemple sur le web, sa clef publique: (RSA, n, e).

 

2. Chiffrement

Bob veut donc envoyer un message à Alice. Il cherche dans l'annuaire la clef de chiffrement qu'elle a publiée. Il sait maintenant qu'il doit utiliser le système RSA avec les deux entiers n et e (prenons par exemple n=5141=53·97 et e=7, premier avec 52·96=4992). Il transforme en nombres son message en remplaçant par exemple chaque lettre par son rang dans l'alphabet.

"JEVOUSAIME" devient : "10 05 22 15 21 19 01 09 13 05".

Puis il découpe son message chiffré en blocs de même longueur représentant chacun un nombre plus petit que n. Cette opération est essentielle, car si on ne faisait pas des blocs assez longs (par exemple si on laissait des blocs de 2 dans notre exemple), on retomberait sur un simple chiffre de substitution que l'on pourrait attaquer par l'analyse des fréquences.

Son message devient : "010 052 215 211 901 091 305"

Un bloc B est chiffré par la formule C = Be mod n, où C est un bloc du message chiffré que Bob enverra à Alice.

Après avoir chiffré chaque bloc, le message chiffré s'écrit : "0755 1324 2823 3550 3763 2237 2052".

 

3. Déchiffrement

Alice calcule à partir de p et q, qu'elle a gardés secrets, la clef d de déchiffrage (c'est sa clef privée). Celle-ci doit satisfaire l'équation e·d mod ((p-1)(q-1)) = 1. Ici, d=4279.
Chacun des blocs C du message chiffré sera déchiffré par la formule B = Cd mod n.

Elle retrouve : "010 052 215 211 901 091 305"

L'instruction d=PowerMod[e,-1,(p-1)(q-1)] de Mathematica permet de calculer d facilement.

En regroupant les chiffres deux par deux et en remplaçant les nombres ainsi obtenus par les lettres correspondantes, elle sait enfin que Bob l'aime secrètement, sans que personne d'autre ne puisse le savoir.

 

Intérêt de la méthode

Tout l'intérêt du système RSA repose sur le fait qu'à l'heure actuelle il est pratiquement impossible de retrouver dans un temps raisonnable p et q à partir de n si celui-ci est très grand (ou alors, si c'est possible, les cryptanalystes qui ont trouvé la méthode la gardent secrète). Alice est donc la seule à pouvoir calculer d dans un temps court. De plus, elle n'a jamais à transmettre les entiers p et q, ce qui empêche leur piratage.

Programme Javascript

Utilisation: La personne voulant déchiffrer le message doit posséder toutes les clefs, alors que les autres ne connaissent que les clefs publiques. Ici, les clefs personnelles sont p, q, d, les clefs publiques sont e et n. Le paramètre "Taille des blocs" indique comment regrouper les chiffres avant le chiffrement proprement dit. Avant de commencer, il faut choisir entre la table de conversion simple (les caractères à utiliser se limiteront alors aux majuscules et à l'espace) et la table de conversion étendue (qui permet les accents, les minuscules, les chiffres et d'autres caractères spéciaux). Vous pouvez utiliser d'autres tables de conversion, mais toutes les tables doivent contenir le symbole " " (espace).

Pour chiffrer: Il suffit d'entrer e, n et la taille des blocs (c'est la clef publique donnée par la personne qui déchiffrera) ainsi que le message dans le champ "Message clair". Appuyez ensuite sur "Chiffrer".

Pour déchiffrer: Entrez, en plus de e, n et la taille des blocs, la valeur de d (ou simplement entrez les trois nombres originaux de p, q et e puis appuyez sur le bouton calcul). Placez le cryptogramme dans le champ "Message chiffré", puis appuyez sur "Déchiffrer".

Création des clefs de (dé)chiffrement: Entrez des nombres premiers dans les champs p et q, puis e satisfaisant la condition énoncée dans la première partie de la page. Il faut que les 3 nombres soient différents. Appuyez ensuite sur le bouton "Calcul" pour trouver n et d. Plus les nombres sont grands, plus de décryptement sera difficile, mais le temps de déchiffrement augmentera aussi.

Clef privée p : q : e : Taille des blocs :
Clef publique n = p·q : d :
     
Table de conversion
Message clair
Message chiffré

Exercice

  1. Créez votre clef privée et votre clef publique (blocs de 3 pour tout le monde).
  2. Une fois que c'est fait, publiez votre clef publique en l'écrivant au tableau noir.
  3. Ecrivez à la personne de votre choix un message chiffré en utilisant sa clef publique que vous aurez repérée au tableau noir (utilisez la table de conversion étendue).
  4. Déchiffrez le message que vous avez reçu.

Travail (programmation)

Prérequis : le code ascii

Téléchargez ce fichier Mathematica et suivez les instructions qu'il contient:

rsa.nb (20 Ko)
Cliquez sur le nom du fichier ci-dessus puis enregistrez sur votre disque dur ce fichier en format Texte en allant dans le menu Fichier/Enregistrer sous...
Ouvrez ensuite ce fichier depuis Mathematica (version 3 ou supérieure), et complétez-le.

Le fichier Mathematica complet est disponible, mais seulement pour les visiteurs autorisés!
Mot de passe :

Références

Didier Müller, 19.2.01