Modification of vigenere cipher cryptographically secure?

Question

After looking for ages online for a python implementation of the Vigenere cipher, and finding few, I decided to implement it myself. After ironing out all of the flaws, it's now a working (and secure) implementation of the Vigenere cipher. But I had an idea.

What if you increase the size of the alphabet that it's using? eg:

With the size of the alphabet being 1114111 , and all letters of the alphabet having been converted into their ASCII representations (a = 97):

Encryption:

$c^i = (m^i + k^i) \bmod 1114111$

Decryption:

$m^i = (c^i + k^i + 1114111) \bmod 1114111$

Would this be cryptographically secure? And I'm assuming that it would be more secure than traditional Vigenere?

Answer 1

Vigenère Cipher

Let's look at some different attacks on the Vigenère cipher and determine how much of a role alphabet size plays.

From Wikipedia:

The primary weakness of the Vigenère cipher is the repeating nature of its key. If a cryptanalyst correctly guesses the key's length, the cipher text can be treated as interwoven Caesar ciphers, which can easily be broken individually.

With a number like 1114111, breaking the individual Caesar ciphers by brute force would still be pretty easy. Maybe if you increase the size even further (128 bits or higher?). However, there could be attacks that perform better than brute force given the nature of the cipher.

Kasiski Examination: Analyzing repeated groups of ciphertext which could correspond to the key. Extending the alphabet size would not affect this method, the best defense against this would be extending the key (ideally to the length of the plaintext, more on that later).

Key Elimination: We can guess the key length (or figure it out somehow, like the Kasiski method) and remove the key from the ciphertext. This makes the alphabet size redundant (even if it was well above 1114111) because the key would be removed from the ciphertext anyway. To stop this, our key must be as long as our plaintext (see one-time-pad below).

Frequency Analysis and Friedman Test: These rely on having information about the plaintext beforehand. Depending on implementation, your method could break these analysis techniques (or at least make them more difficult to implement).

These are just the methods outlined on Wikipedia for breaking the Vigenère cipher (you can of course look deeper into other methods). It should be pretty clear that Vigenère in the modern world can be considered broken, even if you play with the alphabet length and tweak the cipher in little ways.

One Time Pad (OTP)

Your question is tagged with one-time-pad, so I thought I should address this too. The one time pad can be implemented as a Vigenère cipher with a key that has the same length as the plaintext.

The one time pad is perfectly secure, but it has some stipulations and drawbacks.

1. The key must be truly random, and at least as long as the plaintext.
   • This means it shouldn't be entered by a user, repeated to fit the plaintext length, or generated using any pseudorandom number generator
   • Generating true random numbers is difficult and generally impractical*
   • Practically, you could use a CSPRNG, but then your OTP is only as strong as your CSPRNG (i.e. not a true OTP)
2. The key must never be reused. The key is used once to encrypt, then once to decrypt, then discarded. Encrypting multiple plaintexts using the same key can open you up to attacks (like Key Elimination mentioned above).

If these conditions hold, then the OTP is perfectly random, because any one key is equally as likely as any other. Which means that any plaintext is equally as likely as any other plaintext to the adversary. So even with infinite time and resources, the adversary could never reverse the cipher (without the key).

* Generating truly random numbers can be done using a TRNG, usually implemented as an external hardware device. You can purchase these as USB input devices or make your own circuit.

Answer 2

This is actually slightly less secure than ordinary Vigenère encryption with a small modulus. In particular, all the traditional methods for breaking Vigenère encryption work just as well (or better) with a large modulus:

• The key length can still be determined by calculating the index of coincidence and/or via Kasiski examination.
• If the key is significantly shorter than the plaintext, the cipher can still be broken one key value at a time using frequency analysis. (If it's only somewhat shorter, we can still obtain the difference of the plaintext segments encrypted with each repetition of the key and try to solve it by hand. And conversely, just as with ordinary Vigenère, if the key is at least as long as the message, never reused and perfectly random, then it's theoretically unbreakable.)

The reason it's less secure is because increasing the modulus without also increasing the range of possible plaintext values gives the attacker some extra information.

For example, let's say that we've determined the key length to be $\ell$, and that we observe two ciphertext values $\ell$ steps apart (and thus encrypted using the same key value) to have the values 1106983 and 1107073 modulo 1114111. Their difference is thus 1107073 − 1106983 = 90. If we know (or can pretty confidently guess) that the plaintext is printable ASCII text, that doesn't leave many possible choices, since the range of printable ASCII characters (excluding newlines and tabs) is only 95 characters (from space = 32 up to the tilde ~ = 126). In fact, assuming that both plaintext characters are printable ASCII, that they aren't both fairly uncommon punctuation symbols, and that neither one is a newline or a tab, the only remaining possible solution is that 1106983 encodes a space, 1107073 encodes z and the key value is 1106951. And all that can be deduced from just two ciphertext values!

On the other hand, if the modulus had been only, say, 128, then a difference of 90 between two ciphertext values could also represent a difference of 90 − 128 = −38, which gives a lot more possibilities (e.g. h+A or i+B or j+C, etc.)

Of course, even with a small modulus, Vigenère encryption with a repeating short key is still weak and typically easy to break. Making the modulus unnecessarily large just makes it even easier.