Polyalphabetic Substitution: Vigenere Cipher

Basic Encryption and Decryption II

• Monoalphabetic ciphers are weak due to frequency distribution reflecting the underlying alphabet.
• The solution is to flatten the frequency distribution using polyalphabetic substitution.
• Polyalphabetic substitution uses different monoalphabetic substitutions as the message progresses to improve the cipher.
• Techniques like the Vigenere cipher and Vernam cipher employ a set of related monoalphabetic substitution rules, and a key to select a particular rule for a given transformation.
• The Vigenere cipher uses a table of 26 Caesar ciphers with shifts from 0 to 25, a key, and row-column lookup.
• A key is needed that is as long as the message when it is a repeating keyword.
• For example, if the keyword is deceptive, the message "we are discovered save yourself " is encrypted as ZICVTWQNGRZGVTWAVZHCQYGLMGJ and that refers to the Vigenere Table.
• The Vigenere cipher is vulnerable to cryptanalysis if the key is short or repeats, and can be broken with sufficient ciphertext.
• A non-repeating key, like in the autokey system, improves security, but still not resistant to cryptanalysis.
• The Vernam cipher is more secure, using a key as long as the message.
• The Vernam cipher's security relies on the complete randomness of the key.

Weakness of Monoalphabetic Ciphers

• Frequency analysis of 2-letter and 3-letter combinations (digrams and trigrams) is a powerful tool for breaking monoalphabetic ciphers.
• Common digrams like TH, ER, ON, AN, SS, EE, TT, FF are frequent in English text.
• Similarly, common trigrams like THE, AND, THA, ENT, ING, ION, TIO, FOR, NDE, HAS are frequent in English.

Playfair Cipher

• A well-known multiple-letter encryption cipher.
• It treats digrams in the plaintext as single units and translates these into ciphertext digrams.
• It uses a 5x5 matrix of letters, constructed using a keyword.
• Developed by Sir Charles Wheatstone in 1854, it was used by the British and US militaries in World War I and II.
• Repeating letters are separated with filler letters (like x).
• Two letters in the same row swap with the letter to the immediate right (circularly).
• Two letters in the same column swap with the letter below (circularly).
• Otherwise, replace each letter with the letter directly across on the same row.

Playfair Key Matrix - Encryption

• Fill in the keyword (minus duplicates) from left to right and top to bottom.
• Fill in the remaining letters in the matrix alphabetically.
• Encrypt two letters at a time; repeating letters take a filler.

Playfair Key Matrix - Decryption

• Reverse the encryption process:
• Letters in different rows and columns, switch diagonally from the opposite corners of the rectangle.
• Letters in the same row swap with the letter to the immediate left (circularly).
• Letters in the same column swap with the letter above (circularly).
• If no other rule applies, swap each letter with the letter in the opposite corner of the rectangle.

Polyalphabetic Ciphers

• Another way to enhance simple monoalphabetic ciphers.
• Using different monoalphabetic substitutions as the plaintext message progresses.

Vigenère Cipher

• Best known polyalphabetic substitution cipher.
• The set of related monoalphabetic substitution ciphers (MASC's) is made up of 26 Caesar ciphers with shifts from 0 to 25.
• The first row of the table corresponds to a shift of 0, the second to a shift of 1, and the last corresponds to a shift of 25.
• A keyword determines the cipher letter for each plaintext letter.
• Key length impacts security and is a critical factor in brute force attacks. Longer keys increase complexity.

Vigenère Cipher - Example 1 and 2

Examples illustrating the key, plaintext, and ciphertext, often written numerically.

Vigenère Cipher - Example 3

The autokey system (using a non-repeating keyword that is concatenated with the message itself) is introduced to use a non-repeating key phrase for encryption. The increased key length improves the cipher's security but still leaves it vulnerable to cryptanalysis. Critically, this scheme is still not fully resistant to cryptanalysis.

Vernam Cipher

• An ultimate defense against Vigenere cipher cryptanalysis.
• Uses a key as long as the message.
• Encryption involves a bitwise XOR operation between the plaintext and the key.
• Decryption employs the same operation. This makes it extremely difficult to break without knowing the key.

One-Time Pad

• An improvement of the Vernam cipher.
• It uses a truly random key as long as the message, and does not repeat.
• The random nature of the keys makes it statistically unbreakable (in theory).

"Perfect" Substitution Cipher (Example)

• Demonstrates combining letters with a stream of random two-digit numbers using modulo 26 operations for encryption and decryption.

Binary Vernam Cipher

• The Vernam cipher is possible with binary values.
• The binary equivalent of the XOR operation is used for encryption and decryption.

Stream vs Block Ciphers

• Stream ciphers encrypt one symbol of plaintext into one symbol of ciphertext immediately.
• Block ciphers encrypt groups of plaintext symbols as one block.
• Stream ciphers have advantages in speed and low error propagation but are susceptible to modification.
• Block ciphers use diffusion of information from several letters and are immune to insertions but are slower.

Characteristics of "Good" Ciphers

• Shannon characteristics:
  • Amount of secrecy should determine effort of encryption, decryption.
  • Simplicity in algorithm and implementation.
  • Errors in encryption should not propagate or corrupt further information.
  • Ciphered text size should not exceed that of original message.
  • Confusion and Diffusion are essential characteristics of good ciphers.

Cryptanalysis of Polyalphabetic Substitutions

• Kasiski method, uses repeated patterns to determine key length.
• Index of Coincidence (IC), measures variation between frequencies in a distribution, used to identify patterns. A higher IC indicates a greater degree of randomness.

Transpositions (Permutations)

• Plaintext remains the same, characters are reordered.
• Often uses geometric shapes or matrices for arrangement.
• Common example is columnar transposition – letters written into a fixed width matrix and read off vertically, according to a key that defines column order.

Explore polyalphabetic substitution with Vigenere cipher techniques. Understand how it uses multiple monoalphabetic substitutions to flatten frequency distribution, enhancing encryption. Learn about the Vigenere table and its application.