Fonction de hachage itérative
Le message complété M' est découpé en n blocs de 512 bits consécutifs, soient M(1) , … , M(n). La concaténation est notée ||, on a :
- M' = M(1) || … || M(n).
L'algorithme itère une fonction de compression, soit compress : {0,1}160 × {0,1}512 → {0,1}160, et utilise un vecteur d'initialisation IV de 160 bits. Il produit une suite Hi de valeurs de chaînage de 160 bits, la dernière valeur étant le haché.
- H(0) := IV
- H(i+1) := compress(H(i), M(i+1)), pour 0≤ i < n
- SHA-1(M) = H(n).
Le vecteur d'initialisation de 160 bits IV est composé de 5 mots de 32 bits dont les valeurs sont données en hexadécimal (un chiffre hexadécimal représente 4 bits) dans les spécifications,.
Fonction de compression
Dans ce qui suit les opérations sur les mots de 32 bits utilisées sont notées :
- ∧ pour le ET bit à bit ;
- ∨ pour le OU bit à bit ;
- ⊕ pour le OU exclusif bit à bit ;
- ¬ pour le NON bit à bit ;
- + pour l'opération sur les mots correspondant à l'addition arithmétique modulo 232 (l'addition informatique de deux entiers non signés de 32 bits) ;
- x <<< s pour le décalage circulaire de s bits vers la gauche des bits de x, où x est un mot de 32 bits et 0 ≤ s < 32).
En notant << et >> les décalages ordinaires vers la gauche et vers la droite :
- << : décalage binaire à gauche, x << s s'obtient en supprimant les s bits de gauche de x et ajoutant s bits à zéro à droite ;
- >> : décalage binaire à droite, x >> s s'obtient en supprimant les s bits de droite de x et ajoutant s bits à zéro à gauche ;
alors x <<< s = (x << s) ∨ (x >> (32-s)).
La fonction de compression prend en entrée une valeur de chaînage H, analysée en 5 mots de 32 bits, et un bloc de 512 bits B analysé en 16 mots de 32 bits.
La première phase est une phase d'expansion : le bloc B est étendu en un tableau W de 80 mots de 32 bits par la précédure suivante :
fonction expand(B){ Le bloc B de 512 bits et vu comme un tableau de 16 mots de 32 bits B[0] … B[15]
W est un tableau de 80 mots de 32 bits W[0] … W[79]
pour i de 0 à 79 {
si i < 16
alors W[i]:= B[i]
sinon W[i] := (W[i – 3] ⊕ W[i – 8] ⊕ W[i – 14] ⊕ W[i – 16]) <<< 1 Ce décalage circulaire vers la
gauche de 1 bit est la seule
différence avec SHA-0 sur
l'ensemble de l'algorithme
}
renvoyer(W)
}
fonction compress(H,B) {
(a0,b0,c,d0,e0) := H H est analysé comme 5 mots de 32 bits
(a,b,c,d,e) = (a0,b0,c0,d0,e0)
W := expand(B)
pour t de 0 à 79 {
temp := (a <<< 5) + f(t, b, c, d) + e + K[t] + W[t]
(a, b, c, d, e) := (temp, a, b <<< 30, c, d)
}
H := (a+a0, b+b0, c+c0, d+d0, e+e0)
renvoyer(H)
}
La fonction f en jeu à chacun des 80 tours est calculée par opérations bit à bit sur ses 3 derniers arguments et prend 3 formes différentes, en fonction du numéro de tour (premier argument), :
0 ≤ t < 20 : f(t, b, c, d) = (b ∧ c) ⊕ (¬b ∧ d) (= (b ∧ c) ∨ (¬b ∧ d) )
20 ≤ t < 40 : f(t, b, c, d) = b ⊕ c ⊕ d
40 ≤ t < 60 : f(t, b, c, d) = (b ∧ c) ⊕ (b ∧ d) ⊕ (c ∧ d) (= (b ∧ c) ∨ (b ∧ d) ∨ (c ∧ d ))
60 ≤ t < 80 : f(t, b, c, d) = b ⊕ c ⊕ d
Les constantes de 32 bits K[t] prennent 4 valeurs différentes suivant le numéro de tour t, elles sont définies dans les spécifications,.
