Introduction

Étymologiquement, le mot cryptographie provient du grec : kruptos (caché) et graphein (écrire). Le cryptographe essaie donc de mettre en place
des systèmes cryptographiques, ou cryptosystèmes, fiables pour chiffrer (ou sécuriser) des messages circulant dans un réseau
de communication. De son côté, le cryptanalyste tente de disséquer le système utilisé afin de trouver des failles et d’obtenir une information
à partir du message codé, appelé cryptogramme. Cryptographie et cryptanalyse font tous deux partie du domaine général qu’est la cryptologie :
la science du secret (voir aussi ici).

On se place dans la situation suivante : deux personnes, habituellement dénommées Alice et Bob, échangent des informations via
un réseau et un intrus, Charlie ou Eve, espionne les transmissions. Dans ce contexte, les quatre buts principaux de la cryptographie sont :

• la confidentialité : les textes codés et envoyés par Alice et Bob ne doivent pas être compris par Charlie ;
• l’authentification : Bob doit pouvoir être sûr que l’auteur du message est bien Alice et non une autre personne ;
• l’intégrité : le message d’Alice reçu par Bob n’a pas pu être modifié par Charlie lors de la transmission ;
• la non-répudiation : Alice ne peut pas nier être l’auteur et avoir envoyé son message une fois que celui-ci est transmis.

À ces quatre buts s’ajoutent quelques autres comme, par exemple, jouer à pile ou face au téléphone.

Il y a deux grandes familles de cryptographie : la cryptographie à clef secrète (ou symétrique) et la cryptographie à clef publique (ou asymétrique).

Cryptographie à clef secrète

Le principe de la cryptographie à clef secrète est probablement le principe le plus naturel auquel on pense lorsqu’on envisage de cacher une information :
l’émetteur et le récepteur partagent un secret commun qui permet de chiffrer et de déchiffrer un texte. Les opérations pour le codage et pour le décodage sont
alors essentiellement les mêmes, d’où le qualificatif « symétrique » pour de tels cryptosystèmes.

Exemples  :

• Dans un chiffrement à la César, on effectue un décalage constant des lettres du message. En simplifiant, il s’agit de travailler
  dans ${\mathbb{Z}}/26{\mathbb{Z}}$ en identifiant la lettre « A » à $\overline{1}$, « B » à $\overline{2}$, etc. La clef secrète est alors un élément, $\overline{s}\in {\mathbb{Z}}/26{\mathbb{Z}}$.
  Coder consiste à ajouter $\overline{s}$ à chacune des lettres du message alors que soustraire
  $\overline{s}$ à chaque lettre du message codé est l’opération de décodage.

• Pour le chiffrement à la Vigenère, on réalise des décalages sur des blocs du message. La clef secrète est
  alors un mot de $\ell$ lettres de l’alphabet ${\mathbb{Z}}/26{\mathbb{Z}}$, $\overline{s_1}\,\overline{s_2}\cdots \overline{s_\ell}$. On partage le message à coder en
  blocs de $\ell$ lettres et pour chacun d’eux, on ajoute $\overline{s_1}$ à la première lettre, $\overline{s_2}$ à la deuxième, etc. En particulier, un
  chiffrement à la Vigenère avec un mot d’une seule lettre (i.e. $\ell =1$) est un chiffrement à la César. Le chiffrement à la Vigenère ou à la César
  ne perturbent pas suffisamment la structure du langage et une analyse statistique permet de retrouver facilement la clef et de casser tous les
  systèmes de ce type.

• La machine Enigma était le cryptosystème utilisé par les Allemands lors de la seconde guerre mondiale. Certaines circonstances favorables
  (erreurs d’utilisation, vol d’une machine, etc.) et la cryptanalyse intensive d’Enigma (menée essentiellement par A. Turing en Angleterre)
  ont permis de casser [1] ce système complexe. Il est estimé que deux ans de guerre ont été épargnés grâce à ces travaux historiques.

• Le système AES, « Advanced Encryption Standard », est un standard de chiffrement symétrique utilisé couramment depuis le début des
  années 2000 et approuvé par la NSA. [2]

Un des avantages d’un cryptosystème à clef secrète est que les opérations pour coder et pour décoder sont extrêmement rapides à effectuer
et sont peu gourmandes en terme de ressources de calcul. De plus, ce sont des systèmes reconnus assez robustes : comprendre un
message codé
par AES est une entreprise fort compliquée à l’heure actuelle.

