Chapitre 8

Cryptographie basée sur le problème

du logarithme discret

Ce chapitre décrit des techniques de cryptographie à clef publique dont la sécurité repose sur
l’hypothèse que le problème du logarithme discret est difficile, ou autrement dit que la fonction
exponentielle modulo p (x 7→ g x mod p) est à sens unique.
Pour fonctionner, ceci nécessite que les deux participants possèdent en commun un grand nombre
premier p ainsi qu’un élément g ∈ Zp (le « générateur »). Comme g est un élément de Zp , on
n’écrira pas « modulo p » à chaque fois. Il est sous-entendu que les calculs effectués à partir de g
restent dans Zp .
Tout le monde peut utiliser les mêmes valeurs de p et g. Il y a des valeurs recommandées dans
certains standards. La RFC 3526 spécifie des valeurs possibles, comme par exemple :

p = 22048 − 21984 − 1 + 264 · 21918 · π + 124476

 

g=2

D’anciens standards contenaient des paramètres trop petits (768 bits, 1024 bits, ...) dont l’usage
est déprécié. Si on est véritablement paranoïaque et qu’on pense que les standards sont moisis, on
peut générer ses propres paramètres soi-même, à condition de faire un peu attention (cf. § 8.3).
Les paramètres décrivent une structure mathématique appelée un groupe, qu’on ne décrira pas
précisément. Quand on parle « du groupe », on parle de g et p.

8.1 Échange de clef de Diffie-Hellman

Voyons comment faire de la cryptographie avec le problème du logarithme discret. Le protocole
d’échange de clef de Diffie-Hellman est historiquement le premier mécanisme cryptographique pu-
blié qui ne nécessite pas de clef publique. Il a été inventé en 1976 par Diffie (1944–) et Hellman
(1945–). Il semble qu’il ait été également inventé un an plus tôt par les services secrets britan-
niques, mais cela a été gardé secret jusqu’en 1997. En 2018, l’échange de clef Diffie-Hellman est
très largement utilisé (par exemple, c’est le cas quand je me connecte à ma banque).
Voici la description du protocole :

1. Alice choisit un nombre aléatoire 0 ≤ x < p. Elle calcule g x et l’envoie à Bob.

2. Bob choisit un nombre aléatoire 0 ≤ y < p. Il calcule g y et l’envoie à Alice.
x
3. Alice calcule K ← (g y ) (modulo p, bien sûr).
y
4. Bob calcule K ← (g x ) (idem).

À la fin du protocole, Alice et Bob possèdent donc en commun la valeur K = g xy mod p. C’est
essentiellement un élément aléatoire de Zp , si x et y sont choisis au hasard. Pour en tirer une
clef secrète, on peut par exemple le hacher, ce qui permet l’utilisation ultérieure d’un procédé de
chiffrement symétrique.

81
8.2. CHIFFREMENT ELGAMAL

L’idée, c’est que d’éventuels adversaires passifs ne peuvent pas apprendre K en observant l’échange.
En effet, ils voient passer g x et g y , mais à moins de pouvoir résoudre le logarithme discret dans Zp
ils ne peuvent pas apprendre x ou y. De plus, on ne connait pas d’algorithme efficace pour calculer
g xy étant donné g x et g y .

Attention au milieu. Sous cette forme de base, le protocole peut être victime d’une attaque par
le milieu (cf. exercice 8.1). Une des solutions pour l’éviter consiste à ce que chaque participant signe
les messages qu’il envoie. On parle alors d’échange de clef authentifié. Cependant la vérification
des signatures nécessite la connaissance de la clef publique du partenaire (et donc, éventuellement
un système de certificats).

Variante éphémère. Imaginons un serveur web sécurisé. De nombreux clients se connectent,

et établissent une connexion sécurisée grâce à un échange de clef Diffie-Hellman authentifié. Ceci
peut être réalisé de deux manières :
— Soit le serveur utilise le même g x pour tout le monde. Dans ce cas-là, son g x doit être
authentifié par un certificat signé par une autorité. On parle de Diffie-Hellman statique.
— Soit le serveur génère un nouveau g x à chaque nouvelle connection. Il doit alors le signer,
et sa clef publique de vérification doit être authentifiée par un certificat. On parle de Diffie-
Hellman éphémère.

La différence entre les deux, outre le temps de calcul pour le serveur, se trouve dans ce qui se passe
si quelqu’un parvient à « casser » l’échange de clef, et à acquérir le nombre secret x du serveur.

Dans le cas statique, si quelqu’un parvient à récupérer x, alors il peut non seulement déchiffrer
tous les échanges futurs du serveur, mais aussi les échanges passés. Ceci n’arrive pas avec le mode
éphémère (cette propriété d’appelle la Foward Secrecy).

8.2 Chiffrement Elgamal

Est-ce qu’on peut faire du chiffrement à clef publique en « imitant » ce qui se passe dans l’échange
de clef Diffie-Hellman ? Oui, comme cela a été démontré en 1985 par ÉÒm.Ì '@ QëA£ (Taher Elgamal)
(1955–). Ce système a été largement implémenté dans les logiciels libres de crypto (GPG par
exemple), car RSA était couvert par des brevets jusqu’à un passé récent. Le chiffrement Elgamal
est du coup la principale alternative à RSA de nos jours.

