Comprendre le chiffrement asymétrique

Le système de chiffrement asymétrique permet de chiffrer un message en assurant la confidentialité. Il n’y a que le récepteur possédant la clé privée qui peut lire le message. Cette clé privée n’a pas été diffusée.

Ce système permet également d’authentifier l’expéditeur.

Exemple
Si l’expéditeur utilise sa clé privée pour signer un document, il appose sa signature. C’est comme si il apposait son empreinte « digitale ».

Toute personne qui possède la clé publique de l’expéditeur est alors en mesure de retrouver la signature et donc d‘authentifier l’expéditeur.

Le chiffrement asymétrique est plus long que le chiffrement symétrique, on ne pourra de plus pas récupérer la clé privée si on la perd.

Soit deux personnes, qu’on nomme par convention Alice et Bob, qui souhaitent échanger un message chiffré reposant sur une clé privée K, mais qui ne disposent pas d’une communication sécurisée.

Ils utilisent l’algorithme d’échange de clés Diffie-Hellmann, qui repose sur l’arithmétique modulaire, pour s’échanger cette clé de chiffrement privée K.

L’arithmétique modulaire utilise l’opération modulo sur les nombres entiers.

L’opération modulo entre un entier a et un entier b permet d’obtenir le reste de la division euclidienne de a par b.

Si on prend des entiers p, a et x, on calcule ainsi très facilement y = a^x modulo p, par contre retrouver x connaissant y est très difficile si p est grand.

	Alice	Bob
Étape 1	Alice et Bob choisissent ensemble un nombre premier p et un nombre entier g tels que 1 ≤ g < p – 1. Cet échange n’a pas besoin d’être sécurisé.
Étape 2	Alice choisit secrètement un entier a au hasard.	Bob choisit secrètement un entier b au hasard.
Étape 3	Alice calcule  A = ga modulo p.	Bob calcule  B = gb modulo p.
Étape 4	Alice envoie à Bob la valeur de A, tandis que Bob envoie à Alice la valeur de B. Cet échange n’a pas besoin d'être sécurisé.
Étape 5	Alice calcule Ba = (gb)a = gab modulo p. Le nombre obtenu correspond à la clé secrète K.	Bob calcule Ab = (ga)b = gab modulo p. Le nombre obtenu correspond à la clé secrète K.

Alice et Bob connaissent donc la même clé secrète sans se l’envoyer, qui correspond au nombre g^ab modulo p.

Si les transmissions sont interceptées, l’attaquant connaitra p, g, A et B, mais il ne pourra pas retrouver K car il ne connait pas a et b.

En mathématiques, il est en effet très difficile de retrouver a si on connait g, p et B = g^a modulo p.

Voici un exemple d’échange d’une clé secrète avec l’algorithme Diffie-Hellman, pour un petit nombre premier p.

	Alice	Bob
Étape 1	Alice et Bob choisissent ensemble p = 11 et g = 7.
Étape 2	Alice choisit secrètement a = 6.	Bob choisit secrètement b = 9.
Étape 3	Alice calcule A = ga = 76 modulo p = 11.	Bob calcule B = gb = 79 modulo p = 11.
Étape 4	Alice envoie à Bob la valeur de A (76), tandis que Bob envoie à Alice la valeur de B (79). Cet échange n’a pas besoin d'être sécurisé.
Étape 5	Alice et Bob calculent gab = 76 × 9 = 754 modulo p = 11, ce qui vaut 3 : c’est une clé partagée seulement par Alice et Bob.

À la fin de l’algorithme, Alice et Bob connaissent donc la même clé secrète K = 3.

Alice dispose d’une clé publique  et d’une clé privée .

Bob dispose d’une clé publique  et d’une clé privée .

Alice veut envoyer un message confidentiel à Bob, et Bob veut répondre à Alice de façon confidentielle.

Ils doivent suivre la procédure suivante.

1. Alice envoie à Bob : .
2. Bob envoie à Alice : .
3. Alice envoie à Bob un message chiffré avec ,
   il n’y a que Bob qui pourra le déchiffrer avec sa clé privée .
4. Celui-ci lui répond en chiffrant son message avec ,
   il n’y a qu’Alice qui pourra le déchiffrer avec sa clé privée .

Bob et Alice souhaitent se transmettre des informations.

Alice choisit deux nombres premiers p et q assez grands (plus d’une centaine de chiffres) qu’elle garde secrets.

Elle calcule alors leur produit n = pq qu’on nomme module de chiffrement et qui va faire partie de sa clé publique.

Puis elle choisit un nombre entier e qui est premier avec (p – 1)(q – 1).

Elle publie alors dans un annuaire, qui peut se trouver sur le web, sa clé publique RSA (n, e).

Bob veut envoyer un message à Alice, il récupère dans l’annuaire la clé publique RSA (n, e) que Alice a publiée. Cette clé publique lui indique qu’il doit utiliser l’algorithme RSA avec les deux entiers n et e.

Bob découpe d’abord son message en blocs B de même taille qui représentent chacun un nombre plus petit que n.

Il transforme ensuite chaque bloc B en un bloc C qui est chiffré, grâce au calcul C = B^e modulo n.

En regroupant les blocs C obtenus par calcul, Bob obtient le message chiffré qu’il va envoyer à Alice.

On voit que pour chiffrer un message, il va y avoir pas mal de calculs puisqu’il faut transformer chaque bloc B du message en clair en un bloc C qui est chiffré.

Pour déchiffrer le message envoyé par Bob, Alice utilise sa clé privée k qu’elle a obtenue à partir de p et de q.

Cette clé satisfait l’équation ek = 1 modulo (p – 1)(q – 1).

Alice déchiffre chaque bloc C du message chiffré en utilisant la formule B = C^k modulo n.

En regroupant les blocs B obtenus par calcul, Alice obtient le message secret de Bob.

Pour chiffrer un bloc B en un bloc C, connaissant la clé publique RSA (n, e), on doit calculer C = B^e modulo n, avec n et e les entiers qui composent la clé publique reçue.

On appelle cela une exponentiation rapide, et Python possède une fonction native qui permet cela : il faut taper la fonction pow, suivie de B, suivi de l’exposant e qui est lui-même suivi de n.

pow(B,e,n)

Voici le programme associé pour chiffrer un bloc B en un bloc C avec Python.