L'algorithme RSA

Mis à jour le jeudi 10 janvier 2013
RSA

Crypter et décrypter

Quoi de mieux pour introduire la cryptologie qu'un petit historique ?
Il était une fois sur la planète bleue, dans un lointain passé :p , le désir de cacher et de coder ses messages (attention, cacher fait appel à la stéganographie et coder à la cryptographie !). Tout commença en 1900 avant J-C où un scribe égyptien employa des hiéroglyphes erronés volontairement. (Je vais griller quelques étapes ^^ ). Nous arrivons donc aux méthodes grecques et hébraïques. On notera parmi les méthodes grecques, celle de l'historien Polybe, puisque son invention inspirera le futur. La méthode est basée sur un principe de substitution avec l'utilisation d'un carré (voir ici). Toujours avec le principe de substitution, le bon vieux César y a mis sa patte. :D En effet vers 1 siècle avant J-C, César crypte ses messages en remplaçant une lettre par une autre n place(s) après. Accélérons le temps pour faire un tour en 1919, date de parution de la machine Enigma, machine à crypter, qui fut employée par les nazis durant la guerre. En 1977 apparait DES, qui est succédé par AES qui lui, sera utilisé pour le chiffrement de documents aux USA. Nous touchons le but. :p Effectivement, avril 1977, RSA montre le bout de son nez. :D

Cryptage

On trouve principalement deux grandes familles de cryptage : le cryptage symétrique (ou dit à clé secrète) et le cryptage asymétrique (dit aussi à clé publique).

Le cryptage symétrique

On parle de cryptage symétrique lorsqu'un texte, document, etc. est crypté et décrypté avec la même clé, la clé secrète, ce procédé est à la fois simple et sûr. On trouvera principalement parmi les algorithmes de cryptage symétrique : AES, qui serait utilisé pour protéger des documents secrets aux États-Unis (ici). Principal inconvénient : étant donné que l'on n'a qu'une clé, si vous la donnez à X pour qu'il puisse vous envoyer des messages cryptés avec celle-ci, il pourra aussi bien décrypter tous les documents que vous avez crypté avec cette dernière. La clé est donc connue uniquement par le destinataire et l'émetteur et il est plus sûr de faire une clé pour un échange entre X et Y, pour éviter qu'avec une clé on puisse tout décrypter.

Le cryptage asymétrique

Contrairement au cryptage symétrique, ici avec l'asymétrique, on a 2 clés.
Tout d'abord nous avons la clé publique. Celle-ci, tout le monde peut la posséder, il n'y a aucun risque, vous pouvez la transmettre à n'importe qui. Elle sert à crypter le message. Puis il y a la clé privée que seul le récepteur possède, en l'occurrence vous. Elle servira à décrypter le message crypté avec la clé publique.
Pour clarifier mon charabia, une petite illustration :

Principe du cryptage asymétrique

Devinez quoi ? RSA fait partie des cryptages asymétriques ! :D

Rivest, Shamir, Adleman

Alors, vous avez remarqué ? R... S... A... ! Oui, RSA est un sigle provenant des noms de ses inventeurs, qui sont respectivement Ron Rivest, Adi Shamir et Léonard Adleman.
Quelques informations pour situer ces personnages tirées de Wikipédia :
Ron Rivest est né à New York en 1947, et devient cryptologue. Adi Shamir, d'origine Israëlienne, né à Tel Aviv en 1952, est cryptologue et professeur au département de mathématiques appliquées du Weizmann Institute of Science. Il est reconnu pour ses qualités de cryptanalyste. Pour finir, Leonard Adleman, chercheur en informatique théorique et professeur en informatique et en biologie moléculaire à l'Universitée de la Californie du Sud, né en 1945.
Avec cette brochette de génies, on ne peut pas dire que l'algorithme RSA a été fait à la légère. ^^

Un algoriquoi ?

Un algorithme, c'est une suite d'instructions visant à résoudre un problème. Celui-ci a été créé en 1977 et breveté en 1983 par le MIT (Massachusetts Institute of Technology) qui expira le 21 septembre 2000.

Fonctionnement

Alice est retenue prisonnière dans une grotte sombre et répugnante par un ogre affamé, ses jours sont comptés, elle veut envoyer un message à Bob par pigeon voyageur pour qu'il prévienne la gendarmerie nationale.

Euh comment dire... Je veux apprendre à crypter avec RSA et toi tu me parles d'une grotte et d'un ogre. :o

