Polyalphabetic Ciphers - Vigenere Cipher

Polyalphabetic Ciphers

Another way to improve on the simple monoalphabetic technique is to use different monoalphabetic substitutions as one proceeds through the plaintext message. The general name for this approach is polyalphabetic substitution cipher. All these techniques have the following features in common:

1. A set of related monoalphabetic substitution rules is used.

2. A key determines which particular rule is chosen for a given transformation

Vignere Cipher

The Vigenère cipher is a classic method of encrypting alphabetic text by using a simple form of polyalphabetic substitution. It was originally described by Giovan Battista Bellaso in 1553, but it was later misattributed to Blaise de Vigenère, who developed a related but more complex cipher. The Vigenère cipher was considered unbreakable for centuries until it was cryptanalyzed in the 19th century.

Key Features

1. Polyalphabetic Substitution: Uses multiple Caesar ciphers based on the letters of a keyword, making it more resistant to frequency analysis compared to simple substitution ciphers.

2. Keyword-Based: The key determines how each letter in the plaintext is encrypted.

3. Repetitive Key: The key is repeated to match the length of the plaintext.

How It Works

Encryption

1. Choose a Keyword: Select a keyword with no spaces or punctuation.
2. Repeat the Keyword: Extend the keyword so that it matches the length of the plaintext.
3. Shift Each Letter: For each letter in the plaintext, shift it forward by the number of positions indicated by the corresponding letter in the keyword.

Decryption

1. Use the Same Keyword: Align the keyword with the ciphertext.
2. Reverse the Shift: For each letter in the ciphertext, shift it backward by the number of positions indicated by the corresponding letter in the keyword.

Example

Let's encrypt the plaintext "ATTACKATDAWN" using the keyword "LEMON":

1. Repeat the Keyword:

   • Plaintext: A T T A C K A T D A W N
   • Key: L E M O N L E M O N L E M

2. Convert to Numerical Positions (A=0, B=1, ..., Z=25):

   • Plaintext: 0 19 19 0 2 10 0 19 3 0 22 13
   • Key: 11 4 12 14 13 11 4 12 14 13 11 4

3. Encryption:

   • Ciphertext: (0+11) (19+4) (19+12) (0+14) (2+13) (10+11) (0+4) (19+12) (3+14) (0+13) (22+11) (13+4)
   • Ciphertext (mod 26): 11 23 5 14 15 21 4 5 17 13 7 17
   • Ciphertext: L X F O P V E F R N H R

4. Result: The ciphertext is "LXFOPVEFRNHR".

Decryption

To decrypt the ciphertext "LXFOPVEFRNHR" using the keyword "LEMON":

1. Convert to Numerical Positions:

   • Ciphertext: 11 23 5 14 15 21 4 5 17 13 7 17
   • Key: 11 4 12 14 13 11 4 12 14 13 11 4

2. Decryption:

   • Plaintext: (11-11) (23-4) (5-12) (14-14) (15-13) (21-11) (4-4) (5-12) (17-14) (13-13) (7-11) (17-4)
   • Plaintext (mod 26): 0 19 19 0 2 10 0 19 3 0 22 13
   • Plaintext: A T T A C K A T D A W N

3. Result: The plaintext is "ATTACKATDAWN".

Advantages

• Resistance to Frequency Analysis: Since the same letter can be encrypted differently depending on its position in the text and the keyword, it's harder to perform frequency analysis compared to simple substitution ciphers.

Disadvantages

• Keyword Repetition: If the keyword is short, it repeats frequently, making the cipher vulnerable to Kasiski examination and frequency analysis.
• Keyword Management: The security of the cipher depends on keeping the keyword secret.

Cryptanalysis

• Kasiski Examination: By identifying repeated sequences in the ciphertext, an attacker can determine the length of the keyword, which simplifies breaking the cipher.
• Friedman Test: Also known as the Index of Coincidence, this test can be used to estimate the length of the keyword.

Applications

The Vigenère cipher is primarily of historical interest today, as modern encryption methods are far more secure. However, it is a popular teaching tool for illustrating the principles of polyalphabetic substitution ciphers.

Cryptanalysis

The strength of this cipher is that there are multiple ciphertext letters for each plaintext letter, one for each unique letter of the keyword.Thus, the letter frequency information is obscured. However, not all knowledge of the plaintext structure is lost.

It is instructive to sketch a method of breaking this cipher, because the method reveals some of the mathematical principles that apply in cryptanalysis.

For example, if the keyword is deceptive, the message “we are discovered save yourself” is encrypted as

