Théorie des groupes et cryptographie

8 janvier 2022

Les mathématiques sont l’étude de structures abstraites. Un ensemble d’éléments avec des caractéristiques bien définies constitue une structure. La nature des éléments n’importe peu. L’abstraction est ce qui fait la puissance des mathématiques.

Comme son nom l’indique, la théorie des groupes étudie la structure de groupe. Elle est utile pour concevoir des solutions au Rubik’s Cube. Elle devient indispensable en chimie ainsi qu’en cryptographie.

Cet article s’adresse aux lecteurs ayant déjà des bases dans le raisonnement mathématique. L’objectif est de présenter les résultats élémentaires de la théorie des groupes, et de les appliquer pour démontrer le fonctionnement de la cryptographie RSA.

Les démonstrations des propositions simples ne sont pas indiquées, celles des propositions plus avancées sont suggérées. Toutes les démonstrations peuvent être détaillées dans une prochaine version de l’article.

Groupes et sous-groupes

Définition : un ensemble $G$ est un groupe si :

$G$ est muni d’une loi de composition interne
La loi est associative
$G$ possède un élément neutre, noté $e$
Tout élément de $G$ est inversible

Si la loi est commutative, on dit que le groupe est abélien.

Exemple : $(\mathbb{Z}, +)$ est un groupe abélien.

Proposition : soit $G$ un groupe, alors :

L’élément neutre $e$ est unique
L’élément $a \in G$ a un unique inverse, noté $a^{-1}$
L’inverse de $ab$ est $(ab)^{-1}=b^{-1}a^{-1}$

Définition : Soit $H$ un sous-ensemble d’un groupe $G$ , $H$ est un sous-groupe de $G$ si $H$ est aussi un groupe sous la loi de composition de $G.$

Proposition : $H$ est un sous-groupe de $G$ si pour tout $a,b \in H$ , $ab^{-1} \in H.$

Proposition : Soit $G$ un groupe, $a \in G$ . On définit $\langle a \rangle = \{a^k : k \in \mathbb{Z}\}$ . Alors $\langle a \rangle$ est un sous-groupe abélien de $G$ . $\langle a \rangle$ est le sous-groupe généré par $a.$

Proposition : Tout sous-groupe de $(\mathbb{Z}, +)$ est de la forme $n\mathbb{Z}$ avec $n \in \mathbb{Z}$ .

Définition : Soit $G$ un groupe et $a \in G$ :

On définit l’ordre de $a$ comme étant le plus petit entier positif $n$ tel que $a^n=e$ . Notation : $|a| = n$ . Si un tel entier n’existe pas, l’ordre de $a$ est infini.
On définit l’ordre de $G$ , noté $|G|$ , le cardinal fini ou infini de l’ensemble. On définit de même l’ordre de tout sous-groupe de $G$ .

Proposition : Soit $G$ un groupe et $a \in G$ . Si $|\langle a \rangle|$ est fini, égale à $n$ , alors $\langle a \rangle = \{e, a, a^2, \dots, a^{n-1}\}$ , et $a^n=e$ .

Démonstration : Il existe un entier $k>0$ , tel que $a^k=e$ . Le plus petit entier vérifiant cette propriété ne peut être que $n$ .

Proposition : Soit $G$ un groupe et $a \in G$ , alors $|a| = |\langle a \rangle|$ . Autrement dit, l’ordre d’un élément est égal à l’odre du sous-groupe généré par cet élément.

Théorème de Lagrange

Définition : Soit $G$ un groupe et $H$ un sous-groupe de $G$ . Pour tout $a \in G$ , on définit $aH$ la classe à gauche de $G$ suivant $H$ (dénommée coset en anglais). Plus précisément :

$aH$ est appelé coset à gauche
$Ha$ est appelé coset à droite

Proposition : Les $aH$ ( $a \in G$ ) forment une partition de $G$ .

Démonstration : pour tout $a \in G, a \in aH$ car $e \in H$ . Les $aH$ forment donc des ensembles non-vides qui couvrent $G$ . Il reste à montrer que deux tels ensembles distincts sont disjoints. Soit $aH$ et $bH$ distincts. On montre qu’ils sont disjoints par l’absurde. On peut montrer que si un élément appartient aux deux cosets, alors ces deux cosets sont égaux, ce qui contredit l’hypothèse.

Proposition : $a \sim b$ si $aH = bH$ définit une relation d’équivalence.