Non, attendez, Alice va crypter son message à l'aide de RSA. :D
Avant que notre Alice soit prisonnière, Bob a créé une clé publique et une clé privée. Il donne la clé publique à Alice et garde soigneusement la clé privée.
Regardons de plus près le travail de Bob.
Bob créé 2 nombres p et q, les autres nombres seront trouvés grâce à eux :

Nombres

Descriptions

p, q

2 grands nombres premiers

n

p*q

Image utilisateurImage utilisateur

n

(p-1)*(q-1)

e

Image utilisateurImage utilisateur

p,q < e <

n, pgcd(

n , e) = 1

d

Image utilisateurImage utilisateur

p,q < d <

n, e*d mod

n = 1

La clé publique est sous la forme (e, n), celle que Alice possède et que tout le monde peut avoir sans aucun problème, ce couple permettra le cryptage de chaque message et la clé privée qui servira au décryptage se présente sous la forme (d, n), celle que Bob garde précieusement.

Crypter un message, en théorie

Notre Alice veut envoyer un message à Bob. Elle a donc à la base un message clair (mc), elle doit tout d'abord transformer chaque caractère en numérique (cn). Exemple : position dans l'alphabet, ASCII, etc., puis chiffrer chaque nombre pour obtenir les caractères codés (cc).
cne mod n = cc
e et n sont connus grâce à la clé publique de Bob.

Image utilisateurDéterminer p, q, n, n, e

Bon c'est bien gentil la théorie, mais Alice commence à déprimer dans la grotte. Passons à l'action !
Voyons les calculs de Bob pour obtenir les clés et pouvoir chiffrer et déchiffrer.
Bob choisit p = 503 et q = 563, 503 et 563 sont premiers car ils ne sont divisibles que par 1 et eux-mêmes, c'est justement ce qu'il nous faut. Leur taille est plutôt petite, mais pour les explications elle suffira, pour un cryptage fiable avec RSA, il est recommandé d'utiliser des nombres de l'ordre de 100 chiffres voir plus.
Une fois p et q généré, le reste n'est que calcul. Sans trop de difficulté, on trouve n = 283189 = 503*563 et on se calcule vite fait bien fait

Image utilisateur

n = 282124 = (503-1)*(563-1).

On trouve e par conditions, celles vu plus haut, je vous les rappelle : p,q < e <

Image utilisateur

n, PGCD(

Image utilisateur

n, e) = 1.
La première condition délimite une portion de nombre dans laquelle se trouve e. Avec la deuxième on teste chaque nombre compris dans cette portion. Ils sont testés avec le PGCD (plus grand commun diviseur). Il y a de fortes chances que plusieurs e soient possibles, prenez le premier trouvé. ^^ Alors que nous a choisi Bob ?
Déjà on sait que e se trouve entre 563 et 282124. On teste chaque nombre et si PGCD(

Image utilisateur

n, e) = 1, on arrête, on dit alors que

Image utilisateur

n et e sont premiers entre eux. Vous êtes prêt à tester une centaine de milliers de nombres ? :D Je vous rassure, e ne se cache pas très loin :
PGCD(282124, 564) = 4
PGCD(282124, 565) = 1
PGCD(282124, 566) = 2
PGCD(282124, 567) = 1
...
Donc comme je vous ai dit, prenez le 1er venu, soit e = 565.
Bob a donc p, q, n,

Image utilisateur

n et e ; il va pouvoir créer la clé publique (e, n).
Clé publique de Bob : (565, 283189).
Il peut maintenant la donner à Alice et même la publier, il n'y a aucun risque.

Alice est enfermée dans un coin obscur de la grotte, pendant que l'ogre, servi par des gobelins, mange ; elle griffonne sur un bout de papier les calculs pour crypter avec RSA et la clé publique de Bob. :D Elle veut chiffrer le texte suivant :
"Help !".
Message d'une importance capitale. :p

Coder chaque caractère en ASCII

Tout d'abord qu'est ce que l'ASCII ?
Votre ordinateur ne sait lire et sauvegarder que des données numériques. Oh la grosse quiche ! :p Donc il doit remplacer chaque caractère par un nombre, grâce à l'ASCII (American Standard Code for Information Interchange). L'ASCII est en fait une table où chaque caractère a son équivalent numérique.
Une fois votre message élaboré, la première des choses à faire est de transcrire toutes les lettres le composant en un nombre, simplement pour réussir à calculer, donc à crypter chacune des lettres. On peut coder les caractères en ASCII, ou alors, les remplacer par leur position dans l'alphabet, ou encore d'autres possibilités, mais le récepteur devra être au courant de la méthode utilisée.

