La cryptographie RSA expliquée

La sécurité est, par les temps qui courent, un sujet réellement brûlant sur le réseau. Pour les plus matheux d'entre vous, j'ai fait cette page pour vous expliquer comment le chiffrement fonctionne. Et pour les moins matheux, j'espère que les quelques notions d'arithmétique que je vous rappelle en introduction vous aideront à comprendre quand même.

Le procédé décrit ici est le procédé RSA qui est le plus répandu, non seulement sur Internet mais aussi ailleurs.

Arithmétique à connaître

Au cas où vous n'auriez pas étudié l'arithmétique, voici les quelques notions auquelles je fais référence dans cette page. Si vous avez étudié l'arithmétique en mathématiques supérieures, vous pouvez sauter à la section suivante, il n'y a rien de nouveau pour vous ici.

Un diviseur d'un nombre entier n est un nombre d qui vérifie la propriété suivante : il existe un entier k tel que n = kd. On dit alors que d divise n ou que n est divisible par d et on écrit d | n. Tous les entiers sont divisibles par 1 et par eux-mêmes.
Un nombre entier p est dit premier si justement ses seuls diviseurs sont 1 et p.
Autrement dit d | p implique d = 1 ou d = p.
Un nombre p est dit premier avec q si le seul diviseur commun de p et q est 1. Attention, cela ne veux pas forcément dire que p et q sont premiers. Par exemple 12 est premier avec 35 car 12 a pour diviseurs 1,2,3,6 et 12 tandis que 35 a pour diviseurs 1,5,7 et 35. Pourtant 12 et 35 ont d'autres divseurs que 1 et eux mêmes.
L'écriture a^b où a et b sont des entiers se lit a élevé à la puissance b et désigne le nombre a multiplié b fois par lui même.
On dit que r égale n modulo p, ce qu'on écrit r = n mod p, lorsque le reste dans la division de n par p est égal à r. Cela signifie aussi qu'il existe un entier q tel que n = pq + r.
Si n = p^aq^b...r^c, avec des nombres p, q, ... , r tous premiers, ceux-ci sont appelés facteurs premiers de n. Ils sont uniques.

Bon, ben c'est tout ce dont vous avez besoin. J'espère ne pas vous avoir trop effrayé avec ces quelques mathématiques.

Le principe du chiffrement RSA

Le système RSA fonctionne de la manière suivante : celui qui est amené à recevoir des informations secrètes choisit une clé privée [p, q, e] où p et q sont deux grands nombres premiers et e un nombre qui est premier avec p-1 et q-1. A l'aide de ces deux nombres, il forme l'entier n = pq et il diffuse la clé publique [n, e] associée à sa clé privée, laquelle reste secrète.

Quand on veut envoyer un message secret, on le crypte avec la clé publique [n, e] de son destinataire qui le décryptera à l'aide de sa clé privée.

Tout le "truc" réside dans le fait qu'à partir d'un nombre n de plus de 100 chiffres, servant au chiffrement, il est très long et très difficile (même avec plusieurs gros ordinateurs) de retrouver les deux facteurs premiers p et q nécessaires au déchiffrement.

La préparation du chiffrement

Le procédé RSA transforme, à l'aide d'une formule mathématique, un nombre en un autre nombre. Le texte que l'on veut crypter doit donc être sous une forme numérique. Pour cela rien de plus simple, il suffit de remplacer les différents caractères par des chiffres suivant une table de codes, par exemple A=1, B=2, C=3 etc ...

Une solution tout à fait possible consiste à remplacer chaque caractère par sa valeur ASCII, variant de 000 à 255 en décimal ou de 00 à FF en hexadécimal.

Le chiffrement et le déchiffrement

Après cela on dispose donc d'une série de chiffres qui constituent un nombre m, forme numérique du message à transmettre.

On calcule alors c = m^e mod n

Le nombre c obtenu, constitue la forme cryptée de m. Dans le cas d'un échange d'informations sur Internet par exemple, c'est ce nombre c qui va être envoyé au destinataire via le réseau.

Lors de la réception de c, le destinataire effectue la procédure de déchiffrement :

On calcule un nombre d tel que e = d mod (p-1)(q-1). Un tel nombre, appelé inverse modulaire de e modulo (p-1)(q-1), existe et est toujours unique, compte tenu des hypothèses faites sur p, q et e.
Le message original m s'obtient alors par la formule m = c^d mod n

En examinant les deux procédures, vous pouvez remarquer que le chiffrement ne fait intervenir que n, alors que le déchiffrement fait intervenir p-1 et q-1 c'est à dire qu'il faut bel et bien connaître les valeurs de p et q pour décrypter le message.

Vous voulez essayer ?

Si vous disposez du logiciel Maple V release 4, vous pouvez télécharger ce petit programme (compressé en format .ZIP, 1926 octets). Il fournit toutes les procédures pour vous permettre de crypter et décrypter des messages, avec un nombre n de 207 chiffres.

Après avoir décompressé le programme et l'avoir ouvert dans Maple, entrez la commande suivante :

> message:=`Mon message à moi que je veux crypter`;

La variable message contient alors votre message sous forme littérale. Pour passer au format numérique puis crypter votre message, vous tapez :

> m:=code(message); > c:=crypt(m,n,e);

La variable c contient maintenant, sous forme inviolable, votre message ultra-secret. Votre correspondant n'a plus qu'à entrer les commandes suivantes pour tout savoir :

> m:=decrypt(c,p,q,e); > decode(m);

Voilà ! Amusez vous bien mais ne faites pas trop de choses illégales quand même ...

Liens à propos de la cryptographie

L'utilisation du chiffrement en France - Une page assez complémentaire de la mienne car elle ne s'intéresse pas à l'aspect technique mais plutôt aux questions juridiques qui tournent autour de la cryptographie.

RSA Homepage - Le fameux organisme qui a développé le procédé de chiffrement décrit ici. C'est une bonne mine d'informations, j'espère que vous avez du temps devant vous.