Proposition : $f : H \to aH$ telle que $f(h) = ah$ est une bijection. Donc $|H| = |aH|$ .

Théorème de Lagrange : Si $G$ est un groupe fini et $H$ un sous groupe de $G$ , alors $|H|$ divise $|G|$ .

Démonstration : les cosets forment une partition de $G$ et comme $G$ est fini, il existe un nombre fini de cosets distincts : $a_1H, a_2H, \dots, a_rH$ et $|G| = |a_1H| + |a_2H| + \dots + |a_rH|$ et comme $|a_iH| = |H|$ , on a $|G| = r |H|$ .

$r$ est l’index de $H$ dans $G$ et se note $[G:H]$ . On peut donc écrire que :

$|G| = [G:H] \times |H|$

Proposition : Soit $G$ un groupe fini d’ordre $n$ , alors pour tout élément $a \in G$ , $a^n=e$ .

Démonstration : Soit $|a| = k$ , on sait que $a^k=e$ . D’après le théorème de Lagrange, $k$ divise $n$ , il existe un entier $m$ tel que $n=km$ . Donc $a^n=a^{km}=(a^k)^m=e^m=e$ .

Groupe quotient

Définition : Soit $H$ un sous-groupe du groupe $G$ , $H$ est normal si pour tout $a \in G$ , $aH=Ha$ .

Définition : on définit $G/H = \{aH : a \in G\}$ . C’est l’ensemble des cosets de $H$ ou classes (d’équivalence) suivant $H$ .

Proposition : si $H$ est un sous-groupe normal de $G$ , alors $G/H$ est un groupe sous la loi suivante : $aH \cdot bH=(ab)H$ .

Note : $G/H$ est le groupe-quotient de $G$ par rapport au sous-groupe $H$ . Les éléments d’un groupe quotient sont des classes d’équivalence, c’est-à-dire des sous-ensembles d’éléments de $G$ .

Démonstration :

Grâce à la normalité de $H$ , on peut montrer que la loi précédemment définie est bien une loi de composition interne (ie une fonction). Si $x_1H=x_2H$ et $y_1H=y_2H$ , alors on doit montrer que $x_1H \cdot y_1H = x_2H \cdot y_2H$ .
La loi est associative grâce à l’associativité de la loi dans $G$ .
$eH=H$ est l’élément neutre.
$(xH)^{-1}=x^{-1}H$

Le groupe quotient $\mathbb{Z}/n\mathbb{Z}$

$n\mathbb{Z}$ est un sous-groupe de $(\mathbb{Z}, +)$ , clairement normal. Les cosets de ce sous-groupe sont de la forme ${a + n\mathbb{Z}}$ , qu’on note $\overline a$ .

On définit la relation d’équivalence $a \equiv b \pmod n$ si $\overline a = \overline b$ .

Cela signifie que :

$a \in \overline b$
$a=b+kn$
$a-b=kn$
$n$ divise $a-b$
$a$ et $b$ ont le même reste par la division euclidienne par $n$

On sait que $(\mathbb{Z}/n\mathbb{Z}, +)$ est un groupe. Et comme il y a $n$ restes possibles par la division euclidienne par $n$ , on a $\mathbb{Z}/n\mathbb{Z}=\{\overline 0, \overline 1, \dots, \overline{n-1}\}$ .

On a vu précédemment la définition de la loi du groupe quotient :

$\overline a + \overline b = \overline{a+b}$

De façon similaire, on peut définir une loi de multiplication dans $\mathbb{Z}/n\mathbb{Z}$ :

$\overline a \cdot \overline b = \overline{a \cdot b}$

On peut vérifier que cette loi est bien définie. En revanche, $(\mathbb{Z}/n\mathbb{Z}, \cdot)$ n’est pas un groupe. Par exemple $\overline 0$ n’est pas inversible.

On définit $\mathbb{Z}/n\mathbb{Z}^* = \{\overline{a} \in \mathbb{Z}/n\mathbb{Z}: \overline{a} \text{ inversible}\}$ , alors on peut montrer que $(\mathbb{Z}/n\mathbb{Z}^*, \cdot)$ est bien un groupe.

Soit $\overline a \in \mathbb{Z}/n\mathbb{Z}^*$ ,

alors il existe $\overline b \in \mathbb{Z}/n\mathbb{Z}^*$ tel que :

