5
$\begingroup$

I have been learning about Vigenère ciphers and then thought of this scenario:

  • A cryptographer encrypts a plaintext English message with a Vigenère cipher,
  • then another cryptographer, who wants to ensure that the message is very secure, encrypts the ciphertext with another Vigenère cipher (with a different key length).

How can you decrypt the message given only the ciphertext? A step-by-step explanation would be greatly appreciated.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – tylo
    Sep 29, 2014 at 14:25

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Jok3r
    Sep 27, 2014 at 20:55
  • $\begingroup$ 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. $\endgroup$
    – mczraf
    Sep 27, 2014 at 21:20
  • $\begingroup$ 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. $\endgroup$
    – mczraf
    Sep 27, 2014 at 21:36
  • $\begingroup$ 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? $\endgroup$
    – Jok3r
    Sep 27, 2014 at 21:37
  • 1
    $\begingroup$ I got to this question from a slightly different situation: I have a system that already has to use multiple keys. Given that, what can I do to ensure best possible security? If you pick prime numbers as key lengths, you can actually improve the whole system quite well. Applying multiple keys equals creating a new key with a length of the lowest common multiple of all the given key-lengths. So if you use keys of sizes 3,5,7,11, you should get a resulting key of length 1155 which is not too shabby, considering you only used 27 letters total for the keys. $\endgroup$ Feb 10, 2016 at 7:41
7
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

The Vigenere Cipher using one key, is horrible. Lets give it a grade of 59. But, applying the method multiple times, using variable length keys, has a much longer repeat cycle. ie: len 3, len 5, len 7 represent a repeat "cycle" every (3*5*7). Now, include several fixed "iterations", and then include variable iterations saved into the stream, and then, and perhaps a diffrent starting position, and you've defined the google method, for FPE (Format Preserving Encryption). (lol). The problem in the end, is that a 1 to 1 encryption method, is not as strong as a 1 to N encryption, when any part of the input is known. But, I'm with you 100%, multiple rounds, is good enough, for data that is already stored securely, and you dont want to store in the clear, and not increase the size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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