next up previous contents
Next: PGP Up: Background Previous: Description of the RSA

Cryptographic hash functions


Cryptographic hash functions are typically used to compute a message digest when making a digital signature. Instead of encrypting the whole message with the secret key, only the message digest is encrypted. This is much faster than encryption the complete message.

A hash function compresses the bits of a message to a fixed-size hash value in a way that distributes the possible messages evenly among the possible hash values. A cryptographic hash function does this in a way that makes it extremely difficult to come up with a message that would hash to a particular hash value.

Cryptographic hash functions typically produce hash values of 128 or more bits. This number is vastly larger than the number of different messages likely to ever be exchanged in the world.

The message digest algorithm used in PGP is the MD5 Message Digest Algorithm, placed in the public domain by RSA Data Security, Inc. MD5's designer, Ronald Rivest, writes this about MD5 [7]:

It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of tex2html_wrap_inline1247 operations, and that the difficulty of coming up with any message having a given message digest is on the order of tex2html_wrap_inline1183 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the case with any new proposal of this sort.

The level of security provided by MD5 should be sufficient for implementing very high security hybrid digital signature schemes based on MD5 and public-key cryptosystems.

Asgaut Eng
Wed Apr 10 14:07:30 MET DST 1996