# 11.2 Simple Hash Examples

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.