Calculating the amount of zero bits to be appended to the message From FIPS 180-3


  Suppose that the length of the message, $M$, is $l$ bits. Append the bit $1$ to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $l + 1 + k \equiv 448 \mod 512$ . [...] For  example,  the  (8-bit  ASCII)  message  “abc”  has  length $8 \times 3 = 24$, so the message is padded with a one bit, then $448 − (24 + 1) = 423$ zero bits [...].


The example only works for $0 \leq M &lt; 448$, so I've come up with this formula for calculating $k$.

$$k = 448 - (l + 1) + 512 \cdot \left\lfloor \frac{l + 64}{512} \right\rfloor $$

or shorter

$$k = 447 - l + 512 \cdot \left\lfloor \frac{l + 64}{512} \right\rfloor $$

Is this the shortest/most performant way to calculate $k$?
If you have an implementation of an integer modulo operator, then

$$k = (447 - l) \bmod 512$$

should be the right solution. If your modulo operator can return negative results, do this:

$$k = ((447 - l) \bmod 512 + 512) \bmod 512$$

This seems simpler than using your division and flooring.



That said, you actually don't really need the number of zero bits for the padding, but you need to know how many 512-bit (e.g. 64 byte) blocks to hash. These then will be filled by:


the data
one 1 bit
a number of 0 bits (between 0 and 511, to fill the block)
the length, encoded as a 64-bit number.


We need just enough ($b$) blocks to have space for the data and the length (and the one 1-bit):

$$ b = \left\lceil \frac{l + 1 + 64}{512} \right\rceil $$

If you hash only data in whole bytes (as usual), the formula becomes

$$ b = \left\lceil \frac{l_8 + 1 + 8}{64} \right\rceil, $$

with $l_8 = \frac l8$ the length of the data in bytes.