Génération des clefs. Pour produire sa paire de clefs, Alice :

— choisit au hasard un exposant secret 0 ≤ x < p.
— calcule h ← g x (modulo p, bien sûr).

La partie publique de la clef est la description du groupe (p et le générateur g) ainsi que h. La clef
secrète est x.

Chiffrement. Pour envoyer un message chiffré à Alice, Bob doit d’abord le coder comme un
élément non-nul m ∈ Zp . Ensuite Bob :
— Choisit au hasard un nombre 0 ≤ y
< p.
— Fabrique son chiffré C ← g y , mhy et l’envoie à Alice :
L’idée c’est que le message m est « masqué » (comme avec un masque jetable) par hy = g xy . C’est
ici que l’analogie avec l’échange de clef DH apparaît. Le chiffrement est non-déterministe. Sauf

82
 8.3. COMMENT FABRIQUER SES PROPRES PARAMÈTRES ?

dans de rares situations, c’est un avantage. Par contre, le chiffrement est malléable : étant donné
les chiffrement de u et v, on peut produire celui de uv :

C(u) = (g y , uhy )
C(v) = (g z , vhz )

Si on les multiplie entre eux, coordonnée par coordonnée, on trouve (g y+z , uvhy+z ), c’est-à-dire ce
qu’on obtiendrait en chiffrant uv avec l’aléa y + z. Cette malléabilité peut être un problème dans
certaines circonstances, et c’est pourquoi des précautions sont prises pour empêcher qu’elle ne pose
trop de problèmes (cf. § 10.3).

Déchiffrement. Après avoir reçu le message chiffré C = (a, b) de Bob, Alice peut :
— Calculer h ← ax , qui vaut donc g xy .
— Calculer h−1 , c’est-à-dire l’inverse de h dans Zp .
— calculer bh−1 , qui vaut m en principe.
On verra plus tard que le chiffrement Elgamal est sûr sous des hypothèses raisonnables (cf. § 9.4).

8.3 Comment fabriquer ses propres paramètres ?

On a vu comment fabriquer de grands nombres premiers. Par contre, il faut faire attention en
fabriquant le « générateur » pour Diffie-Hellman où Elgamal. Voyons le problème qui peut se poser
à travers un exemple. On choisit p = 181 (c’est bien un nombre premier) et g = 42.
Alice choisit x = 118 et calcule g x = 59.
Bob choisit y = 33 et calcule g y = 59.
Coincidence ? Pour s’en rendre compte, on calcule g i pour plusieurs valeurs de i :
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
gi 42 135 59 125 1 42 135 59 125 1 42 135 59 125 1 42 135
Et là, c’est l’horreur : il semble que g i ne puisse prendre que 5 valeurs distinctes. Du coup, il
n’y aurait que 5 secrets partagés possibles dans l’échange de clefs DH et seulement 5 « masques »
différents possibles dans le chiffrement Elgamal. Autant dire que ça ne chiffre pas beaucoup.
On note hgi = g i | i ∈ N — g est le « générateur » d’un tel ensemble 1 . Il semble ici que la taille


de h42i soit égale à 5, alors que Z181 possède beaucoup plus d’éléments.
En fait, le problème vient de ce que g 5 = 1. En effet, pour voir ce que vaut g i , posons la division
de i par 5 : i = 5q + r. On a alors :

q
g i = g 5q+r = g 5 · g r = g r .

Et on voit bien que g i ne peut prendre que 5 valeurs, de façon cyclique.

8.3.1 Ordre d’un élément modulo p

Définition : Ordre d’un élément modulo p

Si 0 < a < n est premier avec n (donc si a ∈ Zn est inversible), alors l’ordre de a modulo
n est le plus petit entier λ > 0 tel que aλ ≡ 1 mod n.

L’intérêt principal de cette notion d’ordre, par rapport à nos préoccupations, est exprimé dans le
résultat suivant :
Théorème 9 (« passage à l’exponentielle »). Si a est inversible dans Zn et que son ordre est q,
alors on a :
u ≡ v mod q ⇐⇒ au ≡ av mod n.

Démonstration

1. hgi est techniquement le sous-groupe de Z∗p , ∗ engendré par g...

83
8.3. COMMENT FABRIQUER SES PROPRES PARAMÈTRES ?

=⇒ Par définition, on a u − v = kq pour un certain entier k. On a donc :

au ≡ akq+v mod n
k
≡ (aq ) · av
v
≡a .

⇐= Il nous faut montrer que u−v est un multiple de q. On suppose sans perte de généralité
que u ≥ v (on peur les échanger si ce n’est pas le cas). Comme on a au ≡ av mod n et
que a est inversible, on multiplie le tout par l’inverse de a puissance v :

au−v ≡ 1 mod n.

Posons la division euclidienne de u − v par q :

u − v = kq + r, 0 ≤ r < q.

On va montrer que le reste r est nul, ce qui prouvera le résultat annoncé. Pour cela on
écrit :

au−v ≡ 1 mod n
kq+r
a ≡1
q k r
(a ) · a ≡ 1
ar ≡ 1

Comme r < q par définition de la division, et que q est par définition le plus petit entier
non-nul tel que aq ≡ 1 mod p, on est forcé de conclure que r = 0.