Les inconvénients de ces cryptosystèmes sont clairs. D’abord, ils nécessitent beaucoup de clefs : une pour chaque couple de personnes qui
communiquent dans le réseau soit $n(n-1)/2$ clefs pour un réseau de $n$ personnes. De plus, il faut pouvoir communiquer la clef
secrète sans que celle-ci soit révélée à une tierce personne : nous sommes donc revenus au point de départ !

Cryptographie à clef publique

L’idée de la cryptographie à clef publique est née dans les années 1970. La personne qui va recevoir des informations publie dans un annuaire
une clef
qui permet de chiffrer les messages. Seule une clef privée détenue uniquement par le récepteur doit rendre possible le déchiffrement. Dans ce cas,
les opérations de codages et de décodages ne sont pas de même nature, d’où le qualificatif d’« asymétrique ».

Exemples  :

• Le système RSA, du nom de ses inventeurs (Rivest, Shamir et Adleman), inventé en 1977, est probablement le plus célèbre et le plus utilisé à l’heure actuelle (carte bleue, achat sur internet, courriel sécurisé, etc.). Sa sécurité et la disymétrie du système reposent sur le fait qu’il est facile de multiplier des entiers alors qu’il semble difficile de les factoriser du moins dans le cas général.

• Le protocole Diffie-Hellman, à base du problème du logarithme discret que nous expliquerons dans la suite, permet à deux personnes de partager un secret qui peut être ensuite utilisé pour un cryptosystème à clef secrète.

• Le cryptosystème ElGamal repose également sur le problème du logarithme discret. Il est utilisé par le logiciel PGP (Pretty Good Privacy) pour l’envoi des courriels sécurisés par exemple.

Dans un cryptosystème à clef publique, les problèmes du partage et du nombre de clefs ne se posent pas. L’arithmétique développée au
17ème et 18ème siècles (algorithme d’Euclide, congruences modulo $n$, structure de $({\mathbb{Z}}/n{\mathbb{Z}})^\times$ [3], etc.) fournit les principaux outils théoriques
pour la quasi totalité des cryptosystèmes de cette famille. Plus récemment, l’utilisation de théorie comme celle des courbes elliptiques permet
également de réaliser de tels cryptosystèmes. La sécurité de
ces systèmes à clefs publiques repose généralement sur des conjectures et n’est donc pas rigoureusement établie.

Facile, difficile

Un cryptosystème à clef publique s’appuie sur une fonction dite à sens unique. Essentiellement, il s’agit d’une fonction $f$ telle que :

• il est facile d’évaluer $f(x)$ lorsqu’on connaît $x$ dans l’espace de définition de $f$ ;

• connaissant un $y$ dans l’espace d’arrivée, il est difficile de trouver un $x$ tel que $f(x)=y$.

Comme mentionné précédemment, pour le cryptosystème RSA, la fonction à sens unique consiste simplement en la multiplication
des entiers.

Notion de complexité

Il nous faut cependant expliquer plus rigoureusement la notion de facile/difficile ce qui revient à spécifier la complexité d’un algorithme.
Il existe des définitions mathématiques très précises pour cela. Dans ce texte, pour simplifier, nous nous contenterons d’évaluer la
complexité d’un algorithme par
le nombre de multiplications (d’entiers) et de divisions euclidiennes qu’il exécute en fonction de la taille de son entrée. La taille de l’entrée, $\ell$,
est le nombre de chiffres qu’il faut pour le représenter. Ce nombre dépend de la base choisie mais, à une constante près,
la taille de $\ell$ est égale à $\log(\ell)$.

On suppose que nous avons un algorithme à disposition qui prend un nombre $\ell$ en entrée et on note $C(\ell)$ le nombre de
multiplications/divisions faites pour exécuter l’algorithme. Les différents types de complexité que nous envisagerons ici sont les suivantes :

• si $C(\ell) \leq R \log(\ell)$ pour une constante $R \in {\mathbb{R}}$, on dit que l’algorithme est linéaire ;

• si $C(\ell) \leq R\log(\ell)^k$ pour $R\in {\mathbb{R}}$ et $k \in {\mathbb{N}}$, on dit que l’algorithme est polynomial (linéaire si $k=1$, quadratique si $k=2$, cubique si $k=3$, etc.) ;

