Université Paris 8 J.
Lavauzelle
Master 1 Mathématiques et applications — année 2023–24
Cryptographie à clé publique – Feuille de TD 7
11/03/2024
Le corrigé de certains exercices sera disponible à l’adresse suivante :
https://lvzl.fr/teaching/2023-24/cp.html
(⋆) exercice fondamental (⋆⋆) pour s’entraîner (⋆⋆⋆) pour aller plus loin § sur machine
Exercice 1. (⋆)
Exercice 1. (⋆) Un
Un nouveau
nouveau protocole
protocole d’identification
d’identification?.
?.
Alice souhaite s’identifier auprès de Bob. On suppose qu’Alice et Bob détiennent un secret com-
mun x ∈ {0,1}t , pour t ≥ 1, qui doit servir à plusieurs identifications. Le protocole suivant est
proposé :
1. Bob choisit une chaîne aléatoire r ∈ {0,1}t et l’envoie à Alice
2. Alice calcule y = r ⊕ x et renvoie y à Bob.
3. Bob vérifie que x = r ⊕ y.
Question 1.– Pourquoi ce protocole ne peut pas être utilisé pour plusieurs identifications ?
Question 2.– Quelle étape d’un protocole d’identification à trois passes manque t-il dans ce
protocole ?
Exercice 2. (⋆⋆) Schéma d’identification de Feige–Fiat–Shamir.
Dans cet exercice, on s’intéresse au schéma d’identification de Feige-Fiat-Shamir.
Dans le réseau de participants, une autorité de confiance choisit secrètement p et q deux grands
nombres premiers, puis calcule et publie n = pq. On fixe ensuite k un entier, typiquement de
taille log2 log2 n.
Alice, une utilisatrice du réseau, procède comme suit pour engendrer une paire de clefs :
1. Alice choisit aléatoirement s1 , . . . , sk ∈ (Z/nZ)× .
2. Pour tout j = 1, . . . , k, Alice choisit ε j ∈ {−1, 1} aléatoirement, puis calcule p j = ε j /s2j .
3. La clé publique d’Alice est pk = ( p1 , . . . , pk ), la clé privée d’Alice est sk = (s1 , . . . , sk ).
Le protocole d’identification se déroule ainsi :
1
Alice Bob
sk = (s1 , . . . , sk ) pk = ( p1 , . . . , pk )
choisit aléatoirement
r ∈ (Z/nZ)× et ε ∈ {−1, 1}
calcule x = εr2 mod n x
choisit aléatoirement
e e = (e1 , . . . , ek ) ∈ {0,1}k
ej
calcule y = r ∏j sj y
ej
vérifie que x ≡ ±y2 ∏ j p j mod n
Question 1.– Démontrer que le protocole d’identification est valide.
Question 2.– Démontrer que, si un attaquant connaît le défi e de Bob avant de réaliser son
engagement x, alors il peut monter une imposture. En déduire qu’il existe une attaque sur le
système qui réussit avec probabilité 2−k .
Question 3.– Selon vous, sur quel problème (difficile) repose la sécurité du schéma ? Donner
une justification succincte.
Dans les questions suivantes, on cherche à démontrer que le protocole d’identification de Feige-
Fiat-Shamir est une preuve de connaissance à divulgation nulle. Autrement dit, les itérations
du protocole ne révèlent aucune information sur le secret sk d’Alice.
Pour obtenir cette propriété, l’idée est de démontrer que l’on peut simuler la distribution du
transcript ( x, e, y) sans la connaissance de sk.
Question 4.– On suppose que tous les tirages sont uniformes. Quelle loi suit la variable aléatoire
y?
On définit le simulateur de transcript suivant :
1. choisir uniformément e′ = (e1′ , . . . , ek′ ) ∈ {0,1}k ,
e′j
2. choisir uniformément r′ ∈ (Z/nZ)× et ϵ′ ∈ {−1, 1}, puis calculer x = ϵ ′ (r ′ )2 ∏ pj mod n,
3. définir y′ = r ′ .
Question 5.– Démontrer que la loi de ( x ′ , e′ , y′ ) induite par le simulateur est la même que
celle de ( x, e, y) issue du protocole d’identification. En déduire que le protocole est à divulgation
nulle.
