What does “message schedule” mean in SHA-256?

Question

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?

Answer 1

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)

Answer 2

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.