Pour que le logarithme discret soit vraiment difficile, il faut trouver un « générateur » g dont l’ordre
soit très élevé. En effet, le nombre de valeurs différentes que peut prendre g x est précisément l’ordre
de g.
Lemme 5. Pour g ∈ Zp , la taille de hgi est précisément l’ordre de g modulo p.
Démonstration
Soit q l’ordre de g modulo p. Le theorème 9 nous dit que g i = g (i % q)
, donc clairement g i ne
peut pas prendre plus de q valeurs différentes.
Maintenant on va voir que pour tout 0 ≤ i < j < q, g i 6= g j . En effet, si on avait g i = g j dans
ces conditions, alors d’après le théorème 9 on aurait i ≡ j mod q, ce qui est impossible car ils
sont différents et plus petits que q.

8.3.2 Racines primitives modulo p

Il nous faut donc des éléments de grand ordre. Mais y en a-t-il ? Et si oui, comment les trouver ?
Tout d’abord, le petit théorème de Fermat implique que l’ordre d’un élément modulo p est inférieur
ou égal à p − 1. Les élements qui auraient cet ordre sont donc particulièrement intéressants.
Définition : Racine primitive modulo p
Si p est un nombre premier, alors on dit que a ∈ Zp est une racine primitive modulo p si
son ordre est p − 1.

En gros, les racines primitives sont les éléments d’ordre le plus élevé possible. Si g est une racine
primitive, cela signifie que g i prend toutes les valeurs possibles dans 1, 2, . . . , p − 1. La bonne
nouvelle, c’est qu’il y en a toujours.
Théorème 10. Si p est un nombre premier, alors il y a des racines primitives modulo p.
On admet ce résultat, dont la preuve nous emmenerait un peu trop loin. En fait, la réalité se
présente plutôt favorablement, car l’écrasante majorité des élements de Zp sont en fait des racines
primitives (environ p/ log log p en sont).

84
 8.3. COMMENT FABRIQUER SES PROPRES PARAMÈTRES ?

Alors, on peut espérer trouver une racine primitive modulo p en choisissant un élément au hasard,
puis en vérifiant que son ordre est bien p − 1. On espère s’en tirer en O (log log p) essais. Si
l’hypothèse de Riemann généralisée était vraie, alors on

aurait la certitude qu’il existe toujours
une racine primitive modulo p plus petite que O log6 p .
Mais comment faire pour tester si un élément g est une racine primitive ? De manière générale,
déterminer l’ordre d’un élément de Zn est au moins aussi dur que factoriser n, donc ça ne se
présente pas bien. On pourrait vérifier que g i 6= 1 pour toutes les valeurs de i... Mais ça prendrait
vraiment trop longtemps si on voulait s’assurer que g est d’ordre 21000 , par exemple. Heureusement,
on peut s’épargner une bonne partie des tests grâce à l’observation suivante.
Lemme 6. L’ordre d’un élément non-nul a ∈ Zp est un diviseur de p − 1. Plus généralement, si
ak ≡ 1 mod p, alors l’ordre de a est un diviseur de k.
Démonstration
Montrons d’abord que la deuxième partie du résultat annoncé entraine la première (avec
k = p − 1). En effet, En effet, le petit theorème de Fermat affirme que ap ≡ a mod p. Comme
a n’est pas nul, il est forcément inversible modulo p, et on multiplie l’équation précédente par
l’inverse de a des deux côtés pour obtenir : ap−1 ≡ 1 mod p.
Démontrons maintenant la deuxième partie. Supposons que ak ≡ 1 mod p, notons q l’ordre de
a modulo p. D’après le théorème 9 (« passage à l’exponentielle »), on trouve donc k ≡ 0 mod q,
autrement dit q divise k.

Ceci permet de tester un peu plus efficacement si un nombre est une racine primitive ou pas :
Lemme 7. Les deux conditions suivantes sont équivalentes :
i) a 6= 0 est d’ordre q modulo p
ii) aq ≡ 1 mod p et aq/d 6≡ 1 mod p pour tout nombre premier d qui divise q.
Démonstration
i ⇒ ii : c’est facile. Cela découle de la définition de l’ordre, et du fait que q/d est plus petit
que q.
¬i ⇒ ¬ii : c’est le sens intéressant (et moins facile). Supposons donc que a n’est pas d’ordre
q, et montrons que aq 6≡ 1 mod p ou qu’il existe un nombre premier d qui divise q et pour
lequel aq/d ≡ 1 mod p).
Notons λ l’ordre de a, supposons que λ 6= q, que aq ≡ 1 mod p et montrons qu’il existe bien
un diviseur premier d de q tel que aq/d ≡ 1 mod p. D’après le lemme 6, on sait que λ divise
q, et comme ce n’est pas q, c’est un diviseur strict de q. Autrement dit, il existe q 0 tel que
q = λq 0 , avec q 0 > 1. Considérons un diviseur premier d de q 0 (il y en a, cf. théorème 3), et
vérifions qu’il fait l’affaire : notons q 0 = q 00 × d, et alors on a :
00
q00
aq/d = aλq = aλ =1 (car a est d’ordre λ).

CQFD.

