Arithmétique modulaire, RSA et clefs privées

27 avril 2020 — Cryptographie, Python

L’arithmétique modulaire correspond aux calculs effectués « à un multiple de n près ».

Par exemple, si on calcule modulo $12$, on a $7 + 9 = 4$ et $3 \times 8 = 0$.

Ce cas particulier correspond à des calculs sur des nombres d’heures, le résultat s’affichant sur un cadran d’horloge ne permettant de connaître l’heure qu’à un multiple de $12$ heures près.

Pour ramener des calculs d’un ensemble plus grand (ici les entiers relatifs $\Z$) à un ensemble plus petit (ici $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$), les mathématiciens utilisent la notion d’ensemble quotient.

Nous utiliserons ici cette approche, sur le cas particulier des ensembles $\Z/n\Z$ (définis pour tout entier $n > 0$), qui sont le cadre naturel de l’arithmétique modulaire.

Ces ensembles, qui contiennent $n$ éléments, seront très utiles en informatique. Leurs éléments peuvent tous être représentés avec un espace mémoire fini (contrairement à $\Z$) et les calculs y sont exacts (contrairement aux nombres de $\R$, par exemple).

Nous verrons en particulier comment ils sont utilisés en cryptographie.

L’ensemble $\Z/n\Z$

Nous avons vu l’ensemble $\Z$ des entiers relatifs (positifs, négatifs ou nuls).

Pour $n \isin \N, n > 0$, l’ensemble $n\Z$ est défini comme l’ensemble des multiples de $n$ (la notation signifie littéralement « $n$ fois n’importe quel nombre de $\Z$ »).

Ainsi, $2\Z$ est l’ensemble des nombres pairs, $3\Z$ des nombres divisibles par $3$ (e.g. $-333, 0, 21$), etc.

L’ensemble $\Z/n\Z$ est un ensemble d’ensembles, dont les éléments sont les classes d’équivalence modulo $n$.

Une classe d’équivalence modulo $n$, c’est un ensemble de nombres de $\Z$ qui ont tous le même reste quand on considère leur division euclidienne par $n$. En particulier, tous les nombres qui sont dans la même classe d’équivalence diffèrent d’un multiple de $n$.

Par exemple :

• $\Z/2\Z$ correspond à deux sous-ensembles, les nombres pairs et les nombres impairs
• $\Z/3\Z$ correspond à trois sous-ensembles, qui sont les nombres de la forme ${3 \times k}$, ceux de la forme ${3 \times k + 1}$ et ceux de la forme ${3 \times k + 2}$.
• $\Z/12\Z$ correspond à regrouper les nombres d’heures comptés à partir d’un temps $0$, en fonction de ce qu’il donneraient, si on les affichait sur une horloge à cadran (et en ignorant les changements d’heure…)
• etc.

$\Z/n\Z$ contient $n$ éléments, qui correspondent aux ensembles de nombres dont les restes modulo $n$ sont respectivement $0, 1, ..., n-1$.

Par abus de langage, on notera $0, 1, ..., n-1$ les éléments de $\Z/n\Z$. Ils correspondent aux ensembles $n\Z$, ${\{1 + k, k \isin n\Z\}}$, …, ${\{n-1 + k, k \isin n\Z\}}$.

Addition sur $\Z/n\Z$

L’addition est compatible avec le calcul modulo $n$.

Par exemple, d’une addition modulo $3$ ne change pas si on remplace l’un des nombres par un autre qui lui est égal modulo $3$ :

$5 + 20 = 2 + 2 = 1$ modulo $3$

Cette observation nous permet de définir une table d’addition sur $\Z/3\Z$ :

On définit une addition sur $\Z/n\Z$, en considérant le résultat modulo n de l’addition sur $\Z$.

💡 Un ensemble muni d’une opération notée $+$ avec certaines propriétés similaires à l’addition sur $\Z$ s’appelle un groupe.

Multiplication sur $\Z/n\Z$

De la même façon, l’égalité suivante où $a, b, i, j$ sont des entiers quelconques, nous montre que la multiplication de $\Z$ est compatible avec le calcul modulo $n$ :

$(a + i \times n) \times (b + j \times n) = a \times b + (a \times j + i \times b + i \times j \times n) \times n$

Par exemple, dans $\Z/8\Z$ on aura ${6 \times 7 = 2}$ (conséquence de ${6 \times 7 = 42 = 2}$ modulo $8$).

On obtient une multiplication sur $\Z/n\Z$, en considérant le résultat modulo n de la multiplication sur $\Z$.

On obtient par exemple la table de multiplication suivante sur $\Z/5\Z$ :

