49.

Learn Encryption Techniques with BASIC and C++
(Publisher: Wordware Publishing, Inc.)
Author(s): Gil Held
ISBN: 1556225989
Publication Date: 10/01/98

Previous

Table of Contents

Next

Chapter 5
Polyalphabetic Substitution

The conclusion of Chapter 4, Transposition-Based Monoalphabetic Substitution, briefly discussed a major weakness of monoalphabetic substitution-based enciphering techniques. That weakness is its susceptibility to frequency analysis: A relatively long message can be used as a guide for a trial-and-error process in which the most commonly occurring letters in a plaintext alphabet are substituted for the most frequently occurring characters in the enciphered message. A trained cryptanalyst can use this technique as a wedge to further deciphering operations because the correct substitution of one plaintext character for an enciphered character is carried through the entire enciphered message when a monoalphabetic substitution process is employed.

One method used to overcome the weakness of a monoalphabetic substitution system is the use of a polyalphabetic substitution system. Unlike a monoalphabetic substitution system in which each plaintext character is mapped to a fixed ciphertext character, a polyalphabetic substitution system permits each plaintext character to be mapped into a different ciphertext character for a specified number of occurrences prior to being mapped back into its original ciphertext character. The number of different ciphertext characters each plaintext character can be mapped into depends upon the number of ciphertext alphabets used. The number of ciphertext alphabets used defines the period or cyclic redundancy of repetition of the mapping process.

Although a manual enciphering process becomes more difficult to perform as the number of ciphertext alphabets increases, the use of computers significantly reduces this difficulty. This chapter first examines the construction and utilization of several polyalphabetic substitution systems. Similar to previous chapters, this chapter shows you how to construct enciphering and deciphering programs to automate the use of polyalphabetic substitution systems to encipher and decipher messages. This chapter also discusses several variations you may wish to consider in developing different types of polyalphabetic substitution systems.

---

Lawyer and architect Leon Battista Alberti is considered by many to be the father of Western cryptology. The author of the most comprehensive manuscript on cryptanalysis for its time, Alberti is also credited with the invention of polyalphabetic substitution and enciphered code in the fifteenth century.

Alberti’s efforts in the development of a polyalphabetic substitution system took the form of a disk constructed through the use of two copper plates. The circumference of each plate was divided into 24 equal parts known as cells. The larger copper plate, which was stationary, contained the letters of the alphabet entered into each cell in their alphabetic sequence. The letters H, K, and Y were not included as Alberti did not feel they were necessary. Because the letters J, U, and W were not in his alphabet, he inscribed the numbers 1 to 4 to complete the entries in the cells of the fixed plate.

The second plate, whose diameter was smaller than the stationary plate, had 24 cells into which the letters of the Latin alphabet were inscribed in a random order. This plate was movable and was placed over the larger plate, with both plates attached to one another by a needle affixed through the center of both plates. This resulted in the needle providing a relationship between the movable and fixed plate cell entries.

Alberti’s cipher disk enabled the relationship between the plaintext alphabet contained on the circumference on the fixed plate and the ciphertext alphabet contained on the circumference on the movable plate to be altered. To do so simply required the placement of a letter in the movable disk so it was positioned toward a letter on the outer disk. Because each new setting of Alberti’s disk created a new cipher alphabet, each setting resulted in the altering of the plaintext-ciphertext encipherment relationship and enabled encipherment to occur using a polyalphabetic substitution process. All that was required to successfully encipher and decipher messages was for each party to have identical disks and agree upon the initial index letter of the movable disk and a method to change the use of the index.

---

Simple Polyalphabetic Substitution Systems

One of the earliest polyalphabetic substitution systems is known as the Vigenére cipher after its inventor, Blaise de Vigénere. First published in 1586, the Vigenére cipher is based upon the development of a tableau in which all possible displaced alphabets are positioned one under another, commencing with the original alphabet in the top row.

The Vigenére Cipher

Figure 5.1 illustrates the basic Vigenére tableau which consists of 26 rows, with each row containing 26 letters. Note that the Vigenére tableau can be represented as a 26x26 matrix consisting of 676 elements. In fact, the tableau contained in Figure 5.1 was created by the execution of the program POLY1.BAS whose contents are shown in Listing 5.1.

Figure 5.1  Basic Vigenére tableau

Previous

Table of Contents

Next