Specifications SHA-256

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

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
  1. de compléter le message par des informations le rendant compatible avec l'algorithme SHA-256 (remplissage)
  2. son analyse pour le découper en blocs de 512 bits
  3. 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.

Kt = 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.
Wt = 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 2w
< < = 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 2w, 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 de 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 T1 et T2, 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

  1. 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

Architecture : Remplissage | Fonction de compression | Construction de Merkle-Damgard | Construction de Miyaguchi-Preneel | Construction de Matyas-Meyer-Oseas | Construction de Davies-Meyer

  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « Sp%C3%A9cifications SHA-256 ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • 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-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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”