First, suppose that the opponent believes that the ciphertext was encrypted using either monoalphabetic substitution or a Vigenère cipher. A simple test can be made to make a determination. If a monoalphabetic substitution is used, then the statistical properties of the ciphertext should be the same as that of the language of the plaintext.If, on the other hand, a Vigenère cipher is suspected, then progress depends on determining the length of the keyword, as will be seen in a moment. For now, let us concentrate on how the keyword length can be determined.The important insight that leads to a solution is the following: If two identical sequences of plaintext letters occur at a distance that is an integer multiple of the keyword length, they will generate identical ciphertext sequences. In the foregoing example, two instances of the sequence “red” are separated by nine character positions. Consequently, in both cases, r is encrypted using key letter , e is encrypted using key letter , and d is encrypted using key letter .Thus, in both cases, the ciphertext sequence is VTW.We indicate this above by underlining the relevant ciphertext letters and shading the relevant ciphertext numbers.

An analyst looking at only the ciphertext would detect the repeated sequences VTW at a displacement of 9 and make the assumption that the keyword is either three or nine letters in length. The appearance of VTW twice could be by chance and not reflect identical plaintext letters encrypted with identical key letters. However, if the message is long enough, there will be a number of such repeated ciphertext sequences. By looking for common factors in the displacements of the various sequences, the analyst should be able to make a good guess of the keyword length.

Solution of the cipher now depends on an important insight. If the keyword length is $m$ , then the cipher, in effect, consists of $m$ monoalphabetic substitution ciphers. For example, with the keyword DECEPTIVE, the letters in positions 1, 10, 19, and so on are all encrypted with the same monoalphabetic cipher. Thus, we can use the known frequency characteristics of the plaintext language to attack each of the monoalphabetic ciphers separately.

The periodic nature of the keyword can be eliminated by using a nonrepeating keyword that is as long as the message itself.Vigenère proposed what is referred to as an autokey system, in which a keyword is concatenated with the plaintext itself to provide a running key. For example,

key: deceptivewearediscoveredsav

plaintext: wearediscoveredsaveyourself

ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

Even this scheme is vulnerable to cryptanalysis. Because the key and the plaintext share the same frequency distribution of letters, a statistical technique can be applied. For example, $e$ enciphered by , by $e$ , can be expected to occur with a frequency of $0.127^2$, whereas $t$ enciphered by $t$ would occur only about half as often.These regularities can be exploited to achieve successful cryptanalytsis.

Python Code Vigenere Cipher

def generate_key(text, keyword):

    """

    Generate a key by repeating the keyword to match the length of the text.

    """

    keyword = list(keyword)

    if len(text) == len(keyword):

        return keyword

    else:

        for i in range(len(text) - len(keyword)):

            keyword.append(keyword[i % len(keyword)])

    return ''.join(keyword)

def encrypt_vigenere(plaintext, keyword):

    """

    Encrypt the plaintext using the Vigenère cipher and the given keyword.

    """

    key = generate_key(plaintext, keyword)

    ciphertext = []

    for p, k in zip(plaintext, key):

        # Encrypt only alphabetic characters

        if p.isalpha():

            shift = ord(k.upper()) - ord('A')

            if p.isupper():

                encrypted_char = chr((ord(p) - ord('A') + shift) % 26 + ord('A'))

            else:

                encrypted_char = chr((ord(p) - ord('a') + shift) % 26 + ord('a'))

            ciphertext.append(encrypted_char)

        else:

            ciphertext.append(p)

    return ''.join(ciphertext)

def decrypt_vigenere(ciphertext, keyword):

    """

    Decrypt the ciphertext using the Vigenère cipher and the given keyword.

    """

    key = generate_key(ciphertext, keyword)

    plaintext = []

    for c, k in zip(ciphertext, key):

        # Decrypt only alphabetic characters

        if c.isalpha():

            shift = ord(k.upper()) - ord('A')

            if c.isupper():

                decrypted_char = chr((ord(c) - ord('A') - shift + 26) % 26 + ord('A'))

            else:

                decrypted_char = chr((ord(c) - ord('a') - shift + 26) % 26 + ord('a'))

            plaintext.append(decrypted_char)

        else:

            plaintext.append(c)

    return ''.join(plaintext)

# Example usage:

plaintext = "WE ARE DISCOVERED SAVE YOURSELF"

keyword="DECEPTIVE"

encrypted = encrypt_vigenere(plaintext, keyword)

print("Encrypted:", encrypted)

decrypted = decrypt_vigenere(encrypted, keyword)

print("Decrypted:", decrypted)

Output

Encrypted: ZI EGX YMVGQZTKMY VEXI RWPVVINJ

Decrypted: WE ARE DISCOVERED SAVE YOURSELF