Caractère

ASCII

H

72

e

101

l

108

p

112

(espace)

32

!

33

Le message, transcrit en numérique avec l'ASCII, est donc 72 101 108 112 32 33.

Un problème d'envergure !

Imaginez un instant que l'on ait un long texte. Si ce texte venait à être crypté, on aurait donc pour chaque caractère un nombre qui résulte du cryptage, mais dans ce genre de texte la même lettre peut réapparaître plusieurs fois, donc aussi le nombre résultant du cryptage de celle-ci.
Exemple :
coucou
On retrouve le c, le o et le u 2 fois. Un cryptage potentiel pourrait donner :
105320358456105320358456
Pour une même lettre, on retrouve le même code ! Pour un texte codé d'une page si pour une même lettre on a un même code, cela pourrait compromettre sérieusement la sécurité du document puisque si l'analyse de fréquence d'apparition des lettres est utilisé, le texte peut être facilement décodé. En quoi consiste cette analyse ? Tout simplement à dire que pour la langue française en moyenne telle lettre a une fréquence d'apparition de tant de pour cent. Si on retrouve donc sur un texte de 500 mots, 50 fois le code 5489, on peut admettre grâce à cette analyse que tous les 5489 correspondent à "a" par exemple. Même principe pour "b", "c", "d", etc.

La solution :

La solution est de regrouper les codes ASCII en blocs de même longueur.
On leur donne d'abord à tous une longueur fixe, ici 3, en rajoutant des 0 devant si nécessaire. Cette longueur fixe sera toujours 2 ou 3 puisque le code ASCII ne contient aucun nombre avec plus de 3 chiffres.
072 101 108 112 032 033
Et on les regroupe en blocs de longueur 4 :
0721 0110 8112 0320 0033

Avec ceci on n'aura jamais un même code pour une même lettre. Par contre le destinataire devra connaître au préalable les longueurs, sinon une fois décrypté, il ne saura pas comment découper pour retrouver l'ASCII.
On crypte. On décrypte. On retrouve :
0721 0110 81120320 0033
On découpe en blocs de 3.
072 101 108 112 032 000 33
Soit :
72 101 108 112 32 33
On a bien retrouvé notre ASCII.
Bon faut avouer, la méthode est fastidieuse, pour la suite du tutoriel et pour le programme, on ne l'utilisera pas pour privilégier la simplicité. ^^

Crypter le code ASCII

Nous allons crypter le code ASCII de chaque caractère du message. Ce cryptage se fait grâce à un simple calcul, qui prend en compte le bloc, e et n qui sont présents dans la clé publique.
Formule :
Bloce % n = cc
"%" signifie modulo (ou mod).

Maintenant, il suffit juste de crypter chaque bloc comme le montre la formule.

072565 % 283189 = 80488
101565 % 283189 = 2826
108565 % 283189 = 241808
112565 % 283189 = 183218
032565 % 283189 = 45154
033565 % 283189 = 84918

Alice a donc crypté son message "Help !", avec la clé publique de Bob, et elle obtient : 80488 2826 241808 183218 45154 84918.
Il ne lui reste plus qu'à transmettre le message crypté et elle aura fait ce qu'elle pouvait notre pauvre Alice. :p

Décryptage

À partir de maintenant, deux histoires peuvent s'écrire. Soit son message est intercepté et décrypté, soit Bob le reçoit et Alice est sauvée.

Décrypter un message, en théorie

Destinataire indésirable

Ce destinataire, une fois en possession du message, doit créer la clé privée, par le biais de la factorisation de n, puis il décrypte chaque caractère codé (cc) et il obtient le code ASCII de chaque caractère (cn), puis il les transcrit en caractères clairs (ccl) pour obtenir le message clair.
ccd % n = cn
cn -> ccl -> mc
n connu grâce à la clé publique et d doit être calculé après la factorisation de n.

Véritable destinataire

Prenons l'exemple de Bob. Il reçoit le message crypté, il décrypte chaque caractère codé (cc) et il obtient le code ASCII de chaque caractère (cn), puis il les transcrit en caractères clairs (ccl) pour obtenir le message clair.
ccd % n = cn
cn -> ccl -> mc
d et n sont connus grâce à la clé privée de Bob.

Comme vous pouvez le constater, ces 2 cas sont similaires, ce qui les différencie et d'ailleurs ce qui est à l'origine de la fiabilité de RSA, c'est la factorisation de n. On va donc envisager les 2 cas. Alors, on commence par lequel ? :p

