1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 1114111 is kinda quirky; 20 and a bit bits. Does it represent something, or is it simply a wacky number for illustration? $\endgroup$ – Paul Uszak Aug 24 at 16:31
  • 2
    $\begingroup$ Why do you think this would be any better than Vigenere? I don't think this makes any attack on Vigenere more difficult at all (not even a little) - it is as "secure" as standard Vigenere. Which is not secure from today's point of view at all. $\endgroup$ – tylo Aug 24 at 18:22
  • $\begingroup$ @tylo thanks for the feedback! And it is with use of the one time pad. $\endgroup$ – Legorooj Aug 27 at 2:03
  • $\begingroup$ @PaulUszak: it's one less than the number of codepoints in Unicode -- although some codepoints can't be characters, and a lot more aren't. $\endgroup$ – dave_thompson_085 Aug 27 at 2:39
  • $\begingroup$ The idea is it preserves text integrity, EG a is ASCII 97, but A is 65, so it allows decrypts as the same as it went in, also allowing you to use punctuation, etc. $\endgroup$ – Legorooj Aug 27 at 23:57
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Re. 1/bullet 2. Why do you say making true random numbers is "difficult and generally impractical"? I find that they're surprisingly easy to make if you follow some simple rules and can wield a soldering iron/breadboard. $\endgroup$ – Paul Uszak Aug 25 at 2:40
  • $\begingroup$ @PaulUszak I agree with that for sure, I have a couple microcontrollers lying around that I use as TRNGs, I think it's awesome that I can make my own secure entropy. But in general I wouldn't consider rigging your own separate, specialized hardware device practical. $\endgroup$ – Jacob H Aug 25 at 3:08
  • $\begingroup$ You could buy one then. There are plenty. Or use Intel's/NSA's RDRAND if you trust it. Or the ones in other modules like ESP32 and Raspberry Pi. $\endgroup$ – Paul Uszak Aug 25 at 12:49
  • $\begingroup$ Oh for sure, I never said you shouldn't. I am just under the impression that needing to spend money on external hardware (and then interfacing it with your application) would qualify as impractical. I will edit my answer to mention hardware TRNGs though, since people should be aware of them. $\endgroup$ – Jacob H Aug 25 at 12:59
  • 1
    $\begingroup$ Feel free, although it's always in flux :-) But now a warning. The opinions therein are not popular with some on this site, although I strived to support them with mathematical analysis, research and other scientist's works. crypto.se is a kinda 'we love NIST site', so use at your own peril... $\endgroup$ – Paul Uszak Aug 25 at 13:22
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @PaulUszak: Not really. Obviously, the modulus has to be $≥$ the alphabet size for encryption to be reversible. And while keeping the modulus close to the alphabet size slightly reduces the information available to the attacker, the real lesson to take home is that repeating-key Vigenère encryption is weak. If you use a non-repeating keystream of (pseudo-)independent values uniformly distributed modulo the modulus, the size of the modulus doesn't matter (except insofar as using an unnecessarily large modulus bloats the ciphertext size). $\endgroup$ – Ilmari Karonen Aug 26 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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