Dans $\mathbb{R}$, tout nombre (réel) non nul est inversible pour la multiplication.
Ainsi donc, si l'on note $\mathbb{R}^\times$ le groupe des inversibles, on trouve tous les réels non nuls : $\mathbb{R}^\times = \mathbb{R}^*$.
Dans $\mathbb{Q}$, tout nombre (fraction) non nul $\frac{p}{q}$ est inversible, d'inverse $\frac{q}{p}$. Dans ce cas, on a $\mathbb{Q}^\times = \mathbb{Q}^*$.
Par contre, dans $\mathbb{Z}$, il n'y a plus de nombres (entiers) inversibles, à part 1 et -1 : si l'on prend un entier $x \notin \{-1, 1\}$, il est impossible de trouver un autre entier $y$ tel que le produit $xy$ soit égal à 1. Dans ce cas, $\mathbb{Z}^\times = \{-1, 1\}$.
Par contre, si l'on travaille modulo 5, on trouve que $3 \times 2 = 1$ :
>>> 3*2 %5 1
Ainsi, dans l'ensemble $\mathbb{Z}/5\mathbb{Z} = \{0, 1, 2, 3, 4\}$ des entiers modulo 5, que l'on notera plus commodément $\mathbb{Z}_5$, 3 possède un inverse pour la multiplication, qui est 2. De même, 2 est inversible, d'inverse 3.
On peut chercher l'ensemble des inversibles de $\mathbb{Z}_5$ :
>>> for k in range(5): ... for l in range(5): ... if k*l % 5 == 1: ... print k,l ... 1 1 2 3 3 2 4 4
On trouve donc que 1 est inversible d'inverse lui-même, et que 4 est aussi inversible, d'inverse 4 :
>>> print 4*4%5 1
Ainsi donc, on l'a vu, dans $\mathbb{Z}_5$, tout nombre non nul est inversible : $\mathbb{Z}_5^\times = \{1, 2, 3, 4\}$.
Cela n'est pas toujours vrai. Par exemple, dans $\mathbb{Z}_6$, 3 n'est pas inversible. Pour s'en convaincre, il suffit de tester toutes les possibilités...
>>> for k in range(6): ... print 3*k%6 ... 0 3 0 3 0 3
En fait, si on relance la double boucle de tout à l'heure, pour déterminer les inversibles de $\mathbb{Z}_6$, on trouve :
>>> for k in range(6): ... for l in range(6): ... if k*l % 6 == 1: ... print k,l ... 1 1 5 5
C'est-à-dire que seuls 1 et 5 sont inversibles modulo 6 : $\mathbb{Z}_6^\times = \{1, 5\}$.
On peut prouver que, si $p$ est premier, alors l'ensemble des inversibles $\mathbb{Z}_p^\times$ est toujours égal à tout $\mathbb{Z}_p$, sauf O : $\mathbb{Z}_p^\times = \{1, ..., p-1\}$.
Si par exemple on crée une fonction qui renvoie la liste des couples d'inversibles dans $\mathbb{Z}_n$ :
>>> def inversibles(n): ... L = [] ... for k in range(1,n): ... for l in range(1,n): ... if (l,k) in L: ... pass ... if k*l%n == 1: ... L.append((k,l)) ... break ... return L
Alors, pour $n$ inférieur à 15, on trouve :
2 [(1, 1)] 1
3 [(1, 1), (2, 2)] 2
4 [(1, 1), (3, 3)] 2
5 [(1, 1), (2, 3), (3, 2), (4, 4)] 4
6 [(1, 1), (5, 5)] 2
7 [(1, 1), (2, 4), (3, 5), (4, 2), (5, 3), (6, 6)] 6
8 [(1, 1), (3, 3), (5, 5), (7, 7)] 4
9 [(1, 1), (2, 5), (4, 7), (5, 2), (7, 4), (8, 8)] 6
10 [(1, 1), (3, 7), (7, 3), (9, 9)] 4
11 [(1, 1), (2, 6), (3, 4), (4, 3), (5, 9), (6, 2), (7, 8), (8, 7),
(9, 5), (10, 10)] 10
12 [(1, 1), (5, 5), (7, 7), (11, 11)] 4
13 [(1, 1), (2, 7), (3, 9), (4, 10), (5, 8), (6, 11), (7, 2), (8, 5),
(9, 3), (10, 4), (11, 6), (12, 12)] 12
14 [(1, 1), (3, 5), (5, 3), (9, 11), (11, 9), (13, 13)] 6
15 [(1, 1), (2, 8), (4, 4), (7, 13), (8, 2), (11, 11), (13, 7),
(14, 14)] 8
Quand $n$ est premier, le nombre des inversibles est égal à $n-1$.
On s'intéresse dorénavant uniquement au groupe des inversibles $\mathbb{Z}_p^\times = \{1, ..., p-1\}$, pour $p$ premier.
On peut prouver que ce groupe est cyclique : il existe au moins un élément dans $\{1, ..., p-1\}$ tel que ses puissances respectives donnent tout $\mathbb{Z}_p^\times$.
Ainsi, dans $\mathbb{Z}_{13}^\times$, $\dot{2}$ satisfait cette propriété : quand on calcule $2^k%13$, pour $k=1, ..., 12$, on retrouve tout $\mathbb{Z}_{13}^\times = \{1, ..., 12\}$.
>>> for k in range(1, 13): ... print 2**k%13, ... 2 4 8 3 6 12 11 9 5 10 7 1
On dit alors que 2 est une racine primitive modulo 13 de l'unité.
On constate que $2^{12}%13 = 1$. C'est toujours vrai : si $g$ est une racine primitive modulo $p$, alors $g^{p-1} %p = 1$. Ce résultat servira pour le chiffrement El Gamal.
Les éléments de $\mathbb{Z}_p^\times$ ($p$ premier) ne vérifient pas forcément cette propriété. Ainsi, 3 n'est pas une racine primitive modulo 13, puisque ces puissances successives ne redonnent pas tout $\mathbb{Z}_{13}^\times = \{1, ..., 12\}$ :
>>> for k in range(1, 13): ... print 3**k%13, ... 3 9 1 3 9 1 3 9 1 3 9 1
Cependant, on ne sait pas très bien trouver facilement de telles racines primitives : aucune formule générale simple pour calculer les racines primitives modulo $p$ n'est connue.
Faisons le point, et profitons-en pour introduire la notion d'exponentielle discrète...
On connaît la fonction exponentielle, qui à $x$ associe sa puissance $e^x$, $e \approx 2,7182818284590451...$ étant un nombre réel appelé constante d'Euler :
$x \in \mathbb{R} \longmapsto e^x \in \mathbb{R}_+^*$
Son inverse, la fonction logarithme népérien, ou logarithme de base $e$, permet d'effectuer l'opération inverse : étant donné $y>0$, le logarithme permet de retrouver le $x$ tel que $e^x = y$.
$y \in \mathbb{R}_+^* \longmapsto \ln(y) \in \mathbb{R}$
Ici, on remplace le corps des réels $\mathbb{R}$ par le corps fini $\mathbb{Z}_p = \mathbb{Z}/p\mathbb{Z}$, où $p$ est un grand nombre premier.
Le groupe multiplicatif $\mathbb{Z}_p^\times = \{\dot{1}, \dot{2}, ..., \dot{p-1}\}$ est, on l'a vu, cyclique. Cela signifie qu'il existe au moins un entier $g$, compris entre 2 et $p-1$, tel que les puissances successives de $g$ modulo $p$ consituent $\mathbb{Z}_p^\times$ :
$\mathbb{Z}_p^\times = \{g^k %p, \textrm{ pour } 0 \leqslant k \leqslant p-1 \}$
Un tel $g$ est, on l'a vu, appelé une racine primitive modulo $p$, et l'application suivante :
$x \in \mathbb{Z}_{p-1} \longmapsto g^x \in \mathbb{Z}_p^\times$
est de ce fait bijective. Cette application bijective est appelée exponentielle discrète de base $g$. Sa fonction inverse est le logarithme discret de base $g$.
Le calcul de l'exponentielle discrète est assez rapide, en utilisant l'élévation rapide à la puissance, présentée ici.
En revanche, le calcul du logarithme discret s'effectue en un temps non polynomial, avec les algorithmes actuels. Le calcul devient donc vite impraticable quand $p$ est grand.
On est donc en présence d'un problème réputé difficile des mathématiques. Une première utilisation en cryptographie est l'échange de clés selon Diffie et Hellman...
W. Diffie et N. Hellman eurent l'idée, en 1976, d'un échange public de messages entre deux correspondants, leur permettant de s'accorder sur une clé secrète. On n'a pas encore à proprement parler une méthode de chiffrement à clé publique.
On a cependant affaire à la première mise en oeuvre de l'asymétrie des calculs entre une fonction et sa fonction réciproque.
Alice et Bob veulent se mettre d'accord sur le choix d'une clé secrète. Cet accord leur permettra d'effectuer un chiffrement classique.
On souhaite donc ici trouver un moyen de s'échanger une clé en public, au su et à la vue de tout le monde.
Ainsi, l'information publique est $p,g,A,B$, mais cette information ne permet pas de calculer $g^{ab}$, qui sera la clé secrète utilisée entre Alice et Bob.
C'est une application directe du problème du logarithme discret.
On vous demande de choisir un de vos camarades, et de mettre en place entre vous un chiffrement symétrique par mail, avec échange sécurisé de la clé (grâce à Diffie-Hellman).
Vous devrez donc réaliser un module python...
Votre module devra permettre d'obtenir :
De même, votre module devra permettre à Alice et Bob d'obtenir les valeurs $A$ et $B$ à envoyer, à partir des $a$ et $b$ choisis. Enfin, une méthode spéciale devra permettre de constituer la clé privée $g^{ab}$.
Vous aurez à y insérer un algorithme de chiffrement symétrique de votre choix, pour compléter votre module, ainsi qu'une méthode recevant une chaîne de caractères, et renvoyant une liste de nombres à chiffrer (grâce au code ASCII, par exemple).