Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

A theoretical question about the Vigenère cipher:

  1. Without any knowledge about the key (not even it's length) can we tell how much known or chosen plaintext is needed for the adversary to completely recover the key?
  2. What about if we know the key length? (I assume that we'll need plaintext with the same length of the key).
share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

For chosen plaintext and a classic Vigenère cipher, you need only as many characters of plaintext as the length of the key to completely recover the key. It's a trivial reversal. (If the cipher uses 26 scrambled alphabets, it will take more.) if you don't know the length of the key, you will spot the repeating sequence after the second repeat.

For an unknown ciphertext, that's when it gets interesting. You need enough repeats of the keylength to measure the index of coincidence. The Friedman test provides a way to estimate the amount of ciphertext.

share|improve this answer
add comment

The answer to your question is easy: It depends. :-)

First of all I think your two questions can be reduced to one. If you don't know the key length, then you can simply brute force over the different key lengths.

For breaking the Vigenere cipher the proportion cipher_text_length/key_length is the most important number as it determines how many characters of the clear text have been encrypted with the same letter of the key.

But in my opinion there are also other points to be taken into account. For example, it depends on the language of the clear text. Why? Because to determine if a chosen key is the correct one, you need to judge how far the clear text differs from a randomly chosen sequence of letters (or the other way around: how near the clear text comes to the specified language).

For example let's have a look at the English and the German language: In both languages the most frequent letter is "E". The probability of a letter being an "E" is ~17.4% for German and ~12.7% for English. For random text the probability for the letter "E" is 1/26 = ~3.8%. Now lets take the most frequent bigrams of both languages: "ER" in German has a probability of ~3.9% while "TH" in English has a probability of ~2.7%. This leads me to the assumption that German text differs more significantly from a purely random sequence of letters than English. So in case the key is rather long in relation to the given cipher text, it will be easier to break a German Vigenere cipher than an English one.

I once wrote a tool which is breaking Vigenere ciphers. The keys are scored by calculating the fitness of the resulting clear text. The fitness is a measure how probable it is that the text is German or English (depending on the chosen language). My observation is that German texts score slightly higher than English texts, which is no surprise having made the observation above.

So let's have a look at the proportion cipher_text_length/key_length.

The tool I wrote can break the most Vigenere ciphers correctly if the proportion is in the range of ~6 (i.e. the cipher text is around 6 times longer than the key).

Even if the proportion is reduced to 4, lots of Vigenere ciphers can be broken, but in some cases one or another letter of the determined key is wrong (but with human interaction the key can be recovered completely without problems).

So let's take the following cipher (English clear text):

VVRQI EREOY LDPTT MWNFL ECKAV MZPWE EHRZK UHXHI KCISC BGBZH LHEPK DSERK AEESJ KOLIF 
ZJKHB SXSZK SALUA ZPGVX EOKIX OZEIQ VHBHF HWFJI MITSP XHCZS JTYWH VTRSW KVMSG QTKSY 
WYMOF XQPSH IGSOH GMVXC ITPKW YZXAH JVRSK ZWGXT RMTXW AGFDV IQGTK SVXEM OMFWN OFOR

The cipher text is around four times longer than the key. The solver at http://www.guballa.de/pages/geocaching/vigenere-solver.php provides almost the correct key, only one letter is determined incorrectly. This cipher was given as a challenge, refer to http://s13.zetaboards.com/Crypto/topic/6733475/1/.

Not all Vigenere ciphers can be cracked with this accuracy, but in rather exceptional cases even shorter ciphers can be cracked.

Let's take the following Vigenere cipher (German clear text):

ypfznuwwafvtgpqqzt

Here the key length is 5, thus the proportion clear_text_len/key_len is 3.6. Still, the key is determined correctly. You can even shorten the cipher text by cutting off the last 5 characters, reducing the proportion down to 2.6 and even here the correct key is determined. But as I said this is a rather exceptional case.

Why is this case exceptional? Because the fitness function applied is using stochastic methods, and the clear text has very significant characteristics which are recognized by the algorithm.

My first statement was "it depends", and so for some special cases even better results might be achieved. E.g. http://www.sichere.it/vigenere_tool.php shows an interesting approach where extremely short Vigenere ciphers can be broken, but all words of the clear text as well as the key must be found in the dictionary.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.