IF202 Cryptologie td partie 2 2023-2024

Exercice 1 (Cryptosystème de Merkle et Hellman)

Le but de cet exercice est d’étudier un cryptosystème à clé publique fondé sur la difficulté d’un
problème complet de la classe NP. Il a cependant été cassé, ainsi que toutes les variantes qui en ont
été dérivées. À ce jour, la cryptologie à clé publique ne repose pas sur l’hypothèse de la difficulté
des problèmes NP-complet, mais sur la difficulté (supposée) de certains problèmes qui ont trait à la
théorie des nombres. Néanmoins, ce cryptosystème dû à Merkle et Hellman a un intérêt historique
puisqu’il fût l’un des premiers cryptosystèmes à clé publique publiés.
Le cryptosystème repose sur le problème SubsetSum (somme de sous ensembles) qui est NP -
complet :
SubsetSum
entrée : Une suite σ de n nombres entiers a1 , . . . , an et un nombre S.
sortie : OUI s’il existe une sous-suite de nombres dont la somme est S, NON sinon
On s’intéresse à la version fonctionnelle, qui a les mêmes entrées mais qui demande en sortie un
certificat, c’est-à-dire une sous-suite des ai dont la somme vaut S s’il en existe. Cette sous-suite
peut être encodée par un mot b1 . . . bn binaire de longueur n.
1. Soit σ = (1, 5, 6, 11, 14, 20). Existe-t-il une solution pour les entrées σ, 22 et σ, 24 ?
2. Supposons que pour un certain ensemble d’instances, le problème SubsetSum est facile à
condition de connaître une information supplémentaire. Plus précisément, on fait l’hypothèse
suivante :
il existe un ensemble Λ de suites d’entiers et il existe un ensemble de brèches B et une
fonction f : Λ → B qui associe à chaque suite de Λ une brèche b tels que le problème
entrée σ ∈ Λ, b = f (σ) et S entier
sortie un sous ensemble de σ dont la somme des éléments vaut S s’il en existe
est facile.
En déduire un cryptosystème à clé publique.
3. Une suite a1 , . . . , an est super croissante si pour tout i, 1 < i ≤ n, i−1
j=1 aj < ai . Montrer
P
qu’il existe un algorithme polynomial qui résout le problème SubsetSum pour toute entrée
(σ, S) où σ est une suite super croissante.
4. Dans le cryptosystème de Merkle et Hellman, la clé privée est une suite super croissante σ,
et deux entiers q et N tels que N est plus grand que la somme des éléments de σ et q est
premier avec N . La clé publique est la suite obtenue en multipliant chaque élément de σ par
q modulo N .
Quels sont les algorithmes de chiffrement et déchiffrement ? Soit σ = (2, 3, 6, 13, 27, 52),
q = 31 et N = 105. Chiffrer le message 011000 110101. Déchiffrer le message 280 333.
5. Si vous deviez implémenter ce cryptosystème, quelle taille (en bits) préconiseriez-vous pour
la clé privée ?
Malheureusement, il existe des failles dans la transformation de la clé privée vers la clé publique
qui permettent de retrouver la clé privée à partir de la clé publique ou de se passer de celle ci pour
retrouver le message en clair. L’étude de cette attaque dépasse le cadre de ce TD. Voir Shamir, Adi,

1
A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem, Information
Theory, IEEE Transactions on, vol.30, no.5, pp. 699-704, Sep 1984.

Exercice 2 (Cryptosystème de Rabin)

On note :
C4 = {N ∈ N | ∃p, q premiers, |p| = |q|, p ≡ q ≡ 3 (mod 4) , p · q = N }
-ZN = {i ∈ N | 0 ≤ i ≤ N − 1}
-Z∗N = {i ∈ N | 0 ≤ i ≤ N − 1, pgcd(i, N ) = 1}
-QN = {y ∈ ZN | ∃x ∈ ZN , x2 ≡ y (mod N )}.

.
1. Soit p un nombre premier et y ∈ Qp . Combien existe-t-il de racines carrées de. y dans Z/pZ ?
Aide : hZ/pZ, +, ·i est un corps commutatif. On factorisera le polynome X 2 − y dans Z/pZ[X].

