Le chiffrage RSA, un miracle économique!

Comme vous avez pu le constater dans quelques-uns de mes anciens billets (ici et ici), je trouve certains concepts mathématiques fascinants, surtout quand ils sont contre-intuitifs.

L’un d’entre eux est le système de cryptographie asymétrique RSA. Ces trois lettres sont la première lettre des noms de famille des trois chercheurs qui ont découvert cette méthode fantastique vers la fin des années 1970s (Rivest, Shamir et Adleman).

Si vous voulez envoyer une message encrypté à quelqu’un vous pourriez simplement remplacer chaque lettre par un nombre aléatoire, envoyer le message encrypté à votre correspondant et ensuite lui faire parvenir la clé de décryption par un moyen sécuritaire. Cependant, cette façon de faire est peu pratique, car elle nécessite de disposer d’un moyen de communication sécurisé.

L’encryption RSA résout ce problème de manière très élégante grâce à certaines propriétés des nombres premiers. Pour comprendre le concept de base, imaginez qu’Alice envoie à Bob une boîte déverrouillée dont elle conserve la clé, que Bob met son message dans la boîte, la verrouille et la renvoie à Alice, qui peut ensuite utiliser sa clé pour déverrouiller la boîte et lire le message.

N’importe qui peut intercepter la boîte et y mettre un message, mais seule Alice peut la déverrouiller. Évidemment, pour que le message soit vraiment sécuritaire, il faudrait aussi qu’Alice puisse authentifier qu’il provient bien de Bob, mais ce billet se concentrera sur l’encryption du message et non sur l’authentification.

L’arithmétique modulaire
Avant de faire un exemple d’encryption RSA, il faut d’abord comprendre ce qu’est le modulo. Cette fonction donne le résiduel d’une division. Par exemple, 46 divisé par 17 égale 2 résiduel 12, donc:

46 (mod 17) = 12

Tout le monde pratique ce genre d’arithmétique sans même le réaliser, par exemple, supposons qu’il est 22h et que vous devez régler votre réveil-matin de manière à dormir 8 heures. Le calcul que vous faîtes intuitivement est le suivant:

22+8 (mod 12) = 6 car 30 divisé par 12 = 2 résiduel 6, donc vous mettrez votre réveil à 6h00.

Ce qui est encore plus intéressant est d’ajouter un exposant x au premier terme, de manière à obtenir l’expression 3^x (mod 17), si vous choisissez x de manière aléatoire, la réponse aura une probabilité égale d’être n’importe quel chiffre compris entre 0 et 17:

3^3 (mod 17) = 10
3^4 (mod 17) = 13
3^5 (mod 17) = 5
3^6 (mod 17) = 15
3^7 (mod 17) = 11
3^8 (mod 17) = 16

Comme vous pouvez voir, cet algorithme ne suit aucun « pattern » prévisible. Si vous avez une équation de type C = b^e (mod m)

b = 9
e = 3
m = 23

C= 9^3 (mod 23) = 729 (mod 23) = 16

Car 729 = 31 * 23 + 16

Si b, e et m ne sont pas négatifs et que b est plus petit que m, il n’existera qu’une seule solution, ce qui est une propriété intéressante pour un cryptographe. De plus, l’opération est à sens unique, car même si je vous donne la réponse C (16) et m (23), vous ne serez pas capable de deviner b et e.

Un autre concept mathématique à maîtriser pour comprendre le fonctionnement du chiffrage RSA est le totient d’Euler (fonction Phi). Le totient d’Euler donne le nombre de nombres entiers qui sont premiers relativement à N (c’est-à-dire dont le plus grand dénominateur commun est 1).

Par exemple, si on prend N=9, la fonction Phi[9] = 6 car si on divise 9 par 1, 2, 4, 5, 7 et 8, la réponse n’est pas un nombre entier autre que 1. Il y a donc 6 chiffres qui ne divisent pas neuf en un nombre entier différent de 1.

Cependant, si N est un nombre premier, Phi[N] sera égal à N-1 car en tant que nombre premier, aucun chiffre ne peut diviser N en un nombre entier autre que 1.

Par ailleurs, si N est le produit de deux nombres premiers P et Q, Phi[N] = Phi[P] * Phi[Q] = (P-1)*(Q-1).

La fonction du totient d’Euler. La ligne formée par les points en haut sont des nombres premiers, le résultat étant n-1.

Finalement, le chiffrage RSA fait usage du théorême d’Euler:

1 = M^Phi[N] (mod N)

