Cryptographic Applications - Introduction to Cryptography with Java Applets - page 332

if privacy is not a concern) via an insecure channel, whereas the digest is sent by way of a
secure channel. Here, a secure channel may mean:
• An electronic means of data communication known to be safe.
• The telephone, where voice recognition provides the authentication.
• Transporting the data by trusted physical means.
When this is done, the recipient of a message can compute the digest for it, then com-
pare this to the digest received. If they match, the recipient accepts the message as authen-
tic and unmodified (since the digest was sent via secure means.)
Due to the logistical problems involved, this type of assurance is rarely used. The mere
problem of not being able to guarantee a “secure” channel is the reason cryptography evolved
in the first place. However, this example is given to make you realize the importance of
never sending a digest along the same lines of communication as a message. An adversary
can capture both the message and the digest. He can then construct a new message, com-
pute a digest for it, and then send them to you. This is easily done even if a public key
encryption scheme is being used. (Think about it; everyone knows your public key, and
everyone knows the digest function.)

Signing the Digest One of the problems with signing messages in the manner
described earlier is that basically, the sender does double encryption, and double decryption
is done by the recipient. This may be too costly in terms of computer resources, especially
if messages are being transmitted in real time (like an audio or video signal).
One solution is for the sender, say A, to produce a digest from the plaintext. A then singly
encrypts the message using the public key of the recipient, say B. A then doubly encrypts
only the digest, first using the private key of A, then B's public key. The message and the
digest are then sent. It doesn't matter now if the digest is sent with the message. B decrypts
the message, then decrypts the digest first using B's private key, then A's public key. B then
calculates a digest of the decrypted message. If it matches the decrypted digest, B accepts
the message. See Figure 16.9.
Why does this work? Could an adversary capture the message and the digest, and pro-
duce a new message and digest? Since the digest was first encrypted using A's private key,
an adversary has no way to duplicate this. The best she can do is “guess” a digest value for
her modified message, in the hopes that it will match the digest computed by B from her
bogus message. If the digest size is large enough, say 128 bits, this is extremely unlikely;
in this case, the probability of all 128 bits matching is 1/2 128 , or less than 2.939 10 39 .

Encrypting Digest with Message The situation of sending a digest along the same
line of communication as the message is not necessarily unique to public key cryptosystems.
Data authentication is also important for secret key cryptosystems. Even with secret key
ciphers, it is sometimes possible for an adversary to modify a message so that it appears
meaningful to the recipient. This is actually quite easy if the message possesses little struc-
ture; for example, a series of widely ranging numbers in binary format. The adversary does
not need to know the secret key to do this. (If they knew the secret key, you would be up
the creek anyway!)