4.4.3 Génération de clé

On commence par choisir aléatoirement deux nombres premiers très grands (on recommande environ 100 chiffres décimaux pour chacun) que l'on nomme $p$ et $q$. On calcule ensuite $n=pq$. Le totient de $n$ est caculé selon $\phi (n)=(p-1)(q-1)$. Bien que les nombres impliqués dans ces calculs soient immenses, il existe des algorithmes très rapides permettant d'exécuter les calculs rapidement. On choisit ensuite aléatoirement un nombre compris entre $\max (p,q)+1$¹⁰ et $n-1$. Ce nombre doit être relativement premier avec $\phi (n)$. On nommera ce nombre $d$. On calcule ensuite l'inverse modulaire¹¹ de $d$ modulo $\phi (n)$, lequel on nommera $e$. Notons que ce calcul-ci (trouver l'inverse modulaire d'un nombre) est lui-aussi simple: on peut utiliser l'algorithme étendu d'Euclide, lequel implique de simples calculs matriciels sur lesquels nous n'élaborerons pas. Il faut cependant savoir que cet algorithme nécessite l'utilisation du totient de la base modulaire, $\phi (n)$ dans ce cas-ci.

Puisque $e$ et $d$ sont des inverses dans la base modulaire $\phi (n)$, on écrit

$$de\equiv 1\, \, \, (\bmod \phi (n))$$

Ceci est équivalent à

$$de=c\phi (n)+1$$

où $c$ est un entier quelconque. On obtient cette équation par la définition de l'arithmétique modulaire. En la substituant dans l'expression $\left(x^{e}\right)^{d}\, \, \, (\bmod n)$, on obtient¹²

$$\left(x^{e}\right)^{d} \equiv x^{c\phi (n)+1}\, \, \, (\bmod n)$$

$$\equiv \left(x^{\phi (n)}\right)^{c}x\, \, \, (\bmod n)$$

$$\equiv 1^{c}x\, \, \, (\bmod n)$$

$$\equiv x\, \, \, (\bmod n)$$

La relation $\left(x^{e}\right)^{d}\equiv x\, \, \, (\bmod n)$ est étrangement similaire à la propriété $d_{k}(e_{k}(x))=x$, décrite à la section 1. De fait, la fonction de chiffrement de RSA est justement $e_{k}(x)=x^{e}\bmod n$ et le déchiffrement est $d_{k}(x)=x^{d}\bmod n$.

La clé est maintenant générée. $n$ et $e$ seront publiés dans un répertoire et constitueront la clé publique. $e$ restera secrète et constituera la clé privée.