• si $C(\ell) \leq e^{k \log(\ell)^a \log(\log(\ell))^{1-a}}$ pour $k \in {\mathbb{R}}$ et $a\in [0,1]$, on dit que l’algorithme est sous-exponentiel. En particulier, si $a=0$, il s’agit de la classe polynomiale précédente, alors que si $a=1$, il s’agit de la classe exponentielle qui suit ;

• $C(\ell) \leq R \ell = R e^{\log(\ell)}$ pour $R\in {\mathbb{R}}$, on dit que l’algorithme est exponentiel.

Pour effectuer un calcul, si nous avons un algorithme polynomial pour le faire, alors le calcul est qualifié de « facile »
 [4], voire de « très facile » dans le cas d’un algorithme linéaire.
Si le seul algorithme à disposition est exponentiel, le calcul est « très difficile ».

Exemples d’algorithmes

On pose [5]

$p = 10^{100}+43723 $

$\ \ =10000000000000000000000000000000000000000000000000000000$

$ \quad \quad 000000000000000000000000000000000000000043723$

Le nombre $p$ est un nombre premier (ceci se vérifie en quelques milli-secondes avec la commande isprime de PARI/GP). On note $g= \overline{2}$ dans ${\mathbb{Z}}/p{\mathbb{Z}}$ et on veut calculer $g^\ell$, i.e. $2^\ell$ modulo $p$. La méthode naïve consiste à écrire $g^\ell=g\times g \times \cdots g$ avec $\ell-1$ multiplications ; avec la définition précédente de la complexité, ce procédé est exponentiel en $\ell$. On lui préfère
des algorithmes d’exponentiations rapides ; il s’agit essentiellement d’utiliser le principe suivant :

$g^\ell = (g^{\ell/2})^2 $ si $\ell$ est pair

$g^\ell = g \cdot (g^{(\ell-1)/2})^2 $ si $\ell$ est impair

puis de réitérer l’opération.
À chaque étape, on divise la puissance par $2$ jusqu’à obtenir $0$. En analysant simplement cet algorithme,
on montre que le calcul de $g^\ell$ nécessite moins de $2\log\ell$ multiplications [6].

Cet algorithme est donc linéaire.

Il est crucial à ce point de bien cerner la différence entre un algorithme exponentiel et un algorithme linéaire. Supposons que nous fassions
les calculs avec un ordinateur utopique extrêmement puissant qui réalise $10^{12}$ multiplications d’entiers à la seconde. Le calcul de
$g^{10^{30}}$ durerait $10^{18}$ secondes soit un peu plus de 31 milliards d’années (l’âge de l’univers est estimé à environ 14 milliards
d’années). Prenons un ordinateur plus réaliste (comme celui que je suis en train d’utiliser), alors, le calcul de $g^{10^{100}}$ par l’algorithme d’exponentiation rapide prend moins
de 2 millisecondes.

Donnons à présent quelques exemples d’algorithmes importants en cryptographie dans les différentes classes de complexité décrites précédemment :

• L’algorithme d’exponentiation rapide est linéaire. Un autre exemple d’algorithme linéaire est le calcul du pgcd de deux entiers. L’algorithme d’Euclide permet de calculer $\text{pgcd}(\ell_1,\ell_2)$ en effectuant moins de $3\log(\ell_1)$ divisions euclidiennes. L’algorithme d’Euclide étendu pour obtenir des coefficients de Bézout $u, v \in {\mathbb{Z}}$ tels que $u \ell_1 + v\ell_2 = \text{pgcd}(\ell_1,\ell_2)$ est également un algorithme linéaire.

• Il existe plusieurs algorithmes polynomiaux qui déterminent si $\ell$ est un nombre premier ou non. Ainsi, certifier la primalité du
  nombre $p=10^{100}+43723$ prend moins d’une seconde pour un ordinateur classique.

• Les meilleurs algorithmes connus pour factoriser les entiers sont sous-exponentiels avec un $a$ qui vaut $1/3$. Il est quasiment impossible de factoriser des entiers sans forme particulière de plus de 200/300 chiffres en un temps raisonnable. Le record actuel est la factorisation d’un nombre RSA de 230 chiffres.

