Vigenère cipher

The "Vigenère Square" in a modern representation

The Vigenère cipher (also: Vigenère encryption ) is from the 16th century originated hand key method for encryption of kept secret text messages. It is a monographic polyalphabetic substitution method . The plain text is broken down into monograms (individual characters) and these are substituted (replaced) by ciphertext characters that are selected from several (poly) different alphabets in the “Vigenère square” using a password . It is a square arrangement of shifted alphabets standing one below the other (see picture).

The Vigenère cipher is in contrast to the simpler monoalphabetic substitution methods , in which only a single (mono) alphabet is used. Due to its cryptographic security, which was rated as particularly high at the time , it was also referred to as le chiffre indéchiffrable ( French for "the indecipherable cipher"), an assessment that was perhaps correct at the time, but far exaggerated from today's perspective.

history

Such “scrambled” alphabets were proposed by Bellaso in 1553. The key letters can be seen in the leftmost column.

An improved version by Bellaso in 1555

The method goes back to the Tabula recta ( Latin for "square table"), in which the letters of the alphabet are written in lines and shifted one space further to the left with each line. This was given by the German Benedictine abbot Johannes Trithemius (1462-1516) in 1508 in the fifth volume of his six-volume work Polygraphiae libri sex (Six books on polygraphy) written in Latin . In the book published in 1518 after his death, he suggested moving to the next alphabet in his tabula after every single plaintext letter and thus using all available alphabets. With this he invented the "progressive" polyalphabetic encryption. But it was (still) a fixed procedure without a key . This was proposed in 1553 by the Italian cryptologist Giovan Battista Bellaso (approx. 1505–1568 / 81) in the form of a password or a passphrase that could be freely chosen by the encryptor. At that time Latin sayings like VIRTVTI OMNIA PARENT (“Everything obeys proficiency”) were used with pleasure (and cryptographically weak because easy to guess ). The letters of the label determine the order in which the various alphabets must be selected from the table . If all are "used up" (i.e. used once, here after 18 plain text letters), you start all over again. It is therefore a periodic polyalphabetic substitution with a period of 18 in the example .

While Trithemius limited himself to shifted standard alphabets, ie the usual alphabetical order of the letters, Bellaso already used "scrambled" alphabets , which he chose involutorily . This has long been the practice with monoalphabetic substitution methods. Basically, the Italian scholar Leon Battista Alberti (1404–1472) recommended this as early as 1466, long before Trithemius and Bellaso . He suggested changing the alphabets every three or four words. As a mechanical aid, he had invented the "Alberti disk" named after him, an encryption disk , mostly consisting of two round metal disks that sit on a common axis and are connected so that the smaller one can rotate on the larger one. Nearly a century later, in 1563, the Neapolitan scholar Giovanni Battista della Porta (1535–1615) generalized Alberti's scrambled alphabets and Bellaso's password and created the polyalphabetic scrambled alphabet and key cipher. For this purpose Alberti's disk was used, which had to be turned after each letter.

In 1585, the Frenchman Blaise de Vigenère (1523–1596) took up Porta's idea and suggested using the Tabula recta of Trithemius instead of the Alberti disc , but entering scrambled alphabets differently than in the original. This cryptographically strong proposal by Vigenère was forgotten in the following centuries and the method originally proposed by Trithemius became known as the Vigenère cipher.

method

Starting from the standard alphabet with its 26 capital letters, all possible Caesar-shifted alphabets are written below it. You get a square arrangement of 26 × 26 letters, originally called Tabula recta , later also called carré de Vigenère (French for “Vigenère square”). In the following illustration, for the sake of clarity, a line with the plain text letters and a column with the key letters have been added above the actual square, which are generally not required.

Vigenère square

		Plain text
		ABCDEFGHIJKLMNOPQRSTU V W XYZ
