Specifications SHA-1

Spécifications SHA-1

SHA-1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l'histoire, la cryptanalyse et d'autres aspects liés à cette fonction, voir l'article principal : SHA-1.

Sommaire

1 Introduction
2 Symboles et termes utilisés
- 2.1 Paramètres
- 2.2 Symboles
3 Opérations sur les mots
4 Fonctions et constantes
- 4.1 Fonctions
- 4.2 Constantes
5 Prétraitement
6 Calcul du condensé (haché)
7 Liens externes

Introduction

Ce texte est adapté du document officiel FIPS 180-2 (Secure Hash Standard)^[1]. Il décrit les spécifications du standard SHA-1, dont l'objectif est de calculer une représentation condensée de données électroniques (message).
Quand un message inférieur à $264$ bits est passé à l'algorithme implémentant SHA-1, on obtient en sortie ce qu'on appelle un haché, ou condensé de ce message. La longueur d'un condensé obtenu via SHA-1 est de 160 bits.

Cet algorithme peut être découpé en deux phases : le prétraitement et le calcul du condensé.

Le prétraitement implique

de compléter le message par des informations le rendant compatible avec l'algorithme SHA-1 (remplissage)
son analyse pour le découper en blocs de 512 bits
l'initialisation de variables de travail

Le calcul du condensé génère un tableau à partir du message complété, puis le transforme via l'utilisation de fonctions, de constantes, d'opérations binaires détaillées plus loin. L'ensemble effectué de manière itérative permet de générer des séries de valeurs de hachage à chaque tour. Le condensé final est le dernier état de ces valeurs de hachage.

Les caractéristiques de SHA-1 sont les suivantes :

taille du message : $264$ bits maximum
taille des blocs : 512 bits
taille des mots : 32 bits
taille du condensé : 160 bits
niveau de sécurité : $280$ bits (attaque anniversaire); sécurité ramenée à $269$ , puis $263$ , et enfin $252$ d'après des travaux très récents, ce qui rend SHA-1 plus vulnérable (cf. informations générales sur SHA-1).

Symboles et termes utilisés

Paramètres

