Fonction de Hachage - N

FSTS
Fonction de hachage
Master : Réseaux et sécurité informatique (RSI)
Pr. M. A. Elomary
18 octobre 2022
Pr. M.A Elomary FSTS

FSTS
Table des matières
1 Fonction de hachage
Construction de fonctions de hachage
Fonctions de hachage classiques
SHA-1
Ripemd-160
Fonction de hachage & logarithme discret

FSTS
Fonction de hachage
Fonction de hachage
Fonction de hachage
En informatique traditionnelle, une fonction de hachage (traduction
discutable de hash function) et un algorithme simple aidant à gérer
certaines bases de données. La place où est inséré un article dans
une telle base est déterminée par la valeur calculée par cette
fonction. Cette valeur dépend en général de la totalité de l’article afin
que le remplissage de la base de données se répartisse de façon
équilibrée même si de nombreux articles se ressemblent.
La notion de fonction de hachage en cryptographie est plus
restrictive. C’est une faction d’un ensemble infini M (I’espace des
messages) dans un ensemble fini E (l’espace des empreintes),
facilement calculable, et possédant une ou plusieurs des propriétés
décrites ci-après. En général, l’espace des messages est l’ensemble
{0, 1}∗ des mots binaires et l’espace des empreintes celui des trains
de longueur fixée, comme {0, 1}128 ou {0, 1}160 .

FSTS
Fonction de hachage
Fonction de hachage
Définition
• Une fonction de hachage h est dite à sens unique si, pour
essentiellement toutes les valeurs y de l’espace des empreintes, il est
difficile de trouver un message x tel que h(z) = y.
• Une fonction de hachage h est dite faiblement résistante aux
collisions si, pour essentiellement chaque message x, il est difficile de
trouver un message x0 6= x ayant même empreinte h(x) = h (x0 ).
• Une fonction de hachage h est dite (fortement) résistante aux
collisions s’il est difficile de trouver deux messages x et x0 ayant
même empreinte h(x) = h (x0 )

FSTS
Fonction de hachage
La propriété de résistance forte aux collisions implique clairement la

propriété de résistance faible. Si on suppose en plus que les images
réciproques ne sont jamais des singletons, elle implique aussi la
propriété de sens unique.
Le ”paradoxe des anniversaires” montre qu’une recherche de
collision h(x) =√h (x0 ), où ni x ni x0 ne sont imposés, est seulement de
complexité O( m), si m est le cardinal de l’ensemble des valeurs de
h. II existe donc des fonctions de hachage qui sont faiblement
résistantes aux collisions maie pour lesquelles la propriété de
résistance forte n’est pas vérifiée.

FSTS
Fonction de hachage
Une fonction de hachage permet d’obtenir à partir d’une donnée de

longueur quelconque, une empreinte de taille réduite et fixe, mais
caractéristique de la donnée (penser aux empreintes digitales), et
pratiquement impossible à reproduire à partir d’une donnée
différente. Les fonctions de hachage jouent donc un rôle important en
authentification et signature. Mais, de plus en plus, elles trouvent
aussi des applications dans les autres domaines de la cryptographie
moderne. (Bien que leur construction, pour des raisons de rapidité,
fasse en général intervenir des techniques semblables à celles de la
cryptographie symétrique.)

FSTS
Fonction de hachage
Fonction de hachage
De nombreuses fonctions de hachage sont construites à partir d’une
fonction de compression f (une fonction de {0, 1}n dans {0, 1}m avec
m < n) selon le schéma suivant. Le message x est complété par un
procédé réversible afin que sa longueur soit un multiple de n − m (par
exemple en ajoutant un 1 puis un nombre adéquat de 0), puis il est
découpé en blocs xi (1 6 i 6 t) de longueur n − m. L’empreinte h(x) est
alors calculée selon les formules
H0 = IV, Hi = f (xi kHi−1 ) , pour 1 6 i 6 t1 h(x) = Ht
où IV (Initial Value) désigne une constante dans {0, 1}m .

