Spécifications 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 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-256, 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-256, on obtient en sortie ce qu'on appelle un haché, ou condensé de ce message. La longueur d'un condensé obtenu via SHA-256 est de 256 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-256 (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-256 sont les suivantes :

taille du message : $264$ bits maximum
taille des blocs : 512 bits
taille des mots : 32 bits
taille du condensé : 256 bits
niveau de sécurité : $2128$ bits (attaque anniversaire)

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 \le 2^{32}\mbox{ et } 0 \le Y \le 2^{32}$ , on a

Z

le résultat de l'addition modulo

232

X et Y

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

Z

en un mot

z

, et on définit alors

z = x + y

l'opération de décalage binaire à droite $SHR^n(x)~$ , où x est un mot de 32 bits et $0 \le n \le 32$ , est définie par : $SHR^n(x) = x >> n~$
l'opération de rotation binaire par la droite $ROTR^n(x)~$ , où x est un mot de 32 bits et $0 \le n \le 32$ , est définie par : $ROTR^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-256 utilise 6 fonctions logiques travaillant sur des mots de 32 bits notés x, y, z. Le résultat de chacune de ces fonctions est un nouveau mot de 32 bits en sortie.

$Ch(x,y,z) = (x \wedge y) \oplus (\lnot x \wedge z)$

$Maj(x,y,z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z)$

$\sum^{\{256\}}_0(x) = ROTR^2(x) \oplus ROTR^{13}(x) \oplus ROTR^{22}(x)$

$\sum^{\{256\}}_1(x) = ROTR^6(x) \oplus ROTR^{11}(x) \oplus ROTR^{25}(x)$

$\sigma^{\{256\}}_0(x) = ROTR^7(x) \oplus ROTR^{18}(x) \oplus SHR^3(x)$

$\sigma^{\{256\}}_1(x) = ROTR^{17}(x) \oplus ROTR^{19}(x) \oplus SHR^{10}(x)$

Constantes

SHA-256 utilise 64 valeurs constantes de mots de 32 bits, notés $K^{\{256\}}_0, K^{\{256\}}_1, ..., K^{\{256\}}_{63}~$ . ces nombres représentent les 32 premiers bits de la partie décimale des racines cubiques des 64 premiers nombres premiers. Les valeurs suivantes sont exprimées en notation hexadécimale (base 16).

428a2f98	71374491	b5c0fbcf	e9b5dba5	3956c25b	59f111f1	923f82a4	ab1c5ed5
d807aa98	12835b01	243185be	550c7dc3	72be5d74	80deb1fe	9bdc06a7	c19bf174
e49b69c1	efbe4786	0fc19dc6	240ca1cc	2de92c6f	4a7484aa	5cb0a9dc	76f988da
983e5152	a831c66d	b00 327c8	bf597fc7	c6e00bf3	d5a79 147	06ca6351	14292967
27b70a85	2e1b2138	4d2c6dfc	53380d13	650a7354	766a0abb	81c2c92e	92722c85
a2bfe8a1	a81a664b	c24b8b70	c76c51a3	d192e819	d6 990 624	f40e3585	106aa070
19a4c116	1e376c08	2748774c	34b0bcb5	391c0cb3	4ed8aa4a	5b9cca4f	682e6ff3
748f82ee	78a5636f	84c87 814	8cc70 208	90befffa	a4506ceb	bef9a3f7	c67 178f2

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 huit variables suivantes sont affectées de valeurs initiales comme suit :

$H_0^{(0)} = \mbox{0x6a09e667}$
$H_1^{(0)} = \mbox{0xbb67ae85}$
$H_2^{(0)} = \mbox{0x3c6ef372}$
$H_3^{(0)} = \mbox{0xa54ff53a}$
$H_4^{(0)} = \mbox{0x510e527f}$
$H_5^{(0)} = \mbox{0x9b05688c}$
$H_6^{(0)} = \mbox{0x1f83d9ab}$
$H_7^{(0)} = \mbox{0x5be0cd19}$

Calcul du condensé (haché)

Pour ce traitement on utilisera

un tableau de 64 mots, notés $W_0, W_1, ..., W_{63}~$
huit variables notées $a, b, c, d, e, f, g, h~$
huit 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)}~$ .

deux variables, notées $T 1 et T 2$ , mots 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 63$ , selon

$W_t=\left\{\begin{matrix} M_t^{(i)}, & 0\le t\le 15 \\ \\ \sigma_1^{\{256\}} \left( W_{t-2} \right) + W_{t-7} + \sigma_0^{\{256\}} \left( W_{t-15} \right) + W_{t-16}, & 16\le t\le 63 \end{matrix}\right.$

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

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

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

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

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

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

$f = H_5^{(i-1)}~$

$g = H_6^{(i-1)}~$

$h = H_7^{(i-1)}~$

3. Pour t = 0 à 63

{

$T_1 = h + \sum^{\{256\}}_1(e) + Ch(e,f,g) + K^{\{256\}}_t + W_t ~$

$T_2 = \sum^{\{256\}}_0(a) + Maj(a,b,c) ~$

$h = g~$

$g = f~$

$f = e~$

$e = d + T_1~$

$d = c~$

$c = b~$

$b = a~$

$a = T_1 + T_2~$

}

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)}$

$H_5{(i)} = f + H_5^{(i-1)}$

$H_6{(i)} = g + H_6^{(i-1)}$

$H_7{(i)} = h + H_7^{(i-1)}$

}

Après répétition des quatre étapes ci-dessus pour les N blocs du message M, (i.e., après traitement de $M^{(N)}~$ ), le condensé de 256 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)}||H_5^{(N)}||H_6^{(N)}||H_7^{(N)}$

Liens externes

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

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-256 ».

Catégorie : Algorithme de hachage

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Spécifications sha-256 de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

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
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-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
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… … 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-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
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-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 hash functions — The SHA hash functions are a set of cryptographic hash functions designed by the National Security Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm. The five algorithms … Wikipedia

Dictionnaires et Encyclopédies sur 'Academic'

Spécifications sha-256