Système RSA

Nos amis Ronald Rivest, Adi Shamir et Leonard Adleman mirent au point en 1977 un système de codage alors qu'ils essayaient au départ de montrer que ce qu'ils allaient développer étaient une impossibilité logique : aah, la beauté de la recherche...Et savez-vous quel est la base du système ? Je vous le donne en mille : le petit théorème de Fermat ! Mais replaçons dans son contexte les résultats de R, S et A. Jusqu'il y a une trentaine d'années, la cryptographie était l'apanage des militaires et des diplomates. Depuis, les banquiers, les mega business men et women, les consommateurs internautes, les barons de la drogue et j'en passe ont de plus en plus recours aux messages codés. Oui, et alors ? Le problème, c'est que jusqu'ici, l'envoyeur et le destinataire partageait une même clé secrète qu'il fallait faire voyager à l'insu de tous : les états et l'armée ont la valise diplomatique, mais les autres ?

C'est ici que Whitfield Diffie et Martin Hellman apparaissent avec leur idée de principe qu'on peut résumer ainsi : votre amie Josette veut recevoir de vous une lettre d'amour mais elle a peur que le facteur l'intercepte et la lise. Elle fabrique donc dans son petit atelier une clé et un cadenas. Elle vous envoie le cadenas, ouvert mais sans la clé, par la poste, donc à la merci du facteur : le cadenas est appelé clé publique. Vous recevez le cadenas et l'utilisez pour fermer une boîte contenant votre lettre : le facteur ne peut pas l'ouvrir car il n'a pas la clé. Josette reçoit donc la boîte fermée : elle utilise sa clé, qu'elle seule possède, pour ouvrir la boîte et se pâmer devant vos élans epistolaires.

En termes plus mathématiques, cela donne : je fabrique une fonction $\pi$ définie sur $\mathbb{N}$ qui possède une réciproque $\sigma$. On suppose qu'on peut fabriquer de telles fonctions mais que si l'on ne connaît que $\pi$, il est (quasiment) impossible de retrouver $\sigma$. La fonction $_pi$ est donc la clé publique : vous envoyez $\pi$(message) à Josette. Celle-ci calcule $\sigma\bigl(\pi($message$)\bigr)=$ message. Josette est la seule à pouvoir décoder car elle seule connaît $\sigma$.

Tout ceci était très beau en théorie, mais Diffie et Hellman n'arrivèrent pas à proposer de telles fonctions. Mais voici qu'arrivent Ronald, Adi et Leonard...

Je vais vous présenter la méthode en effectuant les calculs grâce à MuPAD. Il ne vous restera plus qu'à prouver mathématiquement que tout ceci fonctionne de manière cohérente...

Nous aurons tout d'abord besoin d'un programme num qui transforme un message écrit en majuscule en un nombre entier et un programme alph qui effectuera la démarche inverse. Je vous les livre sans explications car leur fabrication ne nous intéresse pas arithmétiquement parlant⁷.

$»$ num:=proc(m) local l,L;

$»$ begin l:=numlib::toAscii(m): L:="":

$»$ for i from 1 to nops(l) do L:=L.expr2text(l[i]) end_for:

$»$ text2expr(L); end_proc:

$»$ num("TU ES LE MEILLEUR");

8485326983327669327769737676698582

$»$ alph:=proc(n) local l,L;

$»$ begin L:=[]: l:=expr2text(n):

$»$ for i from 0 to length(l)-1 step 2 do L:=L.[text2expr(substring(l,i,2))] end_for:

$»$ numlib::fromAscii(L); end_proc:

$»$ alph(67697665327065738432767978718469778083328185693274693276693283657383327779\
7832806585868269328069847384328469726983837378);

"CELA FAIT LONGTEMPS QUE JE LE SAIS MON PAUVRE PETIT TEHESSIN"

Ceci étant dit, je vais vous montrer comment quelqu'un peut m'envoyer un message crypté en utilisant le protocole RSA, que personne ne peut comprendre sauf moi, puis comment je vais décrypter ce message.

Avant de m'envoyer un message, on doit connaître ma clé publique, connue de tous et constituée d'un couple de nombres $(n,e)$.

Et avant de connaître cette clé, il faut que je la fabrique - secrètement - de la manière suivante :

Je suis maintenant prêt à recevoir des messages cryptés selon le protocole RSA et vous êtes prêt(e) à m'en envoyer car j'ai rendu publique ma clé $(e,n)$.

Oui, bon, mais je devine que mille questions se bousculent déjà dans vos têtes : comment ça marche? Pourquoi ça marche ? Comment casser le système ? etc.

Pour vous aider, voici quelques questions intermédiaires.

1. Que vaut $\varphi (pq)$ si $p$ et $q$ sont premiers ?

2. Où intervient le théorème d'Euler ? Pourquoi a-t-on le droit de l'utiliser ? Vous pourrez montrez que si $a^u\equiv a[p]$ et $a^u\equiv a[q]$, alors $a^u\equiv a[pq]$ en étudiant $a^u-a$.

3. À quelle opération mathématique correspond le « cassage » naturel du système ? Est-ce un problème facile ?

4. Supposons qu'un même texte en clair $t$ est envoyé à deux personnes ayant choisi le même nombre $n$ et des exposants $e_1$ et $e_2$ premiers entre eux : on trouve facilement $u$ et $v$ tels que $ue_1+ve_2=1$. Alors les deux messages chiffrés sont $c_1\equiv t^{e_1}[n]$ et $c_2\equiv t^{e_2}[n]$. Montrez que, connaissant $c_1$, $c_2$, $e_1$, $e_2$ et $n$, on peut en déduire $t$, ce qui est fort gênant...