Modèles pour la sécurité Master INPG-UJF SCCI
TD - Construction d’une fonction de hachage
Une fonction de hachage h est une fonction de E ⊂ {0, 1}∗ dans F ⊂ {0, 1}m :
h : E ⊂ {0, 1}∗ −→ F ⊂ {0, 1}m
où m est un entier fixé (par exemple m = 128 pour h = MD5).
Une fonction de hachage est dite résistante aux collisions si il est difficile (i.e. extrêmement
coûteux) de trouver (x, y) ∈ E 2 avec x 6= y tels que: h(x) = h(y).
Cet exercice construit une telle fonction de hachage à partir d’une fonction à sens unique (ici le
logarithme discret).
I. Construction d’une fonction de hachage : {0, 1}2m −→ {0, 1}m
Soit p un grand nombre premier tel que q = p−1 2
soit aussi premier. On note Fp = Z/p.Z et F∗p le
groupe multiplicatif ({1, 2, . . . , p − 1}, ×mod p ). On définit de même Fq et F∗q .
Soient α et β deux éléments primitifs (i.e. générateurs) de F∗p . On suppose que α, β et p sont
publics (connus de tout le monde) et on définit h1 par :
h1 : Fq × Fq → Fp
(x1 , x2 ) 7→ αx1 .β x2 mod p
Soit λ l’entier de F∗q égal au logarithme discret de β en base α : αλ = β mod p.
Dans toute cette question, on suppose que λ n’est pas connu et extrêmement coûteux à calculer.
Pour montrer que h1 est résistante aux collisions, on procède comme suit:
• On suppose que l’on connaît une collision pour h1 , i.e.
∃(x1 , x2 , x3 , x4 ) ∈ {0, 1, . . . , q − 1}4 tels que (x1 , x2 ) 6= (x3 , x4 ) et h1 (x1 , x2 ) = h1 (x3 , x4 )
• et on montre qu’on peut alors facilement calculer λ. Pour cela, on définit
d = pgcd(x4 − x2 , p − 1).
Nota Bene. On rappelle que p et q sont premiers et que p = 2q + 1.
1
1. Quels sont les diviseurs de p − 1 ? En déduire d ∈ {1, 2, q, p − 1}.
p − 1 = 2q et q est premier donc ses diviseurs sont {1, 2, q, 2q = p − 1}.
Comme d est un diviseur de p − 1, on en déduit d ∈ {1, 2, q, p − 1}.
2. Justifier −(q − 1) ≤ x4 − x2 ≤ q − 1; en déduire que d 6= q et d 6= p − 1.
Comme 0 ≤ x2 , x4 ≤ q − 1 , on a −(q − 1) ≤ x4 − x2 ≤ q − 1.
Or q est premier; on en déduit que (x4 − x2 ) est premier avec q, donc d 6= q.
3. Montrer que α(x1 −x3 ) ≡ β (x4 −x2 ) mod p.
Evident : αx1 β x2 ≡ αx3 β x4 mod p ⇐⇒ α(x1 −x3 ) ≡ β (x4 −x2 ) mod p
4. On suppose ici d = 1; montrer qu’alors λ = (x1 − x3 ).(x4 − x2 )−1 mod (p − 1).
Si d = 1, soit u = (x4 − x2 )−1 mod (p − 1) : u.(x4 − x2 ) = 1 + k.(p − 1) Alors β (x4 −x2 ).u
mod p ≡ β 1+k(p−1) mod p ≡ β mod p (d’après le théorème de Fermat).
Remplaçant dans 3., on obtient : β = α(x1 −x3 ).u mod p soit λ = (x1 − x3 ).u mod p − 1, cqfd.
5. On suppose ici d = 2 et on pose u = (x4 − x2 )−1 mod q.
5.a. Justifier que β q = −1 mod p; en déduire β u.(x4 −x2 ) = ±β mod p.
5.b. Montrer qu’on a : λ = u.(x1 − x3 ) mod p − 1 ou bien λ = u.(x1 − x3 ) + q mod p − 1.
5.a. Comme d = 2 et p − 1 = 2.q, on a x4 − x2 premier avec q d’où u.(x4 − x2 ) = 1 + k.q.
D’où β (x4 −x2 ).u mod p ≡ β 1+kq mod p ≡ β.(β q )k mod p. Or q = p−1 2
et β est un primitif mod p.
p−1
p−1 q (x −x ).u
D’où β = 1 mod p et β = β 2 = −1 mod p. Finalement β 4 2
= (−1)k .β mod p, cqfd.
(x1 −x3 ).u
5.b. Remplaçant dans 3., on obtient : β = ±α mod p soit β = α(x1 −x3 ).u+δ.q mod p avec
δ ∈ {0, 1}. On a donc δ = 0, i.e. λ = u.(x1 − x3 ) mod p − 1 ou sinon δ = 1, i.e. λ = u.(x1 − x3 ) + q
mod p − 1, cqfd.
6. Conclure en donnant un algorithme qui prend en entrée une collision (x1 , x2 ) 6= (x3 , x4 ) et
qui retourne λ.
Majorer le coût de cet algorithme et en déduire que h1 est résistante aux collisions.
D’après les questions précédentes, on a l’algorithme suivant :
AlgoCalculLogBeta( p, α, β, ;x1 , x2 , x3 , x4 ) {
q = (p − 1)/2;
d = pgcd(x4 − x2 , p − 1) ;
if (d == 1) {
u = (x4 − x2 )−1 mod (p − 1);
λ = (x1 − x3 ).u mod p − 1;
2
}
else {// ici d == 2
u = (x4 − x2 )−1 mod q;
λ = (x1 − x3 ).u mod p − 1;
if (ExpoMod( α, λ, p ) == −β) λ = λ + q ;
}
return λ ;
}
Le coût se ramène à des opérations modulo p − 1, p et q. Donc en O(log1+ p), ce qui est faible
même pour p grand (1024 bits par exemple). Autrement dit, si on connaît une collision pour h1 ,
alors on peut facilement calculer le logarithme discret de β, ce qui contredit l’hypothèse que λ est
très coûteux à calculer.
Par suite, on en déduit que, sous l’hypothèse que λ est très coûteux à calculer, alors h1 est
résistante aux collisions.
II. Extension à une fonction de hachage : {0, 1}∗ −→ {0, 1}m
On suppose donnée une fonction de hachage h1 : {0, 1}2m → {0, 1}m résistante aux collisions
(comme celle de la partie I par exemple) :
h1 : {0, 1}m × {0, 1}m → {0, 1}m
(x1 , x2 ) 7→ h1 (x1 , x2 )
i
A partir de h1 , on définit de manière récursive hi : {0, 1}2 m −→ {0, 1}m par:
2
i−1
hi : {0, 1}2 m −→ {0, 1}m
(x1 , x2 ) 7→ h1 (hi−1 (x1 ), hi−1 (x2 ))
7. Soient (x1 , x2 , x3 , x4 ) ∈ F4q ; expliciter h2 (x1 , x2 , x3 , x4 ) en fonction de h1 .
On a
h2 : ({0, 1}m )4 → {0, 1}m
(x1 , x2 , x3 , x4 ) 7→ h1 (h1 (x1 , x2 ), h1 (x3 , x4 ))
8. Montrer que h2 est résistante aux collisions. Indication : on pourra procéder par l’absurde
en montrant que si l’on connaît une collision pour h2 alors on peut facilement calculer une collision
pour h1 .
Si on a une collision sur h2 , alors ∃x 6= y : h2 (x) = h2 (y). On a deux cas:
• soit h1 (x1 , x2 ) 6= h1 (y1 , y2 ) ou h1 (x3 , x4 ) 6= h1 (y3 , y4 ) : alors comme h1 (x1 , x2 ), h1 (x3 , x4 )) =
h1 (y1 , y2 ), h1 (y3 , y4 )) on a trouvé une collision sur h1 .
• Sinon, supposons par exemple (x1 , x2 ) 6= (y1 , y2 ) (on peut s’y ramener par symétrie). Alors
comme h1 (x1 , x2 ) = h1 (y1 , y2 ), on a trouvé une collision sur h1 .
Comme on suppose que h1 est résistante aux collisions, on en déduit h2 résistante aux collisions.
3
9. Généraliser en justifiant que hi est résistante aux collisions.
Par récurrence, on montre que si hi est résistante aux collisions, alors hi+1 est aussi résistante
aux collisions.
Ceci est vrai pour i = 1. Similairement à la question précédente, on montre que si on trouve une
collision pour hi+1 , alors on construit aussi une collision pour hi .
Comme h1 est résistante aux collisions par hypothèse, alors hi est résistante aux collisions pour
tout i ≥ 2.
10. Combien d’appels à la fonction h1 sont effectués lors d’un appel à hi ?
En déduire que le calcul du hachage d’une séquence de n bits a un coût O(n).
Soit C(i)Ple nombre d’appels à h1 lors de l’exécution de hi . On a C(i) = 2.C(i − 1) + 1 =
2i .C(0) + i−1 k i
k=0 2 = 2 − 1.
Pour un mot de n bits, on appelle donc n/m fois h1 , dont le coût est en O(m1+ ). Par suite le
coût est en O(n.m ) ce que l’on peut assimiler à O(n) puisque m est fixé donc constant.
11. Comment peut-on étendre cette méthode pour construire une fonction de hachage sans
collision de {0, 1}∗ −→ {0, 1}m ?
n
Si n est la taille du message, soit i tel que 2i .m = n, i.e. i = dlog2 m e. On hache le message avec
hi .
Ce procédé nécessite de connaître la taille du message, donc ne marche pas à la volée. Une autre
alternative, plus efficace, est d’utiliser le protocole de Merkle-Damgard comme vu en cours.