S c h l ü s s e l	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	ABCDEFGHIJKLMNOPQRSTU VWXYZ BCDEFGHIJKLMNOPQRSTUV WXYZA CDEFGHIJKLMNOPQRSTUVW XYZAB DEFGHIJKLMNOPQRSTUVWX YZABC EFGHIJKLMNOPQRSTUVWXY ZABCD FGHIJKLMNOPQRSTUVWXYZ ABCDE GHIJKLMNOPQRSTUVWXYZA BCDEF HIJKLMNOPQRSTUVWXYZAB CDEFG IJKLMNOPQRSTUVWXYZABC DEFGH JKLMNOPQRSTUVWXYZABCD EFGHI KLMNOPQRSTUVWXYZABCDE FGHIJ LMNOPQRSTUVWXYZABCDEF GHIJK MNOPQRSTUVWXYZABCDEFG HIJKL NOPQRSTUVWXYZABCDEFGH IJKLM OPQRSTUVWXYZABCDEFGHI JKLMN PQRSTUVWXYZABCDEFGHIJ KLMNO QRSTUVWXYZABCDEFGHIJK LMNOP RSTUVWXYZABCDEFGHIJKL MNOPQ STUVWXYZABCDEFGHIJKLM NOPQR TUVWXYZABCDEFGHIJKLMN opqrs UVWXYZABCDEFGHIJKLMNO PQRST VWXYZABCDEFGHIJKLMNOP Q R STU WXYZABCDEFGHIJKLMNOPQ RSTUV XYZABCDEFGHIJKLMNOPQR STUVW YZABCDEFGHIJKLMNOPQRS TUVWX ZABCDEFGHIJKLMNOPQRST UVWXY	G e h e i m t e x t

To encrypt a plain text such as the sentence "We think Wikipedia is very good", the encryptor first needs a key. Ideally, this should be as long as possible and consist of a sequence of letters that is as "random" as possible . If the length of the key reaches that of the plaintext and if the key is not used more than once, then you get a really "unbreakable" method, as was suggested centuries later, in 1882, by the American cryptologist Frank Miller (1842–1925), and which is known today as a one-time pad (abbreviation: OTP, German: "one-time key procedure"). At the time of Vigenère and well into the 20th century, however, relatively short and often easy-to-guess keys were regularly used, which were also used several times. An example would be using VIGENERE as a keyword.

As a practical aid, the encryptor can write the text to be encrypted in one line and repeat the password as often as necessary:

VIGENERE VIGENERE VIGENERE V
Wikipedi afindenw irsehrgu t

He can now easily determine the corresponding ciphertext letters with the help of the Vigenère square. To do this, he looks for the intersection of the line identified by the respective key letter and the column of the square, which is identified above by the plain text letter. For example, for Vigenère encryption of the first letter W of the text, he looks for the intersection of the line V with the column W and finds the R as the ciphertext letter. The ciphertext completely encrypted in this way is:

RQQMCIUM VNORQIEA DZYIUVXY O

It is usually transmitted in groups of fixed length, for example in groups of five. This measure also serves to prevent the length of the password (here eight) from being revealed. The ciphertext to be transmitted is here:

RQQMC IUMVN ORQIE ADZYI UVXYO

The authorized recipient, like the sender, is in possession of the secret password (here: VIGENERE) and can recover the original plain text from the ciphertext by reversing the encryption steps described above by decryption using the password.

Beaufort cipher

Encryption disk with reversed alphabet (see inner letter ring), suitable for Beaufort encryption and decryption

A variant of the Vigenère cipher arises when the standard alphabet is not shifted to generate the square, but instead the reverted (reversed) standard alphabet is used. This method was used by Sir Francis Beaufort (1774–1857) around 1840 and is named after him. The corresponding square looks like this:

Vigenère square to Beaufort

		Plain text
		a B C D E F G H I J K L M O P Q R S T U V w x y z
S c h l ü s s e l	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	AZYXWVUTSRQPONMLKJIHG FEDCB BAZYXWVUTSRQPONMLKJIH gfedc CBAZYXWVUTSRQPONMLKJI HGFED DCBAZYXWVUTSRQPONMLKJ IHGFE EDCBAZYXWVUTSRQPONMLK JIHGF FEDCBAZYXWVUTSRQPONML KJIHG GFEDCBAZYXWVUTSRQPONM LKJIH HGFEDCBAZYXWVUTSRQPON MLKJI IHGFEDCBAZYXWVUTSRQPO nmlkj JIHGFEDCBAZYXWVUTSRQP ONMLK KJIHGFEDCBAZYXWVUTSRQ PONML LKJIHGFEDCBAZYXWVUTSR QPONM MLKJIHGFEDCBAZYXWVUTS RQPON NMLKJIHGFEDCBAZYXWVUT SRQPO ONMLKJIHGFEDCBAZYXWVU TSRQP PONMLKJIHGFEDCBAZYXWV UTSRQ QPONMLKJIHGFEDCBAZYXW VUTSR RQPONMLKJIHGFEDCBAZYX WVUTS SRQPONMLKJIHGFEDCBAZY XWVUT TSRQPONMLKJIHGFEDCBAZ YXWVU UTSRQPONMLKJIHGFEDCBA ZYXWV VUTSRQPONMLKJIHGFEDCB AZYXW WVUTSRQPONMLKJIHGFEDC BAZYX XWVUTSRQPONMLKJIHGFED CBAZY YXWVUTSRQPONMLKJIHGFE DCBAZ ZYXWVUTSRQPONMLKJIHGF EDCBA	G e h e i m t e x t

