TRB PG Assistant - Cryptography - symmetric cipher model, substitution and transposition techniques, Caesar cipher, monoalphabetic ciphers, Hill cipher, DES E-Book Study Material

Cryptography - Symmetric Cipher Model, Substitution and Transposition Techniques, Caesar Cipher, Monoalphabetic Ciphers, Hill Cipher, DES

1. Introduction to Cryptography

Cryptography is the science of secret communication. It deals with techniques for achieving security—namely confidentiality, data integrity, authentication, and non-repudiation. In essence, it's about transforming readable data (plaintext) into an unreadable format (ciphertext) and back again, in a way that only authorized parties can perform the transformation.

The primary goal of cryptography is to protect information from unauthorized access or modification. This is achieved through encryption (the process of converting plaintext to ciphertext) and decryption (the process of converting ciphertext back to plaintext).

2. The Symmetric Cipher Model

The symmetric cipher model, also known as secret-key cryptography or conventional cryptography, is the simplest form of encryption. In this model, the same secret key is used for both encryption and decryption. This means the sender and receiver must agree on and securely share a secret key before communication can begin.

The process involves:

Sender: Takes the plaintext message and the secret key, and applies an encryption algorithm to produce ciphertext.
Transmission: The ciphertext is sent over a communication channel, which may be insecure.
Receiver: Takes the received ciphertext and the same secret key, and applies the decryption algorithm to recover the original plaintext.

The security of the symmetric cipher model relies entirely on the secrecy of the key. If the key is compromised, an eavesdropper can decrypt any message encrypted with that key.

Key Concept: In symmetric encryption, one key does it all – both locking (encrypting) and unlocking (decrypting). The biggest challenge is securely sharing this single secret key between parties.

Examples of symmetric cipher algorithms include DES (Data Encryption Standard), 3DES, AES (Advanced Encryption Standard), Blowfish, and RC4.

3. Substitution Techniques

Substitution techniques are a fundamental method in cryptography where each character (or block of characters) in the plaintext is replaced by a different character (or block of characters) according to a specific rule or key. The underlying structure of the message remains the same, but the characters themselves are altered.

3.1 Caesar Cipher

The Caesar cipher is one of the simplest and most widely known substitution ciphers. It is a type of monoalphabetic cipher where each letter in the plaintext is shifted a certain number of places down or up the alphabet. For example, a shift of 3 would mean 'A' becomes 'D', 'B' becomes 'E', and so on. When the shift reaches the end of the alphabet, it wraps around.

If the alphabet has 26 letters, there are only 25 possible non-trivial shifts (a shift of 0 or 26 results in the original text). This makes it very vulnerable to brute-force attacks.

Encryption: C = (P + k) mod 26
Decryption: P = (C - k) mod 26

Where:

P is the numerical equivalent of the plaintext letter (A=0, B=1, ..., Z=25).
C is the numerical equivalent of the ciphertext letter.
k is the shift value (the key).

Example: Let k = 3. Encrypt "HELLO".

H (7) -> (7 + 3) mod 26 = 10 -> K
E (4) -> (4 + 3) mod 26 = 7 -> H
L (11) -> (11 + 3) mod 26 = 14 -> O
L (11) -> (11 + 3) mod 26 = 14 -> O
O (14) -> (14 + 3) mod 26 = 17 -> R

Ciphertext: "KHOOR"

Caesar Cipher Shortcut: Think of it as a simple "slide" of letters. Too easy to guess the slide!

3.2 Monoalphabetic Ciphers

A monoalphabetic cipher is a substitution cipher where each letter in the plaintext is consistently replaced by a specific ciphertext letter. The mapping between plaintext letters and ciphertext letters is fixed throughout the entire message. This is a generalization of the Caesar cipher, where the shift is not necessarily a fixed number but can be any arbitrary permutation of the alphabet.

For example, in a monoalphabetic cipher, 'A' might always be replaced by 'Q', 'B' by 'X', 'C' by 'J', and so on, for the entire message.

The key in a monoalphabetic cipher is the specific substitution alphabet. There are 26! (26 factorial) possible keys, which is a very large number (approximately 4 x 10²⁶). This makes brute-force attacks infeasible. However, monoalphabetic ciphers are vulnerable to frequency analysis.

Frequency Analysis: In any natural language, certain letters appear more frequently than others (e.g., 'E' is the most common letter in English). By analyzing the frequency of letters in the ciphertext, an attacker can often deduce the substitution mapping and break the cipher.

Example: Plaintext alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Ciphertext alphabet: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

Encrypting "HELLO" using this mapping:

H -> I
E -> T
L -> S
L -> S
O -> G

Ciphertext: "ITS SG" (Spaces are often ignored or handled separately).

