Cryptology

Classical and Modern

Richard E. Klima, Richard Klima, Neil P. Sigmon, Neil Sigmon

• Publisher: Chapman and Hall/CRC
• Year: 2018
• ISBN:
  9781351692533
• Edition: 2
• Topic: Computer Science
• Subtopic: Cryptography
• Index: Computer Science

Cryptology: Classical and Modern, Second Edition proficiently introduces readers to the fascinating field of cryptology. The book covers classical methods including substitution, transposition, Alberti, Vigenère, and Hill ciphers. It also includes coverage of the Enigma machine, Turing bombe, and Navajo code. Additionally, the book presents modern methods like RSA, ElGamal, and stream ciphers, as well as the Diffie-Hellman key exchange and Advanced Encryption Standard. When possible, the book details methods for breaking both classical and modern methods.

The new edition expands upon the material from the first edition which was oriented for students in non-technical fields. At the same time, the second edition supplements this material with new content that serves students in more technical fields as well. Thus, the second edition can be fully utilized by both technical and non-technical students at all levels of study. The authors include a wealth of material for a one-semester cryptology course, and research exercises that can be used for supplemental projects. Hints and answers to selected exercises are found at the end of the book.

Features:

• 
  
  

• Requires no prior programming knowledge or background in college-level mathematics

• 
  
  

• Illustrates the importance of cryptology in cultural and historical contexts, including the Enigma machine, Turing bombe, and Navajo code

• 
  
  

• Gives straightforward explanations of the Advanced Encryption Standard, public-key ciphers, and message authentication

• 
  
  

• Describes the implementation and cryptanalysis of classical ciphers, such as substitution, transposition, shift, affine, Alberti, Vigenère, and Hill

Chapter 1

Introduction to Cryptology

Throughout the history of human communication, the practice of keeping information secret by disguising it, known as cryptography, has been of great importance. Many important historical figures—for example, Julius Caesar, Francis Bacon, and Thomas Jefferson—have used cryptography to protect sensitive information. Before becoming the “Father of the Modern Computer,” Alan Turing played an integral role during World War II in the successful attacks by the Allies on the Enigma machine, which was used by the Germans to disguise information. Important literary figures have also included cryptography in their writings. In fact, William Friedman, called the “Dean of American Cryptology” on a bust at the U.S. National Cryptologic Museum, was first inspired to study the subject through reading Edgar Allan Poe’s short story “The Gold Bug.” Cryptography is also at the heart of some remarkably fascinating accounts from human history, such as the successful attacks on the Enigma machine by the Allies, and the Allies’ own effective use of Navajo code talkers during World War II. There are numerous books devoted exclusively to the history of cryptography, including excellent accounts by David Kahn [13] and Simon Singh [21]. However, cryptography is not just a historical subject. Most of us use cryptographic methods quite frequently, often without knowing or thinking about it, for example, when we purchase items using a credit card or send information using email.

The main purpose of this chapter is to introduce some terminology and concepts involved with studying cryptography, and to preview what lies ahead in this book. We also give a brief description of some of the benefits to learning about cryptography.

1.1 Basic Terminology

In the field of information security, the terms cryptography, cryptanalysis, and cryptology have subtly different meanings. The process of developing a system for disguising information so that ideally it cannot be understood by anyone but the intended recipient of the information is called cryptography, and a method designed to perform this process is called a cryptosystem or a cipher. Cryptanalysis refers to the process of an unintended recipient of disguised information attempting to remove the disguise and understand the information, and successful cryptanalysis is sometimes called breaking or cracking a cipher. Cryptology is an all-inclusive term that includes cryptography, cryptanalysis, and the interaction between them.

When a cipher is used by two parties to exchange information, the undisguised information (in this book, usually a message written in ordinary English) is called the plaintext, and the disguised information is called the ciphertext. The process of converting from plaintext to ciphertext is called encryption or encipherment. Upon receiving a ciphertext, the recipient must remove the disguise, a process called decryption or decipherment. To be able to effectively encrypt and decrypt messages, two correspondents must typically share knowledge of a secret key, which is used in applying the agreed-upon cipher. More specifically, the key for a cipher is information usually known only to the originator and intended recipient of a message, which the originator uses to encrypt the plaintext, and the recipient uses to decrypt the ciphertext.