a, b, c, ..., h = variables de travail (en l'occurrence des mots de w bits), utilisées dans le calcul des hachés.

$H (i)$ = la valeur de hachage n°i. $H (0)$ est la valeur initiale du hachage. $H (N)$ est la dernière valeur de hachage.

$H_j^{(i)}$ = le mot (w bits) n°j de la valeur de hachage n°i, où $H_0^{(i)}$ est le mot de poids le plus fort (à gauche) de la valeur de hachage i.

$K t$ = constantes itératives selon la valeur de t, utilisées dans le calcul de hachage

k = nombre de 0 ajoutés au message lors du prétraitement (complément)
l = longueur du message M, en bits
m = nombre de bits contenus dans un bloc, soit 512 bits
M = message à traiter
$M (i)$ = bloc n°i (m bits), du message M
$M_j^{(i)}$ = mot (w bits) n°j, du bloc (m bits) n°i, du message M
n = nombre de bits de décalage ou de rotation à appliquer au mot quand associé à une fonction binaire
N = nombre de blocs de m bits contenus dans le message M après complément
T = variable temporaire, mot de w bits, utilisée dans le calcul de condensé
w = nombre de bits contenus dans un mot, soit 32 bits.
$W t$ = le mot n°t du tableau déduit du message

Symboles

La notation hexadécimale utilisée ici sera: $0x$

exemple: $H_0^{(0)} = \mbox{0x12ab34ef}$

$\wedge$ = opération binaire AND
$\vee$ = opération binaire OR
$\oplus$ = opération binaire XOR
$\lnot$ = complément binaire
$+$ = addition modulo $2 w$
$< <$ = décalage binaire à gauche, où $x < < n$ s'obtient en supprimant les n bits de gauche de x et ajoutant n zéros à droite.
$> >$ = décalage binaire à droite, où $x > > n$ s'obtient en supprimant les n bits de droite de x et ajoutant n zéros à gauche.

Opérations sur les mots

Elles utilisent les conventions suivantes :

opérations binaires bit à bit (cf. symboles)
addition modulo $2 w$ , soit $232$

L'opération

x + y

est définie comme suit. Soient deux mots

x et y

représentant les nombres entiers

X et Y

, tels que $0 \le X < 2^{32}$ et $0 \le Y < 2^{32}$ , on a

Z

le résultat de l'addition modulo

232

X et Y

$Z = (X + Y) \mbox{ mod }2^{32} \mbox{, }0 \le Z < 2^{32}$ . On convertit

Z

en un mot

z

, et on définit alors

z = x + y

l'opération de rotation binaire par la gauche $R O T L n (x)$ , où x est un mot de 32 bits et $0 \le n \le 32$ , est définie par: $ROTL^n(x) = (x << n) \vee (x >> 32 - n)$

Fonctions et constantes

Fonctions

Cette section décrit les fonctions utilisées lors du calcul des valeurs de hachage. SHA-1 utilise une succession de fonctions logiques $f_0, f_1, ..., f_{79}~$ . Chaque fonction $f_t~$ , où $0 \le t \le 79$ , travaille sur trois mots de 32 bits, x, y, z et génère un mot de 32 bits en sortie. La fonction $f_t~$ est définie comme suit:

$f_t(x,y,z) = \left\{\begin{matrix} Ch(x,y,z) = (x \wedge y) \oplus (\lnot x \wedge z), & \mbox{si }0 \le t \le 19 \\ Parity(x,y,z) = x \oplus y \oplus z, & \mbox{si }20 \le t \le 39 \\ Maj(x,y,z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z), & \mbox{si }40 \le t \le 59 \\ Parity(x,y,z) = x \oplus y \oplus z, & \mbox{si }60 \le t \le 79 \end{matrix}\right.$

Constantes

SHA-1 utilise quatre valeurs réparties dans les 80 constantes $K_0, K_1, ..., K_{79}~$ , d'après la règle

$K_t = \left\{\begin{matrix} \mbox{0x5a827999}, & \mbox{si }0 \le t \le 19 \\ \mbox{0x6ed9eba1}, & \mbox{si }20 \le t\le 39 \\ \mbox{0x8f1bbcdc}, & \mbox{si }40\le t\le 59 \\ \mbox{0xca62c1d6}, & \mbox{si }60\le t\le 79\end{matrix}\right.$

Prétraitement

Cette opération se déroule en trois étapes : compléter le message M, découper le résultat en blocs, et initialiser les valeurs de hachage $H^{(0)}~$

Complément de M

Il s'agit ici d'ajouter des informations à M pour qu'il soit d'une taille multiple de 512 bits.
pour ce faire, l'on ajoute un bit "1" à la fin du message M, puis k zéros, où k est la plus petite solution non négative de l'équation: l + 1 + k = 448 mod 512
On ajoute alors un bloc de 64 bits correspondant à la représentation binaire de l.

Exemples :

M = "abc", l = 8 x 3 = 24, k = 448 - (l + 1) = 448 - (24 + 1) = 423

On ajoute "1", puis quatre cent vingt trois "0", puis 64 bits finissant par "011000" (pour 24) à M.

On obtient alors un message complété à 512 bits.

M quelconque tel que l = 500 bits, k = 448 - (l + 1) = 448 - (500 + 1) = -53

Comme k ne peut pas être négatif, on lui ajoute 512 en prenant en compte le modulo de l'équation, pour obtenir

k = 459

On ajoute "1", puis quatre cent cinquante neuf "0", puis 64 bits finissant par "111110100" (pour 500) à M.

On obtient alors un message complété à 512 bits.

Découpage en blocs

Le message complété est découpé en N blocs de 512 bits, notés $M^{(1)}, M^{(2)}, ..., M^{(N)}~$ . Chaque bloc de 512 bits est ensuite découpé en 16 mots de 32 bits, notés $M_0^{(i)}, M_1^{(i)}, ..., M_{15}^{(i)}$ .

Initialisations

Les cinq variables suivantes sont affectées de valeurs initiales comme suit :

$H_0^{(0)} = \mbox{0x67452301}$
$H_1^{(0)} = \mbox{0xefcdab89}$
$H_2^{(0)} = \mbox{0x98badcfe}$
$H_3^{(0)} = \mbox{0x10325476}$
$H_4^{(0)} = \mbox{0xc3d2e1f0}$

Calcul du condensé (haché)

Pour ce traitement on utilisera

un tableau de 80 mots, notés $W_0, W_1, ..., W_{79}~$
cinq variables notées $a, b, c, d, e ~$
cinq variables contenant les valeurs de hachage, notées $H_0^{(i)}$ et initialisées précédemment en $H_0^{(0)}$

Ces variables contiendront itérativement de nouvelles valeurs de hachage, $H^{(i)}~$ , pour finalement contenir le condensé de M, dans $H^{(N)}~$ .

une variable T, mot de 32 bits

On traite successivement les N blocs de M selon les étapes suivantes

Pour i = 1 à N
{

1. On remplit le tableau $W_t \mbox{ si }0 \le t \le 79$ , selon

$W_t=\left\{\begin{matrix} M_t^{(i)}, & 0\le t\le 15 \\ \\ ROTL^1 \left( W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16} \right), & 16\le t\le 79 \end{matrix}\right.$

2. On initialise a,b, c, d et e avec les valeurs de hachage du tour précédent

$a = H0^{(i-1)}~$

$b = H1^{(i-1)}~$

$c = H2^{(i-1)}~$

$d = H3^{(i-1)}~$

$e = H4^{(i-1)}~$

3. Pour t = 0 à 79

{

( $f_t~$ notée ci-après est la fonction logique, décrite plus haut)

$T = ROTL^5(a) + f_t(b,c,d)+ e + K_t + W_t ~$

$e = d~$

$d = c~$

$c = ROTL^{30}(b)~$

$b = a~$

$a = T~$

}

4. Calcul des valeurs de hachage intermédiaires

$H_0{(i)} = a + H_0^{(i-1)}$

$H_1{(i)} = b + H_1^{(i-1)}$

$H_2{(i)} = c + H_2^{(i-1)}$

$H_3{(i)} = d + H_3^{(i-1)}$

$H_4{(i)} = e + H_4^{(i-1)}$

}

Après répétition de quatre étapes ci-dessus pour les N blocs du message M, (i.e., après traitement de $M^{(N)}~$ ), le condensé de 160 bits de M est obtenu par concaténation des valeurs

$H_0^{(N)}||H_1^{(N)}||H_2^{(N)}||H_3^{(N)}||H_4^{(N)}$

Remarque : il existe d'autres méthodes de calcul du condensé SHA-1 donnant des résultats identiques.

Liens externes

↑ FIPS PUB 180-2, Secure Hash Standard (incluant SHA-1, SHA-256, SHA-384 et SHA-512)

RFC 3174, US Secure Hash Algorithm 1 (SHA1)
[1], L'attaque récente sur SHA-1 présentée à Eurocrypt 2009.

Fonctions de hachage cryptographiques

Modifier

Algorithmes : AR | Boognish | FFT-hash | HAS-160 | Haval | MD2 | MD4 | MD5 | MD6 | N-hash | PANAMA | RIPEMD | RIPEMD-128 | RIPEMD-160 | RIPEMD-256 | SHA-0 | SHA-1 | SHA-224 | SHA-256 | SHA-384 | SHA-512 | Snefru | StepRightUp | Tiger | VSH | Whirlpool

Cryptanalyse : Paradoxe des anniversaires | Linéaire / Différentielle | Attaque par force brute | Effet avalanche | Pseudo-collision

Portail de la cryptologie

Ce document provient de « Sp%C3%A9cifications SHA-1 ».

Catégorie : Algorithme de hachage

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Specifications SHA-1 de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

Spécifications sha-1 — SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1 Introduction 2 Symboles et… … Wikipédia en Français
Specifications SHA-256 — Spécifications SHA 256 SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1… … Wikipédia en Français
Spécifications sha-256 — SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1 Introduction 2 Symboles et… … Wikipédia en Français
Spécifications SHA-1 — SHA 1 est une fonction de hachage cryptographique qui fournit une empreinte de 160 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article principal : SHA 1. Sommaire 1 Introduction 2 Symboles et… … Wikipédia en Français
Spécifications SHA-256 — SHA 256 est une fonction de hachage cryptographique dérivée de SHA 1 qui fournit une empreinte de 256 bits. Pour l histoire, la cryptanalyse et d autres aspects liés à cette fonction, voir l article SHA 256. Sommaire 1 Introduction 2 Symboles et… … Wikipédia en Français
Sha-1 — Une itération de SHA 1 avec deux rotations vers la gauche et une fonction non linéaire qui dépend du numéro d itération, deux autres variables interviennent à chaque tour SHA 1 (Secure Hash Algorithm) est une fonction de hachage cryptographique… … Wikipédia en Français
SHA-256 — (Secure Hash Algorithm) est une fonction de hachage cryptographique conçue par la National Security Agency des États Unis (NSA), et publiée en 2000. Elle produit un résultat (appelé « hash » ou condensat) de 256 bits et dérive du… … Wikipédia en Français
Sha-256 — (Secure Hash Algorithm) est une fonction de hachage cryptographique conçue par la National Security Agency des États Unis (NSA), et publiée en 2000. Elle produit un résultat (appelé « hash » ou condensat) de 256 bits et dérive du SHA 1 … Wikipédia en Français
SHA-1 — Une itération de SHA 1 avec deux rotations vers la gauche et une fonction non linéaire qui dépend du numéro d itération, deux autres variables interviennent à chaque tour SHA 1 (Secure Hash Algorithm) est une fonction de hachage cryptographique… … Wikipédia en Français
Sha Tin Racecourse — (zh t|t=沙田馬場) is one of the two racecourses for horse racing in Hong Kong. It is located in Sha Tin in the New Territories. It is managed by Hong Kong Jockey Club.Penfold Park is encircled by the track.HistoryIt was first built in 1978 (under the … Wikipedia

Dictionnaires et Encyclopédies sur 'Academic'

Specifications SHA-1

Spécifications SHA-1

Sommaire

Introduction