Monoalphabetic Cipher Vulnerability: While the number of keys is huge, the fixed mapping means letter frequencies in the ciphertext will mirror those in the plaintext language. Attackers exploit this by matching common ciphertext letters to common plaintext letters.

3.3 Hill Cipher

The Hill cipher is a polygraphic substitution cipher, meaning it encrypts blocks of letters rather than individual letters. It uses linear algebra, specifically matrix multiplication, to perform the substitution. This makes it more resistant to frequency analysis than monoalphabetic ciphers.

The cipher works by representing plaintext letters as numbers (e.g., A=0, B=1, ..., Z=25). Plaintext is then divided into blocks of size 'n'. Each block is treated as a vector, and this vector is multiplied by an 'n x n' key matrix. The result is taken modulo 26 to produce the ciphertext block.

Encryption Process:

Choose a key matrix K of size n x n. The determinant of K (mod 26) must be coprime to 26 (i.e., gcd(det(K), 26) = 1) for decryption to be possible.
Convert plaintext letters into numerical vectors of size n. Pad the last block if necessary.
For each plaintext vector P_i, calculate the ciphertext vector C_i = K * P_i (mod 26).

Decryption Process:

Find the inverse of the key matrix K, denoted as K^-1, modulo 26. This requires the determinant of K to be coprime to 26.
For each ciphertext vector C_i, calculate the plaintext vector P_i = K^-1 * C_i (mod 26).

Example (n=2): Key Matrix K = $$ \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} $$

Let's encrypt the plaintext "ACT".

Convert to numbers: A=0, C=2, T=19.

Divide into blocks of 2: (A, C) and (T, P) - Pad 'T' with a dummy letter, say 'P' (15), to make a pair.

Block 1: P₁ = $$ \begin{pmatrix} 0 \\ 2 \end{pmatrix} $$

C₁ = K * P₁ mod 26 = $$ \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \begin{pmatrix} 0 \\ 2 \end{pmatrix} = \begin{pmatrix} (3*0 + 3*2) \\ (2*0 + 5*2) \end{pmatrix} = \begin{pmatrix} 6 \\ 10 \end{pmatrix} $$ mod 26 = $$ \begin{pmatrix} 6 \\ 10 \end{pmatrix} $$

Numerical values 6 and 10 correspond to G and K. So, the first ciphertext block is "GK".

Block 2: P₂ = $$ \begin{pmatrix} 19 \\ 15 \end{pmatrix} $$ (for T and P)

C₂ = K * P₂ mod 26 = $$ \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \begin{pmatrix} 19 \\ 15 \end{pmatrix} = \begin{pmatrix} (3*19 + 3*15) \\ (2*19 + 5*15) \end{pmatrix} = \begin{pmatrix} (57 + 45) \\ (38 + 75) \end{pmatrix} = \begin{pmatrix} 102 \\ 113 \end{pmatrix} $$ mod 26 = $$ \begin{pmatrix} 102 \mod 26 \\ 113 \mod 26 \end{pmatrix} $$ = $$ \begin{pmatrix} 24 \\ 9 \end{pmatrix} $$

Numerical values 24 and 9 correspond to Y and J. So, the second ciphertext block is "YJ".

Ciphertext: "GKYJ"

To decrypt, we would need to find K^-1 mod 26. Determinant of K = (3*5 - 3*2) = 15 - 6 = 9. gcd(9, 26) = 1, so an inverse exists. Inverse of K = (det(K))^-1 * adj(K) mod 26. The modular multiplicative inverse of 9 mod 26 is 3 (since 9 * 3 = 27 = 1 mod 26). Adjugate of K = $$ \begin{pmatrix} 5 & -3 \\ -2 & 3 \end{pmatrix} $$ mod 26 = $$ \begin{pmatrix} 5 & 23 \\ 24 & 3 \end{pmatrix} $$ K^-1 = 3 * $$ \begin{pmatrix} 5 & 23 \\ 24 & 3 \end{pmatrix} $$ mod 26 = $$ \begin{pmatrix} 15 & 69 \\ 72 & 9 \end{pmatrix} $$ mod 26 = $$ \begin{pmatrix} 15 & 17 \\ 20 & 9 \end{pmatrix} $$

Hill Cipher Trick: Think of it as encrypting multiple letters at once using a "matrix shuffle". The key is the shuffle pattern (the matrix), and it needs a special "unshuffle" pattern (inverse matrix) for decryption.

4. Transposition Techniques

Transposition techniques rearrange the order of the letters in the plaintext message without changing the actual letters themselves. Unlike substitution ciphers, the same letter appears in the ciphertext as in the plaintext, but in a different position.

These techniques are often used in combination with substitution to create more complex and secure ciphers.

4.1 Rail Fence Cipher

The Rail Fence cipher is a simple form of transposition cipher. The plaintext is written downwards diagonally on successive "rails" of an imaginary fence, and then read off row by row.

