Le chiffrement RSA expliqué pas à pas [1/5]

2

Dans cette série d’articles, nous allons rentrer dans les détails du chiffrement RSA. Cet algorithme est à la base de beaucoup de communications sécurisées que nous utilisons quotidiennement, notamment à travers les protocoles HTTPS et SSH. Aucune connaissance de chiffrement n’est nécessaire pour la lecture de ces articles. Si vous savez faire des multiplications et des divisions alors vous devriez tout comprendre. Tous les concepts sont expliqués en cas de besoin.

Pourquoi ?

Dans un premier temps, posons-nous la question “pourquoi se compliquer la vie” ?

Pour cela, commençons par introduire le contexte que nous utiliserons tout au long de ces articles.


Nous sommes au lycée d’Arcadia et nous nous intéressons à trois élèves en particulier.

Claire

Claire est très intelligente, sympa, badass et très jolie.

Jim

Jim est également intelligent, sympa et badass bien que timide. Ce qui est le plus important pour notre article est qu’il est amoureux de Claire et veut lui déclarer sa flamme.

Steve

Steve est bien moins bête qu’il n’en a l’air à première vue. Cependant, c’est le tyran de la classe. S’il parvient à savoir que Jim est amoureux de Claire, il n’hésitera pas à utiliser ça à son avantage.

Le problème

Jim est trop timide pour déclarer sa flamme à Claire de vive voix. Il veut donc lui dire par écrit. Il souhaite aussi que personne d’autre que Claire ne puisse lire sa lettre. Jim décide donc de chiffrer sa lettre.

Chiffrer ?

Chiffrer un message consiste à le transformer de manière à ce qu’il devienne illisible sauf pour la ou les personnes qui savent comment le déchiffrer. Pour expliquer ce concept, dans le prochain article, nous nous intéresserons au chiffrement symétrique.

 

Le chiffrement symétrique

Jim veut commencer à parler avec Claire. Il veut lui envoyer le message suivant :

Coucou

Pour chiffrer son message, il va utiliser un chiffrement par décalage de 6. C’est-à-dire qu’au lieu d’écrire la bonne lettre, il écrit la sixième lettre après celle qu’il aurait dû écrire. Ainsi le C devient I et le O devient U. Nous rencontrons cependant notre premier problème: la sixième lettre après U n’existe pas. Il y a cependant une solution simple : revenir au début de l’alphabet. Ainsi le U devient A. Jim enverra donc à Claire le message suivant :

Iuaiua

Si Steve trouve le message, il n’arrivera pas à le lire facilement.

Pour déchiffrer, Claire aura juste à prendre la sixième lettre avant celle qui est écrite pour retrouver le message d’origine.

Définitions

Grâce à cet exemple, nous pouvons donner quelques définitions.

Il est possible de faire un décalage de 3 ou de 7 ou de n’importe quel nombre compris entre 1 et 25. C’est là que la distinction entre clé et algorithme est importante :

  • L’algorithme est le fait de décaler les lettres
  • La clé est le nombre 6

On dit qu’il est facile pour Jim et Claire de chiffrer et déchiffrer un message avec la clé, mais qu’il est difficile pour Steve de déchiffrer le message sans la clé.

Seule la clé change entre deux couples de personnes. C’est donc la seule chose qui a réellement besoin d’être secrète.

 

Notre chiffrement précédent est plein de défauts. Le plus important étant qu’il n’accepte que 25 clés différentes. Les tester toutes (brute-forcer) est parfaitement imaginable. Cependant on peut ralentir l’attaque. Par exemple, nous pouvons faire un décalage de 6 pour les lettres à index pair et de 13 pour les lettres à index impair. Désormais, il y a 25 * 25 soit 625 clés possibles et la clé deviendrait 0613.

On voit bien ici que la difficulté à brute-forcer l’algorithme est directement liée à la taille de la clé et non à l’algorithme.

Quand nous parlons de difficulté, nous parlons en réalité de temps nécessaire à faire l’opération.

Nous pouvons désormais donner des chiffres pour définir ce qu’est une opération facile et une opération difficile.