• Comme on l’a vu, le calcul de $g^\ell$ en effectuant $\ell-1$ multiplications est un algorithme exponentiel.

Le problème de logarithme discret

Soit $G$ un groupe cyclique d’ordre [7]
$n$ engendré par $g\in G$, i.e. :
\[ G=\{g^0,g,g^2,\cdots, g^{n-1}\} \]
et $g^n=g^0=1$, le neutre de $G$. On suppose également que les opérations dans $G$ se font rapidement (comme une multiplication d’entiers).
Une situation typique est de considérer le groupe $G=({\mathbb{Z}}/p{\mathbb{Z}})^\times$ des éléments inversibles modulo $p$ où $p$ est un nombre premier.

Exemple  :
Prenons $G=({\mathbb{Z}}/11{\mathbb{Z}})^\times$. On a donc
\[ G=\{ \overline{1}, \overline{2},\overline{3},\overline{4},\overline{5},\overline{6},\overline{7},\overline{8},\overline{9},\overline{10}\}. \]
Le groupe $G$ est cyclique engendré, par exemple, par $g=\overline{2} \in G$. On peut donc réécrire les éléments de $G$ :
\[ \begin{array}{lclllllllll} G = & \{ g^0, & g^1, & g^2, & g^3, & g^4, & g^5, & g^6, & g^7, & g^8, & g^9\}. \\ & \stackrel{\shortparallel}{\overline{1}} &\stackrel{\shortparallel}{\overline{2}} & \stackrel{\shortparallel}{\overline{4}} &\stackrel{\shortparallel}{\overline{8}} & \stackrel{\shortparallel}{\overline{5}} & \stackrel{\shortparallel}{\overline{10}} & \stackrel{\shortparallel}{\overline{9}}& \stackrel{\shortparallel}{\overline{7}} &\stackrel{\shortparallel}{\overline{3}} & \stackrel{\shortparallel}{\overline{6}} \end{array} \]
et on retrouve bien tous les éléments de $G$ comme des puissance de $\overline{2}$.

On remarque, en fait, que l’algorithme d’exponentiation rapide est générique : il peut s’utiliser dans n’importe quel groupe $G$ pour
calculer $g^\ell$ en effectuant moins de $2\log \ell$ multiplications dans $G$. Ainsi, connaissant $G$, $g$ et $\ell$, il est facile de
calculer $g^\ell$ dans $G$. En revanche, pour la réciproque...

Dans l’exemple précédent, on a $8=\log_{\overline{2}} \overline{3}$. Ceci dit, si on se place dans $G=({\mathbb{Z}}/101{\mathbb{Z}})^\times$, il n’est a priori
pas évident d’obtenir $\log_{\overline{2}} \overline{3}$ (réponse : $\ell = 69$). Dans le groupe $G=({\mathbb{Z}}/p{\mathbb{Z}})^\times$ où $p=10^{100}+43723$,
calculer $\log_{\overline{2}} \overline{3}$ semble une entreprise bien plus compliquée (je ne connais pas la réponse).

Le théorème suivant exprime la difficulté théorique du
problème du logarithme discret.

Un groupe générique est un groupe abstrait théorique dans lequel seules des opérations strictement dans $G$ sont autorisées.
Ainsi, le problème du logarithme discret est en principe un problème difficile à résoudre et la fonction puissance dans $G$ est une
fonction à sens unique. Cependant, dans les faits et pour les applications, il n’existe pas de groupe générique : les groupes dans lesquels
on veut faire les calculs proviennent d’une structure concrète et rien n’interdit de l’utiliser pour résoudre le problème du logarithme discret. Pour certains groupes, la résolution
du problème du logarithme discret est simple comme pour le groupe additif ${\mathbb{Z}}/n{\mathbb{Z}}$ : dans ce
cas $\overline{1}$ est un générateur mais le problème reste simple pour n’importe quel générateur de ce groupe (pourquoi ? [8]).
Dans les groupes multiplicatifs du type
$({\mathbb{Z}}/p{\mathbb{Z}})^\times$, les calculs se font modulo $p$ mais on peut utiliser les propriétés de ${\mathbb{Z}}$ pour résoudre le problème. En effet,

