Polyalphabetic Substitution Ciphers

Basic Encryption and Decryption II

• Monoalphabetic ciphers are weak because their frequency distributions mirror the underlying alphabet.
• A solution is to flatten the frequency distribution using polyalphabetic substitution.
• Polyalphabetic substitution ciphers use different monoalphabetic substitutions as the plaintext message is processed.
• These ciphers use a key to select which substitution rule to apply.
• Examples include the Vigenère cipher and Vernam cipher.

Weakness of Monoalphabetic Ciphers

• Analyzing 2-letter and 3-letter combinations (diagrams and trigrams) reveals common patterns.
• Common digrams and trigrams in English, such as "TH," "ER," "ON," "SS," "EE," "TT," and "FF" can be used as clues for decoding.
• Ciphers can improve by providing multiple substitutes (homophones) for a single letter,
• Two main methods are used—encrypting multiple letters of plaintext at once or using multiple cipher alphabets.

Playfair Cipher

• The Playfair cipher is the best-known multiple-letter encryption cipher.
• It treats digrams (pairs of letters) as units and translates them into ciphertext digrams.
• It's based on a 5x5 matrix of letters using a keyword.
• Invented by Sir Charles Wheatstone in 1854.
• Used as a standard field system by the British and other Allied forces during World War I and II.

Playfair Key Matrix - Encryption

• Fill the matrix with the letters of the keyword (excluding duplicates) and then the rest of the alphabet in alphabetical order.
• Treat pairs of letters in plaintext.
• If letters in the pair are in the same row, replace them with the next letter in that row (circularly).
• If letters are in the same column, replace them with the letter below (circularly).
• Otherwise, substitute each letter with the letter that's in the same row or column occupied by the other letter in the pair.

Playfair Key Matrix - Decryption

• Reverse the encryption process.
• If letters are in different rows and columns, take the opposing corners of their rectangle in the matrix.
• If in the same row, take the letter to the left.
• If in the same column, take the letter above.

Polyalphabetic Ciphers

• Polyalphabetic substitution is an improvement on the basic monoalphabetic cipher.
• Monoalphabetic substitution rules are applied differently as the plaintext proceeds.
• Key characteristics include sets of related monoalphabetic substitution rules, applying a specific rule using a key, and examples like the Vigenère and Vernam ciphers.

Vigenère Cipher

• The Vigenère cipher is one of the simplest polyalphabetic substitution ciphers.
• It's based on a 26-row table (the Vigenère table) representing the 26 Caesar ciphers with shifts from 0 to 25.
• This table is used with a keyword to encrypt a message.
• Each cipher is represented by a key letter.
• The keyword character selects a different Caesar cipher from the table for each plaintext letter.

Vigenère Cipher - Example

• In Example 1, an encryption method and numerical representations are shown
• Example 2 demonstrates the encryption process using a keyword to encrypt plaintext "attack at dawn."
• Example 3 describes the autokey system, which eliminates periodic use of the key phrase and uses the same key with the plaintext to get a running key for encrypting each subsequent letter.

Vernam Cipher

• Vernam cipher provides an ultimate defense against statistical analysis by using a key as long as the message, avoiding statistical relationship.
• This system, invented in 1918 by AT&T engineer Gilbert Vernam, handles binary data using bitwise XOR.
• Encryption uses bitwise XOR of the plaintext and key, and decryption inverts the operation.

One-Time Pad

• A one-time pad, a refinement of the Vernam cipher, uses a randomly generated, one-time key that is as long as the message
• The key is used once, then discarded.
• Every new message necessitates a new key of the same length.
• It eliminates patterns in the resulting ciphertext and makes it statistically impossible to break.

The "Perfect" Substitution Cipher

• An example demonstrates combining letters with randomly selected two-digit numbers using the modulus 26 operation.

Binary Vernam Cipher

• Encryption and decryption using binary data is equivalent to using characters.
• Bitwise XOR of the binary plaintext and key generates the ciphertext, and decryption reverses the operation

Stream vs Block Ciphers

• A stream cipher encrypts each symbol of the plaintext individually into the ciphertext.
• A block cipher encrypts grouped symbols from the plaintext as one block.

Advantages of Stream Ciphers

• Fast transmission due to encrypting each symbol immediately.
• Limited error propagation as each symbol's encryption is independent.

Disadvantages of Stream Ciphers

• Limited diffusion as an encryption of any one symbol does not contain the encrypted symbol of any other symbols.
• Susceptibility to malicious insertions, as an interceptor understanding the cipher text might be able to insert characters.

Advantages of Block Ciphers

• High diffusion; one ciphertext block will depend on multiple plaintext elements.
• Immunity to insertions; an entire block must be present to properly encrypt or decrypt it.

Disadvantages of Block Ciphers

• Slow encryption due to waiting for an entire block's availability before encryption.
• Error propagation as an error in one block may affect subsequent blocks.

Characteristics of "Good" Ciphers (Shannon Characteristics)

• Security needs should drive encryption/decryption labor.
• Keys and ciphering algorithms should be simple.
• Process implementation should be straightforward.
• Error propagation in encryption should be minimal.
• Encrypted text size should not exceed the original message size.

Characteristics of "Good" Ciphers (Confusion and Diffusion)

• Confusion: An interceptor cannot predict how changing one character affects the ciphertext.
• Diffusion: Changes in plaintext affect many parts of the ciphertext, meaning the interceptor needs a lot of ciphertext to infer the algorithm.

Cryptanalysis of Polyalphabetic Substitutions

• Kasiski Method: Identifying repeated patterns in ciphertext to find the key length.
  • Steps outline how to find repeated patterns in the ciphertext and then determine the key length(usually by counting the repeated patterns)
• Index of Coincidence (IC): Measuring the variation between frequencies in a distribution and use this as a way to identify that a text is encrypted by a polyalphabetic cipher

Transpositions (Permutations)

• Changes the order of characters, but the characters themselves remain the same.
• Common techniques include using a geometric figure (like a matrix) to arrange characters.

Transposition Cipher: Columnar Transposition

• Plaintext is organized into a matrix of a specified width.
• Ciphertext is read from the matrix vertically.
• Decryption uses the same matrix, writing the ciphertext column-by-column, and then reads off the result horizontally
• Example is provided for illustration purposes

Explore polyalphabetic substitution ciphers, including Vigenère and Vernam. Learn how these methods use keys to select substitution rules, enhancing security over monoalphabetic ciphers. Understand Playfair cipher basics.