Crypter et décrypter

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 asymé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 :



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

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

Non, attendez, Alice va crypter son message à l'aide de RSA.
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
n	(p-1)*(q-1)
e	p,q < e < n, pgcd(n , e) = 1
d	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).
cn^e mod n = cc
e et n sont connus grâce à la clé publique de Bob.

Dé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 n = 282124 = (503-1)*(563-1).

On trouve e par conditions, celles vu plus haut, je vous les rappelle : p,q < e < n, PGCD(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(n, e) = 1, on arrête, on dit alors que n et e sont premiers entre eux. Vous êtes prêt à tester une centaine de milliers de nombres ? 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 1^er venu, soit e = 565.
Bob a donc p, q, n, 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. Elle veut chiffrer le texte suivant :
"Help !".
Message d'une importance capitale.

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 ! 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 :
1053 2035 8456 1053 2035 8456
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 8112 0320 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 :
Bloc^e % n = cc
"%" signifie modulo (ou mod).

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

072⁵⁶⁵ % 283189 = 80488
101⁵⁶⁵ % 283189 = 2826
108⁵⁶⁵ % 283189 = 241808
112⁵⁶⁵ % 283189 = 183218
032⁵⁶⁵ % 283189 = 45154
033⁵⁶⁵ % 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.

À 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.
cc^d % 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.
cc^d % 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 ?

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. 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 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 % 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
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 :
cc^d % n = cn

80488¹⁴⁰³¹³ % 283189 = 72
2826¹⁴⁰³¹³ % 283189 = 101
241808¹⁴⁰³¹³ % 283189 = 108
183218¹⁴⁰³¹³ % 283189 = 112
45154¹⁴⁰³¹³ % 283189 = 32
84918¹⁴⁰³¹³ % 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
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.

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

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 2⁴ 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 2¹²⁸ 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.

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.