Message Digest Functions

To save of the length of data we need to append to a message to `sign' it we want another one-way function, but this one doesn't want to be one-one. It needs to take a long message $M$ and convert it to a shorter message (it's fingerprint or message digest). This message digest must be generated in such a way that it is nearly impossible to obtain any hint as to the content of the origional message from it's digest. The function must be entirely deterministic .. given the same input it must give the same output.

The technique that is commonly used, and that is used by PGP, is called MD5. The algorithm isn't very exciting mathematically, and if you want to read all about it it is fully explained in RFC1312. Given any length of message it computes a 128 bit message digest. This gives around $3.4*10^{38}$ possible message digests .. so it's unlikely we will ever find two messages that result in the same digest even if everyone on the planet spends their entire lives trying! The UNIX program md5sum calculates the message digest of an arbitary message baed on the MD5 algorithm. Here are some examples.

[stephen@eddie encrypt]$ echo "There is $1500 in the blue box" | md5sum
11bee12a9acd083ce990667488d99ca2  -
[stephen@eddie encrypt]$ echo "There is $1100 in the blue box" | md5sum
d1b2f167ca464a1dd789f0740c6b356c  -
[stephen@eddie encrypt]$ echo "This is a very different message" | md5sum
2c46d4d4f539754c97cbf5919eee09b4  -
[stephen@eddie encrypt]$ echo "There is $1100 in the blue box." | md5sum
dd7d6842aef63ba104b884d9a53d4ebf  -
[stephen@eddie encrypt]$ echo "There is $1500 in the blue box" | md5sum
11bee12a9acd083ce990667488d99ca2  -

We can see that even messages that vary only very slightly result in radically different message digests.

It is easy to see how this is useful in the context of public/private key cryptography. Rather than sign a message by including $S_A(M)$ with it Alice can merely provide $S_A(MD5(M))$. We can still verify it was her who sent it in the same way as we did before since

$$P_A(S_A(MD5(M))) = MD5(M)$$

and since it is conjectured to be computationally infeaible to produce two messages having the same message digest we have lost little by using this technique.