Bruce Schneier - Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C

Suppose a sender wants to send a message to a receiver. Moreover, this senderwants to send the message securely: She wants to make sure an eavesdroppercannot read the message.

A message is plaintext (sometimes called cleartext). The process of disguisinga message in such a way as to hide its substance is encryption. An encryptedmessage is ciphertext. The process of turning ciphertext back into plaintext is decryption. This is all shown in Figure 1.1.

Figure 1.1 Encryption and Decryption.

(If you want to follow the ISO 7498-2 standard, use the terms encipher anddecipher. It seems that some cultures find the terms encrypt and decryptoffensive, as they refer to dead bodies.)

The art and science of keeping messages secure is cryptography, and it ispracticed by cryptographers. Cryptanalysts are practitioners ofcryptanalysis, the art and science of breaking ciphertext; that is, seeingthrough the disguise. The branch of mathematics encompassing bothcryptography and cryptanalysis is cryptology and its practitioners arecryptologists. Modern cryptologists are generally trained in theoreticalmathematics they have to be.

Plaintext is denoted by M, for message, or P, for plaintext. It can be a stream of bits, a text file, a bitmap, a stream of digitized voice, a digital videoimage...whatever. As far as a computer is concerned, M is simply binary data.(After this chapter, this book concerns itself with binary data and computercryptography.) The plaintext can be intended for either transmission or storage.In any case, M is the message to be encrypted.

Ciphertext is denoted by C. It is also binary data: sometimes the same size as M, sometimes larger. (By combining encryption with compression, C may be smaller than M. However, encryption does not accomplish this.) Theencryption function E, operates on M to produce C. Or, in mathematical notation:

E(M) = C

In the reverse process, the decryption function D operates on C to produce M:

D(C) = M

Since the whole point of encrypting and then decrypting a message is torecover the original plaintext, the following identity must hold true:

D(E(M)) = M

In addition to providing confidentiality, cryptography is often asked to doother jobs:

• Authentication. It should be possible for the receiver of a messageto ascertain its origin; an intruder should not be able to masquerade assomeone else.
• Integrity. It should be possible for the receiver of a message toverify that it has not been modified in transit; an intruder should not beable to substitute a false message for a legitimate one.
• Nonrepudiation. A sender should not be able to falsely deny laterthat he sent a message.

These are vital requirements for social interaction on computers, and areanalogous to face-to-face interactions. That someone is who he says he is...thatsomeones credentials whether a drivers license, a medical degree, or apassport are valid...that a document purporting to come from a personactually came from that person.... These are the things that authentication,integrity, and nonrepudiation provide.

A cryptographic algorithm, also called a cipher, is the mathematicalfunction used for encryption and decryption. (Generally, there are two relatedfunctions: one for encryption and the other for decryption.)

If the security of an algorithm is based on keeping the way that algorithmworks a secret, it is a restricted algorithm. Restricted algorithms havehistorical interest, but are woefully inadequate by todays standards. A large orchanging group of users cannot use them, because every time a user leaves thegroup everyone else must switch to a different algorithm. If someoneaccidentally reveals the secret, everyone must change their algorithm.

Even more damning, restricted algorithms allow no quality control orstandardization. Every group of users must have their own unique algorithm.Such a group cant use off-the-shelf hardware or software products; aneavesdropper can buy the same product and learn the algorithm. They have towrite their own algorithms and implementations. If no one in the group is agood cryptographer, then they wont know if they have a secure algorithm.

Despite these major drawbacks, restricted algorithms are enormously popularfor low-security applications. Users either dont realize or dont care about thesecurity problems inherent in their system.

Modern cryptography solves this problem with a key, denoted by K. This key might be any one of a large number of values. The range of possible values ofthe key is called the keyspace. Both the encryption and decryption operationsuse this key (i.e., they are dependent on the key and this fact is denoted by thek subscript), so the functions now become:

EK(M) = CDK(C) = M

Those functions have the property that (see Figure 1.2):

DK(EK(M)) = M

Figure 1.2 Encryption and decryption with a key.

Some algorithms use a different encryption key and decryption key (see Figure1.3). That is, the encryption key, K1, is different from the correspondingdecryption key, K2. In this case:

EK1(M) = CDK2(C) = MDK2(EK1(M)) = M

Figure 1.3 Encryption and decryption with two different keys.

All of the security in these algorithms is based in the key (or keys); none isbased in the details of the algorithm. This means that the algorithm can bepublished and analyzed. Products using the algorithm can be mass-produced. Itdoesnt matter if an eavesdropper knows your algorithm; if she doesnt knowyour particular key, she cant read your messages.

A cryptosystem is an algorithm, plus all possible plaintexts, ciphertexts, andkeys.

There are two general types of key-based algorithms: symmetric andpublic-key. Symmetric algorithms, sometimes called conventionalalgorithms, are algorithms where the encryption key can be calculated from thedecryption key and vice versa. In most symmetric algorithms, the encryptionkey and the decryption key are the same. These algorithms, also calledsecret-key algorithms, single-key algorithms, or one-key algorithms, requirethat the sender and receiver agree on a key before they can communicatesecurely. The security of a symmetric algorithm rests in the key; divulging thekey means that anyone could encrypt and decrypt messages. As long as thecommunication needs to remain secret, the key must remain secret.