title: Calculating k for padding of SHA-256 message
body: <p>I'm implementing the <a href="http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf" rel="nofollow noreferrer">SHS</a> SHA-256 algorithm in <code>VHDL</code> and I am having trouble coming up with a way to solve the equation for <strong>k</strong> when padding the message with zeroes.  The equation is outlined in the SHS description as follows:</p>
  
  <blockquote>
    <p>Append the bit “1” to the end of the
    message, followed by <strong>k</strong> zero bits, where <strong>k</strong> is the smallest, non-negative solution to the equation
    <code>l + 1 + k ≡ 448mod512</code>.</p>
  </blockquote>
  
  <p>I've seen the equation <code>k = 448 - (l mod 512 + 1)</code> which works if <code>l mod 512</code> is less than or equal to 448, but if it is larger you get a negative number for k.  I understand in this case we just need to append the "1", pad with "0"s until we hit 512, and then pad with 448 more zeroes followed by the 64 bit binary representation of the message length.</p>
  
  <p>A similar question asked <a href="https://stackoverflow.com/questions/16983301/sha-256-padding">here</a> is answered with an example:</p>
  
  <blockquote>
    <p>Well, if l = 448 (say), the solution to the equation in the spec gives k = 511</p>
  </blockquote>
  
  <p>I understand where 511 came from, but I can't figure out exactly how I can change the equation to get this number.  Using the equation from above results in <code>k = -1</code>.  I realize I could add 512 to the resultant k in the case that k is negative, and this will get me the right answer.  However, I'd like to know if there is a single line equation that can avoid having to check for that.</p>
  
  <p>Thanks!</p>