SHA-1 Bit Implementation in C#


Introduction:

This is a bit implementation of the SHA-1. It supports messages 2^32 - 65 bits long..., the standard is 2^64 - 1.
The solution consists of one project with the goal of testing the implementation of the algorithm.
Functionality:

  • Introduce an ASCII text and receive the message digest; its limitations are due the size of the textBox object.
  • Introduce a file containing messages and the program will drop a file containing the message digest followed by " ^" each on a new line.
  • Introduce a file containing messages and a second file containing message digests to test if the file dropped by the program and the second file introduced contain the same message digests.

The two files are similar to the ones provided by NIST.

They may contain text (like comments) which won't be processed. The only thing that will be processed will be blocks like:

D>
...
<D

Between D> and <D on each line are compact messages.

"The message files provided use "compact strings" to store the message values. Compact strings are used to represent the messages in a compact form. A compact string has the form:
 
z || b || n(1) || n(2) || ... || n(z)

Where z >= 0 represents the number of n, b is either 0 or 1, and each n(i) is a decimal integer representing a positive number. 

The length of the compact string is given by the summation of the n(i).

The compact string is interpreted as the representation of the bit string consisting of b repeated n(1) times, followed by 1-b repeated n(2) times, followed by b repeated n(3) times, and so on.
Example:

M = 5 1 7 13 5 1 2

Where z = 5 and b = 1. Then the compact string M represents the bit string 1111111000000000000011111011, where 1 is repeated 7 times, 0 is repeated 13 times, 1 is repeated 5 times,0 is repeated 1 time, and 1 is repeated 2 times."

The text above has been taken from the Readme.txt file provided in the sha-vectors.zip by NIST.
The testing part is done in the Form.cs (for one ASCII message), Form2.cs and Test.cs (for the message file).
Other tools used that are part of the FIPS 180-1 are in Tools.cs.

Tools.StringToBitArray, as its name suggests, transforms a ASCII string in a BitArray structure. Tools.Hex transforms either a byte in a two characters long string representing its value in hex, or a Word (UInt32) in an eight characters string representing it's value in hex.

SHA-1 implementation:
In the SHA-1 class constructor constants K0 to K79 are initialized.

The SHA-1.MessageHash receives as parameter a BitArray structure which is the message that will be hashed.
 
First, it initializes the Hs with the initial values. Then, the message is padded.
}

Message padding consists of adding one bit set on 1 at the end of the message then adding a number of bits set on 0 in order for the message to be congruent to 448 modulo 512.

In my implementation the word before the last one is set on 0x00000000 and the last word contains the initial message length. In a full implementation both words are used to store the message length.

The message is divided in 512-bits blocks there are stored in a byte array before they are sent to BlockHash. In BlockHash they are stored in a 16 Words UInt32 Array. The message is processed according to the algorithm.

A, B, C, D, E, F are added to the Hs and, after all blocks have been processed, H0H1H2H3H4H5 is returned as a string in hex.

Note: During the conversion from and to BitArray switching of bits positions are needed due to the fact that SHA-1 uses a big endian representation and the PC's CPU works with little endian representation so that bits are stored in reversed order in memory.

The algorithm implementation is limited to the structure I used to store the message System.Collections.BitArray hwo's size is an integer represented on 32 bits.

TO DO:

  1. Make the implementation work for all messages of length < 2^64 -1.
  2. Test the implementation for the third type of test provided by NIST in the sha-vectors.zip file.

Recommended Free Ebook
Similar Articles