Le chiffrement RSA

Comment peut-on crypter efficacement un texte et plus généralement des informations ? Une première idée peut être de remplacer chaque lettre de l’alphabet par un autre symbole. Ce type de codage est utilisé par exemple dans une énigme présentée sur ce site web. En utilisant ce principe, on peut aussi choisir de représenter chaque lettre de l’alphabet par un nombre : un codage de cette forme est appelé un chiffrement. Voici par exemple un mot français de 4 lettres obtenu en utilisant ce mode de chiffrement :

27 – 35 – 27 – 35

Ce n’est pas si difficile de deviner le mot chiffré car on peut observer déjà qu’il n’y a que deux lettres différentes qui sont utilisées. Ce mot peut être par exemple « papa » ou « bobo ». Il y a en fait possibilités pour créer un mot de ce type mais en recherchant ensuite parmi ces mots ceux qui ont un sens dans la langue française le nombre de possibilités est vite réduit. Peut-on améliorer notre système de chiffrement ? C’est tout à fait possible en adoptant par exemple le chiffrement RSA du nom de ses inventeurs : Rivest, Shamir et Adleman. Ce mode de chiffrement est détaillé dans l’exemple qui suit.

On va choisir deux nombres premiers et puis considérer le produit de ces deux nombres . Il nous faut aussi choisir un nombre entier pour la clé de chiffrement qui est premier avec comme par exemple . Pour coder la lettre « p » qui est la 16-ème lettre de l’alphabet, on calcule le reste de la division euclidienne de 16³ par 55 ce qui nous donne 26 : la lettre « p » peut donc être représentée par le nombre 26. On peut chiffrer de cette manière jusqu’à 55 symboles mais si l’on souhaite chiffrer uniquement les 26 lettres de l’alphabet alors on peut convenir de les énumérer deux fois de suite. La lettre « p » peut dans ce cas être représentée aussi par le reste de la division euclidienne de (16+26)³ par 55 ce qui nous donne 3. Il y a ainsi plusieurs nombres possibles qui peuvent représenter une lettre de l’alphabet. Si l’on continue en utilisant cette méthode on peut de même représenter la lettre « a » par le reste de la division euclidienne de 1³ par 55 ce qui nous donne 1 ou bien le reste de la division euclidienne (1+26)³ par 55 ce qui nous donne 48. Un chiffrement possible pour le mot « papa » peut finalement être :

26 – 1 – 3 – 48

Deviner le mot à partir de ce type de chiffrement est déjà beaucoup plus difficile car des nombres différents peuvent représenter la même lettre, il y a cette fois 26⁴ = 456 976 possibilités de base ! Pour déchiffrer ce code, il nous faut connaître la clé de déchiffrement c’est à dire les nombres et . La première lettre du mot à déchiffrer correspond au reste de la division euclidienne de 26²⁷ par 55 ce qui nous donne 16 puis la 16-ème lettre de l’alphabet « p ». Le reste de la division euclidienne de 1²⁷ par 55 est 1 donc on obtient ensuite la première lettre de l’alphabet « a ». De même le reste de la division euclidienne de 3²⁷ par 55 est 42 et comme 42-26=16 la lettre qui correspond à ce nombre est la 16-ème lettre de l’alphabet c’est à dire « p ». Enfin le reste de la division euclidienne de 48²⁷ par 55 est 27 et puisque 27-26=1 le mot recherché se termine par la première de l’alphabet « a ». La clé de déchiffrement nous a donc bien permis de retrouver le mot « papa ». Quels sont les fondements mathématiques du chiffrement RSA ? Plus de détails sur le chiffrement RSA sont donnés dans le fichier joint ci-dessous.