—ciphertext
2.1 Introduction
In this chapter we discuss some of the basic elements of cryptography. This discussion will lay the foundation for the remaining crypto chapters which, in turn, underpin much of the material throughout the book. We'll avoid mathematical rigor as much as possible. Nevertheless, there is enough detail here so that you will not only understand the “what″ but you will also have some appreciation for the “how″ and “why.″
After this introductory chapter, the remaining crypto chapters focus on modern symmetric key cryptography, public key cryptography, and cryptographic hash functions. A handful of topics that are related to cryptography—but not exactly cryptography, per se—are also covered in later chapters.
2.2 How to Speak Crypto
The basic terminology of crypto includes the following:
Cryptology— The art and science of making and breaking “secret codes.″
Cryptography— The making of “secret codes.″
Cryptanalysis— The breaking of “secret codes.″
Crypto— A synonym for any or all of the above (and more), where the precise meaning should be clear from context.
A cipher or cryptosystem is used to encrypt data. The original, unencrypted data is known as plaintext, and the result of encryption is ciphertext. We decrypt the ciphertext to recover the original plaintext. A key is used to configure a cryptosystem for encryption and decryption.
In a symmetric cipher, the same key is used to encrypt and to decrypt, as illustrated by the black box 1 cryptosystem in Figure 2.1. There is also a concept of public key cryptography where the encryption and decryption keys are different. In public key cryptography, we can make the encryption key public—thus the name public key.2 In public key crypto, the encryption key is, appropriately, known as the public key, whereas the decryption key, which must remain secret, is the private key. In symmetric key crypto, the key is known as a symmetric key. We'll avoid the ambiguous term “secret key.″
Figure 2.1 Crypto as a black box
For an ideal cipher, it is infeasible to recover the plaintext from the ciphertext without the key. That is, even if the attacker, Trudy, has complete knowledge of the algorithms used and lots of other information (to be made more precise later), she can't recover the plaintext without the key. That's the goal, although reality sometimes differs.
A fundamental tenet of cryptography is that the inner workings of a cryptosystem are completely known to the attacker, Trudy, and the only secret aspect is a key. This is known as Kerckhoffs’ principle, which, believe it or not, is due to a guy named Kerckhoffs.
In 1883, Kerckhoffs, a Dutch linguist and cryptographer, laid out six principles of cipher design and use [67]. The principle that now bears his name states (among other things) that a cipher “must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.″ This implies that the design of the cipher is not secret.
What is the point of Kerckhoffs’ principle? After all, it must certainly be more difficult for Trudy to attack a cryptosystem if she doesn't know how the cipher works. So, at first glance, it might seem that Kerckhoff is making Trudy's life easier, which is something that we never want to do. There are at least a couple of problems with trying to rely on a secret design for your security. For one, the details of “secret″ systems (whether in cryptography or elsewhere) seldom, if ever, remain secret for long. Reverse engineering can be used to recover algorithms from software, and even algorithms embedded in tamper‐resistant hardware are sometimes subject to reverse engineering attacks and exposure. And, even more worrisome is the fact that secret crypto‐algorithms have a long history of failing to be secure once they have been exposed to public scrutiny—see [50] for a relatively modern example where Microsoft violated Kerckhoffs’ principle.
Cryptographers will not deem a crypto‐algorithm to be worthy until it has withstood extensive public analysis by many knowledgeable cryptographers. The bottom line is that any cryptosystem that does not satisfy Kerckhoffs’ principle is suspect. In other words, ciphers are presumed “guilty″ until “proven″ innocent. Actually, no practical ciphers are proven secure, but there must be a solid body of cryptanalysis indicating that a cipher is not easy to break.
Kerckhoffs’ principle is often extended to cover various aspects of security well beyond cryptography. In other contexts, this basic principle is usually taken to mean that the security design itself is open to public scrutiny. The belief is that “more eyeballs″ are more likely to expose more security flaws, and therefore ultimately result in a system that is more secure. Although Kerckhoffs’ principle (in both its narrow crypto form and in a broader context) seems to be universally accepted in principle, there are many real‐world temptations to violate this fundamental tenet, almost invariably with disastrous consequences. Throughout this book we'll see several examples of security failures that were directly caused by a failure to heed the venerable meneer Kerckhoffs.
In the next section, we look briefly at a few classic cryptosystems. Although the history of crypto is a fascinating topic [61], the purpose of this material is to provide an elementary introduction to some of the crucial concepts that arise in modern cryptography. So, pay attention since we will see all of these concepts again in the next couple of chapters and in many cases, in later chapters as well.
2.3 Classic Ciphers
In this section, we examine four classic ciphers, each of which illustrates a feature that is relevant to modern cryptosystems. First on our agenda is the simple substitution, which is one of the oldest cipher systems—dating back at least 2,000 years—and one that is good for illustrating some basic attacks. We then turn our attention to a type of double transposition cipher, which includes important concepts that are used in modern ciphers. We discuss classic codebooks, since many modern ciphers can be viewed as the “electronic″ equivalent of codebooks. We also consider the one‐time pad, a cipher that is provably secure. No other cipher in this book (or in common use) is provably secure.
2.3.1 Simple Substitution Cipher
First, we consider a particularly simple implementation of a simple substitution cipher. In the simplest case, the message is encrypted by substituting the letter of the alphabet
| plaintext: |
a b c d e f g h i j k l m n o p q r s t u v w x y z
|
| ciphertext: |
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
|
where we've followed the convention that the plaintext is lowercase,