Example: Encrypt "WE ARE DISCOVERED FLEE AT ONCE" with 3 rails.

Write the message in a zig-zag pattern:


  W . . . E . . . C . . . R . . . L . . . T . . . E 

  . E . R . D . S . O . E . E . F . E . A . O . C . 

  . . A . . . I . . . V . . . D . . . E . . . N . .

Read off the rails row by row:

Rail 1: WECRLTE

Rail 2: ERDSOEEFAO C

Rail 3: AIVDEN

Ciphertext: "WECRLTEERDSOEEFAOC AIVDEN" (spaces are usually removed or handled separately).

Rail Fence Trick: Imagine writing the message on bunk beds (rails) and then reading each bed's contents separately.

4.2 Columnar Transposition

In columnar transposition, the plaintext is written out in rows under a keyword. The number of columns is equal to the length of the keyword. The columns are then reordered based on the alphabetical order of the letters in the keyword. The ciphertext is obtained by reading down the columns in this new order.

Example: Keyword: "ZEBRAS" (length 6) Plaintext: "WE ARE DISCOVERED FLEE AT ONCE"

1. Write the plaintext under the keyword:


  Z E B R A S
  W E A R E D
  I S C O V E
  R E D F L E
  E A T O N C
  E . . . . .

2. Determine the order of columns based on the alphabetical order of the keyword letters: A (1), B (2), E (3), R (4), S (5), Z (6)

3. Read down the columns in this order:

Column A (1): E V L N
Column B (2): A C D T
Column E (3): E S E A E
Column R (4): R O F O
Column S (5): D E E C
Column Z (6): W I R E

Ciphertext: "EVNLACDTESEAE ROFODEE CWI RE" (spaces removed).

Columnar Transposition Trick: The keyword dictates the "column shuffle". You write the message, then rearrange the columns based on the keyword's alphabetical order.

5. DES (Data Encryption Standard)

DES is a symmetric-key block cipher that was widely used for many years. It was developed by IBM and adopted as a federal standard in the United States in 1977. DES encrypts data in 64-bit blocks using a 56-bit key.

Although once considered secure, DES is now considered insecure due to its small key size (56 bits), which makes it vulnerable to brute-force attacks with modern computing power. However, understanding its structure is crucial for appreciating the evolution of block ciphers.

5.1 DES Structure

DES is based on the Feistel cipher structure, which involves a series of rounds. Each round performs a complex transformation on the data, using a subkey derived from the main key.

The main stages of DES are:

Initial Permutation (IP): The 64-bit block of plaintext is first subjected to an initial permutation, rearranging the bits.
16 Rounds of Encryption: The permuted block is then processed through 16 identical rounds. Each round consists of:
- Splitting the 64-bit block into two 32-bit halves: Left (L) and Right (R).
- The right half (R) is expanded, XORed with a round subkey (K_i), and passed through a substitution box (S-box).
- The output of the S-box is permuted (P-box).
- The result is XORed with the left half (L) to produce the new right half (R').
- The original right half (R) becomes the new left half (L').
Mathematically, for round i: L_i = R_i-1 R_i = L_i-1 ⊕ f(R_i-1, K_i) where 'f' is the function involving expansion, S-boxes, P-box, and XOR with the subkey.
Final Permutation (FP): After 16 rounds, the left and right halves are swapped, and then a final permutation (the inverse of the initial permutation) is applied to produce the 64-bit ciphertext block.

Key Generation: The 56-bit key is used to generate 16 subkeys, each 48 bits long, one for each round. This involves:

Permuted Choice 1 (PC-1): The 64-bit key (8 parity bits are discarded) is permuted and split into two 28-bit halves (C and D).
Left Shifts: Each half (C and D) is cyclically shifted to the left by one or two positions depending on the round number.
Permuted Choice 2 (PC-2): The shifted halves are combined and permuted to produce a 48-bit subkey for the current round.

DES Structure Memory Aid: Think of DES as a 16-step "mixing machine". Each step uses a different piece of the secret key (subkeys) to scramble the data. The Feistel structure ensures that decryption is essentially the same process as encryption, just using the subkeys in reverse order.

5.2 Vulnerabilities of DES

The primary vulnerability of DES is its short key length of 56 bits. This means there are only 2⁵⁶ possible keys. While this was considered secure in the 1970s, modern computers can perform brute-force attacks, trying all possible keys until the correct one is found. This can be done in a matter of hours or days with specialized hardware.

Another issue is related to its S-boxes. While designed to provide non-linearity, some differential cryptanalysis attacks can exploit specific weaknesses in the S-boxes if they are not implemented carefully.

Due to these vulnerabilities, DES has been largely replaced by stronger algorithms like AES (Advanced Encryption Standard). However, Triple DES (3DES), which applies DES three times with different keys, was used as an interim solution to increase security, though it is also being phased out.