Specifications SHA-256

SHA-256 is a cryptographic Fonction of chopping derived from SHA-1 which provides a print of 256 bits. For the history, the Cryptanalyse and other related aspects with this function, to see the article SHA-256.

Introduction

This text is adapted official document FIPS 180-2 (Secure Hash Standard) . It describes the specifications of the standard SHA-256 , whose objective is to calculate a condensed representation of electronic data (message).
When a message lower than $2^ {64}$ bits passed to the algorithm implementing SHA-256, one obtains at exit one what is called chopped, or condensed of this message. The length of a digest obtained via SHA-256 is of 256 bits.

This algorithm can be cut out in two phases: the pretreatment and the calculation of the digest.

the pretreatment implies

# to supplement the message by information making it compatible with algorithm SHA-256 (filling)

# its analysis to cut out it in blocks of 512 bits

# the initialization of variables of work

the calculation of the digest generates a table starting from the supplemented message, then transforms it via the use of functions, constants, detailed binary operations further. The unit carried out in an iterative way makes it possible to generate series of values of chopping to each turn. The final digest is the last state of these values of chopping.

The characteristics of SHA-256 are the following ones:

size of the message: $2^ {64}$ bits maximum
size of the blocks: 512 bits
size of the words: 32 bits
size of the digest: 256 bits
security level: $2^ {128}$ bits (tackles birthday)

Symbols and terms used

Parameters

has, B, C,…, H = variable of work (in fact of the words of W bits), used in the calculation of chopped

$H^ {(I)}$ = the value of chopping n° I. $H^ {(0)}$ is the initial value of chopping. $H^ {(NR)}$ is the last value of chopping.

$H_j^ {(I)}$ = the word (W bits) n° J of the value of chopping n° I, where $H_0^ {(I)}$ is the word of weight most extremely (on the left) of the value of chopping I.

$K_t$ = constant iterative according to the value of T, used in the calculation of chopping

K = many 0 additions to the message during the pretreatment (complement)
L = length of the message M, in bits
m = many bits contained in a block, is 512 bits
M = message with traiter
$M^ {(I)}$ = block n° I (m bits), of the message M
$M_j^ {(I)}$ = word (W bits) n° J, of the block (m bits) n° I, of the message M
N = many bits of shift or rotation to be applied to the word when associated with a function binaire
NR = many blocks of m bits contained in the message M after complément
T = variable temporary, word of W bits, used in the calculation of condensé
W = many bits contained in a word, is 32 bits.
$W_t$ = the word n° T of the table deduced from the message

Symbols

The hexadecimal notation used here will be:

\ mbox {0x}

example:

H_0^ {(0)} = \ mbox {0x12ab34ef}

\ wedge

= binary operation AND

\ vee

= binary operation OR

\ oplus

= binary operation XOR

\ lnot

= complement binaire

+

= addition modulo

2^w

<<

= binary shift on the left, where

x << n

is obtained by removing N bits of left of X and adding N zeros on the right.

>>

= binary shift on the right, where

x >> n

is obtained by removing N bits of right-hand side of X and adding N zeros on the left.

Operations on the words

They use following conventions:

binary operations bit bit (cf symbols)
addition modulo $2^w$ , is $2^ {32}$

the operation

x + y

is defined as follows. Are two words

x \ mbox {and} y

representing the integers

X \ mbox {and} Y

, such as

0 \ X \ the 2^ {32} and 0 \ Y \ the 2^ {32}

, one has

Z

the result of the addition modulo

2^ {32}

X \ mbox {and} Y

Z = (X + Y) \ mbox {modulo} 2^ {32} \ mbox {,} 0 \ Z \ the 2^ {32}

. One converts

Z

into a word

z

, and one defines

z then = X + y

the binary operation of shift on the right $SHR^n (X) ~$ , where X is a word of 32 bits and $0 \ N \ the 32$ , is defined by: $SHR^n (X) = X >> n~$
the binary operation of rotation by the line $ROTR^n (X) ~$ , where X is a word of 32 bits and $0 \ N \ the 32$ , is defined by: $ROTR^n (X) = (X >> N) \ vee (X << 32 - N) ~$