Comment générer des racines primitives ? Le lemme 7 donne des critères permettant de
vérifier qu’un générateur donné a bien un ordre donné. Il peut donc servir à tester si un générateur
est une racine primitive, en vérifiant qu’il est bien d’ordre p − 1. La difficulté, c’est qu’il faut
connaître la factorisation de p − 1 en facteurs premiers. Et si p est un nombre aléatoire de 2000
bits, calculer la factorisation de p − 1 semble infaisable.
Pour être sûr d’avoir une racine primitive, plusieurs solutions sont possibles. L’une d’entre elles
consiste à choisir un nombre premier p de telle sorte qu’on connaisse la factorisation de p − 1. Le
problème, c’est que s’assurer du caractère aléatoire et imprévisible de p devient plus compliqué,
même si c’est possible.
Une solution plus simple consiste à utiliser des nombres premiers sûrs. On choisit au hasard un
nombre premier p tel que q = (p−1)/2 est aussi premier. Alors, il est facile de tester si des élements
de Zp sont des racines primitives : la factorisation de p − 1 en facteurs premiers est p − 1 = 2 × q.
Du coup, un élément a ∈ Zq est une racine primitive modulo q si et seulement si a2 6≡ 1 mod p et
aq 6≡ 1 mod p.

85
8.4. SIGNATURE DE SCHNORR

Le problème est que tout ceci n’est pas très efficace (la génération d’un gros nombre premier sûr
est assez lente, disons plusieurs minutes un ordinateur normal en 2018).

8.3.3 Générations efficace de paramètres offrant une sécurité suffisante

En fait, dans bon nombre de situations il n’est pas indispensable d’être sûr que le générateur est
une racine primitive. On peut se contenter de la certitude que son ordre est « suffisamment grand ».
Pour cela, une possibilité consiste à fabriquer un nombre premier p de telle sorte que p − 1 est un
multiple de q, pour q assez grand.

1. Choisir l’ordre q désiré, qui doit être un nombre premier d’au moins 256 bits en 2018.
2. Choisir un nombre uniformément aléatoire k de la bonne taille (1792 bits, par exemple).
3. Si p = 1 + kq n’est pas premier, revenir à l’étape 2.
4. Choisir un élément g ∈ Zp de manière arbitraire.
5. Si g 6= 1 et que g q ≡ 1 mod p, alors g est d’ordre au moins q. Sinon, retourner à l’étape 4.
6. Si on veut que g soit d’ordre exactement q, il suffit de vérifier en outre que g k 6≡ 1 mod p.

Rien n’interdit d’utiliser des ordres q composites, mais ceci a plusieurs défauts : d’abord l’arith-
métique modulo q est plus compliquée car tous les exposants ne sont pas inversibles modulo q, et
d’autre part cela affaiblit généralement la sécurité (cf. ci-dessous).

8.3.4 Sécurité des paramètres

Sans trop rentrer dans les détails, la sécurité des algorithmes de calcul du logarithme discret
dépendent de deux paramètres : la taille de p et la valeur de l’ordre.
Une première famille d’algorithmes (le « calcul d’index ») a une complexité qui est la même que
celle qui consiste à factoriser un entier de la même taille que p. Ceci nécessite donc que p soit assez
grand (2048 bits minimum en 2018).
D’autres algorithmes, plus simples, peuvent marcher si l’ordre a un problème : si l’ordre est très
faible, une recherche exhaustive peut en venir à bout. D’autre part, il existe des algorithmes
√

