I am trying to understand the sha-256 algorithm from FIPS 180-2. I understood the padding and parsing of the message string. However after that it states (page 15):

For $i = 1$ to $N$:

  1. Prepare the message schedule, ${W_t}$: $$ W_t= \begin{cases} M_t(i) & 0 \leq t \leq 15 \\ ROTL^1( W_{t -3} \oplus W_{t-8} \oplus W_{t - 14} \oplus W_{t-16} ) & 16 \leq t \leq 79 \end{cases} $$ ...

But I am unable to understand what $W_t$ is in the first place. Could someone please help me out?

I know it states on page 3:

$W_t\qquad$ The $t$th $w$-bit word of the message schedule.

But what is the message schedule and how is it generated?


2 Answers 2


What this does is expand the 16-word (512-bit) input message block (to the compression function, i.e. one "chunk" of the complete message) into an 64-word array W[t]. The definition of this array is recursive. What it tells you is that the first 16 words of this 64-word array are just the words of the input chunk:

W[t] = M[t]   for 0 <= t <= 15

In other words, for t between 0 and 15, W[t] is equal to M[t].

Then, for 16 <= t <= 63 (the remaining 48 words) the following recurrence is used:

W[t] = MIX(W[t - 2], W[t - 7], W[t - 15],  W[t - 16])   for 16 <= t <= 63

Such that W[t] depends on W[t - 2], W[t - 7], W[t - 15] and W[t - 16] and MIX is the message schedule function (composed of exclusive-or and bit shifts/rotations). Note that words are guaranteed to have been defined previously as the first 16 words have already been initialized, and the remaining values are then successively calculated.

Here W[t] is just a temporary variable just like any other and is used to improve the compression function's quality, and is called the "message schedule" since it preprocesses the message block.

EDIT: I changed the description to SHA256 as @Henno noted you were actually describing SHA1 (though as he correctly observes, the overall structure remains the same for the two hash functions)


You are looking at the SHA-1 specification, not the SHA-256 one. You are quoting pages 15,16 in the PDF you linked to. The remarks Thomas made also apply to SHA-256 though: the message block of 16 32-bit words is expanded to an auxiliary array of 64 (because we have 64 rounds, and we use one of the $W[t]$ in each round) 32-bit words. Then page 19 has the corresponding message schedule for computing the $W[t]$ for $1 <= t <= 64$. On end page 19, start page 20 you then see each $W[t]$ being used in its own round. Note that SHA-1, SHA-256, SHA-384 and SHA-512 all have the same abstract structure.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.