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.

I have been learning about Vigenere ciphers and then thought of this scenario: if a cryptographer encrypts a plaintext English message with a Vigenere cipher and then another cryptographer, who wants to ensure that the message is very secure, encrypts the ciphertext with another Vigenere cipher (with a different key length). Given only the ciphertext, how can you decrypt the message? A step by step explanation would be greatly appreciated.

share|improve this question
    
In short: Your new keylength is LCM of both keylengths. But any keylength is leaked by statistical analysis of auto-correlation in a very obvious way (Friedman test gets more inaccurate for longer keys, due to derivation). Anyway, it is just a longer Vigenere, not something more secure. –  tylo Sep 29 at 14:25

2 Answers 2

up vote 1 down vote accepted

A Vigenère cipher is easily breakable, when the ciphertext is reasonably larger than the key size.

This is due to the fact that its cipher-texts leak statistical information about the pair plaintext - key.

Applying a Vigenère cipher several times, with different keys and key-sizes, would not make your scheme much more secure. It might, at most, requires a larger ciphertext than usual, but anyhow some statistical information would be leaked, which in turn can be used to reveal the key and plaintext content.

The only approach to avoid this statistical leakage is by imposing key size == plain text. However, as you might know, this would not be a Vigenère cipher anymore. This cipher would be the One-Time Pad, which not by accident attains perfect secrecy.

share|improve this answer
    
Yeah, I understand the part about the one-time pad, but could you provide maybe some steps on how I would begin to decrypt the ciphertext I described in my question? –  Jok3r Sep 27 at 20:55
    
I will explain the simplest case, I hope that this would be enough to get the idea. The most frequent letter in english is 'e', which appears with probability ~12% in your plaintext. Now suppose your key size is N. Then select in your ciphertext all letters that appear in positions multiple of N: 1, N, 2N, 3N, ... Do you agree that in 12% of this selected letters you must be dealing with a the encryption of a letter 'e', right? This is due to the fact they would be the encryption of a letter with the same key-letter. Now, supposing you use your two-times Vigenère cipher. –  mczraf Sep 27 at 21:20
    
Continuing my comment above... For your two-times Vigenère cipher: Suppose the key-lengths are N1 and N2. Select the letters in the ciphertext at positions multiples of the LCM of N1 and N2. The letter that appear in 12% of the cases among these selected letters would be the encryption of 'e', since it is a ciphertext letter which have been encrypted using the same pair of letters from key1, key2. –  mczraf Sep 27 at 21:36
    
So, would I use the same frequency analysis approach for all the other letters in the ciphertext? Also, how did you know that the letter e would appear ~12% in my plaintext? –  Jok3r Sep 27 at 21:37
    
This is the main concept for the attack, certainly there are many sophistications from this naive approach. Another thing: for having a practical attack, the adversary would need in general a large ciphertext to be analyzed. But this is not a problem in many scenarios. Regarding the letter frequency, you can check it out here: en.wikipedia.org/wiki/Letter_frequency –  mczraf Sep 27 at 21:41

Applying another round of vigenere would make the ciphtertext (in nearly every case) harder to break, yes. The problem is: This "new" algorithm is just a normal vigenere algorithm with a longer key (if the key lengths of both keys are not equal and not 1). You don't need to apply vigenere a second time, you can just calculate the new key in advance.

Example: We encrypt the plaintext "hello world hello world" with the key "ABC". (Encryption with A doesn't change the plaintext, it's like adding 0.)

hello world hello world  
+
ABCAB CABCA BCABC ABCAB  
=
HFNLP YOSND IGLMQ WPTLE

Now we encrypt the intermediate result again with the key "DDBC":

HFNLP YOSND IGLMQ WPTLE
+
DDBCD DBCDD BCDDB CDDBC
=
KIONS BPUQG JIOPR YSWMG

The length of the first key is 3, of the second key is 4. The least common multiple of both numbers is 12. If we now repeat the first key 4 times and "encrypt" it with the second key, we get a new key which eliminates the need for a intermediate result:

ABC ABC ABC ABC
+
DDB CDD BCD DBC
=
DED CEF BDF DCE

If we encrypt the plaintext with this new key we immediately get the final ciphertext:

hello world hello world
+
DEDCE FBDFD CEDED CEFBD
=
KIONS BPUQG JIOPR YSWMG

You see, double encryption (or more generally, multiple encryption) with vigenere doesn't add extra security by itself. You could just use a longer key from the beginning on. Search for generals attacks on vigenere to break this "double encryption".

What about the one-time-pad? You need a fully random, never before used key, which has to be as long as the plaintext for the one-time-pad. If you really use this scheme, you also don't need a double encryption: The one-time-pad is always fully secure if you tell nobody the key.

share|improve this answer

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.