Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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.
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:
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:
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.