Une opération sera jugée difficile si, avec la meilleure technologie du moment, réaliser l’opération prenait un temps plus long que l’âge de l’univers (13,8 milliards d’années, soit environ 4*10 puissance 17 secondes).

Une opération sera jugée facile si, avec une technologie grand public, réaliser l’opération prenait un temps moins long que la minute (soit 60 secondes)

Cependant, il y a toujours un risque que l’attaquant trouve la clé sur un coup de chance. Nous jugerons que c’est un évènement peu probable si sa probabilité est plus faible qu’une chance sur le nombre d’atomes présents dans l’univers visible (soit moins que 1 chance sur 10 puissance 82).

Un bon algorithme de chiffrement est un algorithme qui rend l’opération de chiffrement et de déchiffrement avec clé facile tout en rendant le déchiffrement sans clé difficile et peu probable.

Le chiffrement à décalage est un chiffrement symétrique, car la même clé est utilisée pour le chiffrement et le déchiffrement.

 

Enfin, une dernière chose mérite notre attention. Dans notre exemple, quand nous arrivons à la fin de l’alphabet, nous recommençons au début. C’est le même effet que les aiguilles d’une horloge. Si elle dépasse le 12, elle retombe à 1. Cette opération a un nom mathématique : le modulo. Il s’agit du reste de la division entière entre deux nombres entiers. 

Résumé mathématique

Un chiffrement définit une fonction de chiffrement (notée c) et une fonction de déchiffrement (notée d).

Etant donné un message M, et une clé k :

c(M,k) = M’

d(M’,k) = M

Comme appliquer d au résultat de c donne le paramètre M d’origine, on dit que d est l’inverse de c.

Nous allons aussi définir une fonction d’attaque (notée a) qui a pour but, étant donné M’ de trouver k. Soit :

a(M’) = k

Le temps d’opération est une notion physique, et non mathématique. L’équivalent du temps d’opération en mathématique est appelé la complexité d’un problème et est noté O. La complexité d’un problème est fonction de la taille du problème à résoudre. Dans le cas du chiffrement, la complexité est déterminée par la taille de la clé et la taille du message à chiffrer. Etant donné qu’on ne connaît pas la taille du message au moment de la création de la clé, nous allons exprimer la complexité en fixant la taille du message. Ainsi, seule la taille de la clé détermine la complexité du problème et sera notée n pour la suite de cet article.

Un problème sera jugé difficile si sa complexité est supérieure ou égale à O(en) (ou en est l’exponentiation de n) et facile dans les autres cas.

Ainsi un bon chiffrement est défini tel que :

O(c) < O(en), O(d) < O(en) et O(a) >= O(en).

 

Enfin, nous pouvons définir le modulo. On dit que 2 nombres x et y sont congrus modulo m (noté x ≡ y (mod m) ) s’il existe un entier z tel que : x = zm + y

Résumé en images


Le (Gros) problème

Nous savons maintenant ce qu’est un chiffrement et Jim peut enfin écrire à Claire ! À un détail prêt : il faut que Jim communique sa clé à Claire. Or il doit le faire par écrit, comme n’importe quel message et passer un mot dans la salle de classe comporte le risque de passer entre les mains de Steve, et si Steve a la clé, alors il pourra lire toutes les conversations. Ce n’est pas un risque acceptable. Il faut trouver une autre solution. Dans notre prochain article, nous étudierons le chiffrement asymétrique avec «trap-door».


Suite au prochain épisode

Partagez cet article.

A propos de l'auteur

Xavier travaille comme développeur et leader technique Java depuis plusieurs années et suit de très près les nombreuses avancées dans le domaine. Expert sur Struts, Spring, Hibernate, JUnit, TestNG, Mockito, Apache commons, Xavier est aussi adepte du Craftsmanship. "La pédagogie et le partage des bonnes pratiques dans un esprit convivial et ludique" est bel et bien son crédo.

2 commentaires

  1. Petit problème de formatage sur le site, le style pour afficher l’exposant du nombre d’atomes dans l’univers ne fonctionne pas. Du coup, 1 chance sur 1082, c’est léger 🙂

Ajouter un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.