In contrast to the original Vigenère cipher, the Beaufort cipher is involutor but not really involutor . This results in the advantage that, as with all involutive ciphers , there is no need to distinguish between encryption and decryption , but the identical method can be used in both cases.

Gronsfeld cipher

In the late 17th century, the imperial field marshal Johann Franz Graf von Gronsfeld-Bronkhorst (1640–1719) proposed a variant of the Vigenère cipher. He reduced the number of shifted alphabets available from 26 to 10 and did not use a password as a key, i.e. a sequence of letters, but instead a number , i.e. a sequence of digits . His reduced square looks like this:

Vigenère square after reduction by Gronsfeld

		Plain text
		a B C D E F G H I J K L M O P Q R S T U V w x y z
S c h l ü s s e l	0 1 2 3 4 5 6 7 8 9	ABCDEFGHIJKLMNOPQRSTU VWXYZ BCDEFGHIJKLMNOPQRSTUV WXYZA CDEFGHIJKLMNOPQRSTUVW XYZAB DEFGHIJKLMNOPQRSTUVWX YZABC EFGHIJKLMNOPQRSTUVWXY ZABCD FGHIJKLMNOPQRSTUVWXYZ ABCDE GHIJKLMNOPQRSTUVWXYZA BCDEF HIJKLMNOPQRSTUVWXYZAB CDEFG IJKLMNOPQRSTUVWXYZABC DEFGH JKLMNOPQRSTUVWXYZABCD EFGHI	G e h e i m t e x t

One possible advantage of the Gronsfeld cipher is that a sequence of digits is often chosen “more randomly” and is then more difficult to guess than a “label” such as VIRTVTI OMNIA PARENT; however, the reduction of the available alphabets from 26 to 10 fundamentally represents a considerable restriction in combinatorial complexity and thus a cryptographic weakening of the method.

Cryptanalysis

→ Main article : Kasiski test

The advantage of a polyalphabetic method such as the Vigenère cipher over the simple monoalphabetic methods common in those centuries - this also includes the nomenclators that were very popular at the time  - is that the frequency range, which is so telltale in monoalphabetic methods, is abolished through the use of many different alphabets . The systematic change of alphabets strengthens the process compared to statistical attack methods. The coincidence index , a universally applicable cryptanalytic tool, which was only developed in the 20th century , is also significantly weakened in polyalphabetic procedures. For a long time - apart from exceptions in which the code breaker could guess the key word or parts of the plaintext - no systematic attack method against the Vigenère encryption, which over the centuries acquired the reputation of an “unbreakable cipher”, was found. Nevertheless, it was rarely used and instead the traditional methods such as nomenclators were used, probably also because many users found the cipher to be too complicated to use.

In 1854, the English scientist Charles Babbage (1791–1871) found a solution to the cipher, but he never published it. The first to describe a generally applicable method of attack on the Vigenère cipher was the Prussian infantry major and cryptologist Friedrich Wilhelm Kasiski (1805–1881). In 1863 he published his book “The Secret Scripts and the Deciphering Art” in Berlin, explaining his idea of ​​deciphering Vigenère-encrypted texts. His deciphering method is still known today under his name as the Kasiski test . The first thing to do is determine the length of the keyword used. To do this, Kasiski searched the ciphertext for letter sequences of length two ( bigrams ) or longer ( trigrams, tetragrams, etc. ) that occur several times, called " Doppler ". Then he determined the distance between the Dopplers. In this way he generated as complete a list as possible of Dopplers occurring in ciphertext and their spacing. In this he looked for common lengths with the help of factorization ( prime factorization ) in order to infer the probable keyword length. In the Cryptologia article Breaking Short Vigenère Ciphers (see literature ) the important page 41 of Kasiski's book is shown. After examining his Vigenère-encrypted sample text with 180 letters, he draws the conclusion: "Here the factor 5 occurs most frequently, the key must therefore contain 5 letters."