Often confused with cryptography is the subject of coding theory or codes. Unlike with cryptography, in which the concern is primarily concealing information, with codes the concern is usually transmitting information reliably and efficiently over a communications medium. For example, Morse code is not a cipher. On the other hand, cryptologists do sometimes refer to ciphers as codes, for instance, the Navajo code, which we consider a cipher since it primarily existed to conceal information. Determining the proper use of the word code is ordinarily easy to derive from context. To minimize confusion, the only cipher that we will refer to as a code is the Navajo code, which we will study in Chapter 2.

1.2 Cryptology in Practice

Throughout this book we will demonstrate many different types of ciphers. In practice, it is usually assumed that when a pair of correspondents use a cipher to communicate a message confidentially, the type of cipher used is known by any adversaries wishing to discover the contents of the message. Thus, the security of a cipher, which is simply a measure of how difficult it would be for an adversary to break the cipher, depends only on how difficult it would be for an adversary to find the key for the cipher. The benefit to this is that by correspondents choosing a cipher with an acceptable level of security, they would not have to worry about keeping the type of cipher secret from adversaries.

The various types of ciphers that have been and are used in practice split into two broad categories—symmetric-key and public-key. Symmetric-key ciphers, the only kind that existed before the 1970s, are also sometimes called private-key ciphers. When using a symmetric-key cipher, the originator and intended recipient of a message must keep the key secret from adversaries. In Chapters 2–8 of this book, we will see a variety of different types of symmetric-key ciphers that have been used throughout history. These types of ciphers are more commonly called classical ciphers, since they are not typically useful in communicating sensitive information in modern society. They are still fascinating and fun to study, though. In Chapters 2, 3, and 7, we will see some types of ciphers for which the keys are formed using English words called keywords. For Enigma machine ciphers, which we will study in Chapter 4, the keys are the initial settings of the machine. In Chapters 6 and 8, we will see some types of ciphers for which the keys are mathematical quantities such as numbers or matrices. A deficiency in symmetric-key ciphers is that correspondents must have a way to identify keys in secret, while the very need for a cipher indicates that they have no secret way to communicate.

The invention of public-key ciphers in the 1970s revolutionized the science of cryptology. Public-key ciphers use a pair of keys, one for encryption and one for decryption. When using a public-key cipher, the intended recipient of a message creates both the encryption and decryption keys, publicizes the encryption key so that anyone can know it, but keeps the decryption key secret. That way, the originator of the message can know the encryption key, which he or she needs to encrypt the plaintext, but only the recipient knows the decryption key. It would seem to be a deficiency in public-key ciphers that adversaries can know encryption keys. However, as we will see when we study the two most common types of public-key ciphers in Chapters 9 and 10, although encryption and decryption keys are obviously related, it usually is not realistically possible to find decryption keys from the knowledge of encryption keys.

The development of public-key ciphers did not lead to the demise of symmetric-key ciphers, though. A major reason for this is the fact that public-key ciphers typically operate much more slowly than symmetric-key ciphers. Thus, for correspondents wishing to use a cipher in communicating a large amount of information, it is often most prudent to use a public-key cipher to exchange the key for a symmetric-key cipher, and then use the symmetric-key cipher to actually communicate the information. In Chapter 11, we will see some types of symmetric-key ciphers that are useful in communicating sensitive information in modern society.

Many fascinating historical accounts of cryptology involve successful cryptanalysis. In Chapter 5, we will study in detail one celebrated such account, the attack on the German Enigma machine by Allied cryptanalysts at Bletchley Park near London, England, during World War II. The goal in cryptanalysis is often to determine the key for a cipher. The most obvious method for accomplishing this, known as a brute force attack, involves testing every possible key until finding one that works. Some types of ciphers have a relatively small number of possible keys, and thus can be attacked by brute force. However, brute force is not a legitimate method of attack against most ciphers, even in our technologically advanced society. For example, for the Advanced Encryption Standard, a type of symmetric-key cipher that we will study in Chapter 11, the minimum number of possible keys is 3.4 × 10³⁸, which would take trillions of years to test even using the most advanced current technology.

