Université Pierre et Marie Curie M1 Cryptographie Année 2010

Feuille d’exercices 4
Avertissement : tous les exercices ne seront pas traités durant les séances ; pour en suivre l’avancement veuillez
consulter mon site personnel dans la rubrique Forum.
Exercice 1. — (Cryptosystème de Massey-Omura) Alice souhaite envoyer un message à Bob codé par un
élément m d’un groupe cyclique G d’ordre n. Ils utilisent le cryptosystème (sans clé) suivant :
1. Alice choisit secrètement un entier xA tel que 1 < xA < n et xA ∧ n = 1, et elle envoie à Bob l’élément
a = mxA .
2. Bob choisit secrètement un entier xB tel que 1 < xB < n et xB ∧ n = 1, et il renvoie à Alice l’élément
b = axB .
3. Alice calcule l’entier yA tel que 1 < yA < n et xA yA ≡ 1 mod n, et elle renvoie à Bob l’élément c = byA .
4. Bob calcule l’entier yB tel que 1 < yB < n et xB yB ≡ 1 mod n, et détermine cyB .
(a) Montrer que l’on a m = cyB .
(b) On prend G = F∗19 . Supposons qu’Alice choisisse l’entier xA = 5 et qu’elle envoie à Bob a = 2. Trouver
l’élément m correspondant.
Exercice 2. — (Système RSA) Soit n un entier ≥ 1. Alice utilise le cryptosystème RSA afin de se faire envoyer
des messages codés par des éléments de Z/nZ. Soit (e, n) sa clé publique.
1. Déterminer sa clé secrète dans chacun des cas suivants :
n o
(e, n) ∈ (5, 35), (139, 265), (31, 3599) .

2. Avec (e, n) = (31, 3599), elle reçoit le cryptogramme 2 + nZ. Quel est le message envoyé ? Soient p et q deux
nombres premiers distincts congrus à 2 modulo 3. Posons
2(p − 1)(q − 1) + 1
n = pq et e = (e est un entier).
3
3. Montrer que e est premier avec ϕ(n) et calculer son inverse modulo ϕ(n).
4. Alice choisit comme clé publique le couple (e, n) = (107, 187). Elle reçoit le cryptogramme 9 + nZ. Quel est
le message envoyé ?
Exercice 3. — (Protocole de Diffie-Hellman) Alice et Bob décident d’utiliser ce protocole pour se fabriquer
une clé secrète. Pour cela, ils rendent public le couple (K, α) où
K = F3 [X]/(X 3 + 2X + 1) et α = X + (X 3 + 2X + 1).
1. Vérifier que K est un corps et que α est un générateur de K ∗ . Conformément à ce protocole, Alice choisit
un entier a compris entre 2 et 25, par exemple a = 9, et transmet α9 à Bob. Ce dernier choisit un entier b
compris entre 2 et 25 et lui renvoie l’élément αb = 2 + α + 2α2 .
2. Quelle est la clé secrète d’Alice et Bob ? On déterminera ses coordonnées dans la base (1, α, α2 ) de K sur F3 .
Exercice 4. — (Algorithme de El Gamal) Alice souhaite se faire envoyer des messages confidentiellement en
utilisant cet algorithme. Elle considère pour cela le corps
K = F2 [X]/(X 4 + X + 1).
Soit α la classe de X modulo (X 4 + X + 1).
1. Justifier que K est un corps et montrer que α est un générateur de K ∗ . Alice rend public le triplet (K, α, α2 +
1), et Bob envoie des messages à Alice en utilisant cette clé publique.
2. Bob veut coder le message 1 + α pour l’envoyer à Alice. Conformément à l’algorithme, il choisit un entier x
compris entre 2 et 14, par exemple x = 3. Que transmet-il à Alice ?
3. Vous interceptez le message (α3 , α3 + α2 + α). Quel était le message envoyé par Bob ?

1
2

Exercice 5. — (Sac à dos)