FSTS
Fonction de hachage
Fonction de hachage
On peut imaginer d’utiliser une fonction de chiffrement par blocs pour
construire une fonction de compression utilisable dans le schéma
ci-dessus. Sont adaptées les fonctions de chiffrement pour lesquelles
la longueur des blocs est égale à celle des clés et assez grande (par
exemple 160) pour que la recherche de collisions soit difficile. Un
certain nombre de telles constructions se sont révélées non sûres,
mais les quatre suivantes semblent être sûres.
f (xkk) = ek (x) ⊕ x
f (xkk) = ek (x) ⊕ x ⊕ k
f (xkk) = ek (x ⊕ k) ⊕ x
f (xkk) = ek (x ⊕ k) ⊕ x ⊕ k

FSTS
Fonction de hachage
En modifiant légèrement ce schéma, on obtient avec certitude une

fonction de hachage résistante aux collisions pour peu que la fonction
de compression le soit :
Théorème : Damgárd-Merkle
Soit f une fonction de compression de (0, 1)n dans (0, 1)m avec
n > m + 1 résistante aux collisions. Si les messages sont complétés
en un nombre entiers de blocs de longueur n − m − 1 par un procédé
révisible alors on obtient une fonction de hachage résistante aux
collisions en posant
Hi = f 0m+1 kx1 , Hi = f (Hi−1 k1kxi−1 ) pour 2 6 i 6 t.


FSTS
Fonction de hachage
SHA-1
Elle attribue une empreinte de 160 bits, A chaque message binaire
de longueur inférieure à 264 bits (ce qui est énorme, environ 1 milliard
de gigaoctets). En voici une description succincte. Le document
official la décrivant est le FIPS 180 − 1 du NIST.
Le message m à traiter est d’abord complété pour obtenir un
message M :
M = mk10 . . . 0k`
où ` est la longueur de m exprimé en binaire sur 64 bits, et où le
nombre de 0 est choisi dans l’intervalle [0, 511] de telle façon que la
longueur de M soit un multiple de 512 bits. Ensuite, M est divisé en
blocs de 512 bits (soit 16 mots de 32 bits) :
M = M1 k · · · kMn .

FSTS
Fonction de hachage
Algorithme correspondant à la fonction SHA-1

Entrée : Entier n et blocs M1 à Mn de longueur 512 .
Sortie : Empreinte de 160 bits.
K0 := 5A827999, K1 := 6ED9EBA1, K2 := 8F1BBCDC, K3 :=

CA62C1D6
A := 67452301, B := EFCDABB9,
C := 98BADCFE, D := 10325476, E := C3D2E1F0
Pour i de 1 à n répéter
Pour j de 0 à 15 définir Wj par Mi = W0 k · · · kW15
Pour j de 16 à 79 répéter
Wj := (Wj−3 ⊕ Wj−8 ⊕ Wj−14 ⊕ Wj−16 ) 1
A0 := A, B0 = B, C0 := C D0 := D, E0 = E
t := [i/20]
E0 = A0 5 + ft (B0 , C0 , D0 ) + E0 + Wj + Kt
(A0 , B0 , C0 , D0 , E0 ) = (E0 , A0 , B0 30, C0 , D0 )
A := A + A0 , B := B + B0 , C := C + C0 , D := D + D0 , E :=
E + E0 Pr. M.A Elomary FSTS
FSTS
Fonction de hachage

K0 := 5A827999, K1 := 6ED9EBA1, K2 := 8F1BBCDC, K3 :=
CA62C1D6
A := 67452301, B := EFCDABB9,
C := 98BADCFE, D := 10325476, E := C3D2E1F0
Pour i de 1 à n répéter
Pour j de 0 à 15 définir Wj par Mi = W0 k · · · kW15
Wj := (Wj−3 ⊕ Wj−8 ⊕ Wj−14 ⊕ Wj−16 ) 1
A0 := A, B0 = B, C0 := C D0 := D, E0 = E
t := [i/20]
E0 = A0 5 + ft (B0 , C0 , D0 ) + E0 + Wj + Kt
(A0 , B0 , C0 , D0 , E0 ) = (E0 , A0 , B0 30, C0 , D0 )
A := A + A0 , B := B + B0 , C := C + C0 , D := D + D0 , E :=
E + E0
Retourner AkBkCkDkE
où les additions notées + entendent, modulo 232 et 00 le symbole
désigne une rotation à gauche. Quand
Pr. M.A Elomary FSTSaux ft , oe sont les fonctions
FSTS
Fonction de hachage
où les additions notées + entendent, modulo 232 et 00 le symbole

