The ViGenere Cipher - a Polyalphabetic Cipher
One of the main problems with simple substitution ciphers is that they are so vulnerable to frequency analysis. Given a sufficiently large ciphertext, it can easily be broken by mapping the frequency of its letters to the know frequencies of, say, English text. Therefore, to make ciphers more secure, cryptographers have long been interested in developing enciphering techniques that are immune to frequency analysis. One of to encrypt the message. A polyalphabetic substitution cipher the most common approaches is to suppress the normal frequency data by using more than one alphabet involves the use of two or more cipher alphabets. Instead of there being a one-to-one relationship between each letter and its substitute, there is a one-to-many relationship between each letter and its substitutes.
The ViGenere Tableauthe
ViGenere Cipher, Proposed by Blaise de Vigenere from the court of Henry Iii of France In The Sixteenth Century, IS A Polyalphabetic Substitution Based On The Following
TABLEAU:
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
A 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
B 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
C 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 b
D D e f G H i J K L M N o P Q R S T U v W x y z a b c
E E F G H i J K L M N o P Q R S T U V W x y z a b c d
F f G H i J K L M N o P Q R S T U V W x YZ A B C D E
G G H i J K L M N o P Q R S T U v W x y z a b C D e f
H h i j k L M n o P q r s T u v w x y z a b C D e f g
I I J K L M N o P Q R S T U v W x Y Z A B C D E F G H
J J K L M N o P q r s T U v w x y z A B C D E F G H i
K K L M N o P q r s T u v w x y z A b C D e f G H i j
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 J KM M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N o P Q R S T U v W x Y Z A B C D E F G H i J K L M
O O P q r s T u V w x y z A b C D e f G H i j k L M n
P P Q R S T U V W x Y Z A B C D E F G H i J K L M N o
Q Q R s T U v w x y z A b C D e f G H i j k L M n o P
R R R S T U V W X Y Z A B C D E F G H i J K L M N o P Q
S S t U v w x y z A b C D e f G H i j k L m N o P Q r
T T U V w x y z A b C D e f G H i j k L m N o P Q r s
U U V w x y z A b C D e f G H i j k L M N o P Q R
V V w x y z A b C D e f G H i j k L M n o P q r s t u
W W x y z A b C D e f G H i J k L m N o P q r s T u V
X x y z A b C D e f G H i j k L M N o P q r s t u v w
Y Y Z A B C D E F G H i J K L M N o P Q R S T U V w x
Z Z Z 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
Note That Each Row Of The Table Corresponds to a Caesar Cipher. THE FIRST ROW IS A Shift of 0; The Second Is A Shift of 1; and The Last IS A Shift of 25.
THE ViGENERE CIPHER USES THIS TABLE TOGETHER WITH WIYWORD TO ENCIPHER A Message. For Example, Suppose We wish to Encipher The PlainText Message:
To be or not to be this is the question
using the keyword RELATIONS. We begin by writing the keyword, repeated as many times as necessary, above the plaintext message. To derive the ciphertext using the tableau, for each letter in the plaintext, one finds the intersection of the row given by the corresponding Keyword Letter and the column given by the plaintext letter itself to pick out the ciphertext letter.
Keyword: Relat Ionsr Elati Onsre Latio NSREL
Plaintext: Tobeo RNOTT Obeth Atist Heque Stion
Ciphertext: Ksmeh Zbblk Smemp Ogajx Sejcs Flzsy
Decipherment of an Encrypted Message Is Equally StraightForward. One Writes The keyword: keyword: Relat Ionsr Elati Onsre Latio NSREL
Ciphertext: Ksmeh Zbblk Smemp Ogajx Sejcs Flzsy
Plaintext: Tobeo RNOTT Obeth Atist Heque Stion
THE IS The PLAINText Letter.
The strength of the Vigenere cipher against frequency analysis can be seen by examining the above ciphertext. Note that there are 7 'T's in the plaintext message and that they have been encrypted by' H, '' L, '' K, '' M , '' G, '' X, 'and' L 'respectively. This successfully masks the frequency characteristics of the English' T. 'One way of looking at this is to notice that each letter of our keyword RELATIONS picks out 1 of the 26 Possible Substitution Alphabets Given In The ViGenere Tableau. Thus, any Message Encrypted by a ViGenere Cipher IS A Collection of As Many Simple Substitution Ciphers As There Are Letters In The Keyword.
Although the Vigenere cipher has all the features of a useful field cipher - ie, easily transportable key and tableau, requires no special apparatus, easy to apply, etc. - it did not catch on its day A variation of it, known. as the Gronsfeld cipher, did catch on in Germany and was widely used in Central Europe. The Gronsfeld variant used the digits of a keynumber instead of a the letters of keyword, but remained unchanged in all other respects. So in fact the Gronsfeld is a WEAKER TECHNIQUE THAN ViGENERE Since It Only Uses 10 Substitution Alphabets (One Per Digit 0..9) instead of the 26 buy by viGenere.solving the viGenery: the Kasiski / Kerckhoff Method
Vigenere-like substitution ciphers were regarded by many as practically unbreakable for 300 years. In 1863, a Prussian major named Kasiski proposed a method for breaking a Vigenere cipher that consisted of finding the length of the keyword and then dividing the message into that many simple Substitution Cryptograms. Frequency Analysis Could The Resulting Simple Substitutions.
Kasiski's technique for finding the length of the keyword was based on measuring the distance between repeated bigrams in the ciphertext. Note that in the above cryptogram the plaintext 'TO' occurs twice bigram in the message at position 0 and 9 and in both cases it lines up perfectly with the first two letters of the keyword. Because of this it produces the same ciphertext bigram, 'KS.' The same can be said of plaintext 'BE' which occurs twice starting at positions 2 and 11, and also is encrypted with the same ciphertext bigram, 'ME.' In fact, any message encrypted with a Vigenere cipher will produce many such repeated bigrams. Although not every repeated bigram will be the result of the encryption of the same plaintext bigram, many will, and this provides the basis for breaking the cipher By measuring and factoring the distances between recurring bigrams -. in this case the distance is 9 - Kasiski was able to guess the length of the keyword for this example, Location 01234 56789 01. 234 56789 01234 56789
Keyword: Relat Ionsr Elati Onsre Latio NSREL
Plaintext: Tobeo RNOTT Obeth Atist Heque Stion
Ciphertext: Ksmeh Zbblk Smemp Ogajx Sejcs Flzsy
The Kasiski Method Would Create Something Like The Following List:
Repeated BigraMlocationDistanceFactorsks993, 9SM1093, 9ME1193, 9 ...
Factoring the distances between repeated bigrams is a way of identifying possible keyword lengths, with those factors that occur most frequently being the best candidates for the length of the keyword. Note that in this example since 3 is also a factor of 9 (and any of its multiples) both 3 and 9 would be reasonable candidates for keyword length. Although in this example we do not have a clear favorite, we've narrowed down the possibilities to a very small list. Note also that if a longer ciphertext were encrypted with the same keyword ( 'RELATIONS'), we would expect to find repeated bigrams at multiples of 9 -. ie, 18, 27, 81, etc. These would also have 3 as a factor Kasiski's important contribution is to note this phenomenon Of repeated bigrams and propose a method - factorying of distances - to analyze it.
Once the length of the keyword is known, the ciphertext can be broken up into that many simple substitution cryptograms. That is, for a keyword of length 9, every 9-th letter in the ciphertext was encrypted with the same keyword letter. Given the structure of the Vigenere tableau, this is equivalent to using 9 distinct simple substitution ciphers, each of which was derived from 1 of the 26 possible Caesar shifts given in the tableau. The pure Kasiski method proceeds by analyzing these simple substitution cryptograms using frequency analysis and the other standard techniques. A variant of this method, proposed by the French cryptographer Kerckhoff, is based on discovering the keyword itself and then using it to decipher the cryptogram. In Kerckhoff's method, after the message has been separated into several columns, corresponding to THE SIMPLE SUBSTITION CRYPTOGRAMS, ONE TALLIES The FREQUENCIES IN Each Column and the Uses Frequency and Logical Analysis To Construct The Key. for Examp le, suppose the most frequent letter in the first column is 'K'. We would hypothesize that 'K' corresponds to the English 'E'. If we consult the Vigenere tableau at this point, we can see that if English 'E' WERE EnciphereED INTO 'K' THEN ROW G of The Table Must Have Been The Alphabet Used for The First Letter of The Keyword. This Implies That The First Letter of The Keyword Is 'G'.