Bon, commençons par le cas où le message serait malheureusement intercepté. Admettons que ce soit un gros gobelin méchant, qui en chassant le pigeon a récupéré celui d'Alice. Comme il n'y comprend rien, il va le porter au gobelin cryptologue. :-° Celui-ci trouvera donc à l'intérieur du message les blocs cryptés. Puisque ce n'est pas lui le destinataire, l'approche pour le décryptage sera différente. Le véritable destinataire, le créateur des clés, aurait utilisé la clé privée, mais lui devra créer la clé privée à partir de la clé publique, pour réussir à décrypter le message !
Clé privée : (d, n).
Comme n est déjà présent dans la clé publique, il reste d à trouver.
Nous avions évoqué plus haut comment l'avoir. Je vous redonne la ligne : p,q < d < n, e*d mod n = 1. Misère ! p et q, on ne les connaît pas ! Exact, mais n est le produit de 2 facteurs premiers qui sont p et q, donc la factorisation de n, nous donne p et q. Cette factorisation est longue, voire très très longue selon la taille de n et vous verrez que c'est le but recherché. On regardera ceci de plus près quelques lignes plus bas.
En factorisant n, on retrouve donc p = 503, q = 563.
Je ne vais pas détailler les calculs suivants car nous les avons déjà rencontrés plus haut.

Image utilisateur

n = 282124, e = 565.

Déterminer d

En analysant un peu les conditions pour trouver d, on remarque que le principe est le même que pour e. On délimite tout d'abord une portion de nombre où se trouve d, d plus grand que p et q et d inférieur à n. Puis on teste les nombres compris dans cette zone avec ce calcul e*d mod

Image utilisateur

n = 1.
565 * 564 % 282124 = 566
565 * 565 % 282124 = 37101
...
565 * 140313 % 282124 = 1
565 * 140314 % 282124 = 566
Cette fois-ci, manuellement il aurait fallu passer un bon bout de temps avant de trouver d. Il vaut mieux appliquer cette méthode à un programme qui nous trouvera d. Mais il y a une autre solution bien plus rapide qui se résume à un seul calcul.

d = 1/e %

Image utilisateur

n
d = 1/565 % 282124
d = 140313

Cette dernière méthode est bien plus pratique.
Avec ces 2 méthodes, on peut aisément trouver d, et donc la clé privée.
Clé privée de Bob (trouvée par les méchants gobelins avec la factorisation de n) : (140313, 282124).

Décrypter le message

Citation : Alice

80488 / 2826 / 241808 / 183218 / 45154 / 84918

Le décryptage sera aussi simple que le cryptage, une simple formule, et nous retrouverons nos blocs de départ, puis on les retranscrit en lettres grâce à la table ASCII.

Formule :
ccd % n = cn

80488140313 % 283189 = 72
2826140313 % 283189 = 101
241808140313 % 283189 = 108
183218140313 % 283189 = 112
45154140313 % 283189 = 32
84918140313 % 283189 = 33

ASCII

Caractère

72

H

101

e

108

l

112

p

32

(espace)

33

!

Et voilà, le message est décrypté, même si ce n'était pas le véritable destinataire !
Pourquoi ?
Tout simplement parce que la sureté du RSA repose sur la factorisation de n et notre n était bien trop petit, il a été factorisé rapidement avec un factorisateur banal.

Je vais prendre un nombre semi-premier, c'est-à-dire le produit de 2 nombres premiers, soit n, du challenge RSA qui n'est plus en vigueur, mais il est encore possible d'accéder à ces nombres. C'est le RSA-576, composé de 174 chiffres :

Citation : Challenge RSA

188 198 812 920 607 963 838 697 239 461 650 439 807 163 563 379 417 382 700 763 356 422 988 859 715 234 665 485 319 060 606 504 743 045 317 388 011 303 396 716 199 692 321 205 734 031 879 550 656 996 221 305 168 759 307 650 257 059

La factorisation en image : début et fin.
Vous pouvez remarquer que fin, c'est vite dit ^^ . En fait la factorisation n'a pas abouti et je ne pouvais pas me permettre de faire tourner mon ordinateur pendant des lustres. L'algorithme de factorisation est peut-être basique mais même avec du bon matériel et un bon algorithme, cela prend quand même énormément de temps, c'est pourquoi RSA est sûr !