Par exemple, 3^Phi[9] (mod 9) = 3^6 (mod 9) = 729 (mod 9) = 1

Ce théorême fait le lien entre l’arithmétique modulaire et le totient d’Euler et est crucial pour le chiffrage RSA.

Un exemple simplifié
La première étape consiste à ce qu’Alice construise sa boîte et la clé. Elle choisit simplement deux nombres premiers P et Q. Pour mon exemple, j’utiliserai 11 et 17, mais il serait préférable d’utiliser des nombres beaucoup plus grands.

Alice calcule ensuite N = P * Q = 11 X 17 = 187

Puis elle calcule Z = (P-1) * (Q-1) = 10 X 16 = 160

Notez que Z est en fait équivalent à Phi[N] = Phi[187] = 160.

Alice doit ensuite choisir son exposant d’encryption E de manière à ce que ce chiffre soit compris entre 1 et Z, et qu’il soit un nombre premier relativement à P et Q. J’ai décidé d’utiliser E = 3 car si je divise P ou Q par 3, la réponse n’est pas un nombre entier autre que 1.

Alice doit ensuite calculer son exposant de décryption D en utilisant la formule suivante:

E*D (mod Z) = 1
3D (mod 160) = 1

En isolant D, on obtient sa valeur de 107. Donc D = 107

Notez que ce calcul peut être fait à partir du théorême d’Euler.

D = ((2*Z)+1)/e = ((2*160)+1)/3 = 107

Alice peut rendre publiques les valeurs de E et N, mais doit absolument garder P, Q, Z et D secrets. Les valeurs de E et N constituent sa boite ouverte.

De son côté, Bob veut envoyer un message secret M à Alice, soit le chiffre 15.

Donc M = 15

Bob calcule la valeur encryptée de son message C = M^E (mod N) en utilisant les valeurs transmises par Alice.

C = 15^3 (mod 187) = 9 Car 15^3 = 3375 = 18*187 + 9

Bob peut ensuite envoyer la valeur de C (9) à Alice de manière publique. Pour le décrypter, Alice n’aura qu’à utiliser son exposant secret D:

M = C^D (mod N) = 9^107 (mod 187) = 15

Le message est décrypté. Notez que si un espion dispose des valeurs de E, N et C, il lui est excessivement difficile de décrypter le message. Il faut être en mesure de factoriser N, ce qui est très fastidieux.

Difficile, mais pas impossible. Il faut juste y dédier un puissant ordinateur qui essayera toutes les combinaisons possibles, ce qui prendra des jours, voire des années, lorsque les valeurs utilisées ont des centaines de chiffres. Tout ce qu’il faut pour que le code soit indéchiffrable est de changer les valeurs de la clé dans un intervalle de temps suffisamment court pour qu’aucun pirate n’ait le temps de les calculer.

Un algorithme qui a changé le monde…
La découverte de cet algorithme a véritablement permi la révolution internet que nous connaissons aujourd’hui. Le chiffrage RSA permet de travailler de la maison en toute sécurité, en permettant d’accéder au réseau interne d’une entreprise à partir d’un laptop connecté à l’internet.

Il permet aussi de sécuriser les SMS envoyé à partir de votre téléphone. Encore plus important le chiffrage RSA protège les données échangées à partir des sites HTTPS, ce qui permet entre autres le commerce électronique, les applications bancaires et la transmission de données par internet. Le chiffrage RSA fait aussi fonctionner les réseaux de Visa, MasterCard et Amex.

Autrement dit, sans chiffrage RSA, Amazon n’existerait peut-être même pas! Le paiement par carte de crédit serait pénible et les services bancaires en ligne impossibles.

Imaginez aussi si les Nazis avaient découvert ce truc en 1940. La décryption de l’Enigma par Turing, un véritable exploit, n’aurait pas eu lieu et la guerre aurait sans doute duré plus longtemps, emportant avec elle des milliers de vies…

Ceci dit, la sécurité du RSA est de plus en plus menacée, notamment par les ordinateurs de plus en plus puissants, mais aussi par l’avènement éventuel d’ordinateurs quantiques, qui pourraient tester toutes les possibilités de facteurs en superposition et découvrir la clé beaucoup plus rapidement. Il faudra alors élaborer un nouveau mode de chiffrage utilisant aussi les ordinateurs quantiques (voir ceci).

Pour une explication plus longue, mais plus facile à comprendre, vous pouvez écouter cette série de vidéos de la Khan Academy.