💡 Un ensemble muni des opérations $+$ et $\times$, avec des propriétés similaires à l’addition et la multiplication sur $\Z$ s’appelle un anneau.

Question : déterminer la table d’addition et de multiplication sur $\Z/2\Z$, à quelles opérations booléennes correspondent-elles ?

Éléments inversibles de $\Z/n\Z$

Observons la table de multiplication de $\Z/6\Z$ :

On remarque que l’on a les égalités suivantes :

• $5 \times 5 = 1$
• $2 \times 3 = 0$

La première égalité nous donne envie de dire que, pour la multiplication, $5$ est inversible et son inverse est $5^{-1} = 5$.

En d’autres termes, une équation d’inconnue $x$ de la forme $5 \times x = 3$ se résout en $x = 5 \times 3 = 3$.

La seconde égalité nous montre en revanche que $2$ et $3$ ne peuvent pas être inversibles, car ils sont « diviseurs de zéro ». Si $2$ était inversible on pourrait réécrire l’égalité $2 \times 3 = 0$ en $3 = 2^{-1} \times 0 = 0$.

On vérifie sur la table de multiplication que les éléments inversibles de $\Z/6\Z$ sont $1$ et $5$.

Retour sur l’identité de Bézout

L’algorithme d’Euclide permet d’obtenir l’identité suivante (je vous renvoie à l’article d’introduction à l’arithmétique, je remplace ici volontairement $b$ par $n$, ce qui ne change pas le résultat) :

Il existe deux nombres ${u, v \isin \Z}$ tels que : ${u \times a + v \times n = \gcd(a, n)}$

Que signifie pour un entier $a$, l’existence d’un inverse $a^{-1}$ dans $\Z/n\Z$ ?

Cela traduit l’égalité ${a \times a^{-1} = 1}$ modulo $n$, ce qui signifie encore qu’il existe un entier ${k \isin \Z}$ tel que : ${a \times a^{-1} - k \times n = 1}$.

En particulier, si $\gcd(a, n) = 1$, on peut construire des entiers ${a^{-1} = u}$ et ${k = -v}$ qui satisfont exactement cette égalité.

L’identité de Bézout nous indique donc que $a$ est inversible modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux.

C’est d’ailleurs bien ce que l’on constatait sur le cas $n = 6$ au-dessus.

Question : Montrer que si l’on considère un nombre $p$ premier, tous les éléments non nuls de $\Z/p\Z$ sont inversibles (pour la multiplication).

Fonction indicatrice d’Euler

On définit la fonction $\phi(n)$ pour un entier $n \gt 0$ appelée fonction indicatrice d’Euler, qui donne le nombre d’éléments inversibles pour la multiplication dans $\Z/n\Z$.

D’après ce qui précède, il s’agit du compte de nombres $k, 0 \lt k \leq n$ qui sont premiers avec $n$.

💻 On peut calculer les premières valeurs de $\phi(n)$ avec le script Python ci-dessous :

from math import gcd
for n in range(1, 100):
    print("phi({n}) = {phi}".format(
        n=n,
        phi=sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)
    ))
phi(1) = 1
phi(2) = 1
phi(3) = 2
phi(4) = 2
phi(5) = 4
phi(6) = 2
phi(7) = 6
...
phi(95) = 72
phi(96) = 32
phi(97) = 96
phi(98) = 42
phi(99) = 60

Calcul de $\phi(n)$

Dans certains cas, on peut calculer simplement la fonction indicatrice d’Euler.

Par exemple, si $p$ est un nombre premier, alors $\phi(p) = p - 1$ car tous les nombres inférieurs à $p$ sont premiers avec $p$.

Dans le cas $n = p \times q$ où $p$ et $q$ sont des nombres premiers distincts, les nombres qui sont premiers avec $n$ sont ceux qui ne sont multiples ni de $p$ ni de $q$.

• Les multiples de $p$ inférieurs à $n$ étant les nombres $p, p \times 2, ..., p \times q$, il y en a $q$.
• De même, il y a $p$ multiples de $q$.
• Le seul multiple commun parmi ceux-ci est $p \times q$, qu’il ne faut donc compter qu’une fois.

On en déduit donc ${\phi(p \times q) = p \times q - p - q + 1 = (p-1) \times (q-1)}$.

Théorème d’Euler

Le théorème d’Euler, qui date de 1761, peut se formuler ainsi :

Si $a$ est un entier premier avec $n$, alors ${a^{\phi(n)} = 1}$ modulo $n$.

On vérifiera par exemple que ${4^{\phi(5)} = 4^4 = 16 = 1}$ modulo $5$.