Functions and constants

Functions

This section describes the functions used during the calculation of the values of chopping. SHA-256 uses 6 switching functions working on words of 32 bitsnotés X, there, Z. The result of each one of these functions is a new word of 32 bits at exit.

$Ch (X, there, Z) = (X \ wedge there) \ oplus (\ lnot X \ wedge Z)$

$Maj (X, there, Z) = (X \ wedge there) \ oplus (X \ wedge Z) \ oplus (there \ wedge Z)$

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

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

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

Constants

SHA-256 uses 64 constant values of words of 32 bits, noted

K^ {\ {256 \}} _0, K^ {\ {256 \}} _1,…, K^ {\ {256 \}} _ {63} ~

. these numbers represent the first 32 bits of the decimal part of the cubic roots of the 64 first prime numbers. The following values are expressed in hexadecimal notation (16 base).

Pretreatment

This operation proceeds in three stages: to supplement the message M, to cut out the result in blocks, and to initialize the values of chopping

H^ {(0)}~

Complement of M

It is a question here of adding information to M so that he is of a multiple size of 512 bits.
with this intention, a bit " is added; 1" at the end of the message M, then K zeros, where K is the smallest nonnegative solution of the equation: L + 1 + K = 448 MOD 512
One then adds a block of 64 bits corresponding to the binary representation of L.

Examples:

M = " abc" , L = 8 X 3 = 24, K = 448 - (L + 1) = 448 - (24 + 1) = 423

" is added; 1" , then four hundred and twenty three " 0" , then 64 bits finishing by " 011000" (for 24) in M.

One then obtains a supplemented message with 512 bits.

M unspecified such as L = 500 bits, K = 448 - (L + 1) = 448 - (500 + 1) = -53

As K cannot be negative, one adds 512 to him by taking of account the modulo of the equation, to obtain

k=459

One adds " 1" , then four hundred and fifty-nine " 0" , then 64 bits finishing by " 111110100" (for 500) in M.

One then obtains a supplemented message with 512 bits.

Cutting in blocks

The supplemented message is cut out in NR blocks of 512 bits, noted

M^ {(1)}, M^ {(2)},…, M^ {(NR)}~

. Each block of 512 bits is then cut out in 16 words of 32 bits, noted

M_0^ {(I)}, M_1^ {(I)},…, M_ {15} ^ {(I)}

Initializations

The eight following variables are affected initial values as follows:

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

Calculation of the digest (chopped)

For this treatment one will use

a table of 64 words, noted $W_0, W_1,…, W_ {63} ~$
eight variables noted $a, B, C, D, E, F, G, h~$
eight variables containing the values of chopping, noted $H_0^ {(I)}$ and initialized previously in $H_0^ {(0)}$

These variables will repeatedly contain new values of chopping,

H^ {(I)}~

, for finally containing the digest of M, in

H^ {(NR)}~

two variables, noted $T_1 \ mbox {and} T_2$ , words of 32 bits.

One treats successively the NR blocks of M according to the following stages

For I = 1 with NR
{

1. One fills out table

W_t \ mbox {if} 0 \ T \ the 79

, selon

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

2. One initializes has, B, C, D, E, F, G and H with the values of chopping of the preceding turn

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. For T = 0 to 63

{

T_1 = H + \ sum^ {\ {256 \}} _1 (E) + CH (E, F, G) + K^ {\ {256 \}} _t + W_t ~

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

h = g~

g = f~

f = e~

e = D + T_1~

d = c~

c = b~

b = a~

a = T_1 + T_2~

}

4. Calculation of the intermediate values of chopping

H_0 {(I)} = + H_0^ {has (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)}

}

After repetition of the four stages above for the NR blocks of the message M, (i.e., after treatment of $M^ {(NR)}~$ ), the digest of 256 bits of M is obtained by concatenation of the values

$H_0^ {(NR)}||H_1^ {(NR)}||H_2^ {(NR)}||H_3^ {(NR)}||H_4^ {(NR)}||H_5^ {(NR)}||H_6^ {(NR)}||H_7^ {(NR)}$

External bonds

Random links: