SHA-2

L'algorithme peut être découpé en deux phases

• Le prétraitement : le message est complété par remplissage comprenant la taille du message (renforcement de Merkle-Damgård) de façon à pouvoir le découper en blocs de 512 bits ;
• Le calcul du condensé par itération de la fonction de compression sur la suite des blocs obtenus en découpant le message (schéma itératif de Merkle-Damgård).

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

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

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

${\displaystyle 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
${\displaystyle M^{(i)}}$ = bloc n° i (m bits), du message M
${\displaystyle 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.
${\displaystyle W_{t}}$ = le mot n° t du tableau déduit du message

La notation hexadécimale utilisée ici sera: ${\displaystyle {\mbox{0x}}}$

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

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

Les opérations utilisées sont les suivantes :

• les opérations bit à bit sur les mots de 32 bits (voir le paragraphe #Symboles pour les notations utilisées) ;
• l'opération sur les mots correspondant à l’addition modulo 2³², c'est-à-dire que la somme z = x + y de deux mots x et y représentant des entiers naturels X et Y (0 ≤ X < 2³² et 0 ≤ Y < 2³²) est la représentation binaire de l'entier Z, tel que Z = X + Y mod 2³², 0 ≤ Z < 2³²,
• l'opération de décalage des bits à droite ${\displaystyle SHR^{n}(x)}$, où x est un mot de 32 bits et ${\displaystyle 0\leq n<32}$, est définie par :

  ${\displaystyle SHR^{n}(x)=x>>n}$ ;

• l'opération de rotation binaire vers la droite ${\displaystyle ROTR^{n}(x)}$, où x est un mot de 32 bits et ${\displaystyle 0\leq n<32}$, est définie par :

  ${\displaystyle ROTR^{n}(x)=(x>>n)\vee (x<<(32-n))}$.

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.

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

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

${\displaystyle \Sigma _{0}^{\{256\}}(x)=ROTR^{2}(x)\oplus ROTR^{13}(x)\oplus ROTR^{22}(x)}$

${\displaystyle \Sigma _{1}^{\{256\}}(x)=ROTR^{6}(x)\oplus ROTR^{11}(x)\oplus ROTR^{25}(x)}$

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

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

SHA-256 utilise 64 valeurs constantes de mots de 32 bits, notés ${\displaystyle K_{0}^{\{256\}},K_{1}^{\{256\}},...,K_{63}^{\{256\}}~}$. 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).

${\displaystyle K_{0}^{\{256\}},...,K_{7}^{\{256\}}}$	0x428a2f98	0x71374491	0xb5c0fbcf	0xe9b5dba5	0x3956c25b	0x59f111f1	0x923f82a4	0xab1c5ed5
${\displaystyle K_{8}^{\{256\}},...,K_{15}^{\{256\}}}$	0xd807aa98	0x12835b01	0x243185be	0x550c7dc3	0x72be5d74	0x80deb1fe	0x9bdc06a7	0xc19bf174
${\displaystyle K_{16}^{\{256\}},...,K_{23}^{\{256\}}}$	0xe49b69c1	0xefbe4786	0x0fc19dc6	0x240ca1cc	0x2de92c6f	0x4a7484aa	0x5cb0a9dc	0x76f988da
${\displaystyle K_{24}^{\{256\}},...,K_{31}^{\{256\}}}$	0x983e5152	0xa831c66d	0xb00327c8	0xbf597fc7	0xc6e00bf3	0xd5a79147	0x06ca6351	0x14292967
${\displaystyle K_{32}^{\{256\}},...,K_{39}^{\{256\}}}$	0x27b70a85	0x2e1b2138	0x4d2c6dfc	0x53380d13	0x650a7354	0x766a0abb	0x81c2c92e	0x92722c85
${\displaystyle K_{40}^{\{256\}},...,K_{47}^{\{256\}}}$	0xa2bfe8a1	0xa81a664b	0xc24b8b70	0xc76c51a3	0xd192e819	0xd6990624	0xf40e3585	0x106aa070
${\displaystyle K_{48}^{\{256\}},...,K_{55}^{\{256\}}}$	0x19a4c116	0x1e376c08	0x2748774c	0x34b0bcb5	0x391c0cb3	0x4ed8aa4a	0x5b9cca4f	0x682e6ff3
${\displaystyle K_{56}^{\{256\}},...,K_{63}^{\{256\}}}$	0x748f82ee	0x78a5636f	0x84c87814	0x8cc70208	0x90befffa	0xa4506ceb	0xbef9a3f7	0xc67178f2

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 ${\displaystyle H^{(0)}~}$

Il s'agit ici de compléter le message M pour qu'il soit d'une taille multiple de 512 bits. Le bourrage utilise la représentation binaire de l'entier l qui est la longueur en bits du message M (renforcement de Merkle-Damgård). Pour ce faire on ajoute successivement :

• un bit à 1 à la fin du message M,
• k bits à 0 de bourrage, où k est le plus petit entier naturel vérifiant l + 1 + k ≡ 448 mod 512
• un bloc de 64 bits qui donne la représentation binaire de l.

Exemples :

• Pour M = "abc", l = 3 × 8 = 24 bits, k ≡ 448 - (24 + 1) ≡ 423 mod 512, donc k= 423 ;
  • on ajoute à M
    • d'abord un bit à 1,
    • puis 423 bits à 0 ,
    • puis 64 bits représentant 24 en binaire, soit « 0000 ... 0000 0001 1000 »

  on obtient alors un message complété dont la longueur est le plus petit multiple de 512 bits supérieur à la longueur initiale de M.

• Pour M de longueur ${\displaystyle l=500}$ bits, k ≡ 448 - (500 + 1) ≡ -53 mod 512 ; donc k= 512 - 53 = 459 ;
  • on ajoute à M
    • d'abord un bit à 1,
    • puis 459 bits à 0,
    • puis 64 bits représentant 500 en binaire, soit « 0000 ... 0000 0001 1111 0100 »

  on obtient alors un message complété dont la longueur est supérieure de 512 bits au plus petit multiple de 512 bits supérieur à la longueur initiale de M.

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

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

${\displaystyle H_{0}^{(0)}={\mbox{0x6a09e667}}}$
${\displaystyle H_{1}^{(0)}={\mbox{0xbb67ae85}}}$
${\displaystyle H_{2}^{(0)}={\mbox{0x3c6ef372}}}$
${\displaystyle H_{3}^{(0)}={\mbox{0xa54ff53a}}}$
${\displaystyle H_{4}^{(0)}={\mbox{0x510e527f}}}$
${\displaystyle H_{5}^{(0)}={\mbox{0x9b05688c}}}$
${\displaystyle H_{6}^{(0)}={\mbox{0x1f83d9ab}}}$
${\displaystyle H_{7}^{(0)}={\mbox{0x5be0cd19}}}$

Pour ce traitement on utilisera

• un tableau de 64 mots, notés ${\displaystyle W_{0},W_{1},...,W_{63}~}$
• huit variables notées ${\displaystyle a,b,c,d,e,f,g,h~}$
• huit variables contenant les valeurs de hachage, notées ${\displaystyle H_{0}^{(i)}}$ et initialisées précédemment en ${\displaystyle H_{0}^{(0)}}$

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

• deux variables, notées ${\displaystyle T_{1}{\mbox{ 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 ${\displaystyle W_{t}}$ pour t de 0 à 63, selon

${\displaystyle W_{t}=\left\{{\begin{matrix}M_{t}^{(i)},&0\leq t\leq 15\\\\\sigma _{1}^{\{256\}}\left(W_{t-2}\right)+W_{t-7}+\sigma _{0}^{\{256\}}\left(W_{t-15}\right)+W_{t-16},&16\leq t\leq 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

${\displaystyle a=H_{0}^{(i-1)}~}$

${\displaystyle b=H_{1}^{(i-1)}~}$

${\displaystyle c=H_{2}^{(i-1)}~}$

${\displaystyle d=H_{3}^{(i-1)}~}$

${\displaystyle e=H_{4}^{(i-1)}~}$

${\displaystyle f=H_{5}^{(i-1)}~}$

${\displaystyle g=H_{6}^{(i-1)}~}$

${\displaystyle h=H_{7}^{(i-1)}~}$

3. Pour t de 0 à 63

{

${\displaystyle T_{1}=h+\Sigma _{1}^{\{256\}}(e)+Ch(e,f,g)+K_{t}^{\{256\}}+W_{t}~}$

${\displaystyle T_{2}=\Sigma _{0}^{\{256\}}(a)+Maj(a,b,c)~}$

${\displaystyle h=g~}$

${\displaystyle g=f~}$

${\displaystyle f=e~}$

${\displaystyle e=d+T_{1}~}$

${\displaystyle d=c~}$

${\displaystyle c=b~}$

${\displaystyle b=a~}$

${\displaystyle a=T_{1}+T_{2}~}$

}

4. Calcul des valeurs de hachage intermédiaires

${\displaystyle H_{0}^{(i)}=a+H_{0}^{(i-1)}}$

${\displaystyle H_{1}^{(i)}=b+H_{1}^{(i-1)}}$

${\displaystyle H_{2}^{(i)}=c+H_{2}^{(i-1)}}$

${\displaystyle H_{3}^{(i)}=d+H_{3}^{(i-1)}}$

${\displaystyle H_{4}^{(i)}=e+H_{4}^{(i-1)}}$

${\displaystyle H_{5}^{(i)}=f+H_{5}^{(i-1)}}$

${\displaystyle H_{6}^{(i)}=g+H_{6}^{(i-1)}}$

${\displaystyle 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 ${\displaystyle M^{(N)}~}$), le condensé de 256 bits de M est obtenu par concaténation des valeurs

${\displaystyle H_{0}^{(N)}||H_{1}^{(N)}||H_{2}^{(N)}||H_{3}^{(N)}||H_{4}^{(N)}||H_{5}^{(N)}||H_{6}^{(N)}||H_{7}^{(N)}}$

• (en) Henri Gilbert, Helena Handschuh : Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: 175-193
• Versions successives du Secure Hash Standard du NIST à partir de l'apparition de SHA-2 (voir aussi la page Secure Hashing)
  • FIPS 180-2 version d'août 2001
  • FIPS 180-3 version finale d'octobre 2008
  • FIPS 180-4 mars 2012

• Secure Hash Algorithm
• SHA-1
• SHA-3

• Calculateur en ligne Encodage de chaînes de caractères par les fonctions de hachage les plus utilisées.
• (fr) Calculatrice qui génère SHA-256 en ligne
• (fr) Calculatrice qui génère SHA-512 en ligne
• (en) Une implémentation open source en C++ Comporte toutes les variantes de l'algorithme.