génériques dont la complexité est en O q (la méthode ρ ou bien l’algorithme baby steps / giant
steps. Ceci implique donc de s’assurer que l’ordre est un nombre de 256 bits au moins en 2018.
Enfin, si l’ordre est composite et s’écrit q = q1 · q2 , il faut savoir que calculer un logarithme peut
se ramener à un calcul avec un ordre q1 et un calcul avec un ordre q2 (il s’agit de l’algorithm de
Pohlig-Hellman). Si l’ordre est friable (n’a que de petits diviseurs), alors le calcul peut être facile.
Les nombres premiers sûrs évitent ce problème, de même que le choix d’un ordre premier.

8.4 Signature de Schnorr

L’idée de départ du chiffrement Elgamal est que la connaissance de g x permet le chiffrement, tandis
que x permet le déchiffrement. Ici, il nous faudrait l’inverse : un mécanisme où x permette de signer,
tandis que g x permette de faire la vérification.
La méthode de signature numérique la plus simple reposant sur le problème du logarithme discret
est sûrement la signature de Schnorr, décrit par Claus-Peter Schnorr en 1989. Il a été peu utilisé
concrètement car il était protégé par un brevet jusqu’à 2008.
Le procédé de signature est dérivé d’un protocole d’authentification interactif. Il fonctionne dans
un groupe muni d’un générateur d’ordre premier suffisament

8.4.1 Protocole d’authentification de Schnorr

Protocole S (preuve de connaissance d’un exposant). Un prouveur P (Peguy) connaît un exposant

secret x et il a publié son exponentielle h = g x . Le protocole lui permet convaincre un vérifieur

86
 8.4. SIGNATURE DE SCHNORR

V (Victor) qu’elle connaît bien x, mais sans lui révéler (« Zero-Knowledge Proof of Knowledge »).
Ceci permet notamment à Peguy de démontrer son identité à Victor.

S1. [Mise en gage.] Peguy choisit aléatoirement un exposant secret r (donc un nombre non-nul
modulo q), calcule R = g r puis transmet R à Victor.

S2. [défi.] Victor choisit aléatoirement un exposant c puis l’envoie à Peguy.

S3. [réponse.] Peguy calcule l’exposant a ≡ r − cx mod q et l’envoie à Victor.

Après l’étape S3, Victor vérifie si R ≡ g a · hc mod p. Si c’est le cas, il est convaincu que Peguy
connaît bien x. Pendant une exécution du protocole, seuls R, c et a transitent entre les participants.
On note (R, c, a) une transcription du protocole. Elle est correcte si R ≡ g a · hc mod p.

8.4.2 Sécurité du protocole

Ce protocole possède deux propriétés de sécurité intéressantes. On peut d’abord démontrer que
réussir à tromper Victor le vérifieur (c.a.d. le convaincre qu’on connaît le logarithme de h alors qu’on
ne le connaît pas) est aussi dur que le problème du logarithme discret. Dans un deuxième temps,
on démontre que ni Victor ni d’éventuels adversaires passifs ne peuvent apprendre d’information
sur le secret.

Tricher dans le protocole est dur. Supposons qu’on dispose d’un algorithme déterministe
efficace A, capable d’exécuter correctement le protocole (à la place du prouveur). Cet algorithme
prend h en entrée, mais pas x, et il reçoit une source de bits aléatoires en provenance de l’extérieur
pour effectuer ses choix aléatoires.

On va montrer qu’on peut utiliser cet algorithme pour calculer le logarithme discret de h, c’est-
à-dire reconstituer x. Il s’ensuit que « tricher » dans le protocole est au moins aussi difficile de
calculer le logarithme discret.

L’idée consiste à exécuter A deux fois en lui fournissant les mêmes bits aléatoire. Par conséquent,
chaque fois qu’on va exécuter A, il va produire le même nombre aléatoire r et donc la même mise
en gage R. On lui envoie deux défis différents c 6= c0 , et on suppose que A produit deux réponses
correctes a 6= a0 . On obtient donc :

R ≡ g a · hc mod p,
0 0
R ≡ g a · hc mod p.

0 0
On divisant ces deux congruences, on trouve 1 ≡ g a−a · hc−c mod p. D’après le théorème 9
(« passage à l’exponentielle »), et comme h ≡ g x mod p, ceci implique 0 ≡ (a−a0 )+x(c−c0 ) mod q.
On en déduit que x ≡ (a − a0 ) · (c − c0 )−1 mod q est le logarithme de h dans le groupe, et qu’il est
facile à calculer à partir de la sortie de A.

Aucune information sur le secret n’est révélée. Que peut apprendre le vérifieur ? Que
voient passer des adversaires passifs qui espionnent le protocole ? L’un et les autres observent
des transcriptions correctes du protocole. On va montrer ici qu’il est très facile de produire des
transcriptions correctes sans posséder le secret x.

Les adversaires « apprennent » donc des informations qu’on peut facilement produire sans posséder
le secret x... et donc par conséquent ils n’apprennent aucune information sur x.

Pour produire une transcription correcte, c’est très simple : choisir un défi c et une réponse a
uniformément au hasard modulo q. Calculer R de telle sorte que la transcription soit correcte, en
posant R = g a hc . Grace au choix aléatoire de a (et c), on sait que R est uniformément distribué,
comme s’il avait été choisi pendant une exécution normale du protocole.

87
8.5. SIGNATURE ELGAMAL

8.4.3 Signature de Schnorr

En gros, ce qui fait qu’on ne peut pas tricher dans le protocole de Schnorr, c’est qu’on doit choisir
R sans connaître le défi c. C’est donc le côté « interactif » qui bloque les tricheurs potentiels.
Pour transformer ceci en schéma de signature (non-interactif) on utilise une technique standard,
la transformation de Fiat-Shamir, qui consiste à générer le challenge de manière déterministe mais
imprévisible avec une fonction de hachage. La clef (publique) de vérification est h = g x , la clef
(secrète) de signature est x.
Pour signer un message M ∈ {0, 1}∗ :
1. Choisir r uniformément au hasard modulo q, calculer R ← g r mod p.
2. Calculer le « défi », c ← H(R k M ) mod q.
3. Calculer la « réponse », a ← r − cx mod q.
4. La signature est (c, a).

Signer un message M revient à « démontrer » qu’on connaît x, avec un défi généré à partir de
M : moralement, on ne peut le faire que si on connaît x (sinon, qu’est-ce qui nous empêcherait de
tricher au protocole de schnorr ?).
Pour vérifier si (c0 , a0 ) est bien une signature de M , on effectue la vérification du protocole d’au-
thentification, avec un détail : on ne connaît pas R, mais on peut le reconstituer à partir du « défi »
et de la « réponse ».
0 0
1. Calculer R0 ← g a hc mod p.
2. La signature est valide si c0 ≡ H(R0 k M ) mod q.

Une signature de Schnorr est constituée de deux nombres modulo q, donc si q occupe 256 bits, une
signature de Schnorr occupe 64 octets.

8.5 Signature ElGamal

Historiquement, la signature
ElGamal est le premier schéma à
clef publique qui n’est pas
complètement trivial.

Phong Q. Nguyen

Est-ce qu’on peut utiliser le chiffrement Elgamal pour faire des signatures ? On ne peut pas vraiment
utiliser la technique « signer = déchiffrer, vérifier = re-chiffrer ». Si la signature de M est le
déchiffrement de M , et qu’on re-chiffre la signature, on obtiendra un résultat qui contient de l’aléa,
donc qui n’a aucune chance d’être M .
Pour faire des signatures avec les mêmes idées que le chiffrement Elgamal, il faut ruser. La signature
Elgamal est largement utilisée elle aussi. Elle a été standardisée par le gouvernement américain sous
le nom de DSA (« Digital Signature Algorithm »), et elle a été largement déployée par exemple dans
le logiciel SSH pour l’authentification sans mot de passe (en effet, la signature RSA était elle aussi
couverte par des brevets). Maintenant, ECDSA (« Elliptic Curves Digital Signature Algorithm »)
est encore plus largement utilisée .
La génération des clefs est identique à celle du chiffrement. On choisit un grand nombre premier
p, et un générateur g d’ordre q (on suppose que l’ordre est elevé — si g est une racine primitive,
son ordre est p − 1).
Pour signer un message m ∈ Zp :
1. Choisir au hasard un élément inversible k ∈ Zq
2. Calculer r ← g k
3. Calculer s ← (m − xr)k −1 mod q
4. Si s = 0, retourner à l’étape 1.
5. La signature est (r, s)

88
 8.5. SIGNATURE ELGAMAL

Pour vérifier que (r, s) est une signature de m ∈ Zp :

1. Vérifier que 0 < r < p et 0 < s < q.
2. Vérifier que g m ≡ hr rs mod p.
Note importante : il faut toujours choisir un nouveau k à chaque signature. Tout échec est fatal. Par
exemple, les ingénieurs de Sony avaient apparemment mal compris la spécification de ce schéma de
signature, car sur la console de jeu Playstation 3, les jeux sont signés avec ECDSA, et la console
de charge que les jeux signés, donc « approuvés » par Sony. Seulement, tous les jeux ont été signés
avec le même r... Et ceci permet de retrouver facilement la clef secrète !

Exercices

Exercice 8.1 : Quel problème affecte le protocole d’échange de clef Diffie-Hellman si les messages
ne sont pas authentifiés ?

Exercice 8.2 : On considère le mécanisme de chiffrement symétrique E(k, m) = mk mod p, pour

un nombre premier p fixé et commun à tous. Les messages appartiennent à Zp . Ce mécanisme de
chiffrement possède la particularité que E(k1 , E(k2 , m)) = E(k2 , E(k1 , m)).
Comment peut-on effectuer le déchiffrement ?

Exercice 8.3 : Bob est un opposant dans un régime répressif qui reçoit des messages avec Alice,
une journaliste étrangère. Ils partagent une clef symétrique et s’échangent des messages chiffrés,
car Bob a été mis sur écoute. En plus, il craint d’être enlevé par la police politique puis torturé
jusqu’à ce qu’il révèle la clef symétrique. Les bourreaux vérifieraient alors que la clef est valide en
déchiffrant tous les messages précédemment échangés avec Alice et en vérifiant s’ils ont un sens.
Concevez un mécanisme de chiffrement symétrique qui permet d’exprimer sa véritable opinion mais
où, en cas d’urgence, on peut justifier de manière plausible que les messages précédemment chiffrés
étaient favorables au régime.
Indice : il faut prévoir deux mécanismes de déchiffrement : un normal et un autre pour les cas
d’urgence.

Exercice 8.4 : On considère un (mauvais) schéma de mise en gage basé sur le logarithme discret :

Commit(b) := g b mod p,

Justifier que ceci est perfectly binding. Est-ce que le bit mis en gage est vraiment dissimulé ?

Exercice 8.5 : La première manière d’améliorer le mauvais mécanisme de l’exercice 8.4 repose sur
le chiffrement Elgamal :
Commit(r, m) := (g r , mhr ) ,
où r ∈ Zq est aléatoire, q est l’ordre du générateur g, m 6= 0 est le message à mettre en gage
(m ∈ Z∗p ) et h est un autre générateur du groupe engendré par g modulo p (h = g x pour un certain
x et h a le même ordre que g). On n’essaiera pas de mettre en gage m = 0, pour des raisons
évidentes.
Justifier que ceci est perfectly binding. Est-ce computationally hiding ?

Exercice 8.6 : La deuxième manière d’améliorer le mauvais mécanisme de l’exercice 8.4 donne
des propriétés symétriques. On considère le schéma de mise en gage inventé par Torben Pryds
Pedersen en 1991 :
Commit(r, m) := g m hr mod p,
où r est aléatoire ; m est le message à mettre en gage et h est un autre générateur du groupe
engendré par g modulo p (il faut ici que l’ordre de q soit un nombre premier). Justifier que ceci est
statistically hiding et computationally binding.

Exercice 8.7 : Que se passe-t-il si on fait deux signatures Elgamal avec le même aléa ?

89
8.5. SIGNATURE ELGAMAL

Exercice 8.8 : On considère le protocole d’échange de clef authentifié par mot de passe (PAKE)
suivant :
1. L’étudiant génère une paire de clefs Elgamal (avec un générateur g qui est une racine primitive
modulo p), et envoie son nom ainsi que {pk}pwd à la borne wifi.
2. La borne wifi déchiffre pk avec le bon mot de passe, génère une clef de session aléatoire K et
renvoie le chiffré Elgamal de K avec la clef publique reçue (autrement dit la borne répond
{K}pk ).
3. L’étudiant et la borne continuent les échanges en chiffrant tout avec K.
Ce protocole est-il résistant aux attaques hors-ligne par dictionnaire ?

Exercice 8.9 : SPEKE (Simple Password Exponential Key Exchange) est un protocole d’échange
de clef authentifié par mot de passe (PAKE). Il était protégé par un brevet jusqu’à mars 2017.
Alice et Bob possèdent en commun un mot de passe pwd et veulent s’en servir pour établir une clef
de session symétrique. Pour cela, ils choisissent un nombre premier sûr p, et effectuent l’échange
de clef Diffie-Hellman en utilisant g ← H(pwd)2 mod p.
Justifier que g est d’ordre (p−1)/2 avec très forte probabilité. Le protocole résiste-t-il aux attaques
hors-ligne par dictionnaire ?

Exercice 8.10 : Démontrer que la propriété « être un nombre premier » est dans NP. Pour cela,
on peut démontrer puis utiliser le résultat suivant :
« S’il existe un nombre a d’ordre n − 1 modulo n, alors n est un nombre premier. »

90
 A.5. CHAPITRE 8

A.5 Chapitre 8
8.1 On n’a pas de garantie sur l’identité de son partenaire. On pourrait croire qu’on communique
avec un serveur bancaire, alors que la communication a été interceptée et qu’on révèle ses identi-
fiants bancaires à un serveur pirate.
8.2 On calcule d ← k −1 mod p − 1 (ceci limite le choix de la clef k, qui doit être inversible modulo
p − 1) et on pose D(k, y) = y d mod p.
Vérifions que c’est correct. Par construction, kd ≡ 1 mod p − 1 donc il existe un entier q tel que

d
q
kd = 1 + q(p − 1). On trouve alors xk ≡ x1+q(p−1) ≡ x xp−1 ≡ x mod p (en vertu du petit
théorème de Fermat).
8.3 L’idée générale est la suivante : Bob et Alice partagent un nombre secret x ainsi qu’une clef
de l’AES k. Lorsqu’Alice envoie un message sensible M , elle génère en passant un autre message
M 0 favorable au régime. Elle effectue le chiffrement Elgamal du message M 0 , mais en utilisant
AES(k, M ) comme aléa. Autrement dit :

E(M, M 0 ) = AES(k, M ), M 0 × AES(k, M )x mod p).