On en déduit également, comme $19$ est premier, que ${19^{\phi(97)} = 19^{96} = 1}$ modulo $97$.

Ce dernier résultat montre à quel point le théorème d’Euler peut simplifier certains calculs ($19^{96}$ est un nombre plus grand que le nombre d’atomes d’hydrogène dans le soleil…).

Une autre façon équivalente de formuler ce théorème, dans le langage de $\Z/n\Z$, est la suivante :

Si $a \isin \Z/n\Z$ est inversible alors ${a^{\phi(n)} = 1}$.

Nous allons donner l’idée de la preuve dans le cas de $\Z/7\Z$, dont voici la table de multiplication :

Les éléments inversibles, au nombre de $6$, sont $1, 2, 3, 4, 5, 6$ (tous premiers avec $7$, puisque $7$ est premier).

Considérons le produit de ces éléments $P = 1 \times 2 \times 3 \times 4 \times 5 \times 6$.

En multipliant $P$ par $3^{\phi(7)}$ on obtient :

On remarque en particulier que :

• le produit $P$ étant par définition constitué de $\phi(7) = 6$ éléments, on peut « répartir » les facteurs $3$ devant chaque élément du produit
• chaque nouveau facteur obtenu est un autre nombre, toujours inversible (car produit de deux nombres inversibles)
• les nombres inversibles obtenus sont deux-à-deux distincts, on a donc uniquement changé l’ordre des facteurs de $P$

En simplifiant par $P$ (lui-même inversible), on obtient bien que $3^{\phi(7)}$ = $1$.

Question : En utilisant le théorème d’Euler et le calcul de $\phi(p)$ où $p$ est un nombre premier, montrer le petit théorème de Fermat ci-dessous (historiquement, ce résultat fut découvert précédemment) :

Pour $p$ premier et $a$ un entier quelconque, on a ${a^p = a}$ modulo $p$.

Application à la cryptographie

Nous avons vu précédemment comment le théorème d’Euler pouvait permettre de simplifier considérablement certains calculs comme $19^{96}$ modulo $97$.

Ce résultat est au coeur d’un algorithme appelé RSA, qui permet de générer des clefs cryptographiques (clef privée et clef publique, on parle de cryptographie asymétrique) et de les utiliser pour chiffrer et déchiffrer des messages.

Voici comment fonctionnent les différentes parties de cet algorithme.

Génération des clefs

1. Choisir deux nombres premiers $p$ et $q$ et noter $n = p \times q$.
   On a alors $\phi(n) = (p-1) \times (q-1)$ (voir le calcul de $\phi(p \times q)$ plus haut).

2. Choisir un nombre $e$ premier avec $\phi(n)$.

3. Calculer un inverse $d$ de $e$ modulo $\phi(n)$ : ${d \times e = 1 + k \times \phi(n)}$, où ${k \isin \Z}$

Les clefs générées sont alors :

• Une clef publique : $(n, e)$
• Une clef privée : $(n, d)$

Nous discuterons plus loin de l’implémentation pratique des différentes étapes.

Chiffrement d’un message

Pour être chiffré, un message doit être encodé sous la forme d’un nombre ${m < n}$.

Le message chiffré est obtenu par le calcul modulo $n$ suivant :

${c = m^e \mod n}$

Une autre façon (équivalente) de formuler les choses est d’identifier un message en clair à un élément ${m \isin \Z/n\Z}$ et calculer le message chiffré comme l’élément $c = m^e \isin \Z/n\Z$.

Déchiffrement d’un message chiffré

À partir du message chiffré $c$, par construction un nombre entre $0$ et ${n - 1}$ (inclus), on obtient le message déchiffré par la formule suivante :

${m = c^d \mod n}$

Preuve du fonctionnement

Il s’agit de vérifier que la formule de déchiffrement de $c$ redonne bien le message $m$ d’origine.

On a par construction ${d \times e = 1 + k \times \phi(n)}$.

On développe alors la formule de déchiffrement :

On obtient deux cas. Le premier permet de conclure rapidement. Le second nécessite des calculs un peu plus compliqués…

1. Si $\gcd(m, n) = 1$, le théorème d’Euler indique que $m^{\phi(n)} = 1 \mod n$ et le calcul donne ${c^d = m \mod n = m}$ : on retrouve bien $m$.
2. Sinon, c’est que $p$ ou $q$ divise $m$. Les deux ne peuvent être diviseurs simultanément puisque ${m < n = p \times q}$), on peut supposer par exemple que $p$ divise $m$.

On peut alors écrire ${m = p^{\alpha} \times M}$, où $\alpha > 0$ et $M$ n’est divisible ni par $p$ ni par $q$ et est donc premier avec $n$.

