CHAPTER 3 POLYALPHABETIC CIPHERS - Shodhganga

38

CHAPTER 3 POLYALPHABETIC CIPHERS

3.1

INTRODUCTION

In a polyalphabetic cipher, multiple cipher alphabets are used. To facilitate encryption, all the alphabets are usually written out in a large table, traditionally called a tableau. Usually the tableau is 26 ? 26, so that 26 full ciphertext alphabets are available. The method of filling the tableau, and of choosing which alphabet to use next, defines the particular polyalphabetic cipher. All such ciphers are easier to break than were believed since the substitution alphabets are repeated for sufficiently large plaintexts. One of the most popular was that of Vigenere cipher.

A simple substitution cipher involves a single mapping of the plaintext alphabet onto ciphertext characters (Menezes et al 1997). A more complex alternative is to use different substitution mappings (called multiple alphabets) on various portions of the plaintext. This results in so-called polyalphabetic substitution. In the simplest case, the different alphabets are used sequentially and then repeated, so the position of each plaintext character in the source string determines which mapping is applied to it. Under different alphabets, the same plaintext character is thus encrypted to different ciphertext characters, precluding simple frequency analysis as per monoalphabetic substitution. The simple Vigenere cipher is a polyalphabetic substitution cipher. The definition is repeated here for convenience.

39

3.2

ADVANTAGES OF POLYALPHABETIC CIPHERS

The advantage of Polyalphabetic ciphers is that they make frequency analysis more difficult. Frequency analysis is the practice of decrypting a message by counting the frequency of ciphertext letters, and equating it to the letter frequency of normal text. For instance if P occurred most in a ciphertext whose plaintext is in English, one could suspect that P corresponded to E, because E is the most frequently used letter in English. Using the Vigenere cipher, E can be enciphered as any of several letters in the alphabet in the Vigenere cipher, thus defeating simple frequency analysis (vigenre_cipher).

3.3

VIGENERE CIPHER

The Vigenere cipher is a method of encryption invented by Giovan Batista Belaso and described in his 1553 book, "La cifra del. Sig. Giovan Batista Belaso". It was misattributed to Blaise de Vigenere in the 19th century, and given his name. The cipher is a keyword-based system that uses a series of different Caesar ciphers based on the letters of the keyword. It is a simplified version of the more general polyalphabetic substitution cipher, invented by Alberti ca 1465. This cipher is well-known because while it is easy to understand and implement, it often appears to beginners to be unbreakable. Consequently, many programmers have implemented obfuscation or encryption schemes in their applications which are essentially Vigenere ciphers, only to have them broken by the first cryptanalyst who comes along. Use and cryptanalysis of the Vigenere cipher is therefore frequently introduced at the beginning of courses on cryptography.

In the Vigenere cipher, the first row of the tableau is filled out with a copy of the plaintext alphabet, and successive rows are simply shifted one

40

place to the left. (Such a simple tableau is called tabula recta, and mathematically corresponds to adding the plaintext and key letters, modulo 26.) A keyword is then used to choose which ciphertext alphabet to use. Each letter of the keyword is used in turn, and then they are repeated again from the beginning. So if the keyword is 'CAT', the first letter of plaintext is enciphered under alphabet 'C', the second under 'A', the third under 'T', the fourth under 'C' again, and so on. In practice, Vigenere keys were often phrases several words long. In 1863, Friedrich Kasiski published a method, which enabled the calculation of the length of the keyword in a Vigenere ciphered message. Once this was done, ciphertext letters that had been enciphered under the same alphabet could be picked out and attacked separately as a number of semi-independent simple substitutions complicated by the fact that within one alphabet letters were separated and did not form complete words, but simplified by the fact that usually a tabula recta had been employed. As such, even today a Vigenere type cipher should theoretically be difficult to break if mixed alphabets are used in the tableau, if the keyword is random, and if the total length of ciphertext is less than 27.6 times the length of the keyword. These requirements are rarely understood in practice and so Vigenere enciphered message security is usually less than what might have been.

Other notable polyalphabetics include:

? The Gronsfeld cipher. This is identical to the Vigenere except that only 10 alphabets are used, and so the "keyword" is numerical.

? The Beaufort cipher. This is practically the same as the Vigenere, except the tabula recta is replaced by a backwards one, mathematically equivalent to ciphertext = key ? plaintext.

41

This operation is self-inverse, so that exactly the same table is used in exactly the same way, for both encryption and decryption. ? The autokey cipher, which mixes plaintext in to the keying to avoid periodicity in the key. ? The running key cipher, where the key is made very long by using a passage from a book or similar text.

3.3.1 Definition of Vigenere Cipher

A simple Vigenere cipher of period t, over an s-character alphabet, involves a t -character key k1k2k3...kt. The mapping of plaintext m= m1m2m3.......... to ciphertext c=c1c2c3... is defined on individual characters by ci =m i+ ki mod s, where subscript i in ki is taken modulo t (the key is re-used). The simple Vigenere uses t shift ciphers defined by t shift values ki, each specifying one of s (mono-alphabetic) substitutions; ki is used on the characters in position i , i+s , i+2s..... . In general, each of the t substitution is different; this is referred to as using t alphabets rather than a single substitution mapping. The shift cipher is a simple Vigenere with period t=1.

3.3.2 Vigenere Table

Blaise de Vigenere was born in 1523 in Saint-Pourcain, France. While serving as a diplomat in Rome, he came into contact with Giovanni Battista della Porta in 1549 and learned from Porta's Traicte? des Chiffres 1585 describing various encryption systems. Vigenere's book, "A Treatise on Secret Writing" was published when Vigenere returned to Paris. It contains the basic 26?26 Vigenere tableaux Table 3.1.

42

Table 3.1 Vigenere tableaux

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 A ABCDEFGHIJKLMNOPQRSTUVWXYZ B BCDEFGHIJKLMNOPQRSTUVWXYZA C CDEFGHIJKLMNOPQRSTUVWXYZAB D DEFGHIJKLMNOPQRSTUVWXYZABC E EFGHIJKLMNOPQRSTUVWXYZABCD F FGHIJKLMNOPQRSTUVWXYZABCDE G GHIJKLMNOPQRSTUVWXYZABCDEF H HIJKLMNOPQRSTUVWXYZABCDEFG I IJKLMNOPQRSTUVWXYZABCDEFGH J JKLMNOPQRSTUVWXYZABCDEFGHI K KLMNOPQRSTUVWXYZABCDEFGHIJ L L M N O P Q R S T U V W X Y Z A B C D E F G H I JK M MNOPQRSTUVWXYZABCDEFGHIJKL N NOPQRSTUVWXYZABCDEFGHIJKLM O OPQRSTUVWXYZABCDEFGHIJKLMN P PQRSTUVWXYZABCDEFGHIJKLMNO Q QRSTUVWXYZABCDEFGHIJKLMNOP R RSTUVWXYZABCDEFGHIJKLMNOPQ S STUVWXYZABCDEFGHIJKLMNOPQR T T U V W X Y Z A B C D E F G H I J K LM N O P Q R S U UVWXYZABCDEFGHIJKLMNOPQRST V VWXYZABCDEFGHIJKLMNOPQRSTU W WXYZABCDEFGHIJKLMNOPQRSTUV X XYZABCDEFGHIJKLMNOPQRSTUVW Y YZABCDEFGHIJKLMNOPQRSTUVWX Z ZABCDEFGHIJKLMNOPQRSTUVWXY

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download