2. Donner un algorithme efficace (de complexité polynomiale) pour le problème suivant (4RAC) :
entrée : p premier tel que p ≡ 3 (mod 4), y ∈ Qp
sortie : {x ∈ Zp | x2 ≡ y (mod p)}.
. . .
Soit N = pq avec p, q premiers entre eux . On rappelle que ψ :x mod N 7→ (x (mod p), x
(mod q)) est un isomorphisme d’anneaux de Z/N Z dans Z/pZ × Z/qZ.
. . . .
3. Que valent ψ −1 (1, 0), ψ −1 (0, 1) ? Plus généralement, comment calculer ψ −1 (y) pour y ∈
Z/pZ × Z/qZ ?
4. Démontrer que, si la factorisation (p, q) de l’entrée N est connue, et p, q ≡ 3 (mod 4), alors
le problème suivant (4RAC) admet un algorithme de complexité polynomiale :
entrée : N ∈ C4 , y ∈ QN
sortie : {x ∈ ZN | x2 ≡ y (mod p)}.
5. Montrer que, réciproquement, le problème (4FACTORISATION) ci-dessous, se réduit poly-
nomialement à (4RAC) :
entrée : N ∈ C4
sortie : p ≥ 2, q ≥ 2 tels que p · q = N .
6. Définir une fonction à sens unique et à brèche secrète issue du problème (4RAC) ; en déduire
un cryptosystème (dit de Rabin) à clés publiques.
7. Montrer qu’une attaque à texte chiffré est poynomialement équivalente à (4FACTORISA-
TION).

8. Montrer qu’une attaque à texte clair est possible.

Exercice 3 (Cryptosystème RSA)

On considère ici le cryptosystème RSA (voir annexe) qui est fondé sur le problème algorithmique
RacineIemeModulaire.
1. Montrer que, pour tout couple de clés (sk, pk), et tout message m, on a bien

Dec(sk, Enc(pk, m)) = m.

2
 Aide : utiliser le théorème d’Euler ou l’un de ses corollaires.

2. Vérifier que, étant donnés des nombres premiers p, q et N = p · q, on peut générer aléa-
toirement, selon une loi uniforme, un entier e ∈ ZN , tel que pgcd(e, ϕ(N )) = 1 en temps
polynomial.

3. Vérifier que, étant donnés des nombres premiers p, q, l’entier N = p · q, et e ∈ ZN , tel que
pgcd(e, ϕ(N )) = 1, on peut calculer en temps polynomial un entier d ∈ ZN , tel que d · e ≡ 1
(mod ϕ(N )).

4. Montrer que les fonctions de chiffrement et de déchiffrement sont calculables en temps poly-
nomial.

5. Démontrer que RacineIemeModulaire est plus facile que Factorisation (pour des ré-
ductions déterministes, en temps polynomial).

6. À partir de quelle hypothèse de théorie de la complexité, peut-on prouver qu’il est difficile :
a- de déterminer la clé secrète à partir de la clé publique ?
b- de déchiffrer les cryptogrammes sans connaître la clé secrète ?
Remarque : RacineIemeModulaire est plus facile que Factorisation ; l’inégalité en sens contraire
est supposée vraie (espéré ?) mais non prouvée !

Exercice 4 (Cryptosystème d’El-Gamal)

On considère le cryptosystème d’El-Gamal (voir annexe) qui est fondé sur le problème algorith-
mique de Diffie-Hellman.
1. Montrer que, pour tout couple de clés (sk, pk), et tout message m, on a bien

Dec(sk, Enc(pk, m)) = m.

2. Étudier la sécurité de ce système. Pour cela, démontrer que l’un (au moins) des problèmes
de Diffie-Hellman (on précisera lequel ou lesquels) est plus facile que déchiffrer les crypto-
grammes d’El-Gamal en ne connaissant que la clé publique.

3. Un attaquant sait résoudre le problème du logarithme discret (par exemple, parcequ’il a

fabriqué un ordinateur quantique). Peut-il déchiffrer les cryptogrammes d’El-Gamal en ne
connaissant que la clé publique ?

Exercice 5 (Échanges de clés)

L’objet de cet exercice est d’étudier différents protocoles d’échanges de clés, entre Alice et Bob,
via un canal C, qui peut être écouté par Eve ; la sécurité repose sur la difficulté des problèmes de
DiffieHellman. On considère les propriétés suivantes :
Fonctionnalité À la fin du protocole, les deux participants partagent une même clé.
Rafraîchissement de la clé Chaque participant est assuré que la clé est nouvelle.