On obtient :

(on a utilisé que $M$ est premier avec $n$, ce qui ramène au cas 1)

On a par ailleurs :

et aussi :

La dernière simplification vient du petit théorème de Fermat qui permet d’écrire ${a^{q-1} = 1 \mod q}$, lorsque $q$ est premier et $a$ n’est pas divisible par $q$.

Ces deux derniers calculs nous montrent que $p^{\alpha \times e \times d} - p^{\alpha}$ est divisible par $p$ et par $q$, donc également par $n = p \times q$, ce qui nous permet de reprendre le calcul initial :

🙂

💻 Implémentation de RSA en Python

Nous avons décrit la recette de l’algorithme RSA, je vous en propose maintenant une implémentation basique en Python, afin de vérifier que tout cela fonctionne bien !

⚠️ Cette implémentation naïve ne doit évidemment pas être utilisée en production, elle n’est ni optimale ni robuste du point de vue de la sécurité. Son but est purement didactique.

Pour démarrer, cliquez sur le bouton Run ▶️, puis commencez par générer une paire de clefs.

Voici par exemple ce que j’ai obtenu :

Création des clefs

DEBUG: p=257205938468792623586345060713, q=564292122274801049105971923463,
       n=145139284880236882068996179284591347066612215282786124209119,
       e=5, d=29027856976047376413799235856753969801173724322018761444989
Clef privée :
eyJtb2R...3MzcyNDMyMjAxODc2MTQ0NDk4OX0=
Clef publique :
eyJtb2R..CAiZXhwb25lbnQiOiA1fQ==

Chiffrement

Entrez la clef publique :
eyJtb2R..CAiZXhwb25lbnQiOiA1fQ==
Message à chiffrer :
Lorem ipsum
Message chiffré :
12906681535323653913467296579360861757391479192915128204736

Déchiffrement

Entrez la clef privée :
eyJtb2R...3MzcyNDMyMjAxODc2MTQ0NDk4OX0=
Message à déchiffrer :
12906681535323653913467296579360861757391479192915128204736
Message déchiffré :
Lorem ipsum

Quelques remarques

• Les clefs — couples (module, exposant) — sont sérialisées en utilisant base64.
  De façon générale, différentes implémentations de RSA peuvent utiliser différents formats pour représenter les clefs (nous y reviendrons).
• L’étape 2 de l’algorithme de génération des clefs demande de générer $e$ premier avec $\phi(n)$. Nous avons ici utilisé une méthode essai-erreur pour trouver une valeur de $e$ satisfaisante :

  e = 2
  while gcd(e, phi) != 1:
      e += 1

• Dans cette implémentation naïve, nous avons simplement codé en dur une liste de nombres premiers. Le problème de la génération de grands nombres premiers est compliqué.
  Beaucoup d’algorithmes reposent sur des méthodes probabilistes (le nombre généré pourrait ne pas être premier, mais la probabilité que ce soit le cas est négligeable, par exemple inférieure à $10^{-15}$).
• Le calcul de l’inverse modulaire est disponible nativement dans Python à partir de la version 3.8 :

  d = pow(e, -1, phi)

  Si vous utilisez une version antérieure, vous pouvez utiliser l’implémentation de SymPy ou implémenter votre propre version (par exemple avec l’algorithme d’Euclide étendu, détaillé ici).

RSA dans la vraie vie

Navigation en HTTPS

J’ai obtenu les informations ci-dessous avec Firefox en cliquant sur le petit symbole 🔒 à gauche de la barre d’adresse, depuis https://www.github.com.

On peut y lire notamment que :

• le certificat utilise RSA avec une clef sur 2048 bits : il s’agit de la taille du module $n$ généré.
• l’exposant $e$ est $65537$. Pour certaines raisons, ce nombre est très souvent utilisé comme exposant public.
• le contenu du module est également affiché (en hexadécimal)

Utilisation dans le cadre de TLS

En pratique, RSA est un algorithme assez lourd en terme de calculs et qui ne permet, comme nous l’avons vu, que de chiffrer des messages $m <n$.

Dans le cadre de HTTPS et du protocole sous-jacent TLS, RSA peut être utilisé pour :

• authentifier le serveur à l’aide de sa clef publique (comme celle ci-dessus)
• échanger une clef de session, qui servira par exemple à l’établissement d’un chiffrement symétrique à l’aide d’un algorithme comme AES

D’autres algorithmes basés notamment sur les courbes elliptiques, objets mathématiques plus sophistiqués, constituent une alternative de plus en plus fréquente à RSA, en particulier pour l’échange de clef.

Décorticage de clefs avec OpenSSL

