Polyalphabetic cipher

Polyalphabetic cipher

A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case. The Enigma machine is more complex but still fundamentally a polyalphabetic substitution cipher.

History

The Alberti cipher by Leon Battista Alberti around 1467 was believed to be the first polyalphabetic cipher. Alberti used a mixed alphabet to encrypt a message, but whenever he wanted to, he would switch to a different alphabet, indicating that he had done so by including an uppercase letter or a number in the cryptogram. For this encipherment Alberti used a decoder device, his "cipher disk", which implemented a polyalphabetic substitution with mixed alphabets.

Although Alberti is usually considered the father of polyalphabetic cipher, Prof. Ibrahim A. Al-Kadi's 1990 paper ( ref- 2) to the Swedish Royal Institute of Technology in Stockholm regarding the Arabic contributions to cryptology reported (based on a recently discovered ancient script) the knowledge of polyalphabetic ciphers 500 years before Alberti.

Dr. Al-Kadi reported on the Arabic scientist by the name of Abu Yusuf Yaqub ibn Is-haq ibn as Sabbah ibn 'omran ibn Ismail Al-Kindi, who authored a book on cryptology the "Risalah fi Istikhraj al-Mu'amma" (Manuscript for the Deciphering Cryptographic Messages) circa 750 AD. Al-Kindi introduced cryptanalysis techniques (including those for polyalphabetic ciphers) , classification of ciphers, Arabic Phonetics and Syntax and most importantly described the use of several statistical techniques for cryptoanalysis. [This book apparently antedates other cryptology references by 300 years.] [It also predates writings on probability and statistics by Pascal and Fermat by nearly 800 years.]

Johannes Trithemius, in a book published after his death, invented a "progressive key" polyalphabetic cipher. Unlike Alberti's cipher, which switched alphabets at random intervals, Trithemius switched alphabets for each letter of the message. He started with a tabula recta, a square with 26 alphabets in it (Trithemius, writing in Latin, used 24 alphabets). Each alphabet was shifted one letter to the left from the one above it, and started again with A after reaching Z (see image).Trithemius's idea was to encipher the first letter of the message using the first shifted alphabet, so A became B, B became C, etc. The second letter of the message was enciphered using the second shifted alphabet, etc. Alberti's cipher disk implemented the same scheme. It had two alphabets, one on a fixed outer ring, and the other on the rotating disk. A letter is enciphered by looking for that letter on the outer ring, and encoding it as the letter underneath it on the disk. The disk started with A underneath B, and the user rotated the disk by one letter after encrypting each letter.

Trithemius' cipher was trivial to break, and Alberti's machine implementation not much more difficult. Key progression in both cases was poorly concealed from attackers. Even Alberti's implementation of his polyalphabetic cipher was rather easy to break (the capitalized letter is a major clue to the cryptanalyst). For most of the next several hundred years, the significance of using multiple substitution alphabets was missed by almost everyone. Polyalphabetic substitution cipher designers seem to have concentrated on obscuring the choice of a few such alphabets (repeating as needed), not on the increased security possible by using many and never repeating any.

The principle (particularly Alberti's unlimited additional substitution alphabets) was a major advance -- the most significant in the several hundred years since frequency analysis had been developed. A reasonable implementation would have been (and, when finally achieved, was) vastly harder to break. It was not until the mid-1800s (in Babbage's secret work during the Crimean War and Friedrich Kasiski's generally equivalent public disclosure some years later), that cryptanalysis of well-implemented polyalphabetic ciphers got anywhere at all.

References

* Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 0-486-20097-3

* Leon Battista Alberti, A Treatise on Ciphers, trans. A. Zaccagnini. Foreword by David Kahn, Galimberti, Torino 1997.

* Ibrahim A. Al-Kadi "The origins of cryptology: The Arab contributions”, "Cryptologia", 16(2) (April 1992) pp. 97–126.

See also

* Topics in cryptography


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Cipher — For other uses, see Cipher (disambiguation). Edward Larsson s rune cipher resembling that found on the Kensington Runestone. Also includes runically unrelated blackletter writing style and pigpen cipher. In cryptography, a cipher (or cypher) is… …   Wikipedia

  • Cipher disk — The Union Cipher Disk from the American Civil War was 3.75 inches (95 mm) in diameter and made of light yellow heavy card stock. It consisted of two concentric disks of unequal size revolving on a central pivot. The disks were divided along their …   Wikipedia

  • polyalphabetic substitution — /pol ee al feuh bet ik, pol ee /, Cryptography. a system of substitution that mixes together a number of cipher alphabets in a cryptogram so that each plaintext letter is represented by a cipher that repeatedly changes. Cf. monoalphabetic… …   Universalium

  • polyalphabetic substitution — /pol ee al feuh bet ik, pol ee /, Cryptography. a system of substitution that mixes together a number of cipher alphabets in a cryptogram so that each plaintext letter is represented by a cipher that repeatedly changes. Cf. monoalphabetic… …   Useful english dictionary

  • polyalphabetic — adjective Describing a substitution cipher in which plaintext letters in different positions are enciphered using different cryptoalphabets …   Wiktionary

  • Substitution cipher — In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters,… …   Wikipedia

  • Vigenère cipher — The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution.The Vigenère (pronEng|ˌviːdʒɪˈnɛəɹ, veedj ih nair )… …   Wikipedia

  • Alberti cipher — The Alberti Cipher was one of the first polyalphabetic ciphers. Leon Battista Alberti Created in the 15th century (1466/67) by Leon Battista Alberti, it was the peak of cryptography at that time.Its inventor was Leon Battista Alberti, an… …   Wikipedia

  • Classical cipher — A cipher is a means of concealing a message, where letters of the message are substituted or transposed for other letters, letter pairs, and sometimes for many letters. In cryptography, a classical cipher is a type of cipher that was used… …   Wikipedia

  • Running key cipher — In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream. Usually, the book to be used would be agreed ahead of time, while… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”