Breaking The Vigenere Encryption System
by Adriano M. Garsia
We recall that a Caesar k-shift is the
circular permutation which replaces each letter of the alphabet by the
letter k places later (with wrap around). In Vigenere
encryption, the key consists of a period p and a
sequence k1,k2,...,kp
of Caesar shifts. This given, the plaintext
is broken up into successive strings of p letters each and
the sth letter of each string is replaced
by its image under the Caesar ks-shift. This
encryption system is vulnerable to letter-frequency analysis. The
letter frequencies observed in the sequence of sth
letters have the same distribution as the plaintext letters only ks-shifted.
To break Vigenere encryption, one guesses a period p
and then, by comparing the histogram of observed frequencies of sth
letters to the histogram of English letter probabilities, one is led to
the correct value of ks. A wrong guess for the
period p leads to relatively flat histograms for all or most
of the values of s. The code breaker in this case repeats the
analysis with a new trial period.
The Applet below is programmed to illustrate this codebreaking
process. It was written by David Little and Mike Zabrocki.
- Upon pressing the Random Cyphertext button the
Applet will display some text which is Vigenere encrypted by a randomly
selected key.
- Press the Break button to start the process. The
Applet assumes (most often incorrectly) that p=1. Thus it
proceeds
as if every letter of plaintext was encrypted by the same Caesar shift.
It displays (in red) the histogram of observed letter frequencies,
alongside
a (blue) histogram of english letter probabilities. It also displays
the first 25 characters of your text, decoded according to your current
keyword.
- Press the Period + several times (if
necessary) until the red histogram resembles a shifted version of the
blue
histogram. This given, use the mouse to drag the red histogram to the
position
where it best aproximates the blue histogram. You can also use the
keyboard to type the image of "E". Pressing the SPACE key will shift
the histogram by one position. The Applet stores the shift
corresponding to that position as a tentative value for k1.
- Push the Position Right button and the Applet
will display, again in red, the histogram giving the observed
frequencies
of the 2nd letters of the successive strings. Drag
the
red histogram to the best position as before to obtain the tentative of
k2. Repeat this process until you have
tentatively determined all the other ks.
- At this point you may press the Decrypt button.
The Applet will then decrypt the given cyphertext as if it was
encrypted
by means of the values of k1,k2,...,kp
you have just determined.
A look at the resulting text will make it clear if all of your guesses
were correct or which, if any, need to be changed.