1. Mise en oeuvre sur SageMath : un exemple simple
Choisir deux petits nombres premiers distincts et affecter ces valeurs respectivement à $p$ et $q$ dans Sage.
{{{id=16| p = 23 q = 29 /// }}}Vérifier à l'aide de Sage que les nombres $p$ et $q$ sont bien premiers.
{{{id=18| p.is_prime() /// }}} {{{id=151| q.is_prime() /// }}}Remarque : l'aide de la commande is_prime indique que, par défaut, cette fonction exécute un test déterministe de primalité. En l'appelant par $\mathrm{is.prime(Proof}=\mathrm{False)}$, c'est un test de pseudoprimalité qui est effectué. On peut aussi directement demander un test de pseudoprimalité par la commande is_ pseudoprime.
Calculer $pq$ et l'affecter à $n$.
{{{id=19| n = p*q /// }}} {{{id=103| n /// }}}Dans Sage, la fonction qui calcule l'indicatrice d'Euler $\varphi$ est euler_phi.
{{{id=20| euler_phi(n) /// }}}On affecte ce résultat à une nouvelle variable, qu'on choisit de nommer phi.
{{{id=108| phi = euler_phi(n) /// }}}Trouver un entier $e\in\mathbb{Z}$ tel que $\mathrm{pgcd}(e,\varphi(n))=1$.
Il s'agit de prendre un nombre n'ayant aucun facteur premier commun avec $\varphi(n)$. Pour cela, on peut s'aider par exemple de la factorisation de $\varphi$.
{{{id=21| factor(phi) /// }}}On choisit par exemple de prendre $e=5$. En pratique, pour une véritable implémentation de RSA, il vaut mieux éviter de choisir $e$ trop petit.
{{{id=23| e = 13 /// }}}Trouver un entier $d \in \mathbb{N}$ tel que $de \equiv 1 \bmod \varphi(n)$.
Comme $e$ et $\varphi(n)$ sont premiers entre eux, $e$ est inversible modulo $\varphi(n)$, autrement dit il existe un entier $d$ comme voulu. Pour trouver $d$ en pratique, on écrit l'algorithme d'Euclide étendu : il fournit deux entiers $d$ et $s$ tels que $de + s\varphi(n) = 1$. Modulo $n$, on aura donc $de \equiv 1 \bmod \varphi(n)$. Si jamais $d$ est négatif, on sait qu'on peut le remplacer par un multiple approprié de $\varphi(n)$ de manière à avoir un entier naturel.
Dans Sage, le résultat de l'algorithme d'Euclide étendu entre deux entiers $a$ et $b$ s'obtient par la commande $xgcd(a,b)$. Consulter l'aide de Sage pour comprendre à quoi correspondent les trois valeurs retournées par cette fonction.
{{{id=24| xgcd(e,phi) /// }}}On peut donc prendre $d = 237$. Vérifions-le.
{{{id=25| d = 237 (d*e).mod(phi) /// }}}Transmettre votre clé publique $(n,e)$ à votre voisin.
{{{id=26| print "Ma cle publique est", (n,e) /// Ma cle publique est (667, 13) }}}Pour information, voici votre clé privée.
{{{id=115| print "Ma cle privee est", (p,q,d) /// Ma cle privee est (23, 29, 237) }}}Mon voisin souhaite m'envoyer un message confidentiel. Il le crypte à l'aide de ma clé publique $(n,e)$ (et non pas avec sa propre clé !). Je reçois le message $c$ suivant.
{{{id=27| c = 158 c /// }}}Je déchiffre ce message à l'aide de ma clé privée.
{{{id=28| (c^d).mod(n) /// }}}Le message qu'a voulu m'envoyer mon voisin est donc 444, dans sa forme déchiffrée.
2. Mise en oeuvre sur SageMath : un exemple grandeur nature
Obtenir de grands nombres premiers de manière aléatoire.
D'après le théorème des nombres premiers, la probabilité pour qu'un entier naturel d'au plus $k$ décimales et choisi au hasard soit premier est de l'ordre de $1/\ln(10^k)$ c'est-à-dire environ $1/(2,3 k)$. Pour fabriquer au hasard de grands nombres premiers, on peut donc procéder ainsi : on tire au hasard un entier et on teste s'il est premier ou non. S'il ne l'est pas, on en essaye un autre, etc. jusqu'à en trouver un. L'heuristique précédente assure que cette méthode va aboutir après un nombre suffisant et raisonnable de lancers avec une probabilité élevée. Pour accélérer la recherche, on a intérêt à utiliser un test de pseudoprimalité (is_pseudoprime), puis lorsqu'un candidat a réussi ce test, à confirmer sa primalité par un test déterministe (is_prime).
Estimons le nombre d'entiers à tester. Notons $q=1-1/\ln(10^k)$ la probabilité qu'un entier naturel d'au plus $k$ décimales et choisi au hasard ne soit pas premier. La probabilité d'avoir $n$ échecs successifs est égale à $q^n$. Elle est inférieure à $5\%$ dès lors que $n\geq \frac{\log (0,05)}{\log q}$.
{{{id=124| k = 310 log(0.05)/log(1-1/(ln(10^k))).n() /// }}}Dans Sage, la commande .n() permet d'obtenir une valeur approchée (elle signifie numerical approximation).
Par exemple pour $k=310$, nous avons 95% de chance de trouver un nombre premier en testant $2136$ nombres entiers. Pour obtenir un premier à exactement $310$ décimales, le calcul est similaire et l'estimation assez proche.
Trouvons de cette manière un nombre premier à au moins 310 chiffres. Dans le programme ci-dessous, la commande # permet d'introduire des commentaires, qui ne sont pas interprétés par Sage.
{{{id=45| p = ZZ.random_element(10^312) # On choisit au hasard un nombre entier inferieur a 10^312 N = 1 # On initialise le compteur pour le nombre de tests while (len(p.digits()) < 310) or (not p.is_pseudoprime()): p = ZZ.random_element(10^310) N = N+1 /// }}}La boucle while fait recommencer le test dès lors que le nombre a moins de 310 décimales ou qu'il n'est pas premier.
La valeur finale de $N$ retourne le nombre de tests effectués.
{{{id=122| N /// }}}Comptons le nombre de décimales de $p$.
{{{id=89| len(p.digits()) /// }}}On peut aussi afficher le nombre $p$.
{{{id=121| p /// }}}Il reste à confirmer sa primalité par un test déterministe. La commande % time permet d'afficher le temps utilisé pour exécuter une commande.
{{{id=132| %time p.is_prime() /// CPU time: 21.61 s, Wall time: 21.62 s }}}Même chose avec un autre nombre premier $q$.
{{{id=51| q = ZZ.random_element(10^312) while (len(q.digits()) < 310) or (not q.is_pseudoprime()): q = ZZ.random_element(10^312) /// }}} {{{id=53| len(q.digits()),q /// }}} {{{id=72| %time q.is_prime() /// CPU time: 21.94 s, Wall time: 21.94 s }}}On termine en calculant notre clé publique $n$ et par vérifier qu'elle a au moins 617 décimales.
{{{id=52| n = p*q n /// }}} {{{id=91| len(n.digits()) /// }}}Variantes. On aurait aussi pu utiliser les commandes next_prime (qui retourne le nombre premier suivant immédiatemment un entier donné) ou la commande toute faite random_prime (qui retourne un nombre premier au hasard d'une taille donnée).
Calcul de $\varphi(n)$.
{{{id=54| # euler_phi(n) # Trop long ! /// }}}Le calcul de $\varphi(n)$ par la commande est trop long. C'est normal car Sage va chercher à le factoriser $n$ afin de calculer $\varphi(n)$. Comme $n$ a plus de 610 décimales, c'est une tâche impossible en un temps raisonnable. La sécurité de RSA réside ici.
Pour calculer $\varphi(n)$, on se rappelle que comme $n=pq$ avec $p$ et $q$ premiers distincts, on a $\varphi(n)=\varphi(p)\varphi(q) = (p-1)(q-1)$. On demande à Sage de calculer directement ce nombre, qui suppose de connaître les facteurs $p$ et $q$ de $n$ (clé privée).
{{{id=55| phi = (p-1)*(q-1); phi /// }}}Choix de e
On doit trouver $e$ entier naturel tel que son pgcd avec $\varphi(n)$ est égal à $1$. Là encore, il n'est pas question de factoriser $\varphi(n)$, qui est très grand...
La majorité des entiers plus petit que $\varphi(n)$ n'ont aucun facteur commun avec lui. On procède donc en tirant des entiers au hasard, jusqu'à en trouver un qui réalise la condition souhaitée.
{{{id=56| e = ZZ.random_element(phi) while gcd(e, phi) != 1: e = ZZ.random_element(phi) /// }}} {{{id=57| e /// }}}Vérification :
{{{id=136| e.gcd(phi) /// }}}Choix de $d$.
On cherche un entier $d \in \mathbb{N}$ tel que $de \equiv 1 \bmod \varphi(n)$. À nouveau, c'est l'algorithme d'Euclide étendu qui permet de le faire.
{{{id=139| e.xgcd(phi) /// }}}On extrait de ce résultat la deuxième composante de la liste. Remarque : en Python (et donc en Sage), la numérotation des listes commence à $0$. On demande donc ici la $1$ère composante.
{{{id=58| d = e.xgcd(phi)[1] d /// }}}Clés publique et privée
Notre clé publique est donc :
{{{id=59| (n,e) /// }}}et notre clé privée est :
{{{id=61| (p,q,d) /// }}}Chiffrage et déchiffrage d'un message
On choisir un message numérique $m$ au hasard, avec $m<n$.
{{{id=66| m = ZZ.random_element(n) m /// }}}On vérifie que $m$ est bien strictement inférieur à $n$.
{{{id=67| m < n /// }}}Chiffrons le message avec notre clé privée. Il s'agit de calculer $m^e \bmod n$.
{{{id=62| # (m^e).mod(n) # Trop long ! /// }}}La commande ci-dessus prend beaucoup trop de temps : elle fait calculer $m^e$, puis le réduire modulo $n$. Ce n'est pas une manière adaptée de calculer des puissances modulo $n$. Il vaut mieux utiliser l'exponentiation rapide (square and multiply), qui s'obtient dans Sage par la commande power_mod.
{{{id=63| %time c = power_mod(m,e,n) c /// CPU time: 0.06 s, Wall time: 0.07 s }}}On déchiffre ensuite le message à l'aide de notre clé privée. Pour cela, on évalue $c^d \bmod n$, en utilisant encore l'exponentiation rapide.
{{{id=64| power_mod(c,d,n) /// }}}Vérifions que le message initial, et le message chiffré puis déchiffré coïncident.
{{{id=65| power_mod(c,d,n) == m /// }}}