La méthode
Principe du cryptage RSA
Notons pour commencer que (dé)crypter un message quelconque (texte, image, musique...) revient à (dé)crypter un nombre $t$, via le code ASCII ou la numérisation, par exemple.
- On rend publique une "clé" [$n,c$], et on garde privé une clé $d$, où $n,c,d$ sont des entiers naturels.
- Le message envoyé n'est pas $t$, mais $(t^c) \% n$, qui n'a rien à voir avec le message d'origine $t$.
Le cryptage RSA utilise le fait que, pour des clé bien choisies :
$(t^c)^d \% n = t \% n$
Dit autrement, $(t^c)^d \equiv t [n].$ En d'autres termes, $(t^c)^d$ et $t$ ont même réduction modulo $n$.
Comment (dé)crypter
Le chiffrement
D'où la marche à suivre pour crypter un message :
- à l'aide d'un dictionnaire convenu (ASCII...), on traduit le message en un nombre $t$,
- puis, on élève ce nombre $t$ à la puissance $c$,
- enfin, on réduit le nombre $t^c$ obtenu modulo $n$ : c'est ce nombre $x$ que l'on envoie.
Le déchiffrement
Pour décrypter un message $x$ :
- on élève $x$ à la puissance $d$,
- on réduit le nombre obtenu modulo $n$ : on retrouve $t$,
- il reste à traduire le nombre en message, par le dictionnaire convenu (ASCII...).
Choix des clés
Le principe précédent ne marche pas toujours : il faut bien choisir ses clés...
Le $n$
On trouve deux nombres premiers $P_1$ et $P_2$, les plus grands possibles (se rapporter à ElGamal, pour savoir comment trouver ces nombres premiers). Alors :
$n=P_1 P_2$
Dans la pratique, $P_1$ et $P2$ devraient avoir plusieurs centaines de chiffres chacun, avec un certain nombre de chiffres de différence entre eux : le record de factorisation étant à ce jour de 307 chiffres, il faudrait que $n$ soit plus grand que cela.
$c$ et $d$
Les entiers $c$ et $d$ sont choisis de sorte que $cd-1$ soit un multiple de $(P_1-1)(P_2-1)$. En d'autres termes, il doit exister $k$ tel que
$cd + k (P_1-1)(P_2-1) = 1$
C'est une identité de Bézout, les coefficients recherchés peuvent se trouver grâce à l'algorithme de Bézout.
Plus précisément, on peut procéder comme suit. Supposons que bezout(a,b)=(r,u,v), où au+bv=r (et donc r=pgcd(a,b) et u,v sont les ''coefficients de Bézout de a,b. Il suffit alors :
- Tirer $c$ aléatoirement, et faire (r,u,v)=bezout(c,$(P_1-1)(P_2-1)$)
- Tant que $r \neq 1$, faire:
- $c = c+1$,
- (r,u,v)=bezout(c,$(P_1-1)(P_2-1)$)
La clé de chiffrement sera le dernier $c$ trouvé, et la clé de déchiffrement le dernier $u$ retourné, pourvu qu'ils soient tous deux positifs.
Il est préférable d'avoir un très petit $c$ (public), et un très grand $d$ (privé).
Travaux pratiques
Le sujet
- Écrire une fonction clef qui, à $P_1, P_2$ renvoie le couple $(n,c)$, et $d$.
- Écrire une fonction crypte, qui reçoit un message chiffré $t$, et la clé publique $n$,$c$ et qui renvoie le message crypté $t^c \%n$,
- Écrire une fonction décrypte qui, à un message crypté $x$, à $n$ et à la clé privée $d$ renvoie le message décrypté $x^d \%n$,
- Enfin, testez vos fonctions : trouvez deux grands nombres premiers, obtenez les clés privées et publiques, et cryptez des nombres (inférieurs à $n$, à cause du modulo).
Pour aller (un peu) plus loin
Si le sujet vous intéresse, vous pouvez le raffiner un peu :
- en découpant les nombres à crypter en paquets tels que le modulo $n$ n'entraîne pas de perte d'informations,
- en créant une fonction permettant de transformer du texte en un grand nombre, et inversement,
- en généralisant à d'autres supports (musique, image, film, etc.)
- en faisant une exponentiation efficace,
- en obtenant vous-même des grands nombres premiers originaux.