In a very simplistic and step by step example, how do I get the 'w' values for SHA256?

Question

I've been to https://docs.google.com/spreadsheets/d/1mOTrqckdetCoRxY5QkVcyQ7Z0gcYIH-Dc0tu7t9f7tw/edit#gid=1194752368, http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html, and https://en.wikipedia.org/wiki/SHA-2#Pseudocode (the pseudocode is for sha256)

The use of those links, not withstanding, I cannot create the 'W' values beyond the first 16 values. Everything I read is complex beyond my understanding.

In a very simplistic and step by step example, how do I get the 'w' values for SHA256?

Answer 1

In SHA-256, $W$ is a vector of 64 values $W_i$ each 32-bit, collectively forming an expanded form of the input to a compression step. Said input is a 512-bit sub-block of the message to be hashed par SHA-256 after that message was padded. The $W_i$ depend only on said input.

$W_0$ to $W_{15}$ are said input, formatted as 32-bit words. $W_{16}$ to $W_{63}$ are computed from these by applying for $i$ from 16 to 63 the recurrence defined by FIPS 180-4 section 6.2.2 as (within a reordering of terms): $$W_i\gets W_{i-16}\;\tilde+\;\sigma_0(W_{i-15})\;\tilde+\;W_{i-7}\;\tilde+\;\sigma_1(W_{i-2})$$ where $\;\tilde+\;$ is addition with truncation of the result to 32-bit.

In the above expression, $\sigma_0$ and $\sigma_1$ are 32-bit functions of a 32-bit argument defined by FIPS 180-4 section 4.1.2 as: $$\begin{align} \sigma_0(x)&\gets(x\ggg\,\,\,7)\oplus(x\ggg18)\oplus(x\gg\,\,\,3)\\ \sigma_1(x)&\gets(x\ggg17)\oplus(x\ggg19)\oplus(x\gg10) \end{align}$$ where $\oplus$ is bitwise-XOR, $\ggg$ is right-rotation of a 32-bit word (also known as right-rotate-no-carry or right-circular-shift), $\gg$ is right-shift of a 32-bit word (also known as right-logical-shift).

For example, to compute $W_{16}$, we

1. apply the function $\sigma_0$ to $W_1$ (right-rotating that value by 7 and 18 bits, right-shifting it by 3 bits, then combining the resulting three 32-bit values by XOR);
2. apply the function $\sigma_1$ to $W_{14}$ (right-rotating that value by 17 and 19 bits, right-shifting it by 10 bits, then combining the resulting three 32-bit values by XOR);
3. add $W_0$, $W_9$, and the two above results, truncating the result to 32-bit.

---

Note: the reason for using shift rather than rotate for one of the terms of $\sigma_0$ and $\sigma_1$ is discussed here.

Note: often (including in almost any careful hardware implementation) it is kept only the chronologically last obtained 16 values of $W$, evolving as the compression rounds are performed per the transformation: $$W_i\gets W_i\;\tilde+\;\sigma_0(W_{(i+1\bmod16)})\;\tilde+\;W_{(i+9\bmod16)}\;\tilde+\;\sigma_1(W_{(i+14\bmod16)})$$

Answer 2

Following the wiki code: we have a message block of $512$ bits (or $64$ bytes) that you're dealing with. We see those as $16$ words of $32$ bits each. These are W[0],..., W[15], in order.

Then e.g. W[16] = W[0] ^ f_1(W[1]) ^ W[9] ^ f_2(W[14]) where f_1(w) transforms the word w into ror(w,7)^ror(w,18)^(w>>3) where ror is implemented as in the link in my comment above, and f_2(w) = ror(w,17)^ror(w,19)^(w>>10) Then W[17] is the same with all indices moved up 1, etc. So : W[17] = W[1] ^ f_1(W[2]) ^ W[10] ^ f_2(W[15]) and next W[18] = W[2] ^ f_1(W[3]) ^ W[11] ^ f_2(W[16]), etc.

So W[16],....., W[63] are all computed based on the previously computed W[i] in a way that mixes up the bits, and we get a 4-fold expansion of the message block words that are used as starting values.

Conceptually, what's happening in this hash function (and others like this) is that we're using a block cipher $E(m,k)$ (often called the "transform" function in code implementations) with block size (for $m$) of 256 bits (8 words) and keysize (for $k$) of 512 bits. To handle a message with blocks $m_0,m_1, m_2, \ldots, m_N$ (where the last block(s) have padding and a total length) is to define $h_0$ to be a fixed block, and then computing $h_1 = E(h_0,m_0) + h_0$ (message block addition happens per word, modulo $2^{32}$), $h_2 = E(h_1, m_1) + h_1$, etc. up to $h_{N+1} = E(h_N, m_N) + h_N$ and then $h_{N+1}$ is the final hash. Adding the input to the cipher output makes the result irreversible (which is what we want with hash functions).

The $E$ function uses a message block as key, and the computation of the $W$ words is its key schedule: it creates round keys for the block cipher (which has 64 rounds for SHA-256 and uses one $W$ word per round, this is the last big loop in the Wikipedia pseudo code).

I think the pseudo code can quite well be translated into pure Python, using a good ror function, of course.

It would help if you can tell where your code no longer gives the right result as compared to the spread sheet links. And it's more of a stackoverflow question if it's about code itself, IMHO.