Cryptographic Hashing

Cryptographic hash functions

A cryptographic hash function is a "special" type of hash function that adds some additional properties:

MD5 was a widely used cryptographic hash function; it has since been replaced by the SHA family. [2]

How it Works

NOTE: In this section, the exact details on the algorithm are taken from [3].
Here is an example of how the hash code of a message is calculated, using the SHA-1 algorithm (since it's easier for me to understand than MD5):

1. Padding: Add a 1 to the end of the message (in binary), then pad the message with 0's until its length is 64 bits short of being a multiple of 512. Then, add its length (the length before padding) onto the end of the message (this is 2 words, so the length of the padded message is a multiple of 512 bits). Now, the
2. Functions and constants: In the SHA-1 algorithm, a series of 80 functions, f(t, B, C, D), is used, each operating on 3 words (in these functions, AND means the bitwise AND across the 2 input words, and so forth).
   If t is between 0 and 19 inclusive, then f(t, B, C, D) = (B AND C) OR ((NOT B) AND D)
   If t is between 20 and 39, or 60 and 79 inclusive, then f(t, B, C, D) = B XOR C XOR D
   Otherwise (t is between 40 and 59 inclusive), f(t, B, C, D) = (B AND C) OR (B AND D) OR (C AND D)
   There are also 80 constant words, K(t), used.
   If t is between 0 and 19 inclusive, then K(t) = 5A827999 (in hex)
   If t is between 20 and 39, then K(t) = 6ED9EBA1
   If t is between 40 and 59, then K(t) = 8F1BBCDC
   Otherwise, K(t) = CA62C1D6
3. Determine the hash code: The following variables are used in calculating the hash code:
   
   • A buffer, ABCDE, containing 5 words
   • A buffer, H0 H1 H2 H3 H4, containing 5 words
   • An 80-word sequence, W(0) W(1) et cetera
   • A single-word buffer, TEMP
   • A series of 16-word blocks, M(1) ... M(n), containing the original message. This is why we needed to pad the message to a multiple of 512 bits.
   Initially, the H's have been initialized as follows:
   • H0 = 67452301
   • H1 = EFCDAB89
   • H2 = 98BADCFE
   • H3 = 10325476
   • H4 = C3D2E1F0
   Now, we process each M from 1 to n (in order). For each M(i), do the following:
   1. Set W(k) equal to the kth word of M(i), starting from the left
   2. For t from 16 to 79, W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)). S^j is the "circular left shift by j" operation - shift the input j bits to the left, then tack the first j bits onto the right.
   3. Let A = H0, B = H1 and so on.
   4. For t from 0 to 79, do the following:
      • TEMP = S^5(A) + f(t, B, C, D) + E + W(t) + K(t) (the + operator here means "add the words as if they were numbers, and discard the overflow")
      • E = D
      • D = C
      • C = S^30(B)
      • B = A
      • A = TEMP
   5. H0 = H0 + A, H1 = H1 + B and so on
   After all of the M's have been processed, the message digest is H0 H1 H2 H3 H4. Notice that the message digest is 5*32 = 160 bits, no matter how long the input message is.

An Application

References

See Also

External Links