Le décryptage du côté de Bob, qui lui est le vrai destinataire, soit le créateur des clés privée et publique, est similaire à celui d'un destinataire indésirable, à la différence que Bob ne doit pas passer par la factorisation de n pour trouver p et q puisqu'il les a déjà.
Voilà, la force de RSA !
Il calcule d, comme vu plus haut et il peut ensuite sans problème décrypter le message d'Alice.
Bob crée donc sa clé privée : (140313, 282124).
Rien de nouveau, il va décrypter de la même manière que notre gobelin cryptologue. Une fois décrypté, Bob pourra sauver Alice. ^^ Houraa ! :-°

Pour un programme de décryptage, il y a donc toujours 2 cas à prendre en compte. Soit il faut factoriser n pour trouver la clé privée ou simplement demander la clé privée à l'utilisateur.

Clé de chiffrement

Dans cette partie annexe, nous allons approfondir le terme de clé et nous verrons les législations qui s'y rapportent.

Qu'est ce qu'une clé de chiffrement ?

Citation : Wikipédia

Une clé est un paramètre utilisé en entrée d'une opération cryptographique (chiffrement, déchiffrement, scellement, signature numérique, vérification de signature).
Une clé de chiffrement peut être symétrique (cryptographie symétrique) ou asymétrique (cryptographie asymétrique) : ...
Une clé peut se présenter sous plusieurs formes : mots ou phrases, procédure pour préparer une machine de chiffrement (connexions, câblage, etc. Voir machine Enigma ), données codées sous une forme binaire (cryptologie moderne).

Dans ce chapitre, nous avons travailler avec 2 clés pour un cryptage asymétrique. Ces 2 clés étaient sous forme de chiffres, mais tout ceci a été vu plus haut. Nous allons maintenant nous intéresser à la taille d'une clé, exprimée en bits.
La taille d'une clé en bits est le nombre de bits qu'il faut pour l'écrire.
Exemple :
Ma clé est 10. Elle a donc une taille 4 bits. Puisque 10 égal en binaire 1010, il y a deux 1 et deux 0 soit 4 bits.

En cryptage symétrique, on dira qu'il y a 24 choix pour trouver la clé, soit 16 possibilités.

En asymétrique, c'est la taille de n qui est importante, puisque c'est n qui est factorisé et qui permet donc le décryptage.
Et le nombre de possibilités de n n'est guère utile puisqu'il est donné dans la clé publique.
Exemple :
Reprenons notre n.
n=283189 -> 1000101001000110101. Soit une taille de 19 bits, ce qui est beaucoup trop mince pour un chiffrement fiable.

Les tailles des clés utilisées en asymétrique et en symétrique ne peuvent être comparées. On utilise des tailles plus importantes pour des algorithmes comme RSA que pour DES.
Pourquoi ?
Parce que les chiffrements asymétriques reposent sur des problèmes arithmétiques, comme la factorisation pour RSA. Il est alors nécessaire que n dépasse les 1024 bits soit environ 300 chiffres, sinon la factorisation est trop rapide et le document n'est plus sécurisé.
Pour les chiffrements symétriques, étant donné qu'il n'y a qu'une clé, on utilise la méthode du brute force. Avec une clé beaucoup plus petit que n, on a quand même une sécurité fiable. Il faut un minimum de 128 bits soit 2128 possibilités, ce qui laisse déjà un petit moment au brute force pour se faire les dents. ^^

Il est possible aussi pour remédier au problème de l'échange de la clé secrète, de la crypter avec un chiffrement asymétrique et de crypter le message avec un chiffrement symétrique. Étant donné que la clé secrète est cryptée, elle peut être envoyée sans problème au destinataire du message qui devra faire un double décryptage : celui de la clé et celui du message. :p

La loi

La loi du 21 juin 2004, libéralise l'utilisation des moyens de cryptologie. Cependant la fourniture de clés de déchiffrement est soumise à déclaration ou autorisation. Voir wikipédia.

Avant de conclure, voici une petite liste de quelques outils qui pourront vous être d'une grande utilité avant d'avoir fait votre programme :

Ce chapitre est maintenant clos. J'espère avoir accompli ma noble tâche que je me suis fixée :D : vous faire comprendre clairement l'utilisation de l'algorithme RSA. D'ailleurs si j'ai oublié des points importants, n'hésitez pas à m'envoyer des MP ou à laisser un commentaire. ^^
Êtes-vous prêt à vous lancer dans l'élaboration de programmes pour RSA ? Je suis sûr que oui, alors rendez-vous à la partie suivante. :p

Les auteurs

Exemple de certificat de réussite
Exemple de certificat de réussite