désigne une rotation à gauche. Quand aux ft , oe sont les fonctions
boréliennes suivantes, définies sur des mots de 32 bits :
f0 (B, C, D) = (B ∧ C) ∨ (B̄ ∧ D)
f1 (B, C, D) = f0 (B, C, D) = B ⊕ C ⊕ D
f2 (B, C, D) = (B ∧ C) ∨ (C ∧ D) ∨ (D ∧ B)

FSTS
Fonction de hachage

Le NIST a normalisé de nouvelles fonctions de hachage, nommées
SHA-256, SHA-384 et SHA-512, inspirées de SHA-1 mais produisant
des empreintes plus longues (les noms correspondant à la longueur
des empreints en bits). Ces nouvelles fonctions sont décrites dans le
draft FIPS 180-2.

FSTS
Fonction de hachage
Ripemd-160
Ripemd-160
Elle calcule elle aussi des empreintes de 160 bits et est dans sa
construction assez similaire à SHA-1.

FSTS
Fonction de hachage

Bien que trop lente pour être performante en pratique, la fonction
définie ci-après est une fonction de hachage dont la résistance forte
aux collisions est prouvée. Précisément, elle repose sur le problème
du logarithme discret.
Exemple : Soit p un nombre premier tel que q = (p − 1)/2 soit aussi

premier (impair) et soient α et β deux générateurs (individuellement)
de (Z/pZpZ)∗ . La fonction de Chaum/ van Heijst/Pfitzmann est définie
par (
Zq × Zq −→ (Z/pZ)∗
(x, y) −→ αx β y

FSTS
Fonction de hachage
Théorème
Toute collision dans la fonction de Chaum/ van Heijst/Pfitzmann
permet de calculer logα β.

Fonction de Hachage - N

Transféré par

Droits d'auteur :

Formats disponibles

Fonction de Hachage - N

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Fonction de Hachage - N

Transféré par

Droits d'auteur :

Formats disponibles

FSTS

Master : Réseaux et sécurité informatique (RSI)

Pr. M.A Elomary FSTS

Pr. M.A Elomary FSTS

Pr. M.A Elomary FSTS

Pr. M.A Elomary FSTS

Construction de fonctions de hachage

La propriété de résistance forte aux collisions implique clairement la

Pr. M.A Elomary FSTS

Construction de fonctions de hachage

Une fonction de hachage permet d’obtenir à partir d’une donnée de

Pr. M.A Elomary FSTS

Construction de fonctions de hachage

H0 = IV, Hi = f (xi kHi−1 ) , pour 1 6 i 6 t1 h(x) = Ht

où IV (Initial Value) désigne une constante dans {0, 1}m .

Pr. M.A Elomary FSTS

Construction de fonctions de hachage

Pr. M.A Elomary FSTS

Construction de fonctions de hachage

En modifiant légèrement ce schéma, on obtient avec certitude une

Hi = f 0m+1 kx1 , Hi = f (Hi−1 k1kxi−1 ) pour 2 6 i 6 t.

Pr. M.A Elomary FSTS

Fonctions de hachage classiques

Pr. M.A Elomary FSTS

Algorithme correspondant à la fonction SHA-1

K0 := 5A827999, K1 := 6ED9EBA1, K2 := 8F1BBCDC, K3 :=

Algorithme correspondant à la fonction SHA-1

Algorithme correspondant à la fonction SHA-1

où les additions notées + entendent, modulo 232 et 00 le symbole 

Pr. M.A Elomary FSTS

Fonctions de hachage classiques

Fonctions de hachage classiques

Pr. M.A Elomary FSTS

Pr. M.A Elomary FSTS

Fonction de hachage & logarithme discret

Fonction de hachage & logarithme discret

Exemple : Soit p un nombre premier tel que q = (p − 1)/2 soit aussi

Pr. M.A Elomary FSTS

Fonction de hachage & logarithme discret

Pr. M.A Elomary FSTS

Vous aimerez peut-être aussi

où les additions notées + entendent, modulo 232 et 00 le symbole