1. Pour les suites d’entiers et ¿ volumes À V suivants, résoudre le problème du sac à dos correspondant :
(2, 3, 7, 20, 35, 69) et V = 45, (1, 2, 5, 9, 20, 49) et V = 73,
(1, 3, 7, 12, 22, 45) et V = 67, (4, 5, 10, 30, 50, 101) et V = 186.
2. Soit (vi )i≥0 une suite d’entiers positifs telle que l’on ait vi+1 > 2vi pour tout i. Montrer qu’elle est super
croissante.
3. Montrer que la suite d’entiers strictement positifs super croissante dont chaque terme est le plus petit possible
est la suite (2i )i≥0 .
Exercice 6. — (Sac à dos de Merkle-Hellman) Alice et Bob utilisent le cryptosystème du sac à dos de Merkle-
Hellman pour communiquer. L’alphabet utilisé est l’alphabet usuel, chaque lettre étant codée par un entier écrit en
binaire avec cinq composantes (ε4 ε3 ε2 ε1 ε0 )2 (on a A=(00000)2 , · · · , Z=(11001)2 ). Les unités de message sont des
mots de trois lettres (ils ont donc quinze composantes). Les notations étant celles figurant dans le paragraphe 7 du
chapitre IV du cours, Alice choisit la suite d’entiers (4, 5, 12, 23, 45), ainsi que m = 400 et a = 381.
1. Vérifier que ces données sont conformes au principe d’utilisation de ce cryptosystème.
2. Déterminer la clé publique d’Alice.
3. Bob veut envoyer à Alice le message OUI. Indiquer le procédé qu’il doit suivre et comment Alice retrouve-t-elle
le message.
Exercice 7. — Soit p un nombre premier de Mersenne : on a p = 2` − 1 où ` est premier. Posons
K = Fp [X]/(X 2 + 1).
Notons i la classe de X modulo (X 2 + 1).
1. Montrer que K est ¿ le À corps à p2 éléments.
2. Soient a et b deux éléments de Fp tels que a2 +b2 soit un générateur de F∗p (cette hypothèse n’est pas restrictive
car tout élément de Fp est somme de deux carrés). Montrer que a + ib est un générateur de K ∗ .
3. En déduire que 4 + i et 3 + 2i sont des générateurs du groupe F∗312 .
4. Deux personnes Alice et Bob souhaitent se construire une clé de chiffrement commune en utilisant le protocole
de Diffie-Hellman dans le groupe F∗312 , avec le générateur 4 + i.
(a) Alice choisit secrètement l’entier 193 et Bob envoie à Alice l’élément 1 + 19i. Quelle est la clé commune
de chiffrement ?
(b) Quel élément de K ∗ doit envoyer Alice à Bob pour qu’il connaisse la clé ?
 3

