How exactly is the input message of SHA-256 (pre-)processed?

Question

I’m very interested how SHA-256 handles messages, but I’ve got 3 questions. (As I have already read in some answers before, SHA-256 is not directly performed on the message but on an array, thanks for that.)

1. In my understanding after padding the message to a multiple of 512 bit length, we put the message into a

   64 entry message schedule array w[0..63] of 32-bit words

   Is this an array with 64 elements, each allowed to be 32 bits long?

2. copy chunk into first 16 words w[0..15] of the message schedule array

   But then I ask myself, if we have a message that is, for example 4096 bits long and we only fill the first 16 elements of the array with the original message, what happens to the other (4096-16*32 = 3584) 3584 bits of the message?

3. s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)

   What are the rightrotate and rightshift operators doing to the elements in the array?

Answer 1

1. So is this an array with 64 elements, each allowed to be 32 bits long?

Yes, although you could also use 128 elements of 16 bits or 256 elements of 8 bits if the (embedded) processor doesn't support 32 bit operations. SHA-256 however operates on 32 bits internally, so that's the most efficient word size.

If the implementation uses anything other than 32 bit operations then the 32 bit operations need to be replicated with one of the other word sizes.

2. But then I ask myself, if we have a message that is, for example 4096 bits long and we only fill the first 16 elements of the array with the original message, what happens to the other (4096-16*32 = 3584) 3584 bits of the message?

They'll be processed after that chunk. SHA-256 operates on batches of 512 bits at a time, this is the 16 words as 16 * 32 = 512 bits chunk (Wikipedia pseudo code says: for each chunk).

Each chunk is processed and this updates the h0..h7 state, which provides the start of the next processing of the chunk. The final state is used to produce the output.

3. What are the rightrotate and rightshift operators doing to the elements in the array?

Well, they move the bits of the selected word to the right. The rightrotate operation will put the bits that "fall off" the word back on the left. In cryptography we call this transpositioning.

It is possible to emulate any of these operations using bitwise masking operations if they are not directly available in the runtime (Java for instance does not support rotate, only shift).

Processors generally directly support shift and rotation.

---

Notes

Note that it is important to note that SHA-2 is defined to be big endian and SHA-3 (unfortunately) little endian. This is important when implementing the algorithm on a runtime with a different endianess.

Obviously the wikipedia pseudo code should not be implemented directly. For each chunk it reads:

create a 64-entry message schedule array w[0..63] of 32-bit words

normally you make sure that SHA-256 implementation only allocates the message schedule array once, after which it can be reused for each chunk. The pseudo code was written to understand the algorithm rather than to provide a hint on how to implement it efficiently.