Cet algorithme est en fait une adaptation des algorithmes sous-exponentiels pour factoriser les entiers. À l’heure actuelle, les groupes du type
$({\mathbb{Z}}/p{\mathbb{Z}})^\times$ restent néanmoins les plus utilisés pour les cryptosystèmes à base du problème du logarithme discret. On ne sait pas si on peut
résoudre le problème du logarithme discret dans ces groupes plus rapidement qu’avec l’algorithme du théorème précédent.
Un autre type de groupe de plus en
plus utilisé est le groupe des points d’une courbe elliptique définie sur un corps de la forme ${\mathbb{Z}}/p{\mathbb{Z}}$. À part pour certaines courbes,
les meilleurs algorithmes connus pour résoudre le problème du logarithme discret sur ces groupes restent exponentiels.

Cryptosystèmes à base du problème du logarithme discret [protocoles]

Protocole Diffie-Hellman

Le premier protocole de base utilisant le problème du logarithme discret est celui de Diffie-Hellman. Alice et Bob s’entendent publiquement
sur un groupe $G$ cyclique d’ordre $n$ et sur un générateur $g$ de ce groupe. Alice tire secrètement un entier $k_A$ au hasard
avec $1\leq k_A \leq n$ et calcule $y_A = g^{k_A}$ dans $G$. Elle envoie alors $y_A$ à Bob. On remarque qu’un espion qui écoute la
communication entre Alice et Bob ne peut retrouver $k_A$ que s’il sait résoudre le problème du logarithme discret et calculer $\log_g y_A$.
Bob, de son côté, tire secrètement un entier $k_B$ au hasard avec $1\leq k_B \leq n$ et calcule $y_B= g^{k_B}$ qu’il envoie à Alice.
Alice reçoit donc $y_B$ et calcule $y_B^{k_A} = g^{k_Bk_A}$ et Bob qui a reçu $y_A$ calcule $y_A^{k_B}=g^{k_Ak_B}$. Ainsi, Alice et Bob
partagent un secret en commun $y=g^{k_Bk_A} =g^{k_Ak_B}$ sans qu’aucun des deux aient besoin de savoir le secret de
l’autre. [9]

A priori, un espion connaît $G$, $g$, $y_A$ et $y_B$. Il doit retrouver $y=g^{k_Ak_B}$ grâce à ces données. Il s’agit du problème
de Diffie-Hellman. Bien sûr, s’il sait résoudre le problème du logarithme discret dans $G$, il peut calculer $k_A$ et obtenir le secret
d’Alice et Bob avec $y=y_B^{k_A}$. Réciproquement, nous avons seulement la conjecture suivante qui fait toujours l’objet de recherche :

Comme expliqué ci-dessus, on utilise aujourd’hui les groupes du type $G=({\mathbb{Z}}/p{\mathbb{Z}})^\times$ pour les applications cryptographiques.
La sécurité de ces systèmes repose sur les deux « croyances » suivantes : on pense qu’il est aussi difficile de résoudre le problème
Diffie-Hellman que le
problème du logarithme discret et on pense qu’il est difficile de résoudre le problème du logarithme discret dans $G$. On ne sait
démontrer aucune de ces deux assertions.

Protocole ElGamal

Le protocole Diffie-Hellman est à la base de nombreux autres protocoles. Par exemple,
le protocole ElGamal permet d’échanger des
messages secrets. Alice veut recevoir des messages confidentiels, disons de Bob. Comme précédemment, ils s’entendent sur un groupe
$G$ cyclique d’ordre $n$ engendré par $g$. Alice choisit $k_A$ secrètement, calcule $y_A=g^{k_A}$ et publie $(G,g,y_A)$ dans
un annuaire. Bob veut envoyer le message $m$ à Alice. On peut supposer que le message à transmettre est un élément $m$ du groupe $G$.
Bob choisit
un entier $k_B$ secrètement, calcule $y_B=g^{k_B}$ et $s_B=my_A^{k_B}$. Il envoie $y_B$ et $s_B$ à Alice. Pour retrouver $m$, Alice
n’a plus qu’à calculer $s_By_B^{-k_A}$, en effet :
\[ s_By_B^{-k_A} = (m y_A^{k_B})(g^{-k_Bk_A}) = m g^{k_Ak_B}g^{-k_Ak_B} = m. \]
Un espion connaît $y_A,y_B$ et $s_B$. S’il peut retrouver $m$ alors il connaît $s_Bm^{-1}=y_A^{k_B} = g^{k_Ak_B}$ et il sait donc résoudre
le problème Diffie-Hellman ce qui est supposé être un problème difficile.