Once you have found the key length, in the second step of deciphering the ciphertext can be broken down into its components, each of which was encrypted with the same alphabet. In Kasiski's example, the first, sixth, eleventh, and so on would be considered the first group. The second group consists of the second, seventh, twelfth letters and so on. The third from the third, eighth, thirteenth, and so on. Within each group there is a simple Caesar encryption that can be easily cracked using the frequency analysis. In many cases, the most common ciphertext letter in each group is simply the plaintext "e", the most common letter in most European languages. Once you have identified the "e", all the other letters result immediately, because the Vigenère cipher only uses shifted alphabets and not scrambled ones, as the namesake had actually suggested.

Finally, the code breaker should try to open up the keyword (" Rohrbach's requirement "). Only then is his work considered to have been successfully completed.

literature

• Friedrich L. Bauer : Deciphered secrets - methods and maxims of cryptology . Springer, Berlin 2000 (3rd edition), ISBN 3-540-67931-6 .
• Albrecht Beutelspacher : Cryptology - An introduction to the science of encryption, concealment and concealment. 2nd Edition. Vieweg , Braunschweig 1991, ISBN 3-528-18990-8 .
• Chris Christensen : Gronsfeld Cipher and Beaufort Cipher . MAT / CSC 483, 2006. PDF; 50 kB (English). Retrieved May 23, 2016.
• Helen Fouché Gaines : Cryptanalysis, A Study of Ciphers and Their Solution . Courier Corporation, 1956, ISBN 0-486-20097-3 .
• Friedrich Wilhelm Kasiski : The Secret Scripts and the Deciphering Art ES Mittler and Son, Berlin 1863. Accessed: May 23, 2016.
• Klaus Pommerening : Kasiski's Test - Couldn't the Repetitions be by Accident? Cryptologia , 30: 4, 2006, pp. 346-352, doi: 10.1080 / 01611190600803819 (English). Retrieved May 23, 2016.
• Tobias Schrödel : Breaking Short Vigenère Ciphers , Cryptologia, 32: 4, 2008, pp. 334–347, doi: 10.1080 / 01611190802336097 (English). Retrieved May 23, 2016.
• Simon Singh : Secret Messages - The Art of Encryption from Antiquity to the Times of the Internet. Translated from the English by Klaus Fritz. With numerous black and white illustrations . Deutscher Taschenbuch Verlag , Munich 2012 (11th edition), ISBN 978-3-423-33071-8 .

Web links

• Encryption according to Bellaso.Retrieved : May 23, 2016.
• Encryption according to Gronsfeld Retrieved: May 20, 2016.
• Video: Vigenère encryption . Christian Spannagel 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19818 .
• An implementation of the Vigenère cipher written in C.

Individual evidence

1. ↑ Tobias Schrödel: Breaking Short Vigenère Ciphers , Cryptologia , 32: 4, 2008, pp. 334–347, doi: 10.1080 / 01611190802336097 (English). Retrieved May 23, 2016.
2. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, p. 134.
3. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, p. 121.
4. ^ Steven M. Bellovin: Frank Miller - Inventor of the One-Time Pad . Cryptologia. Rose-Hulman Institute of Technology. Taylor & Francis, Philadelphia PA 35.2011,3 (January), pp. 203-22. ISSN  0161-1194 .
5. ↑ ^{a b} Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, p. 123.
6. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, p. 124.
7. ↑ Klaus Pommerening: Kasiski's Test: Couldn't the Repetitions be by Accident? . Cryptologia, 30: 4, p. 346, doi: 10.1080 / 01611190600803819 .
8. ↑ Simon Singh: Secret Messages . Carl Hanser Verlag, Munich 2000, p. 90. ISBN 3-446-19873-3 .
9. ↑ Tobias Schrödel: Breaking Short Vigenère Ciphers , Cryptologia, 32: 4, 2008, p. 336, doi: 10.1080 / 01611190802336097 (English). Retrieved May 23, 2016.