# SHA-1 Algorithm pseudocode interpretation

Page 1 of 1

## 3 Replies - 9100 Views - Last Post: 18 June 2010 - 04:28 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=178143&amp;s=48c9c037da6764bab03fe02552fd889e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 jnz

Reputation: 0
• Posts: 8
• Joined: 17-June 10

# SHA-1 Algorithm pseudocode interpretation

Posted 17 June 2010 - 02:00 PM

I'm writing a small library for personal learning sake and it would be very nice (and a large learning curve) to:
A ) Read and understand psudocode written like this
B ) Implement, test and improve said code.
C ) Understand how it works, what it does and invent my own (simple) hash algorithm.

With that said my main problem reading this code is 2nd and 3rd line of the code.

```append 0 ≤ k < 512 bits '0', so that the resulting message length (in bits)
is congruent to 448 ≡ −64 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

```

What I would like to know is: How do I interpret "x < y < z" is it literal meaning 'x' is smaller than 'y' and 'z' and 'y' is smaller than 'z' or is there something different here?

The second problem I have in the code would be this: "congruent to 448 ≡ −64 (mod 512)". I'm assuming this means that the resulting data would be aligned to 512 bits IE "bitLength(data) % 512 == 0". Is this correct?

Finally, the reason this is on the C/C++ section is I am going to implement this in C++ and eventually request help in improving and speeding up my code.

( http://en.wikipedia.org/wiki/SHA-1 )
```Note 1: All variables are unsigned 32 bits and wrap modulo 232 when calculating
Note 2: All constants in this pseudo code are in big endian.
Within each word, the most significant byte is stored in the leftmost byte position

Initialize variables:
h0 = 0x67452301
h1 = 0xEFCDAB89
h3 = 0x10325476
h4 = 0xC3D2E1F0

Pre-processing:
append the bit '1' to the message
append 0 ≤ k < 512 bits '0', so that the resulting message length (in bits)
is congruent to 448 ≡ −64 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

Initialize hash value for this chunk:
a = h0
b = h1
c = h2
d = h3
e = h4

Main loop:
[26]
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f = (b and c) or ((not B)/> and d)
k = 0x5A827999
else if 20 ≤ i ≤ 39
f = b xor c xor d
k = 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f = (b and c) or (b and d) or (c and d)
k = 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f = b xor c xor d
k = 0xCA62C1D6

temp = (a leftrotate 5) + f + e + k + w[i]
e = d
d = c
c = b leftrotate 30
b = a
a = temp

Add this chunk's hash to result so far:
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e

Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4

```

Is This A Good Question/Topic? 0

## Replies To: SHA-1 Algorithm pseudocode interpretation

### #2 Oler1s

• D.I.C Lover

Reputation: 1397
• Posts: 3,884
• Joined: 04-June 09

## Re: SHA-1 Algorithm pseudocode interpretation

Posted 17 June 2010 - 02:35 PM

Quote

How do I interpret "x < y < z" is it literal meaning 'x' is smaller than 'y' and 'z' and 'y' is smaller than 'z' or is there something different here?
The algorithm says 0<= k < 512, so the 0 and 512 are bounds. That is, k can be any value between 0 (inclusive) and 512 (not inclusive). 0 < 512 is obviously true. They aren't talking about that mathematical relationship.

Quote

The second problem I have in the code would be this: "congruent to 448 ≡ −64 (mod 512)". I'm assuming this means that the resulting data would be aligned to 512 bits IE "bitLength(data) % 512 == 0". Is this correct?
Well, careful here. Sha-1 wants a message length that is a multiple of 512. But, as part of the Sha-1 algorithm, you add the message length to the end of your "raw" message. That length is expressed as a 64 bit integer. So the actual message looks like: your message + padding + 64 bit integer = multiple of 512.

### #3 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: SHA-1 Algorithm pseudocode interpretation

Posted 17 June 2010 - 02:36 PM

x < y < z meand that x is less than y, and y is less than z, it therefore implies that x is less than z (since it is less than y, which is less than z).

Basically that little snippet seems to be saying that add padding bits until the length mod 512 is 448 (or 64 bits less than some multiple of 512).

### #4 jnz

Reputation: 0
• Posts: 8
• Joined: 17-June 10

## Re: SHA-1 Algorithm pseudocode interpretation

Posted 18 June 2010 - 04:28 AM

Thank you very much for the replies! I have implimented the C code according to the psudocode but still trying to make it work. I will post back when/if I need help with that.