There are many families of hash functions. The discrete log hash function that we described in the previous section is too slow to be of practical use. One reason is that it employs modular exponentiation, which makes its computational requirements about the same as RSA or ElGamal. Even though modular exponentiation is fast, it is not fast enough for the massive inputs that are used in some situations. The hash functions described in this section and the next are easily seen to involve only very basic operations on bits and therefore can be carried out much faster than procedures such as modular exponentiation.
We now describe the basic idea behind many cryptographic hash functions by giving a simple hash function that shares many of the basic properties of hash functions that are used in practice. This hash function is not an industrial-strength hash function and should never be used in any system.
Suppose we start with a message of arbitrary length . We may break into -bit blocks, where is much smaller than . We denote these -bit blocks by , and thus represent . Here , and the last block is padded with zeros to ensure that it has bits.
We write the th block as a row vector
where each is a bit.
Now, we may stack these row vectors to form an array. Our hash will have bits, where we calculate the th bit as the XOR along the th column of the matrix, that is . We may visualize this as
This hash function is able to take an arbitrary length message and output an -bit message digest. It is not considered cryptographically secure, though, since it is easy to find two messages that hash to the same value (Exercise 9).
Practical cryptographic hash functions typically make use of several other bit-level operations in order to make it more difficult to find collisions. Section 11.4 contains many examples of such operations.
One operation that is often used is bit rotation. We define the right rotation operation
as the result of shifting to the right by positions and wrapping the rightmost bits around, placing them in leftmost bit locations. Then gives a similar rotation of by places to the left.
We may modify our simple hash function above by requiring that block is left rotated by , to produce a new block . We may now arrange the in columns and define a new, simple hash function by XORing these columns. Thus, we get
This new hash function involving rotations mixes the bits in one position with those in another, but it is still easy to find collisions (Exercise 9). Building a cryptographic hash requires considerably more tricks than just rotating. In later sections, we describe hash functions that are used in practice. They use the techniques of the present section, coupled with many more ways of mixing the bits.