Dans la situation normale, Bob déchiffre M avec k (déchiffrement AES). Dans la situation d’ur-
gence, Bob prétend que le chiffrement Elgamal a été utilisé et révèle sa clef secrète x. Le déchiffre-
ment avec x révèle les messages M 0 .
8.4 Le mécanisme est perfectly binding si une mise en gage de 0 ne peut pas être « ouverte » comme
une mise en gage de 1. Or ici, c’est bien le cas : g 0 = 1 6= g = g 1 ...
Le bit mis en gage n’est pas du tout dissimulé : si la mise en gage est 1, c’est que le bit mis en
gage est 0.
8.5 D’après l’exercice 3.8 (en généralisant un peu), le mécanisme est perfectly binding s’il n’existe
pas de paire r, r0 telle que Commit(r, m) = Commit (r0 , m0 ) avec m 6= m0 .
Or, Commit(r, m) = Commit (r0 , m0 ) implique la double congruence
0
gr ≡ gr mod p,
0
mhr ≡ m0 hr mod p.

La première implique (en vertu du théorème 9) que r ≡ r0 mod q. Comme h est lui aussi d’ordre
0
q, il s’ensuit que hr ≡ hr mod p (toujours théorème 9, mais dans l’autre sens cette fois). Comme
h doit être inversible, multiplier des deux côtés par l’inverse de hr donne m ≡ m0 mod p, et donc
le schéma de mise en gage est bien binding.
Pour le côté hiding : tout d’abord, si on est capable de casser le logarithme discret, alors on peut
récupérer r à partir de g r , puis récupérer le message. Le mécanisme de mise en gage ne peut donc
pas être statistically hiding. Mais dans le fond, la mise en gage est essentiellement le chiffrement
élgamal du message (où h joue le rôle de la clef publique), donc extraire le message de la mise en
gage ne doit pas être facile.

 Il est possible d’argumenter que briser la propriété de hiding du schéma de mise en gage revient