Réductions et méthodes de résolution du problème du logarithme discret

Soit $G$ un groupe cyclique d’ordre $n$ engendré par $g$ et soit $y\in G$. On cherche donc $\ell \in {\mathbb{Z}}$ tel que $y=g^\ell$.

Recherche exhaustive

La méthode naïve se résume à calculer $g$, $g^2$, $g^3$, etc. jusqu’à obtenir $y=g^\ell$.
Il s’agit donc d’effectuer $\ell$
multiplications dans $G$. Si le nombre $\ell$ est aléatoire, il est de l’ordre de grandeur de $n$ et l’algorithme est exponentiel.

Réduction de Pohlig-Hellman

La méthode de Pohlig-Hellman permet de réduire le problème dans des cas très particuliers. Supposons en effet que l’ordre du groupe $n$ soit
le produit
$n=pq$ de deux nombres premiers entre eux et supposons connue cette factorisation. Par l’algorithme d’Euclide étendu,
on peut trouver
deux entiers $u$ et $v$ tels que $pu + qv =1$ en un nombre linéaire de multiplications. Alors $y^{pu}$ est un élément de $G$ dont l’ordre
est divisible par $q$ et $y^{pu}$ appartient à un sous-groupe de $G$ d’ordre $q$. Le seul sous-groupe de $G$ d’ordre $q$ est le
sous-groupe cyclique
engendré par $g^p$ et il existe donc $\ell_1 \in {\mathbb{Z}}$ tel que $y^{pu} = (g^p)^{\ell_1}$. Le nombre $\ell_1$ est le [10]
logarithme discret de $y^{pu}$ en base
$g^p$. Il est plus facile de déterminer $\ell_1$ que de calculer directement $\ell$ puisqu’il s’agit d’un problème du logarithme discret
dans un groupe d’ordre $q$ au lieu d’un groupe d’ordre $n$.
De même, il existe $\ell_2 \in {\mathbb{Z}}$ tel que $y^{qv} = (g^q)^{\ell_2}$ ; il s’agit du logarithme discret de $y^{qv}$ en base $g^q$. Il est également
plus facile de déterminer $\ell_2$ que de calculer $\ell$ directement. Finalement, on a :
\[ y=y^1 = y^{pu+qv} = y^{pu} y^{qv} = g^{p\ell_1 + q\ell_2}, \]
et $\ell = p\ell_1 + q\ell_2$ est une solution du problème initial. On a donc trouvé $\ell$ en résolvant deux problèmes plus simples que
celui du départ : le fait que l’ordre du groupe ne soit pas une puissance d’un nombre premier réduit la sécurité des systèmes reposant
sur le problème du logarithme discret dans $G$. Il est inutile de considérer ce cas (i.e. $n=pq$ avec $p$ et $q$ premiers entre eux)
pour construire un cryptosystème à
base du logarithme discret.

De la même façon, si l’ordre du groupe $G$ est de la forme $n=p^\alpha$ où $p$ est un nombre premier, on peut résoudre le problème
du logarithme discret dans $G$ en résolvant $\alpha$ problèmes du logarithme discret dans des groupes d’ordre $p$.

La conclusion de cette
réduction de Pohlig-Hellman est la suivante : pour la sécurité des cryptosystèmes à base de logarithme discret dans un groupe $G$, on prend des groupes dont l’ordre est un nombre premier.

Méthode Baby-steps/Giant-steps