3
 Autocertification des clés Chaque participant est assuré que seul son partenaire (celui avec
qui il communique via le canal C : A ou B ou E) pourra connaitre la clé de session échangée.
Authentification des clés Chaque participant est assuré de l’identité de l’autre participant
(A ou B, mais pas E)
Confirmation de la clé Chaque participant est assuré que son partenaire connaît la clé.
On suppose que Bob (resp. Alice) a pour clé privée skB = (p, α, xBob ) (resp. skA = (p, α, xAlice )
et pour clé publique pkB = (p, α, yBob ) (resp. pkA = (p, α, yAlice )). Ils communiquent via un canal C
qui peut être écouté par Eve (l’espion) et sur lequel Eve peut aussi envoyer des messages. Les couples
(p, α) considérés sont formés d’un entier premier p et d’un générateur α de Z∗p et sont supposés tels
que le problème DiffieHellman est difficile. On considère les protocoles suivants :
Version 1 Alice envoie à Bob EncElGamal (p, α, yBob ), K . La clé échangée est K.

Version 2 Alice envoie à Bob αK1 mod p. Bob envoie à Alice αK2 mod p. La clé échangée est
K := αK1 ·K2 mod p.
K1
Version 3 Alice envoie à Bob αK1 mod p. La clé échangée est K := yBob mod p.
Version 4 Alice envoie à Bob αK1 mod p. Bob envoie à Alice αK2 mod p. La clé échangée est
K := αK1 ·xBob +K2 ·xAlice mod p.
Version 5 Alice envoie à Bob : αK1 mod p.
Bob envoie à Alice : αK2 mod p,
La clé échangée est K := αK1 ·K2 mod p.
Alice envoie à Bob : Enc(K, S(skA , [αK1 mod p], [αK2 mod p])).
Bob envoie à Alice : Enc(K, S(skB , [αK2 mod p], [αK1 mod p])).
Enc désigne ici la fonction de chiffrement d’un cryptosystème symétrique (par exemple A.E.S)
et S est un procédé de signature (par exemple RSA).
Pour chacune des propriétés définies plus haut et chaque protocole, déterminer si le protocole satisfait
la propriété. N.B. Il y a donc 5 × 5 cas à étudier.

Exercice 6 (Pile ou face)

Alice et Bob veulent jouer à pile ou face mais ils n’ont pas toujours de pièce à lancer, n’ont pas
confiance l’un dans l’autre et sont parfois à 15000 km de distance. Par contre ils connaissent la
cryptologie.
1. Alice propose le protocole suivant : Bob tire aléatoirement un bit (selon une loi uniforme),
ensuite Alice tire léatoirement un bit (loi uniforme). Enfin Alice et Bob calculent le ou ex-
clusif des deux bits qui est le résultat du tirage. Ce jeu est-il équitable ?

2. Alice et Bob prennent un café. Alice propose d’utiliser le protocole suivant pour déterminer
qui paie les cafés :
- Alice choisit un bit a
- Charles, en qui A et B ont confiance, tire un bit aléatoire b, selon une loi uniforme.
- si a ⊕ b = 1 Alice gagne, sinon Alice perd.
Bob doit-il accepter ?

4
 3. Alice et Bob sont à 15000 km de distance l’un de l’autre ; ils communiquent par téléphone,
et ne se font pas confiance. Bob propose le protocole suivant. Soit f : {0, 1}∗ → {0, 1}∗ .
(a) Alice choisit un mot x et calcule y = f (x) ;
(b) Alice envoie y à Bob ;
(c) Après avoir reçu y, Bob choisit un bit b et l’envoie à Alice ;
(d)
(e)
Compléter les deux dernières étapes de ce protocole.
On suppose que leur canal de communication est sûr : chaque joueur peut-il vérifier qui est
le gagnant ?
Quelle hypothèse doit satisfaire la fonction f pour que ce jeu soit équitable ?
Qui est favorisé si f ne satisfait pas l’hypothèse ?
4. Voici un autre protocole qui repose sur l’utilisation d’un cryptosystème « commutatif » :

∀k1, k2 ∈ K, ∀m ∈ M : Deck1 (Enck2 (Enck1 (m))) = Enck2 (m)

Cette propriété n’est en général pas vérifiée par les cryptosystèmes à clé secrète. Elle est par
contre vérifiée par le systèmes à clé publique RSA.
(a) Alice et Bob génèrent une paire (clé privée, clé publique) que l’on notera respectivement
(sa, pa) et (sb, pb).
(b) Alice choisit aléatoirement deux nombres m0 ≡ 0 (mod 2) et m1 ≡ 1 (mod 2) (m0 peut
être vu comme “pile” et m1 comme “face”).
(c) Alice choisit une permutation σ de {0, 1} et envoie à Bob le message c0 := Encpa (mσ(0) ),
puis le message c1 := Encpa (mσ(1) ).
(d) Bob choisit un bit i ∈ {0, 1} et renvoie à Alice le résultat Encpb (ci ).
(e) Alice déchiffre ce message avec sa clé privée et envoie à Bob le résultat Decsa (Encpb (ci )) =
Decsa (Encpb (Encpa (mσ(i) ) = Encpb (mσ(i) .
(f) Bob déchiffre le message et envoie le résultat mσ(i) à Alice.
(g) Alice vérifie que mσ(i) ∈ {m0 , m1 } et lit le résultat du lancer.
(h) Alice et Bob révèlent leurs clés secrètes.
(i) si σ(i) = 1 Alice gagne, sinon Alice perd.
Montrer que :
- ce jeu est équitable
- ce jeu est protégé contre la triche : chaque participant détecte immédiatement toute tenta-
tive de tricherie.

Exercice 7 (Preuve à divulgation nulle 1 )

Paul prétend avoir résolu la grille de sudoku #2349 du journal l’Univers. Un problème de sudoku
se présente sous la forme d’une grille de dimension 9 × 9, dont certaines cases sont pré-remplies avec
1. L’exercice est tirée de R. Gradwohl, M. Naor, B. Pinkas and, G. Rothblum, Cryptographic and Physical Zero-
knowledge Proof Systems for Solutions of Sudoku Puzzles. Theory Comput. Syst. 44(2) : 245-268 (2009) [Link]
[Link]/~naor/PAPERS/sudoku_abs.html

5
des entiers entre 1 et 9. Une solution au problème est l’attribution d’un entier ∈ {1, . . . , 9} à chaque
case non pré-remplie de telle sorte que chaque ligne, colonne ou sous grille 3 × 3 ne comporte pas
deux fois le même entier. Victoria a néanmoins quelques doutes et souhaiterait que Paul lui montre
sa solution afin de pouvoir vérifier ses dires. Au lieu de cela, Paul propose d’effectuer le protocole
suivant :
— Paul dessine au sol une grille de taille 9 × 9. Sur chaque case, il dépose 3 cartes. Si la case
correspond à une case pré-remplie du problème, les trois cartes sont déposées faces ouvertes ;
leur valeur est celle indiquée dans la case correspondante. Sinon, les trois cartes sont déposées
faces cachées.
— Victoria Pour chaque ligne/colonne/sous-grille, choisit (aléatoirement) une des trois cartes
de chaque case dans la ligne/colonne/sous-grille correspondante.
— Paul rassemble les cartes choisies par Victoria en tas : un tas par ligne/colonne/sous-grille.
Il mélange ensuite chacun des tas séparément.
— Victoria récupère les tas et vérifie qu’aucun d’entre eux ne contient deux cartes de même
hauteur. Si c’est le cas, Victoria accepte l’affirmation de Paul et rejette sinon.
1. Montrer que si Paul a effectivement résolu la grille, et que Paul et Victoria suivent le proto-
cole, Victoria accepte toujours. Le système de preuve est dit consistant.
2. Supposer que Paul ne connaît pas la solution du problème. Montrer que Victoria accepte
avec probabilité au plus 1/3, même si Paul ne respecte pas le protocole. Bonus : montrer que
cette probabilité est en fait au plus 1/9. Le protocole est dit robuste : Victoria rejette avec
une probabilité non nulle les assertions fausses.
3. En déduire un protocole dans lequel Victoria accepte avec probabilité < 1/310 lorsque Paul
ne connaît pas la solution.
4. Démontrer que le système de preuve est à divulgation nulle : le protocole ne révèle rien sur
la solution du problème, même si Victoria ne respecte pas sa partie du protocole.
Un procédé de mise en gage est la donnée d’un algorithme Commit qui prend en paramètre des
couples ∈ M × K et vérifie les propriétés
— Engagement Il n’existe pas m 6= m′ ∈ M, k, k′ ∈ K tels que Commit(m, k) = Commit(m′ , k′ ).
— Dissimulation Étant donné Commit(m, k), le problème de calculer m (ou toute fonction non
triviale f (m)) est difficile.
5. Supposer l’existence de procédés d’engagement. Donner un protocole de preuve à divulga-
tion nulle pour le problème du sudoku qui repose sur de tels procédés plutôt que sur la
manipulation de paquets de cartes.
6. Le problème sudoku est NP-complet 2 . Paul prétend qu’un graphe G est 3-coloriable. Peut-il
le démontrer à Victoria sans indiquer comment le 3-colorier ?

2. Takayuki Yato, Complexity and Completeness of Finding Another Solution and its Application to Puzzles,
Master thesis, U. of Tokyo, Jan 2003 [Link]