The security of a cipher is not always tied directly to the number of possible keys, though. For example, although the number of possible keys for a substitution cipher is more than 4 × 10²⁶, we will see in Chapter 2 that substitution ciphers can sometimes be broken relatively easily through a technique called frequency analysis. Also, as we will see in Chapters 3 and 8, there are other types of ciphers against which both a brute force attack and frequency analysis may be pointless, but which can sometimes still be broken relatively easily by adversaries who know a small part of the plaintext, called a crib. In addition, any cipher, no matter how theoretically secure, is always susceptible to being broken due to human error on the part of the users of the cipher. For example, the types of public-key ciphers that we will study in Chapters 9 and 10 are essentially unbreakable, but only provided certain initial parameters are chosen correctly.

The final cryptologic issues we will consider in this book relate to message authentication, specifically verifying that a ciphertext received electronically was really sent by the person claiming to have sent it, and that keys identified electronically really belong to the person claiming to own them. Especially in our digital age, confirming that one is communicating with whom he or she believes to be communicating can be as important as what is actually communicated. We will address these issues in Chapter 12, through the ideas of digital signatures and public-key infrastructures.

1.3 Why Study Cryptology?

An obvious question, especially for individuals with limited experience or natural interest in technical fields, is why would cryptology be worthwhile to study? For that matter, why is the subject of cryptology even important in our society?

One answer to these questions is that due to the ever-increasing dependence of our society upon technology in the communication of information, for instance through ATM transactions and credit card purchases, effective cryptography is essential for commerce that is both private and reliable. Effective cryptography is also essential for personal privacy by individuals who use cell phones or email, or who even just have personal information such as Social Security or driver license numbers stored in government databases. In fact, the dependence of our government and military upon cryptology to ensure secure and authentic communication is so profound that it led to the formation of an entire federal agency, the National Security Agency, whose primary purpose is to create and analyze cryptologic methods, and whose published vision includes “global cryptologic dominance.” In the near future, our society will also likely see an increased dependence upon devices such as smart cards, which are pocket-size cards with integrated computer circuits embedded with cryptographic methods, for identification and financial transactions.

Cryptology is also a multidisciplinary science. As we have noted, the subject is rich with fascinating historical accounts, several of which we will comment on in this book. As we will see in the earlier chapters of this book, knowledge of letter frequencies is important in cryptanalyzing some types of ciphers. Linguistics thus plays a role in cryptology, since letter frequencies naturally vary in different languages. Sociology and culture are evident in cryptology as well. For instance, the Navajo culture and societal beliefs were critical in the development and success of the Navajo code. As we will see in the later chapters of this book, the design and engineering required to construct computers capable of generating the parameters needed for implementing modern ciphers securely and efficiently also play a role in cryptology.

The National Security Agency

The National Security Agency (NSA) is the primary agency for cryptology in the U.S. It is responsible for collecting and analyzing communications between foreign entities, and developing methods for protecting communications originating from U.S. entities. Created in 1952 by President Harry Truman, the NSA specializes in foreign signals intelligence (SIGINT). SIGINT is information from electronic signals and targets, and can be derived from sources such as communications systems, electronic signals, and weapons systems. Research is also a vital component of the operations of the NSA. Its research goals include dominating global computing and communications networks, coping with information overload, providing methods for secure collaboration within the U.S. government and its partners, and penetrating targets that threaten the U.S.

To achieve its goals, the NSA employs a very large number of mathematicians. Computer scientists, engineers, and linguists are also in high demand at the NSA.

The discipline that plays the most integral and important role in cryptology, though, is mathematics. Cryptology provides numerous applications of mathematical topics ranging from elementary arithmetic to advanced collegiate mathematics. In Chapter 4, we will see how combinatorics can be used to analyze the difficulty of breaking Enigma machine ciphers. In Chapter 7, we will see how probability and statistics can be used in the cryptanalysis of Vigenère ciphers. Beginning in Chapter 6, we will explore how modular arithmetic can be used in the implementation and cryptanalysis of several types of ciphers. In Chapters 8 and 11, we will see how matrices can be used in the implementation of classical Hill ciphers and the modern Advanced Encryption Standard. In Chapters 9 and 10, we will see how number theory, specifically division...