L’algorithme Baby-steps/Giant-steps est dû à Shanks. Il permet de résoudre le problème du logarithme en effectuant environ $2\sqrt{n}$ multiplications
dans le groupe $G$. Pour cela, on pose $m=\lceil \sqrt{n} \rceil$ où $\lceil \cdot \rceil$ désigne l’entier immédiatement supérieur. La division
euclidienne de $\ell$ par $m$ donne $\ell=mk +r$ avec $0\leq r \leq m$ et, grâce au choix de $m$, il vient $0 \leq k \leq m-1$. L’équation $y=g^\ell$ s’écrit
$(g^m)^k = yg^{-r}$. On effectue alors les « pas de géant » que l’on stocke dans un tableau :
\[ PG=[(g^m)^0,(g^m)^1,(g^m)^2,\cdots,(g^m)^k,\cdots, (g^m)^{m-1}]. \]
Cette étape nécessite un calcul de puissance ($g^m$) et $m$ multiplications donc environ $\sqrt{n}$ multiplications. Ensuite, on calcule
les pas de bébé : $yg^{-0}$, $yg^{-1}$, $yg^{-2}, \cdots$ jusqu’à obtenir un élément $yg^{-r}$ égal à un élément du tableau $G$ (par exemple, le
$k$-ième élément de $G$). L’obtention de la collision demande moins de $m$ multiplications dans $G$ et lorsqu’elle a lieu nous avons
$(g^m)^k = yg^{-r}$ soit $y=g^{mk+r}$ et $\ell=mk+r$ est une solution du problème du logarithme discret. Nous pouvons donc résoudre le
problème du logarithme discret en effectuant au plus environ $2\sqrt{n}$ multiplications. C’est nettement mieux que la recherche exhaustive mais
$\sqrt{n}$ reste exponentiel puisque $\sqrt{n} = e^{\frac{1}{2} \log(n)}$.

Dans les faits, il faut plus que $2\sqrt{n}$ multiplications car pour détecter efficacement la collision, il faut trier le tableau $G$ ce qui peut se faire en
$\sqrt{n}\log{\sqrt{n}}$ étapes. [11] Un inconvénient de l’algorithme
Baby-steps/Giant-steps est la nécessité de disposer d’un grand espace mémoire pour son exécution (la taille du tableau $PG$ est d’environ
$\sqrt{n}$), ce qui le rend inutilisable assez rapidement.
Il existe d’autres algorithmes simples qui permettent de résoudre génériquement le problème du logarithme discret dans $G$
en effectuant un ordre de $\sqrt{n}$ multiplications et qui ne nécessitent pas d’espace mémoire (citons l’algorithme rho de Pollard, voir par exemple, dans les livres cités dans les références). Ces algorithmes reposent sur le principe du paradoxe des anniversaires : dans un tirage aléatoire avec remise dans une urne
de $n$ boules, il y a environ une chance sur deux d’avoir obtenu deux fois la même boule au bout de $\sqrt{n}$ tirages.

Index-calculus

Toutes les méthodes précédentes s’appliquent dans des groupes génériques. Le théorème de Shoup affirme que l’on ne peut pas faire mieux dans ce cas. En revanche, pour les groupes $G$ du type $({\mathbb{Z}}/p{\mathbb{Z}})^\times$ où $p$ est un nombre premier, il existe un
algorithme, appelé index-calculus, qui est actuellement le plus rapide pour résoudre le problème du logarithme discret dans $G$.
Il est sous-exponentiel avec un $a=1/3$. Nous n’en dirons pas plus dans cette présentation.

Faisabilité d’un cryptosystème à base de logarithme discret

Nous voulons construire un groupe $G$ de la forme $({\mathbb{Z}}/p{\mathbb{Z}})^\times$ avec $p$ un nombre premier pour lequel le problème du logarithme discret
semble être difficile. Ceci permettra d’obtenir les cryptosystèmes expliqués dans la partie [protocoles] . Pour un tel groupe, il nous faut :

• A. Un grand nombre premier $p$, disons $p \approx 10^{100}$ de sorte que $p-1$ soit « presque » premier. En effet, l’ordre du groupe $({\mathbb{Z}}/p{\mathbb{Z}})^\times$ est égal à $p-1$ et comme $p$ est impair, $p-1$ est pair et n’est pas un nombre premier ce qui permet la réduction de Pohlig-Hellman. Ceci dit, si
  $p-1=2q$ où $q$ est un nombre premier, la réduction n’apporte pas grand chose au problème. On voudrait donc idéalement un nombre
  premier $p$ tel que $(p-1)/2$ est encore premier.

• B. Il faut trouver un générateur $g$ du groupe $G=({\mathbb{Z}}/p{\mathbb{Z}})^\times$ et, en particulier, être sûr qu’il existe. Pour cela, il faudra pouvoir calculer
  l’ordre d’un élément de $G$.

