In the NIST documentation for the Secure Hash Standard, it says to pad every message by appending the bit "1" to the end of the message, followed by k zero bits, where k is equal to the equation l (length of message in bits) + 1 + k = 448 mod 512. Then, it says to append a 64-bit block that is equal to the length expressed using a binary representation. The padded message should be a multiple of 512 bits. However, it does not seem to indicate how this would work for a message that is 512 bits or larger. My guess is that the equation above would be equal to the nearest multiple of 512 greater than the length minus 64. For example, for a message of 550 bits, k would be equal to 410. Am I right?


You're close; for a message of 550 bits, k=409; remember, k doesn't include the fixed 1 bit that you initially append.

In general, $k=512i + 447 - m$, where $m$ is the length of the message (in bits), and $i$ is the integer value that yields $0 \le k < 512$. In your example, $m=550$, and $i=1$; this gives us $k=512\times 1 + 447 - 550$

  • $\begingroup$ Do you know why it doesn't state this in the NIST documentation? $\endgroup$ – user41777 Dec 5 '16 at 5:32
  • $\begingroup$ @metroidsocrates it does, you quoted it. Section 5.1.1, "L +1+ K ≡ 448mod512", thats what the +1 is for. My method is K = 512-((L+65) mod 512) mod 512 $\endgroup$ – Richie Frame Dec 5 '16 at 14:01
  • $\begingroup$ @poncho m=550 ? $\endgroup$ – Richie Frame Jan 4 '17 at 10:37
  • $\begingroup$ @RichieFrame: I don't understand what you're asking. If you're wondering that 550 isn't a multiple of 8, well, SHA-256 is defined for arbitrary bitlengths (well, up to $2^{64}-1$ bits, anyways), and so it is well defined for 550 bit messages. Now, most SHA-256 implementations don't handle messages that aren't a multiple of 8 bits long, however some do (and NIST refers to those implementations as "bit oriented") $\endgroup$ – poncho Jan 5 '17 at 2:17
  • $\begingroup$ no, i mean the final equation, where you have a 550 and not a 410, the preceding sentence says m=410 $\endgroup$ – Richie Frame Jan 5 '17 at 3:31