TD : Cryptographie
Christophe Ritzenthaler
Exercices
Un protocole d’échange
Alice veut envoyer à Bob le message x ∈ {0, 1}n . Alice (resp. Bob) possède une clé
secrète a (resp. b) de même longueur que x. Ils effectuent le protocole suivant :
1. Alice envoie A1 = x ⊕ a à Bob.
2. Bob envoie B1 = A1 ⊕ b à Alice.
3. Alice envoie A2 = B1 ⊕ a à Bob.
Montrer que Bob peut retrouver le message x. Montrer que si Oscar a intercepté tous
les échanges, il peut également retrouver x.
Questions sur RSA
1. Peut-on avoir un exposant de chiffrement e pair pour RSA ?
2. Soit la clé publique n = 55, e = 13 pour RSA. Calculer la clé secrète d puis
i
déchiffrer y = 4. Pour indication 42 ≡ 16, 36, 31, 26, 16 (mod 55) pour i =
1, 2, 3, 4, 5.
Une attaque cyclique sur RSA
Soit (n, e) une clé publique pour RSA. Soit x ∈ (Z/nZ)∗ un texte clair et y son chiffré.
Montrer qu’il existe un entier k tel que
k
xe ≡ x (mod n)
et que
k−1
ye ≡x (mod n).
Pensez-vous qu’une telle attaque est dangereuse pour RSA ? Justifiez.
1
Une attaque sur les bits de plus haut poids
Soit p, q deux grands nombres premiers tels que p < q < 2p et n = pq. Soit (d, e) un
couple de clé privée/publique pour RSA tel que e < φ(n) et d < φ(n).
√
1. Montrer que p + q ≤ 3 n.
2. Montrer que si on note k = (ed − 1)/φ(n)
kn + 1 √
− d < 3 n.
e
3. On suppose jusqu’à la fin que e = 3. Montrer qu’alors k = 2.
4. Soit d0 = b kn+1 0
e c. Comparer d et d. En conclure qu’environ la première moitié
des bits de d ne sont pas des hard-core bits.
Partage d’un secret
Le protocole de partage d’un secret de Shamir est basé sur le lemme suivant
Lemme : Soient l ≤ t deux entiers positifs, p un nombre premier et (xi , yi ) ∈ Z/pZ,
1 ≤ i ≤ l des couples tels que les xi sont distincts et non nuls. Alors il y a exactement
pt−l polynômes P ∈ Z/pZ[X] de degré au plus t − 1 tel que P (xi ) = yi .
Nous présentons maintenant un protocole de partage d’un secret s ∈ Z/pZ entre
n personnes de telle sorte que t d’entre elles (mais pas moins) peuvent reconstituer le
secret initial.
1. Initialisation : soit p premier plus grand que n + 1 et xi ∈ Z/pZ n éléments
distincts. Le distributeur D publie les xi .
2. Le partage :
(a) D choisit secrètement aj ∈ Z/pZ, 1 ≤ j ≤ t − 1 et construit le polynôme
t−1
X
a(X) = s + aj X j .
j=1
(b) D calcule les parts yi = a(xi ) et les distribue secrètement à chaque membre
du groupe.
3. La reconstruction du secret : montrer que si t membres du groupe collaborent, ils
peuvent retrouver le secret.
4. Sécurité : supposons que m < t membres du groupe collaborent. Montrer que
pour tout s0 ∈ Z/pZ il existe exactement pt−m−1 polynômes a0 (X) ∈ Z/pZ[X] de
degré ≤ t − 1 tel que a0 (0) = s0 et a0 (xi ) = yi , 1 ≤ i ≤ m. En déduire que ces
membres ne peuvent pas obtenir d’information sur le secret s.
2
Signature ElGamal
Soit p un grand nombre premier et h une fonction de hachage à valeurs entières dans
[0, p − 2]. Soit g un élément primitif de G = (Z/pZ)∗ . On considère le protocole de
signature suivant pour Alice :
Clé publique : (p, g, b) avec b ≡ g a (mod p) ;
Clé secrète : a ∈ [0, p − 2];
Signature : y → (y, r, s) avec r ≡ g k (mod p), s ≡ k −1 (m − ra) (mod p − 1) avec
m = h(y) et k ∈ [1, p − 2] différent à chaque signature;
Vérification : on vérifie que 0 ≤ r ≤ p − 1. Si non, rejeter la signature ; calculer
m = h(y) ; calculer v ≡ g m (mod p) et w ≡ br rs (mod p) ; vérifier que v = w.
1. Rappeler les critères que doit remplir une signature.
2. Montrer que si la signature est correcte, on a bien v = w.
3. Quel élément un attaquant devrait-il calculer à priori pour signer des textes à la
place d’Alice ?
4. Quel est la taille du paramètre de sécurité p pour qu’une telle attaque soit impos-
sible de nos jours ?
5. Peut-on alors effectivement (i.e. en terme de temps de calcul) utiliser ce protocole
?
Dans la suite, nous allons voir certaines attaques contre ce protocole de signature
lorsqu’on oublie certaines des recommandations.
L’importance de k
Montrer que si Alice se sert deux fois du même k pour signer deux messages y1 et y2
différents, alors Oscar peut en général retrouver le secret a (On regardera l’expression
s).
L’importance de la condition 0 ≤ r ≤ p − 1
Supposons que notre protocole ne vérifie pas cette condition. On va montrer que Oscar
peut alors créer des falsifications sélectives, i.e. des signatures de nouveaux messages
ayant un sens à partir d’une ancienne signature. Soit donc (y, r, s) une signature valide
produite par Alice. Oscar souhaite signer un message y 0 avec la signature d’Alice. Oscar
calcule :
u ≡ h(y 0 )h(y)−1 (mod p − 1).
Il calcule ensuite
s0 ≡ su (mod p − 1).
3
Il trouve r0 tel que
r0 ≡ ru (mod p − 1), r0 ≡ r (mod p).
1. Montrer comment et sous quelles conditions il peut réaliser tous ces calculs.
2. Vérifier que (y 0 , r0 , s0 ) est une signature valide.
3. Montrer que si h est sans collision alors la condition 0 ≤ r ≤ p − 1 empêche la
falsification.
L’importance de la fonction h
Supposons que Alice n’utilise pas de fonction de hachage, i.e. m = y dans notre proto-
cole. Oscar peut alors réaliser une autre falsification comme suit :
1. Soit i, j des entiers tels que 0 ≤ i, j ≤ p − 2. On cherche r sous la forme r ≡ g i bj
(mod p).
2. Montrer que la relation v = w est équivalente à
g y−is ≡ br+js (mod p).
3. Ceci est le cas en particulier si
(
y − is ≡0 (mod p − 1)
.
r + js ≡0 (mod p − 1)
4. Donner la condition pour que ce système admette une solution puis déterminer
(r, s, y) en fonction de i, j.
5. Pourquoi cette falsification est moins puissante que la précédente ?
