EXAMEN DE CRYPTOGRAPHIE

Examen de Sécurité Informatique
Durée : 1h30 - Documents non autorisés Exercice 1 (7pts)
1. On considère le crypto système (sans clé) suivant :
Un grand nombre premier p est public et les unités de message sont des
entiers m, 1 ? m < p.
Si Alice veut envoyer un message m à Bob, la marche à suivre est la
suivante.
(On admet que le canal de transmission n'introduit pas d'erreurs)
i. Alice choisit un entier a tel que 1 ? a < p et pgcd(a ,p - 1) = 1.
Alice calcule l'inverse a' de a dans Z/(p - 1)Z. Alice envoie C = ma
mod p à Bob.
ii. Bob choisit un entier b tel que 1 ? b < p et pgcd(b , p - 1) = 1. Bob
calcule l'inverse b' de b dans Z/(p - 1)Z, il renvoie D = Cb mod p à
Alice.
iii. Alice renvoie E = Da' mod p à Bob.
iv. Bob calcule Eb' mod p et retrouve m. Pourquoi ?
2. Soit p = 31.
a- Montrer que 2 et 4 sont des générateurs de (Z/31Z).
b- Soit A l'ensemble des entiers x, 1 ? x < 31, tels que pgcd(x , 30) = 1
(x premier avec 30). Calculer le cardinal de A puis énumérer tous ses
éléments, ainsi que leurs inverses mod 30.
c- Trouver b ( A, b ( 1, tel que 4b = 4 mod 31.
d- On utilise le cryptosystème précédent avec p = 31. Un pirate
intercepte les échanges entre Alice et Bob et connaît C = 4, D = 4 et
E = 8. Montrer que le pirate peut facilement retrouver m, dont on
donnera la valeur. Exercice 2 : (6pts)
Soit p et q deux nombres premiers distincts tels que :
p (2 mod 3 et q ( 2 mod 3.
1. Montrer que 2(p - 1)(q - 1) + 1 est divisible par 3.
2. On pose k = ((pq). Calculer l'inverse d dans Z/kZ de
[pic]
3. Soit p = 17 et q = 11. On pose n = p q. Alice et Bob communiquent en
utilisant l'algorithme RSA.
a- La clé publique de Bob est (107, n). Quelle est sa clé secrète ?
b- Alice veut transmettre le message M à Bob, Bob reçoit C = 9. Quel
était le message M envoyé par Alice ?
Exercice 3 : (7pts)
Pour la signature ElGamal, Alice choisit un nombre premier p, un
générateur g dans Zp , un nombre aléatoire a tel ue a < p - 1 et calcule y=
ga mod p. sa clé publique est (p, g, y), sa clé privée est a.
Pour signer un message m