Polyalphabetic substitution
Polyalphabetic replacement ciphers (from ancient Greek πολύς polýs “a lot” and ἀλφάβητος alphábetos “alphabet”) denote forms of text encryption in cryptography in which a letter or character is assigned a different letter or character. In contrast to monoalphabetic substitution , many (“ poly ”) secret alphabets are used to generate the ciphertext from the plaintext .
Caesar encryption as the source progresses
→ Main article: Gronsfeld cipher
This encryption method works similarly to Caesar encryption , but with the difference that the current plaintext character is shifted depending on its position in the plaintext string in the alphabet, starting again at the beginning if necessary. As easy as this process is, the ciphertext can also be quickly deciphered by moving the characters in the other direction in the alphabet depending on their position.
Example:
Klartext: i n t e r n e t Positionen: 1 2 3 4 5 6 7 8 Geheimtext: J P W I W T L B
Vigenère encryption
The Vigenère encryption developed in the 16th century (after Blaise de Vigenère ) has long been considered a secure encryption algorithm (" Le Chiffre indéchiffrable ", German: "The indecipherable encryption"). A keyword determines how many and which alphabets are used. The alphabets are derived from the Caesar substitution .
The British mathematician Charles Babbage succeeded in deciphering a Vigenère cipher for the first time around 1854. However, this discovery was not made public at the time. The Prussian infantry major Friedrich Kasiski published his solution in 1863 (see Kasiski test ) and thus went down in history.
Examples
The key word is “AKEY”, the text “secret”. Four Caesar substitutions encode the text. The first substitution is a Caesar encryption with the key "A". “A” is the first letter in the alphabet. He shifts the first letter of the text to be encrypted, the "g", by 0 places, it remains "G". The second letter of the key, the "K", is the eleventh letter in the alphabet, it shifts the second character of the text, the "e", by ten characters. “E” becomes “O” (see table). The third character of the key ("E") shifts by 4, "Y" by 24 places. The shifting of the next letter of the text begins again with "A", the first letter of the key:
Text: geheimnis Schlüssel: AKEYAKEYA Geheimtext: GOLCIWRGS
| text | |||
|---|---|---|---|
| ABCD E F G H I JKL M N OPQR S TUVWXYZ | |||
|
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 |
ABCDEF G H I JKLMNOPQR S TUVWXYZ |
G e h e i m t e x t |
With the help of the Vigenère square, encryption is even easier: Again, the keyword “AKEY” and the text “secret” are. This means that each letter of the text is assigned a letter of the key, such as the “G” of the text and the “A” of the key. Now look for the row of the key letter (here the A row) and the column of the letter to be encrypted (here the G column), you get “G”. At the second letter of the text, the E, look for the K-row (key) and the E-column (text) and get an "O". In this way, the square serves as a visual aid to simplify the encryption.
Cryptanalysis
Keywords that are relatively short in relation to the text offer little security. The length of the key can be found out by correlating the text with itself ( shifted by n places) and finding the n with the greatest correlation value. If the key length (period) n is known, the cryptanalysis of the Vigenère encryption is reduced to that of the Caesar encryption: All first, second, ..., n -th letters of a period belong to the same Caesar encryption, and a frequency analysis reveals the letter assignment.
In the case of a text that consists only of the repetition of a character, the period is shown directly in the ciphertext . A normal text has sufficient redundancies so that the period can be derived from a certain length of the text compared to the key ( Kasiski test , Friedman test ).
Text: eeeeeeeeeeeee Schlüssel: AKEYAKEYAKEYA Geheimtext: eoiceoiceoice
In this way you can quickly find out the key length of the encrypted text. Now only the ciphertext has to be broken down into columns. The columns which were encrypted with the same letter are combined. The corresponding alphabet shift of the individual partial texts is now solved by means of a frequency analysis.
If the text has little or no redundancy, for example because it is short, the key length cannot be found using the Kasiski test. Provided that the key is a word from a dictionary and the text also begins with a word, the key can be found in many cases by cleverly sorting out improbable N-gram pairs. To this end, text / key combinations are first evaluated, regardless of which of them is plain text or key. The number of possibilities is halved from 26 to 13 in the first step (N / E → R and E / N → R). All remaining N-gram pairs are now weighted according to their probability of being at the beginning of a word. If at least one of the N-grams is extremely unlikely at the beginning of a word, the whole pair is discarded.
Example: EIN / TKX and all 4-grams following this branch can be discarded, since TKX is considered extremely unlikely to be the beginning of a message or a key.
Usually it is already evident from tetragrams that the number of remaining pairs has been reduced so much that it is possible to check all remaining options. Instead of 456,976 (= 26 ^ 4 for tetragrams), there are usually only about one hundred useful options left. Using a dictionary, all words that begin with these tetragrams can now be tried out as keys until a conclusive plain text is obtained. A detailed description was published in 2008 and is implemented in CrypTool v1.4.30.
Only a plain text consisting of statistically equally distributed, nonsensical letter sequences would not be easily accessible to a ciphertext-only attack .
Autokey encryption
The Autokey Vigenère encryption (also known as the Vigenère self-key method), also published by Blaise de Vigenère in " Le Chiffre indéchiffrable ", avoids the periodicity of the keyword by lengthening the key by adding the plain text:
Text: geheimnis Schlüsselwort: AKEY Schlüssel: AKEYGEHEI Geheimtext: GOLCOQUMA
Against known plaintext attacks , the process is of course just as susceptible as the standard Vigenère encryption. In the case of ciphertext-only attacks, however, the cryptanalysis is more complex than with the standard method. However, there are different approaches to this. This is how you take advantage of the fact that certain n-grams occur frequently in natural language. You try to use this as a key in all possible places. If you get meaningful-sounding plaintext syllables as a result, you have found the likely plaintext at this point, but also the key for a subsequent position and, from the key syllable itself, the plaintext of a previous position. It then only remains to determine the length of the shift (keyword length) in order to find the appropriate positions to insert. With this one can generate further parts of the key and the plain text etc. Another possibility is to use different frequencies for the individual letters in the natural language. If you look at a letter in the ciphertext, it can have been formed from different combinations of letters in the plain text and key. However, not all of these combinations are equally likely in natural language. If you guess the right combination, you have parts of the previous plain text or the following key text at your disposal, spaced apart from the keyword length, in order to decipher further letters of the ciphertext, etc.
Vernam
The special case where the key is as long as the text to be encrypted is called the Vernam cipher . If the key is a random sequence of letters and the key is only used once, the process is also known as a one-time pad . Correct decryption is impossible with this without knowledge of the key, and it offers perfect security, which was shown by Claude Elwood Shannon .
Rotor machines
With Vigenère encryption, the key word determines the number and selection of the cipher alphabets. Rollers or wheels on which the letters of the alphabet are engraved do the same. Correctly oriented to each other, you can read the encrypted text directly from them.
If you agree to change the position of the rollers in relation to each other for each letter, the number of available alphabets can be increased many times over (see Enigma , Fialka ).
See also
- Homophonic encryption
- Cryptology
- CrypTool - Free educational software on the subject of cryptography and cryptanalysis, open source
literature
- Friedrich L. Bauer : Deciphered Secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, ISBN 3-540-67931-6 , p. 46.
- Simon Singh : Secret Messages . the art of encryption from antiquity to the times of the Internet , Munich, Hanser, 2000, ISBN 978-3-446-19873-9
Web links
- Encrypt texts online with Autokey -Vigenère
- Encrypt text online with the Vigenère code
- Programming example Vigenère cipher in Java with source code and explanation
supporting documents
- ↑ a b Jörn Müller-Quade : Hieroglyphs, Enigma, RSA - A history of cryptography . Faculty of Computer Science at the University of Karlsruhe, p. 36. Accessed: May 28, 2008. PDF; 2.1 MB
- ↑ Cryptologia (Volume 32, Issue 4, October 2008)
- ↑ Vigenère Autokey procedure ( page no longer available , search in web archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. . Stina Bridgeman: Code Making and Code Breaking . Accessed December 21, 2009. PDF, 88 kB, eng.
- ↑ Classical cryptography . Hans Werner Lang: Cryptography . Retrieved December 21, 2009.