1. Solutions
1 1) On a les égalités ¡ ¢y ¡ ¢y ¡ ¢x y
cyB = byA B = axB yA B = mxA yA B B
Il existe deux entiers naturels u et v tels que l’on ait xA yA = 1 + un et xB yB = 1 + vn. Soit e l’élément neutre de
G. Puisque G est d’ordre n, on a mun = mvn = e. Par suite, on obtient
¡ ¢1+vn
cyB = m1+un = m.
2) On a dans cet exemple n = 18. Supposons que Bob choisisse l’élément xB = 7. Dans ce cas, il renvoie à Alice
7
l’élément b = 2 = 14 mod 19. On vérifie que l’on a yA = 11 car on a 5 × (−7) + 18 × 2 = 1. Alice renvoie ainsi à
11
Bob l’élément c = 14 . Par ailleurs, vu l’égalité 7 × 13 − 5 × 18 = 1, on a yB = 13. Ainsi Bob effectue l’opération
(1411 )13 modulo 19. On a 11 × 13 ≡ 17 mod 18. D’après le petit théorème de Fermat, on a donc
(1411 )13 ≡ 1417 mod 19.
On en déduit que l’on a m = 14−1 mod 19 = 15 mod 19 (on a −4 × 14 + 3 × 19 = 1) i.e. m = 15 ∈ F∗19 .
2 1) On a 35 = 5 × 7 et ϕ(n) = 24. Par ailleurs, on a 1 = 5 × 5 − 24, donc 5 est son propre inverse modulo 24. Dans
ce cas, la clé secrète est donc (5, 24).
On a 265 = 5 × 53 et ϕ(n) = 208. Il s’agit de déterminer l’inverse de 139 modulo 208. On peut utiliser pour cela
l’algorithme d’Euclide, ce qui conduit à l’égalité 1 = 3 × 139 − 2 × 208. La clé secrète est donc (3, 208).
On a 3599 = 59 × 61, d’où ϕ(n) = 3480. En utilisant l’algorithme d’Euclide, on obtient directement l’égalité
4 × 3480 − 449 × 31 = 1,
de sorte que l’inverse de 31 modulo 3480 est 3031. La clé secrète est ainsi (3031, 3480). 2) Le message m envoyé est
(2 + nZ)3031 . Afin de déterminer son représentant compris entre 1 et n, on procède comme suit. On remarque que
l’on a 3031 = 7 × 433. On a 59 ≡ 3 mod 8, donc 2 n’est pas un carré modulo 59, d’où 229 ≡ −1 mod 59 (critère
d’Euler). On en déduit que l’on a
¡ ¢7
2433 ≡ 227 = −4−1 ≡ 44 mod 59 et 2433 ≡ 447 ≡ 23 mod 59.
Par ailleurs, on a
¡ ¢7
2433 ≡ 213 ≡ 18 mod 61 et 2433 ≡ 187 ≡ −2 mod 61.
On est donc amené à chercher l’entier N tel que 1 ≤ N ≤ 3599 vérifiant les congruences
(1) N ≡ 23 mod 59 et N ≡ −2 mod 61.
On utilise pour cela l’algorithme donné par le théorème chinois. On a la relation de Bézout
30 × 59 − 29 × 61 = 1,
¡ ¢ ¡ ¢
d’où l’on déduit que l’entier −2 30 × 59 − 23 29 × 61 = −44227 vérifie les congruences (1). Il en résulte que
N = 2560. Le message m envoyé est donc
m = 2560 + nZ.
3) On a ϕ(n) = (p − 1)(q − 1) i.e. on a 3e = 2ϕ(n) + 1, donc e est premier avec ϕ(n) et 3 est l’inverse de e modulo
ϕ(n). 4) On a n = 11 × 17, ϕ(n) = 160. D’après la question 3, l’inverse de 107 modulo 160 est 3. Le message m
qui lui a été envoyé est donc
m = 93 mod 187 = 168 mod 187.
3 1) Le polynôme X 3 + 2X + 1 ∈ F3 [X] est irréductible sur F3 car il n’a pas de racines dans F3 et son degré est 3,
donc K est un corps de cardinal 27. Le groupe K ∗ est d’ordre 26. Les ordres de ses éléments autres que l’élément
neutre, sont donc 2, 13 ou 26. En fait, −1 est le seul élément d’ordre 2 de K ∗ , car par exemple ±1 sont les seules
racines du polynôme X 2 − 1 ∈ K[X]. On a α3 = α − 1, d’où α9 = α3 − 1 (car K est de caractéristique 3) i.e.
α9 = α + 1, d’où α12 = α2 − 1 puis α13 = −1 et notre assertion. 2) On a α4 = α2 − α et α5 = 2α2 + α + 2, d’où
¡ ¢5
b = 5. La clé secrète d’Alice et Bob est donc α9 = α45 . Déterminons ses coordonnées dans la base (1, α, α2 ) de
K sur F3 . On a α26 = 1, d’où α45 = α19 = α−7 . Par ailleurs, on a α6 = α2 + α + 1, d’où α7 = α2 − α − 1. De
l’égalité
X(X 3 + 2X + 1) − (X 2 + X + 1)(X 2 − X − 1) = 1,
 4

on déduit alors que l’on a

α45 = −(α2 + α + 1).
4 1) Le polynôme X 4 + X + 1 ∈ F2 [X] n’a pas de racines dans F2 et n’est pas divisible par X 2 + X = 1 qui est
le seul polynôme irréductible de degré 2 de F2 [X], donc X 4 + X + 1 est irréductible sur F2 et K est un corps. Le
groupe K ∗ est d’ordre 15. On a α4 = α + 1, d’où l’on ¡déduit que α3 et α5 sont
¢ distincts
¡ de 1, ce ¢qui entraı̂ne que
l’ordre de α dans K ∗ est 15. 2) Il transmet le couple α3 , (1 + α)(1 + α2 )3 i.e. α3 , α3 + α2 + 1 . 3) On cherche
l’entier a tel que 1 ≤ a ≤ 14 et que 1 + α2 = αa . On remarque pour cela que l’on a (1 + α2 )2 = 1 + α4 = α. De
l’égalité (1 + α2 )16 = 1 + α2 (on a x16 = x pour tout x ∈ K), on déduit alors que l’on a 1 + α2 = α8 i.e. on a a = 8.
On a
αxa = α24 = α9 .
Par définition, si m est le message envoyé par Bob, on a
mαax = α3 + α2 + α.
¡ ¢14
L’inverse de αax i.e. de α9 est α9 = α126 = α8×15+6 = α6 , autrement dit, on a
¡ 9 ¢−1
α = α 2 + α3 .
On a donc m = (α + α2 + α3 )(α2 + α3 ), d’où m = α2 .
5 Soient k un entier ≥ 1 et (vi )0≤i≤k−1 une suite d’entiers super croissante. Rappelons que par définition on a
i−1
X
(1) 0 < v0 < v1 < · · · < vk−1 et vi > vj pour tout i tel que 0 ≤ i ≤ k − 1.
j=0

