Vigenere Cipher | Sahithyan's Notes

A classical, poly-alphabetic cipher. Invented in 1533 by Giovan Battista Bellaso, misattributed to Blaise de Vigenère.

Each letter is shifted by an amount that depends on its position in the message, so the ciphertext letter frequencies are flattened. Also a stream cipher.

You can find an implementation of the Vigenère cipher in sahithyandev/ciphers.

Encryption

The key is repeated and aligned with the plaintext (as shown below for the key LEMON).

plaintext:  IAMINEVITABLE
key:        LEMONLEMONLEM

Each plaintext letter is shifted forward in the alphabet by the position of the key letter above it (A = 0, B = 1, …, Z = 25).

I shifted by L (11) gives T
A shifted by E (4) gives E

For a key of length $n$ , each key letter picks one of 26 possible shift amounts, independently of the other $n - 1$ key letters. So the number of possible keys is $26 \times 26 \times \dots$ ( $n$ times) $= 26^n$ .

Decryption

The key is repeated and aligned with the ciphertext the same way. Each ciphertext letter is shifted backward by the position of the key letter above it.

T shifted back by L (11) gives I
E shifted back by E (4) gives A

Attacking

Security depends significantly on keeping the key length secret. Once the key length is found, the cipher can be attacked in the same manner as a shift cipher, using statistical properties of the plaintext language for each block of ciphertext extracted from separate keyword positions.

Kasiski Test

Determines the keyword length.

Steps:

Locate a repeating character sequence in the ciphertext.
Count the distances between successive occurrences of that sequence.
Take the greatest common divisor of these distances as the keyword length, or a multiple of it.

Repeated short strings, often common bigrams or trigrams of the language, that align to the same keyword position produce the same ciphertext string.

Worked Example

Plaintext finishhimfinishhim under keyword RUN, with $A = 0$ to $Z = 25$ . The plaintext is the same short phrase said twice, so its repetition shows up directly in the ciphertext.

The keyword is repeated to match the plaintext length.

plaintext:   f i n i s h h i m f i n i s h h i m
keystream:   R U N R U N R U N R U N R U N R U N
ciphertext:  W C A Z M U Y C Z W C A Z M U Y C Z

Each position adds the keystream letter modulo $26$ .

$f (5) + R (17) = 22 = W$
$i (8) + U (20) = 28 \equiv 2 = C$

Ciphertext is WCAZMUYCZWCAZMUYCZ.

Decryption subtracts the keystream letter modulo $26$ at each position.

$W (22) - R (17) = 5 = f$
$C (2) - U (20) = -18 \equiv 8 = i$

Numbering ciphertext positions from 1, the trigram WCA appears at positions 1 to 3 and 10 to 12.

Distance between the occurrences is $10 - 1 = 9$ . Only 1 distance is available, so the keyword length is a divisor of $9$ . Divisors are $1$ , $3$ , $9$ . Length $1$ is ruled out by trying it and getting non-language output. Length $3$ already recovers language, so the keyword length is $3$ .

Split the ciphertext into 3 columns, column $i$ holding positions $i, i + 3, i + 6, \dots$ . Each column is a shift cipher under one keyword letter.

Frequency analysis on each column recovers the shifts $17, 20, 13$ , which is the keyword RUN.

Decrypting with RUN gives finishhimfinishhim.