Understanding the Vigenère Cipher
Tags: python, programming, cryptography, tutorial
Published: 2023-08-23 07:00:38

## About Vigenère Cipher

The Vigenère cipher is a classic encryption technique that dates back to the 16th century. It was invented by a French diplomat and cryptographer named Blaise de Vigenère, hence the name. It was known as “le chiffre indéchiffrable,” which means “the indecipherable cipher,” and remained unbroken until British polymath Charles Babbage broke it in the 19th century.

## How it works

The Vigenère cipher is a polyalphabetic substitution cipher that uses a keyword to encrypt and decrypt messages. The key idea behind the Vigenère cipher is to use multiple Caesar ciphers based on the letters of the keyword.

{% embed https://cognivibes.github.io/programming/01/caesar-cipher %}

Let's say we have a plaintext message {% katex inline %}P{% endkatex %} consisting of {% katex inline %}n{% endkatex %} letters: {% katex inline %}P = p_1, p_2, \ldots, p_n{% endkatex %}​. We also have a keyword {% katex inline %}K{% endkatex %} consisting of {% katex inline %}m{% endkatex %} letters: {% katex inline %}K = k_1, k_2, \ldots, k_m{% endkatex %}​, where {% katex inline %}m \leq n{% endkatex %}.

To encrypt the message, we repeat the keyword until it matches the length of the plaintext. Let {% katex inline %}K' = k_1, k_2, \ldots, k_m, k_1, k_2, \ldots, k_m, \ldots\{% endkatex %} repeated until it matches the length of {% katex inline %}P{% endkatex %}.

To encrypt each letter {% katex inline %}p_i{% endkatex %}​ in the plaintext, we find the corresponding letter {% katex inline %}k_j{% endkatex %}​ in the keyword {% katex inline %}K'{% endkatex %} where {% katex inline %}j{% endkatex %} is the index of {% katex inline %}p_i{% endkatex %}​ modulo {% katex inline %}m{% endkatex %}. Then, we shift the letter {% katex inline %}p_i{% endkatex %}​ by the index of {% katex inline %}k_j{% endkatex %}​ in the alphabet. Let {% katex inline %}E{% endkatex %} represent the encrypted message.

The mathematical representation of the encryption process is given by:
{% katex %}E_i = (p_i + k_j) \mod 26{% endkatex %}
where {% katex inline %}E_i{% endkatex %}​ is the {% katex inline %}i{% endkatex %}-th letter of the encrypted message and {% katex inline %}j = (i−1) \mod m{% endkatex %}.

To decrypt the message, we use a similar process. We repeat the keyword until it matches the length of the ciphertext. Let {% katex inline %}K'' = k_1, k_2, \ldots, k_m, k_1, k_2, \ldots, k_m, \ldots\{% endkatex %} (repeated until it matches the length of {% katex inline %}E{% endkatex %}).

To decrypt each letter {% katex inline %}E_i{% endkatex %}​ in the ciphertext, we find the corresponding letter {% katex inline %}k_j{% endkatex %}​ in the keyword {% katex inline %}K'{% endkatex %} (where {% katex inline %}j{% endkatex %} is the index of {% katex inline %}E_i{% endkatex %}​ modulo {% katex inline %}m{% endkatex %}). Then, we shift the letter {% katex inline %}E_i​{% endkatex %} back by the index of {% katex inline %}k_j{% endkatex %}​ in the alphabet. Let {% katex inline %}D{% endkatex %} represent the decrypted message.

The mathematical representation of the decryption process is given by:
{% katex %}D_i = (Ei−kj) \mod 26{% endkatex %}
where {% katex inline %}D_i{% endkatex %}​ is the {% katex inline %}i{% endkatex %}-th letter of the decrypted message and {% katex inline %}j = (i−1) \mod m{% endkatex %}.

Note that in these equations, we use modular arithmetic with {% katex inline %}26{% endkatex %} since there are {% katex inline %}26{% endkatex %} letters in the English alphabet. Additionally, we assume a simple mapping where {% katex inline %}A{% endkatex %} is represented by {% katex inline %}0{% endkatex %}, {% katex inline %}B{% endkatex %} by {% katex inline %}1{% endkatex %}, and so on.

### Example

Let's use the word "KEY" as the keyword and encrypt the plaintext message "HELLO" using the Vigenère cipher.

First, we repeat the keyword "KEY" to match the length of the plaintext "HELLO". Thus, the repeated keyword becomes "KEYKE".

The corresponding numerical representation of the plaintext message "HELLO" is: 
{% katex %}H \rightarrow 7\\\
E \rightarrow 4\\\
L \rightarrow 11\\\
L \rightarrow 11\\\
O \rightarrow 14{% endkatex %}

Using the mathematical encryption formula {% katex inline %}E_i = (p_i+k_j) \mod 26{% endkatex %}, we can calculate the encrypted values as follows:
{% katex %}E_1 = (7 + 10) \mod 26 = 17 \rightarrow R\\\
E_2 = (4 + 4) \mod 26 = 8 \rightarrow I\\\
E_3 = (11 + 24) \mod 26 = 9 \rightarrow J\\\
E_4 = (11 + 10) \mod 26 = 21 \rightarrow V\\\
E_5 = (14 + 4) \mod 26 = 18 \rightarrow S{% endkatex %}

Thus, the encrypted message is "RIJVS".

To decrypt the ciphertext "RIJVS" back to the original plaintext, we repeat the keyword "KEY" to match the length of the ciphertext. Thus, the repeated keyword becomes "KEYKE".

Using the mathematical decryption formula {% katex inline %}D_i=(E_i−k_j) \mod 26{% endkatex %}, we can calculate the decrypted values as follows:
{% katex %}D_1 = (17 - 10) \mod 26 = 7 \rightarrow H\\\
D_2 = (8 - 4) \mod 26 = 4 \rightarrow E\\\
D_3 = (9 - 24) \mod 26 = 11 \rightarrow L\\\
D_4 = (21 - 10) \mod 26 = 11 \rightarrow L\\\
D_5 = (18 - 4) \mod 26 = 14 \rightarrow O{% endkatex %}

Thus, the decrypted message is "HELLO".

### Vigenère Table
Encryption/decryption in case of Vigenere Cipher is a tedious task. The Vigenère table, also known as the Vigenère square or the Tabula Recta, is used to simplify the process of encryption and decryption. 

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l8qh04lpm65fqigsbth5.png">
  <figcaption>Fig 1. The Vigenère Table</figcaption>
</figure>

It consists of a grid or matrix that provides a systematic way of encrypting and decrypting messages using the Vigenère cipher. The table is formed by aligning multiple Caesar ciphers together, each with a different shift value determined by a keyword. The rows and columns of the table represent the letters of the alphabet, and each cell contains the letter resulting from combining the row and column letters using the Caesar cipher.

## The Code

The encryption-decryption script can be downloaded from here: {% embed https://github.com/cogniVibes/vigenere-cipher %}


Here is the source code of *encryption_decryption.py*:

```python
def vigenere_cipher(text, keyword, mode):
    result = ""
    keyword_length = len(keyword)
    keyword = keyword.upper()
    key_index = 0

    for i, char in enumerate(text):
        if char.isalpha():
            ascii_offset = ord('A') if char.isupper() else ord('a')
            keyword_shift = ord(keyword[key_index % keyword_length]) - ord('A')
            
            if mode == "decrypt":
                keyword_shift = -keyword_shift  # Reverse the shift for decryption

            char = chr((ord(char) - ascii_offset + keyword_shift) % 26 + ascii_offset)
            key_index+=1
        result += char

    return result

# Get mode
while True:
    print('Do you want to (e)ncrypt or (d)ecrypt?')
    response = input('> ').lower()
    if response.startswith('e'):
        action = 'encrypt'
        break
    elif response.startswith('d'):
        action = 'decrypt'
        break
    print('Please enter the letter e or d.')

print("Enter the message.")
message = input('> ')

print("Enter the keyword.")
keyword = input('> ').upper()

# Perform encryption/decryption
result = vigenere_cipher(message, keyword, action)

# Display the result
print(f"Result: {result}")
```

The vigenere_cipher function performs the encryption or decryption operation based on the provided parameters. It initializes an empty string called result to store the final result. It calculates the length of the keyword and converts it to uppercase.

Next, it iterates through each character in the text input. If the character is a letter, it determines whether it is uppercase or lowercase and assigns an ASCII offset accordingly. It calculates the shift value for the current character based on the corresponding letter in the keyword. If the mode is set to "decrypt," it reverses the shift value.

Then, it applies the shift to the current character by subtracting the ASCII offset, adding the keyword shift, and taking the modulo 26 to wrap around the alphabet. Finally, it converts the shifted value back to a character using the ASCII offset and appends it to the result string. The key_index is incremented to ensure the keyword characters are used cyclically.

After processing all characters in the text, the result string contains the encrypted or decrypted message, depending on the mode.

The code prompts the user to enter the encryption or decryption mode (encrypt or decrypt) and stores the response in the action variable. It keeps asking for input until a valid mode is provided.

Then, it asks the user to enter the message and keyword, storing them in the message and keyword variables, respectively.

The vigenere_cipher function is called with the provided inputs (message, keyword, and action), and the result is stored in the result variable.

### The Program in Action

Here is a sample output that we get upon executing the program:

```console
Do you want to (e)ncrypt or (d)ecrypt?
> e
Enter the message.
> Enemy is approaching! Send troops immediately!
Enter the keyword.
> Moonlight
Result: Qbszj qy hibfcnnpouz! Esbq ezuvie wazplohmqzm!

Do you want to (e)ncrypt or (d)ecrypt?
> d
Enter the message.
> Qbszj qy hibfcnnpouz! Esbq ezuvie wazplohmqzm!
Enter the keyword.
> Moonlight
Result: Enemy is approaching! Send troops immediately!
```
Here the key used is *Moonlight*.

## Conclusion

There are several ways to hack the Vigenère Cipher, such as Kasiski examination, Friedman test, frequency analysis, dictionary attack, etc. However, these are advanced methods and require complex application of combinatorics and statistics. Discussing even one of those would require a separate post. For now we will focus on encryption and decryption. I will surely post a Vigenère hack tutorial in future.

**Note:** Vigenère Cipher, although complex, is still too easy to break using modern methods and should not be used for serious encryption purposes.