Pour tout entier naturel V (le volume), le problème du sac à dos relatif à V et à une telle suite (vi ) est facile à
résoudre. Il s’agit de déterminer des entiers ai égaux à 0 ou 1, s’ils existent, tels que l’on ait
k−1
X
V = ai vi .
i=0
Il existe au plus une solution. Pour résoudre ce problème, on utilise l’algorithme décrit dans l’alinéa 2 du paragraphe
6 du chapitre IV. 1) La suite (2, 3, 7, 20, 35, 69) est super croissante et n = (010110)2 est la solution (qui correspond
à l’égalité 45 = 35 + 7 + 3). Il en est de même de la suite (1, 2, 5, 9, 20, 49). On constate qu’avec l’entier V = 73 le
problème n’a pas de solution.
La suite (1, 3, 7, 12, 22, 45) n’est pas super croissante. Dans ce cas, il y a exactement deux solutions (110000)2 et
(101110)2 .
La suite (4, 5, 10, 30, 50, 101) est super croissante et l’on trouve la solution (111010)2 . 2) Il s’agit de démontrer que
la suite (infinie) (vi ) satisfait la condition (1). On a v1 > v0 . Si pour i ≥ 1, vi est plus grand que la somme des i
premiers termes, on a les inégalités
X i
vi+1 > 2vi > vj ,
j=0
d’où le résultat par récurrence. 3) On vérifie d’abord que la suite (2i )i≥0 est super croissante. Par ailleurs, soit
(ai )i≥0 la suite super croissante telle que pour tout i le terme ai soit le plus petit possible. Remarquons que cette
suite existe. En effet, on prend a0 = 1 et pour tout i ≥ 1, ai est le plus petit entier naturel vérifiant la condition
i−1
X
0 < a0 < · · · < ai−1 < ai et ai > aj .
j=0

Vérifions que l’on a ai = 2i . C’est vrai si i = 0. Soit i un entier ≥ 0. Supposons que l’on ait aj = 2j pour tout j
tel que 0 ≤ j ≤ i. On a alors
Xi
ai+1 > 2j = 2i+1 − 1.
j=0
Par suite, le plus petit entier ai+1 possible est 2i+1 , d’où l’assertion.
 5

6 Rappelons d’abord le principe de ce cryptosystème (paragraphe 7 du chapitre IV). Chaque utilisateur choisit une
suite d’entiers super croissante (v0 , v1 , · · · , vk−1 ), un entier m tel que
k−1
X
(1) m> vi ,
i=0
et un entier a tel que 1 ≤ a < m et pgcd(a, m) = 1. Il détermine ensuite l’entier b tel que
1 ≤ b < m et ab ≡ 1 mod m,
et pour tout i = 0, · · · , k − 1, l’entier wi tel que
(2) 1 ≤ wi < m et wi ≡ avi mod m.
Il garde secret les entiers vi , m, a et b. Sa clé publique est la suite (w0 , · · · , wk−1 ). Une personne souhaitant lui
envoyer un message binaire P = (εk−1 · · · ε0 )2 , lui transmet l’entier
k−1
X
C= εi wi .
i=0
Afin de décrypter ce message, l’utilisateur calcule l’entier V tel que
0 ≤ V < m et V ≡ bC mod m.
L’égalité
k−1
X
(3) V = εi vi ,
i=0
et l’algorithme du sac à dos super croissant, appliqué avec la suite (v0 , v1 , · · · , vk−1 ), lui permet alors de retrouver
le message P .