grosso-modo à briser la sécurité sémantique du chiffrement Elgamal, ce qui revient précisement à
résoudre le problème Diffie-Hellman décisionnel. Tous les détails dans le chapitre 9.

8.6 D’après l’exercice 3.9, le mécanisme est statistically hiding si pour tout y (de la bonne taille)
il existe une paire r, r0 telle que y = Commit(r, 0) = Commit (r0 , 1). Soit donc y un élément du
groupe engendré par g modulo p. Il existe donc un exposant u tel que y = g u . Notons aussi h = g x .
Pour que y = Commit(r, 0), il faut que y = hr , donc que (th. 9) u ≡ rx mod q. Il suffit donc de
choisir r ← ux−1 mod q (x est inversible modulo q car x 6= 0 et q est premier).
Pour que y = Commit(r, 1), il faut que y = ghr , donc que u ≡ 1 + rx mod q. Il suffit donc de
choisir r0 ← (u − 1)x−1 mod q.
Le mécanisme est donc statistically hiding. Calculer r et r0 tels que définit ci-dessus nécessite de
connaître les logarithmes de y et de h en base g, ce qui n’est pas forcément faisable calculatoirement,
mais ce n’est pas le problème : il suffit de savoir qu’ils existent.

122
 A.5. CHAPITRE 8