Pour le point A., on ne sait pas démontrer qu’il existe une infinité de nombres premiers $p$ tels que $(p-1)/2$ est premier. Des conjectures fines
de théorie des nombres prédisent qu’il en existe bien une infinité et que la probabilité pour qu’un nombre $p$ aléatoire inférieur à $X$ soit
premier et tel que $(p-1)/2$ soit encore premier est environ
\[ 1.3 \frac{1}{\log(X)^2}. \]
Pour $X=10^{100}$, il devrait donc y avoir environ 1 chance sur 40000 de tirer un tel nombre premier. Comme tester la primalité est facile (dans le sens qu’il existe des algorithmes polynomiaux pour cela [12]), obtenir
de tels nombres ne devrait pas poser trop de problèmes. Par exemple le nombre $p=10^{100}+43723$ est le plus petit nombre supérieur à
$10^{100}$ qui vérifie cette propriété. On a en effet que :

\[ \begin{array}{lll} \frac{p-1}{2} & = & 50000000000000000000000000000000000000000000000000000\\ &&00000000000000000000000000000000000000000021861 \end{array} \]

est un nombre premier. On peut vérifier que $\overline{2}$ est un générateur de $({\mathbb{Z}}/p{\mathbb{Z}})^\times$. Ceci dit le nombre $p$ a une forme
trop particulière, on peu trouver d’autres nombres premiers, $p$ avec $(p-1)/2$ premier, en tirant des nombres au hasard.
on préfère prendre des nombres au hasard. Sur un ordinateur classique, on obtient en moins de 2 secondes
le nombre $\tilde{p}$ suivant :

\[ \begin{array}{lll} \tilde{p}&=& 264042058349580654188298785388391081426100009133910822781\\ &&0485299213367577046869571383876657462423879 \end{array} \]

Pour le point B., il nous faut trouver un générateur de $({\mathbb{Z}}/\tilde{p}{\mathbb{Z}})^\times$. Tout d’abord le théorème classique suivant nous assure que le groupe est cyclique :

Puisque dans notre cas $p-1=2q$ où $q$ est un nombre premier, on peut facilement [13] calculer l’ordre d’un élément $a\in G$. En effet, le théorème de Lagrange
affirme que l’ordre d’un élément divise l’ordre du groupe ainsi l’ordre de $a$ est soit $1, 2, q$ ou $p-1$ et il suffit donc de calculer
$a, a^2$ et $a^q$ (et le calcul de $a^q$ est simple grâce à l’exponentiation rapide)
pour obtenir son ordre. On teste si $\overline{2}$ est générateur. S’il l’est, on a fini sinon on teste $\overline{3}$, puis $\overline{5}$,
etc. En théorie, ce procédé peut prendre du temps car on ne dispose que du théorème suivant :

Faire $p^{1/4}$ multiplications reste exponentiel en $p$ puisque $p^{1/4} =e^{1/4 \log p}$. Ceci dit sous une conjecture célèbre, appelée "hypothèse
de Riemann généralisée", il existe un énoncé bien plus optimiste :

Ainsi, sous l’hypothèse de Riemann, le procédé expliqué ci-dessus pour obtenir un générateur est polynomial de degré 6. Dans les faits,
on obtient très rapidement
un générateur. Dans l’exemple du nombre premier $\tilde{p}$, on peut prendre simplement $g=\overline{7}$. On laisse le problème suivant
au lecteur téméraire à forte espérance de vie : trouver $\ell \in {\mathbb{Z}}$ tel que
\[ \overline{2} = \overline{7}^\ell \mbox{ dans } ({\mathbb{Z}}/\tilde{p}{\mathbb{Z}})^\times. \]

Pour les systèmes cryptographiques actuels utilisant le problème du logarithme discret dans des groupes $G=({\mathbb{Z}}/p{\mathbb{Z}})^\times$, il est
recommandé de travailler avec des nombres premiers $p$ d’environ 600 chiffres (et avec des sous-groupes d’ordres inférieurs). On peut
réduire la taille des nombres si on utilise les courbes elliptiques mais il s’agit d’une autre histoire...

Bibliographie

A. Menezes, P. van Oorschot et S. Vanstone, Handbook of applied cryptography, CRC Press.

The PARI group, le logiciel PARI-GP, libre disponible ici

D. Stinson, Cryptography, Theory and Practice, Chapman & Hall/CRC.

G. Zémor, Cours de cryptographie, Cassini Eds, enseignement des mathématiques numéro 6.