1) On vérifie que la suite (v0 , v1 , v2 , v3 , v4 ) = (4, 5, 12, 23, 45) est super croissante, que l’on a a = 381 = 3 × 127,
puis
X4
m = 400 > vi = 89 et pgcd(381, 400) = 1.
i=0
Les données proposées sont donc conformes au principe d’utilisation du cryptosystème. 2) On détermine l’entier b
tel que 1 ≤ b < 400 et 381b ≡ 1 mod 400. Ë l’aide de l’algorithme d’Euclide, on trouve que l’on a b = 21. Il s’agit
ensuite de déterminer les entiers wi définis par l’égalité (2) ci-dessus. On vérifie alors que la clé publique d’Alice
est
(w0 , w1 , w2 , w3 , w4 ) = (324, 305, 172, 363, 345).
3) On vérifie que l’on a
O = (01110)2 , U = (10100)2 , I = (01000)2 .
Pour chacun des trois messages (ε4 ε3 ε2 ε1 ε0 )2 ci-dessus à envoyer, Bob transmet donc à Alice successivement le
message
X4
εi wi .
i=0
Il transmet ainsi les messages cryptés
C1 = 363 + 172 + 305 = 840, C2 = 345 + 172 = 517, C3 = 363.
Afin de retrouver le mot OUI, Alice calcule les trois entiers Vi tels que
0 ≤ Vi < 400 et Vi ≡ 21Ci mod 400.
On trouve
V1 = 40, V2 = 57, V3 = 23.
Les égalités (3) qui correspondent à chacun des Vi sont respectivement
40 = 23 + 12 + 5, 57 = 45 + 12, 23 = 23,
 6

et Alice peut alors retrouver le mot OUI.

7 1) On a p ≡ 3 mod 4, donc −1 n’est pas un carré dans Fp i.e. X 2 + 1 est irréductible dans Fp [X]. Il en résulte
que K est un corps à p2 éléments (qui est unique à isomorphisme près). 2) Soit m un entier ≥ 1. Démontrons que
l’on a l’implication
(1) (a + ib)m ∈ Fp =⇒ p + 1 divise m.
Soit d le pgcd de m et p + 1. Il existe u et v ∈ Z tels que d = um + v(p + 1). Puisque K ∗ est d’ordre p2 − 1, on a
¡ ¢p−1
(a + ib)p+1 = 1, donc (a + ib)p+1 appartient Fp . Il résulte que l’on a
¡ ¢u ¡ ¢v
(2) (a + ib)m (a + ib)p+1 = (a + ib)d ∈ Fp .
Vérifions alors que l’on a d = p + 1. Supposons le contraire. Puisque p + 1 est une puissance de 2, d divise alors
p+1
2 . D’après (2), on en déduit que
p+1
(a + ib) 2 ∈ Fp .
Par ailleurs, le carré de cet élément est a2 + b2 . En effet, p étant congru à 3 modulo 4, on a ip = −i, et vu que l’on
a ap = a et bp = b, on obtient
(a + ib)p+1 = (a + ib)p (a + ib) = (ap + bp ip )(a + ib) = (a − ib)(a + ib) = a2 + b2 .
Cela conduit à une contradiction, car a2 + b2 étant un générateur de F∗p , ce n’est pas un carré dans Fp (un carré
est d’ordre divisant p−1
2 ). On a donc d = p + 1, par suite p + 1 divise m. Cela prouve l’implication (1). Considérons
alors un entier n ≥ 1 tel que
(a + ib)n = 1.
D’après (1), p + 1 divise n. Soit r ∈ Z tel que n = (p + 1)r. L’égalité (a + ib)p+1 = a2 + b2 entraı̂ne alors
(a2 + b2 )r = 1.
Puisque a2 + b2 est un générateur de F∗p , p − 1 divise r, donc p2 − 1 divise n. Ainsi a + ib est d’ordre p2 − 1, d’où
le résultat. 3) Il s’agit de démontrer que 13 et 17 sont des générateurs de F∗31 . Démontrons que tel est bien le cas
pour 13, l’argument pour 17 est analogue. On a (critère d’Euler)
³ 13 ´
1315 ≡ mod 31.
31
Par ailleurs, on a ³ 13 ´ ³ 31 ´ ³ 5 ´ ³ 13 ´ ³ 3 ´
= = = = = −1,
31 13 13 5 5
d’où la congruence
1315 ≡ −1 mod 31,
ce qui entraı̂ne l’assertion (le fait que 13 ne soit pas d’ordre 6 ni d’ordre 10 modulo 31 résulte alors des congruences
132 ≡ 14 mod 31 et 133 ≡ −4 mod 31). 4.1) Conformément au protocole de Diffie-Hellman, la clé commune de
chiffrement est
α = (1 + 19i)193 .
On a 193 = 6 × 31 + 7, d’où les égalités
α = (1 − 19i)6 (1 + 19i)7 = 216 (1 + 19i) = 2 + 7i.
4.2) Alice doit envoyer à Bob l’élément β = (4 + i)193 . On obtient
β = (4 − i)6 (4 + i)7 = 176 (4 + i) = 1 + 8i.