3 Replies - 9100 Views - Last Post: 18 June 2010 - 04:28 AM Rate Topic: -----

#1 jnz   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
h2 = 0x98BADCFE
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   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1397
  • View blog
  • 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.
Was This Post Helpful? 2
  • +
  • -

#3 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • 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).
Was This Post Helpful? 2
  • +
  • -

#4 jnz   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1