3
$\begingroup$

I'm doing a decryption competition at a nearby college. We are allowed one cheat sheet so I'm trying to make one. I realized that the Vigenère cipher was very similar to the one time pad and wanted to make sure that I know the difference.

As I understand it, the only difference is that a one time pad has a key that is as long as the message. The Vigenère cipher can use a key that is shorter than the message, so you repeat the key till the end of the message.

Is above description correct?

$\endgroup$
  • 3
    $\begingroup$ Welcome to Cryptography. Yes. $\endgroup$ – kelalaka Feb 19 at 18:43
  • 1
    $\begingroup$ One way to look at it is that the Vigenère cipher is a way to generate a pad like a one-time pad, except each letter in the pad is related to the last one, and it repeats, so it's not a very good way to generate a pad. A much better way to generate a pad is, for example, using the ChaCha stream cipher with a 256-bit key. $\endgroup$ – Squeamish Ossifrage Feb 19 at 18:46
  • $\begingroup$ Almost. Mr Unicorn's bullet point (1) is the crux here. The OTP key is generated by physical non algorithmic processes such as random key board presses (then) or interference within a folded laser beam (now). $\endgroup$ – Paul Uszak Feb 20 at 12:39
  • $\begingroup$ Your teachers will thank you if you write down "Vigenère cipher" correctly. You can always look at the tag vigenere and copy the name. $\endgroup$ – Maarten Bodewes Feb 20 at 23:51
5
$\begingroup$

The Vigenère cipher is essentially a series of interwoven Caesar ciphers, in which the size of the shift is different for each character and is defined by the keyword.

The one-time pad (OTP) is a very similar technique in which the only difference is that key is generally:

  • truly random,
  • at least as long as the message,
  • and never reused (thus the name),

making it provably confidential if the key is kept secret.

In this way, both ciphers make use of modular addition, which is still in use in most modern digital cryptography. But, in the case of the OTP, the length of the key guarantees that the ciphertext is not vulnerable due to repetition in the way that the Vigenère cipher is.

$\endgroup$
1
$\begingroup$

While the Vigenère is very similar to the One-Time Pad (OTP) in the sense of encrypting and decrypting one character at a time with the corresponding nth place characters of the private key (pad) or plain text message, compared to using bits in the OTP, the main difference is the use of XOR (often denoted as ${\oplus}$ 'Exclusive Or', 'disjunction', which returns true only when inputs differ, else returns false) as used in the OTP (when it arrived in electronic format in the early 1900's).

XOR

Therefore, as OTP can operate on binary bits using the XOR operand which fits well with computers (i.e. machine-readable code), it allows math to be performed such as this truth table for XOR for each bit:

If A =0 and B =1, then:

  • ${A \oplus B = B}$
  • ${A \oplus A = A}$
  • ${B \oplus B = A}$
  • ${B \oplus A = B}$

An attacker on the OTP that obtains two different ciphertexts which were computed from the same key (i.e. making it a two-time pad) can XOR both ciphertexts together which would result in a third ciphertext that could be used for cryptanalysis to compute the key that encrypted both (and thus break the security that would have otherwise held if the key was only used once). This is why a key must never be re-used, hence 'one-time' part of OTP. This commutative quality doesn't exist with Vigenère (as you must look up a ciphertext character of which there are 26 of the same on the lookup table).

Lookup Tables

While Vigenère may be comparable to Ceasar ciphers in terms of shifting characters 'modulo the alphabet', the lookup table can vary such as in the case of a DIANA lookup table which given the same ciphertext would produce a different message given the same key (compared to a Vigenère lookup table).

The weakness in Vigenère or Diana style ciphers (or any custom lookup table using that algorithm) is that the ciphertext can leak information if the private key (pad) isn't random (just like with the one-time pad) and given that encrypting with letters implies communicating in a language such as English.

In other words, common words would be subject to frequency analysis (unless the message was a random string of letters) on the resulting ciphertext (as a given plain text letter will encrypt to the same resulting ciphertext letter, as the same key is used for the entire message despite each character being independent of the other). (*See malleability and known-plain texts attacks).

Information-theoretic security

There could be perfect secrecy in either cipher, as a particular ciphertext could be the result of many other plaintext and keys and thus an attacker would have no way to tell which is the correct one as many key/message combinations produce the same ciphertext, for a long enough string.

For example using the OTP, if you had a message in the form of a binary string (0s and 1s)of length n and sufficiently random key of length n, that resulted in a ciphertext of length n, there would be ${2^(n2)}$ possible inputs into the XOR function that an attacker would brute-force search, in terms of the message space multiplied by the keyspace ${(2^n*2^n)}$.

However, there are also exactly 2^n additional number of unique message/key pairs that result in the same exact ciphertext (my interpretation, can be seen in truth table), so even if an attacker's calculations produced the correct ciphertext there would be no way to check which of the 2^n number of combinations is the correct one (as they all map to the same ciphertext).

This assumes the message space, keyspace, and ciphertext space are all ${2^n}$ and have the same lengths.

Finally, if we tried this exercise with the Vigenère cipher, we would find that each ciphertext letter will repeat at most 26 times as the ciphertext table is ${26*26}$ letters (676 total) where a given letter is never repeated on a single row AND column (i.e. the letter A appears once in the first column which is also the first row where it isn't repeated).

Therefore, there are at least 26 possible keys that would decrypt to 26 different letters, for every ciphertext letter. So a message of length n would have ${26^n}$ possible key combinations for each of the ${26^n}$ resulting ciphertext. So any given ciphertext of length ${n}$, can only have at most ${26^n}$ inputs. with no way to tell which is correct as they all produce the same ciphertext.

Thus the main differences between Vigenère and OTP are:

  • Vigenère requires a lookup table and modulo arithmetic
  • OTP can be computed only with XOR using binary strings
  • binary strings that represent words are subject to frequency analysis just as words are subject to using Vigenère
  • both require random keys even if the formats differ (letters vs binary)
  • the potential entropy for a given string will differ, as the libraries are different (2 vs 26), so 132-bit random key would be needed to equate to the entropy of a 28-letter key in Vigenère (where 2^131 is almost 28^10).

P.S. regarding the question of shorter keys that become repeated, if a key of length ${n}$ is repeated ${x}$ number of times it still results in an overall key length of ${l}$ that matches the message length, and such an approach (while not recommended) could be applied with the OTP too if a string of n length was repeated ${x}$ number of times in order to satisfy the length of the message.

$\endgroup$

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.