Digital Cryptography: A Subtle Art
This chapter is from the book
This chapter is from the book
This chapter is from the book
This chapter introduces the basic building blocks of modern digital cryptography, describes what they can do for you, and explains how to compose them to produce useful and practical secure services.
If you are familiar with these basics, you can probably skip this chapter. Good general references in this area are [NetSec] and [Schneier]. This chapter—and indeed this book—do not generally get down to the details of bit-level formats or algorithms. That is, they do not provide enough information for you to implement the cryptographic algorithms mentioned. Nevertheless, this chapter should provide a foundation of knowledge about modern digital cryptography that will make later chapters more comprehensible.
Sections 2.1, 2.2, and 2.3 generally discuss "symmetric" functions where the originator and receiver compute the same quantity or use the same secret key. Sections 2.4, 2.5, and 2.6 focus on "asymmetric" functions involving a public-private key pair. The remaining sections (2.7–2.11) discuss a variety of other important aspects of basic digital cryptography.
2.1 Message Digests
Message digest functions convert sequences of bits, possibly quite long, called messages, into fixed-length binary "fingerprints" or message digests of the original sequences. See Figure 2-1. A message digest function has two goals:
)
Figure 2-1 Message digest function
It should be computationally infeasible to find another message whose digest is the same as the digest of a given message.
It should be computationally infeasible to find two arbitrary messages whose digests are the same.
In the common case where an authentication method takes a large amount of computational effort and that effort is proportional to the number of bits being authenticated, you can secure a large document by authenticating its much smaller fixed-size message digest.
A message digest function is not identical to a checksum. A checksum is usually quite simple and is designed to detect transmission errors or accidental changes. An adversary can deliberately circumvent the testing of a checksum by adjusting the message to leave the checksum unchanged. By comparison, a message digest is complex and is designed to defeat attempts by an adversary to change the message.
First, consider a checksum calculated by simply adding all octets in a message and discarding the bits of the sum above the least significant eight bits. In most cases, an adversary could easily modify the message to become a different message with the same checksum. For example, inserting an octet with value V into the message will have no effect on the checksum if you can also insert a second octet with value (256 - V) anywhere in the message.
Next, consider a more complex function in which you take the product of the octets in the message, adding to each octet its position in the message, and the check octet is the middle eight bits of this product. For example, if the message consists of bytes with values
V1, V2, V3,...
then the check octet is the middle eight bits of
(V1 + 1) * (V2 + 2) * (V3 + 3)...
With this level of complexity, it is no longer quite so trivial for an adversary to figure out how to change the message without changing the check byte, although it can still be done. Cryptographically or computationally secure message digest functions are substantially more complex than this example, producing check quantities of at least 128 bits or 16 eight-bit bytes. They largely meet the following goals.
Expressing the goals of message digests more formally, if the message digest is N bits, then
To find a second message with the same message digest as a given message, no method should require an expected effort significantly less than trying 2N-1 possible other messages;
To find two arbitrary messages with the same message digest, no method should require an expected effort significantly less than trying 2N/2 messages, remembering all their digests, and looking for a match.
Like other modern digital cryptographic functions, message digest functions are typically used and sometimes defined only for integer numbers of octets, rather than arbitrary numbers of bits.