Computer Security and Cryptography

17.7 HASH FUNCTIONS

To hash is to it chop into small pieces. Corned beef hash is the quintessential American food made with left over meat, eggs and whatever is lying around in the refrigerator. A hashing function h is a mapping from values x in some finite set into a value y contained in another (larger) set that mixes up the values x. Hashing is a synonym for a (uniformly distributed) random mapping in cryptography (Fig. 17.6).

A hash function h is

• A one-way hash function if it is computationally infeasible to determine the message m given the hash-of-message h(m).
• A collision-resistant hash function if given the hash-of-message h(m) it is computationally infeasible to determine any other message m* with the same hash value h(m) = h(m*).

A message digest is a hash function that derives a fixed-length hash value for every message in some message domain. The processes of computing the message digest with a PKC and verifying the message digest is depicted in Figures 17.7 and 17.8.

Even if a hash function is not collision-resistant, knowing the hash h(m) of

m: Bank A to Bank : Credit Acct#04165-02388, $ 1,000; debit Acct# …

Figure 17.6 High-cholesterol hashing.

Figure 17.7 Deriving ...