$\overline a \cdot \overline b = \overline 1$
$\overline{a \cdot b} = \overline 1$
$ab \equiv 1 \pmod n$
$ab = 1 + kn$
$ab -kn = 1$
$\text{pgcd}(a, n) = 1$ d’après le théorème de Bachet-Bézout

On montre ainsi que $| \mathbb{Z}/n\mathbb{Z}^* | = \Phi(n)$ , $\Phi$ étant l’indicatrice d’Euler.

Protocole RSA

Chiffrement RSA

On choisit $p$ et $q$ deux nombres premiers très grands et on forme $n=pq$ . On a $\Phi(n)=(p-1)(q-1)$ .

Soit $\overline e \in \mathbb{Z}/\Phi(n)\mathbb{Z}^*$ (choix quelconque, e pour encryption) et $\overline d$ son inverse. On a donc :

$ed \equiv 1 \mod \Phi(n)$
$ed = 1 + k\Phi(n)$

$e$ et $d$ sont les représentants uniques de leurs classes $< \Phi(n)$ .

$(e, n)$ est la clé publique
$(d, n)$ est la clé privée

On se place maintenant dans le groupe $(\mathbb{Z}/n\mathbb{Z}^*, \cdot)$ qui a pour ordre $\Phi(n)$ .

Soit $\overline M \in \mathbb{Z}/n\mathbb{Z}^*$ un message à chiffré ; on prend l’unique représentant $M < n$ . Si le message est trop grand, on le chiffre par bloc.

Chiffrement du message : $\overline C = \overline{M} ^e$
Déchiffrement du message : $\overline{C}^d = \overline M$

Démonstration :

$\overline{C}^d = \overline{M}^{ed} = \overline{M}^{1+k\Phi(n)}=\overline{M} \cdot \overline{M}^{k\Phi(n)} = \overline M$
En effet $\overline{M}^{\Phi(n)} = \overline 1$ par le théorème de Lagrange
On a donc $C^d \equiv M \pmod n$
$M = C^d \mod n$
On retrouve bien l’unique $M < n$

Sécurité du protocole RSA

La sécurité de ce protocole s’appuie sur le fait que la connaissance de la clé publique $(e,n)$ ne permet pas de déduire la clé privée $(d,n)$ . Le nombre $n$ étant déjà publique, pour trouver $d$ , un hacker devra connaître la décomposition de $n$ en facteurs premiers (trouver $p$ et $q$ ). A partir de $p$ et $q$ , il pourra calculer $\Phi(n)$ et trouver $d$ sans peine.

Il est très difficile de décomposer un grand nombre en facteurs premiers, mais il est facile de vérifier une solution (si on donne $p$ et $q$ , il est simple de vérifier que $n$ est bien égal à $pq$ ).

Pour des nombres $p$ et $q$ choisis suffisamment grands (au moins 2048 bits), le chiffrement RSA est considéré comme très sûr avec la technologie informatique actuelle et pour un avenir prévisible. La principale menace pour RSA serait un progrès significatif dans la technologie, notamment le développement des ordinateurs quantiques, qui pourraient potentiellement casser le chiffrement RSA en utilisant des algorithmes quantiques, comme l’algorithme de Shor.

Signature numérique

Celui qui envoie un message peut le signer en utilisant sa clé privée. Pour se faire il hache d’abord le message selon un protocole convenu (via une fonction de hachage cryptographique) et obtient $\overline H \in \mathbb{Z}/n\mathbb{Z}^*$ .

$H = \text{hash}(M)$ , avec $H < n$

Il génère ensuite une signature sur le hash du message : $\overline{S} = \overline{H}^d$ .

La signature consiste à envoyer $S < n$ avec le message $M$ .

Vérification : $\overline{S}^e = \overline{H}$ , en effet :

$\overline{S}^e = \overline{H}^{de}$
$\overline{S}^e = \overline{H}^{1+ k \Phi(n)}$
$\overline{S}^e = \overline{H}$
$S^e \equiv H \pmod n$
$H = S^e \mod n$

Le destinataire peut alors vérifier que le hash correspond bien à celui du message reçu.

Conclusion

La théorie des groupes est un outil puissant pour la cryptographie. Elle permet de comprendre le fonctionnement et de démontrer le protocole RSA. Elle devient encore plus indispensable pour les protocoles de cryptographie plus modernes basés sur les courbes elliptiques.