Passons au côté binding. Le raisonnement ci-dessus montre que quelqu’un qui pourrait calculer
des logarithmes en base g pourrait briser la propriété de binding. Supposons qu’on dispose d’un
0
algorithme A qui prend en argument g, h, y et qui produise r, r0 tels que y ≡ hr ≡ ghr mod p.
r 0 −r
Comme h est inversible, on déduit de ces deux congruences que 1 ≡ gh mod p. On en déduit
(th. 9) que 0 ≡ 1 + x(r0 − r), où x est tel que h = g x . Alors, on trouve x = 1(r0 − r)−1 mod q, et
on a obtenu le logaritme discret de h en base g modulo p. Par conséquent, l’algorithme A ne peut
pas être sensiblement plus efficace qu’un algorithme qui résoud le logarithme discret, et le schéma
mise en gage est computationally binding.
8.7 On obtient deux signatures de deux messages m1 , m2 avec le même r = g k , notons-les (r, s1 ) et
(r, s2 ). Si elles sont valides, on a

g m1 ≡ hr rs1 mod p,
m2 r s2
g ≡h r mod p.

Comme g est inversible, on multiplie la première par l’inverse de la second et on trouve : g m1 −m2 ≡
rs1 −s2 mod p. Par le théorème 9, il s’ensuit que m1 − m2 ≡ k(s1 − s2 ) mod q. Ceci permet de
calculer k ← (m1 − m2 )(s1 − s2 )−1 mod q (attention, si q n’est pas premier, l’inverse n’existe pas
forcément. Dans ce cas-là, il faut éventuellement d’autres signatures...).
Un fois qu’on a k, on re-regarde la première congruence qui nous donne, via le th. 9 : m1 ≡
rx + ks1 ≡ q, et ceci permet de récupérer la clef secrète ! x ← (m1 − ks1 )r−1 mod q.
8.8 Ce protocole est résistant aux attaques hors-ligne par dictionnaire. Un adversaire peut tenter le
déchiffrement de {pk}pwd avec tous les mots de passes possibles. Mais il n’a aucun moyen de vérifier
qu’il est en train d’essayer le bon : il ne peut pas obtenir K sans casser le chiffrement Elgamal, et
donc pour « confirmer » pwd il lui faudrait un moyen de décider si pk est une clef publique Elgamal
valide. Or vu que g est une racine primitive, pk = g x est uniformément distribué dans Z∗p , et donc
il n’est pas possible de distinguer pk d’un nombre aléatoire inférieur à p. Par contre, si on trouve
un nombre supérieur à p on sait que pwd n’est pas bon (ceci doit se produire en moyenne avec
probabilité 50%).
Voilà une situation où il ne faut PAS utiliser un chiffrement authentifié !
8.10 Démontrons le résultat intermédiaire
Démonstration
Si a est d’ordre n − 1 modulo n, alors les n − 1 nombres :

a1 mod n, a2 mod n, ..., an−2 mod n, an−1 mod n,

sont tous différents (en vertu du lemme 5). Il y a donc là les entiers 1, 2, 3, . . . , p − 1, puisqu’il
ne peut pas y avoir zéro. De plus chacun de ces nombres est inversible (comme a est inversible,
on écrit b son inverse, et l’inverse de ai est bi ).
Cela signifie que n n’a aucun diviseur en commun avec chacun des entiers inférieurs à n.
Autrement dit, n est premier.
Ceci nous dit que pour assembler un certificat compact et facilement vérifiable de la primalité de
n, on peut se contenter d’exhiber un élément a de Zn et prouver qu’il est d’ordre n − 1. Pour cela,
on fournit la liste de tous les diviseurs premiers d1 , . . . , dk de n − 1 et l’algorithme de vérification
consiste vérifier que les conditions du lemme 7 sont bien réunies.
Pour que le certificat soit complet, il faut aussi qu’il permette de justifier que les di sont tous
premiers ! Mais pour ça on peut utiliser la même technique récursivement (ça donne bien des
certificats de taille polynomiale, qui se vérifient en temps polynomial).

 On connaît depuis 2002 un algorithme polynomial déterministe pour tester la primalité, dû à trois
chercheurs indiens : Manindra Agrawal (1966–), Neeraj Kayal (≈ 1984–), et Nitin Saxena (1981–).
Mais il est très lent (bien plus que le test de Miller-Rabin qui est probabiliste) et... trop compliqué pour
nous.

123