Bit shifting a bit array and binary math for SHA-1

Question

I am posting for a sanity check so please forgive me if this sounds a little basic. I am trying to learn more about encryption so I figured a good starter project would be implement the Sha-1 hashing algorithm. I found a walk-through and have hit a point where I do not know if the walk-through is wrong or my understanding of bitness/rotation/binary operations is wrong.

From the document:

Step 11.2: Put them together

After completing one of the four functions above, each variable will move on to this step before restarting the loop with the next word. For this step we are going to create a new variable called 'temp' and set it equal to: (A left rotate 5) + F + E + K + (the current word).

Notice that other than the left rotate the only operation we're doing is basic addition. Addition in binary is about as simple as it can be.

We'll use the results from the last word(79) as an example for this step.

A lrot 5:
00110001000100010000101101110100
F:
10001011110000011101111100100001
A lrot 5 + F
Out:
110111100110100101110101010010101

Notice that the result of this operation is one bit longer than the two inputs. This is just like adding 5 and 6, you will need a new place value to represent the answer. For everything to work out properly we will need to truncate that extra bit eventually. However, we do not want to do that until the end!

This does not quite work out. What I think would happen is:

A = 00110001000100010000101101110100
F = 10001011110000011101111100100001
A Left rotate 5 = 00100010001000010110111010000110
(A Left Rotate 5) + F = 10101101111000110100110110100111 (which is still 32 bits)

What I need is just another set of eyes on this to say "Yes krtzer, you are correct and this document is wrong" Or "Your understanding of bitness, endianness, and/or bit rotation is wrong, this is how it works".

Right now I am not sure if my integer representation is wrong (the spec says use U32s, but this section says that I need to keep track of the extra bits), the endianness of my program is messing up the rotation (I use little endian) or there is something else.

Any experience or insight will be appreciated!

Answer 1

You are correct in your understanding of how everything works. The problem was with the article (which I wrote). An extra digit must always be added in the beginning of step 11.2, whether it's necessary or not, and if it's not necessary, it should be set to 1.

The article now reads:

Notice that the result of this operation is one bit longer than the two inputs. After each iteration the new word should be one bit longer than the last. Sometimes this will be a necessary carrier bit (like the extra place value you need to represent the result of adding the two single digit numbers 5 and 6 in base 10), and when that's not needed you must simply prepend a 1. For everything to work out properly we will need to truncate that extra bit eventually; however, we do not want to do that until the end!

The article was also unclear about the fact that an already rotated A was being shown in the example.