OpenSSL est une bibliothèque libre et ouverte de fonctionnalités cryptographiques, écrite en C. Elle est de fait très utilisée, par exemple par des serveurs web ou par OpenSSH.

Nous allons l’utiliser ici pour générer des vraies clefs, telles qu’elles sont utilisées en pratique.

La commande ci-dessous permet de générer une paire de clefs RSA 2048 bits, et de l’enregistrer dans un fichier dummy.pem.

(Cette clef n’est évidemment pas utilisée en production. Le contenu est tronqué pour alléger la présentation.)

$ openssl genrsa -out dummy.pem 2048
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAxZTA6Tlfs+/le2obemsioULR3ipwupIXvnATYGpjpbdLsKEn
HJnoOl/IoeQHzDcS10/NKHWWklcK4WfxnRX62XyyWYmnnfJQPLepGPujbPYsxLAu
l4ON9INOulHXHKrorqyQNvzeCm46gQAeEd2+IH2HtFHEM2Avtw0qYxQc5y0rEeTQ
...
v+gagQKBgFHsYq9M8E7Po67DNfK9f0qfxev1PTV584vVWs4O0vr2p/+RorEed3Xa
W02mZnqg0wS/4wuKz43UUU9x8GEZuNIW0/5XX/YrvEV90OktQ9lbanNLWJaqSyoC
6PLdT49uniyhkiySmVt9EgJSIaYy32F3HCYaNWkF9pyZ+SNXlB23
-----END RSA PRIVATE KEY-----

La commande suivante permet d’examiner un tel fichier pour voir ce qu’il contient :

$ openssl rsa -text -noout < dummy.pem
Private-Key: (2048 bit)
modulus:
    00:c5:94:c0:e9:39:5f:b3:ef:e5:7b:6a:1b:7a:6b:
    22:a1:42:d1:de:2a:70:ba:92:17:be:70:13:60:6a:
    ...
    08:32:9a:2c:57:cc:3c:1b:08:1f:1f:e4:38:de:a4:
    40:43:98:39:56:70:d5:d5:03:71:1f:3a:06:dd:d0:
    da:6f
publicExponent: 65537 (0x10001)
privateExponent:
    4d:9d:b6:fe:a7:84:39:fa:66:8a:c9:cf:0b:93:24:
    ...
    38:1c:d4:5c:1e:67:37:08:6a:81:cf:56:ad:8f:b5:
    11
prime1:
    00:fe:94:9b:60:59:99:11:4c:8d:48:f4:a4:39:af:
    ...
    b9:f0:d6:3b:d9:f4:4d:d3:07
prime2:
    00:c6:ae:c8:d8:32:17:25:bc:89:86:cc:b2:38:e7:
    ...
    6f:ba:ac:12:be:7a:89:5b:59
exponent1:
    00:ae:b5:ed:ab:c1:d1:7a:3d:be:f8:42:6c:31:ea:
    ...
    7c:dc:fb:29:37:fa:a1:2e:21
exponent2:
    0a:d1:19:3e:2b:fb:f6:a1:fd:1a:c9:aa:2a:4e:f6:
    ...
    3f:61:7e:e3:bf:e8:1a:81
coefficient:
    51:ec:62:af:4c:f0:4e:cf:a3:ae:c3:35:f2:bd:7f:
    ...
    9c:99:f9:23:57:94:1d:b7

Nous pouvons faire les observations suivantes :

• Ce format encode les deux clefs (privées et publique) dans le même fichier. La commande openssl rsa -in dummy.pem -pubout permet d’en extraire une clef publique.
• Le fichier stocke le module $n$ et les exposants $e$ (public) et $d$ (privée), mais aussi d’autres données.
  Ces informations supplémentaires permettent d’optimiser la fonction de déchiffrement du message, le calcul pouvant alors être rendu plus rapide.
  Cette optimisation, appelée RSA-CRT, utilise le théorème des restes chinois.

Attaques contre RSA

RSA reste très largement utilisé, mais des scénarios d’attaque sont connus si les clefs ne respectent pas certaines contraintes.

En particulier, le module $n$ doit être suffisamment grand pour rendre extrêmement complexe sa factorisation (aujourd’hui, on considère qu’il faut une taille de clef d’au moins $2048$ bits).

D’autres scénarios d’attaque existent, par exemple l’attaque de Wiener, qui permet de retrouver la clef privée à partir de la clef publique lorsque $d$ est trop petit.

Un exercice intéressant pourrait être de la mettre en oeuvre pour casser l’implémentation naïve fournie plus haut…

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

• ← De la construction des réels à la norme IEEE 754
• Polynômes, extensions de corps et QR codes →