5
$\begingroup$

The Vigenère cipher can relatively easy be broken when the key size is small compared to the size of the message. One first finds the length of the key, and then uses frequency analysis to actually find the key.

  1. How can one "add" something non-complicated to the Vigenère cipher to make it harder to break? Would it for example help to first apply a permutation the message in some way?

  2. Are there any general strategies for this when using other ciphers?

Improve this question
$\endgroup$
6
  • $\begingroup$ You could compress the data before encrypting it. But why do you want to use classic ciphers? $\endgroup$
    – CodesInChaos
    Aug 23, 2012 at 21:34
  • 1
    $\begingroup$ For a substitution cipher it's easy: Use a 128 bit block instead of a 4.7 bit one. $\endgroup$
    – CodesInChaos
    Aug 23, 2012 at 21:35
  • $\begingroup$ @CodesInChaos: Thanks for the comment. I don't want to use this for anything serious, I am just learning. I would like to understand how one might combine the Vigenere with something simple. Something that would be easy to understand and to implement. What do you mean by the 4.7 bit one? $\endgroup$
    – Thomas
    Aug 23, 2012 at 22:08
  • $\begingroup$ The 26-character English alphabet is about 4.7 bits large. You are basically substituting a values drawn from a pool 4.7 bits large. He is pointing out that instead replacing 128-bit blocks with other 128 bit blocks would greatly improve the quality of the substitution. $\endgroup$
    – B-Con
    Aug 23, 2012 at 22:16
  • $\begingroup$ @B-Con: Ahh, I see. So 2^(4.7) = 26. How would one actually do this? I am not sure that I understand. $\endgroup$
    – Thomas
    Aug 23, 2012 at 23:08

3 Answers 3

Reset to default
3
$\begingroup$

Sticking to monoalphabetic ciphers, Vigenere can be combined with a secret random-like substitution of the plaintext or/and ciphertext alphabet, making it significantly more resistant.

If Vigenere encryption is $$x_j\mapsto (x_j+K[j\bmod k])\bmod{26}$$ where array $K$ is the key or length $k$, I'm discussing $$x_j\mapsto (S[x_j]+K[j\bmod k])\bmod{26}$$ $$x_j\mapsto S'[(x_j+K[j\bmod k])\bmod{26}]$$ $$x_j\mapsto S'[(S[x_j]+K[j\bmod k])\bmod{26}]$$ where arrays $S$ or/and $S'$ are secret 26-letter permutations, which extends the key. Using permutations is necessary so that decryption is possible (this is not required for $K$).

Another option is to use a (possibly public) substitution $S$, and two (or more) rounds of Vigenere cipher with different keys $K$ and $K'$ (preferably: of coprime length): $$x_j\mapsto (S[(x_j+K[j\bmod k])\bmod{26}]+K'[j\bmod k'])\bmod{26}$$

None of this is secure; in particular, any variation on this line suffers that with the same key, identical letters at the same position in the ciphertext occurs iff there are identical letters at the corresponding position in the plaintext, which is a serious weakness.

Improve this answer
$\endgroup$
3
$\begingroup$

For Vigenère specifically, you can make it harder to break by increasing the size of the key and by making the key truly random. If the key is truly random, longer than the plaintext and never reused, then Vigenère becomes equivalent to a One Time Pad.

Even without going that far, it is possible to strengthen many, though not all, cyphers by lengthening and/or randomising the key.

Improve this answer
$\endgroup$
2
$\begingroup$

You can greatly increase the security of the Vigenere cipher by encrypting a second time with a key whose length is relatively prime to that of the first key.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This only increase the the length of the key. You have a new key with the length = LCM(k1,k20) $\endgroup$
    – kelalaka
    Sep 26, 2018 at 16:44
  • $\begingroup$ @kelalaka If the length of the effective key is greater than the plaintext, then the ciphertext would be immune to the Kasiski examination and Friedman tests, correct? $\endgroup$
    – Patriot
    Oct 4, 2019 at 10:43
  • $\begingroup$ @Patriot Then you have an OTP if you use it once. Of course, one has to talk about the key generation, too. Hey, wait, two-time Vigenere is applicable to crib-dragging, too. $\endgroup$
    – kelalaka
    Oct 4, 2019 at 10:48
  • $\begingroup$ @kelalaka In the year since I posted this I learned it doesn't increase security as much as I thought. You're correct the new key's length in characters is LCM(k1, k2). But its security is less than a "normal" key of the same character length. $\endgroup$
    – Meler Lawler
    Oct 4, 2019 at 11:15

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.