Chapter 2 Classical Ciphers and Their Cryptanalysis

      Goals, Discussion In this chapter, we survey some historical ciphers which have been used since antiquity. (They are all symmetric ciphers. Public key ciphers were not invented until the 1970s and are discussed in Chapter 3.) Although the ciphers presented here are obsolete, they still provide good examples of cryptographic procedures. For example the Vigenère cipher, being a block cipher, is a forerunner of modern block ciphers such as Advanced Encryption Standard (AES). From these classical ciphers, we can also learn about various attacks in cryptography. This subject is pursued more fully in Chapter 7.

      New, Noteworthy We discuss the Vigenère cipher and show how it can be broken by finding the length of the keyword and then the keyword itself. We explain clearly the simple principles involved without getting bogged down in lengthy formulae. We also give a detailed but accessible description of the famous Enigma system used in World War II both from the mechanical and the mathematical point of view.

2.1 Introduction

Since the early stages of human civilization, there has been a need to protect sensitive information from falling into the wrong hands. To achieve such secrecy, mankind has relied on a branch of mathematics known as cryptography, which is the study of designing methods to securely transmit information over nonsecure channels. In order to achieve this goal, one must first encipher, or scramble, the intended message to prevent an eavesdropper from obtaining any useful information, should the message be intercepted. The message (referred to as plain text) is scrambled into cipher text using a predetermined key, known to both the sender and receiver. The encrypted message is constructed in such a way so as to be resilient against attack, while allowing the intended recipient to decipher, or unscramble the message with ease. The methods we will be investigating in this section to accomplish this task may be outdated and in some cases obsolete, but they can still provide us with valuable insight into some techniques that are still in use today.

2.2 The Caesar Cipher

      While Julius Caesar was building his empire, he needed a method to transmit vital messages without risk of the enemy obtaining any crucial information. To achieve this goal, he employed one of the first known ciphering methods. The idea was to substitute each letter of the plain text with the letter appearing three spaces to the right in the alphabet, i.e. a is enciphered to D, b is enciphered to E, and z is enciphered to C (the alphabet wraps around). Thus, “six” is enciphered to “VLA.”

In practice, this can be easily achieved using a simple device consisting of two disks, such as the one shown in Figure 2.1. Both disks have the alphabet engraved on their perimeter, and they can rotate with respect to each other. If we assign the inner disk to represent the plain text alphabet and the outer disk to represent the cipher text alphabet, enciphering is accomplished simply by rotating the outer disk by three letters counter clockwise and reading off the cipher text corresponding to the plain text. To decipher the message, one must only reverse the procedure. The “key” of the cipher is just the number of letters that the outer disk is shifted by, and is denoted by k. Both sender and recipient are in possession of this common secret key.

      For a numerical explanation, suppose we label by the numbers . Using Caesar's key of three, the plain text message “six” is enciphered as follows:

Figure 2.1 Caesar cipher wheel.

Note that in the above example, . We replace 26 by which is the remainder when we divide by 26 (see Chapter 19 for details). In this case, the remainder is 0, corresponding to the letter A. Similarly, becomes . The number 9 corresponds to the letter J.

      To decipher the message, reverse the operation (shift left by Скачать книгу