Cryptography: Monoalphabetic vs Polyalphabetic, DES Weak Keys, and IDEA Round Operation

---

Part A: Monoalphabetic vs Polyalphabetic, Which is More Vulnerable?

Monoalphabetic cipher is more vulnerable than polyalphabetic cipher.

Definition

• Monoalphabetic Cipher: A substitution cipher where each plaintext letter is always replaced by the same fixed ciphertext letter throughout the entire message. Example: Caesar Cipher.
• Polyalphabetic Cipher: A substitution cipher that uses multiple substitution alphabets in rotation. Example: Vigenere Cipher.

Justification

Why monoalphabetic is weaker:

1. Since every occurrence of a plaintext letter maps to the same ciphertext letter, the statistical frequency distribution of the original language is preserved in the ciphertext.
2. An attacker can perform frequency analysis: in English, 'E' appears ~13% of the time, 'T' ~9%, etc. By counting ciphertext letter frequencies and matching them to known language frequencies, the key can be recovered without brute force.
3. In polyalphabetic ciphers, the same plaintext letter is encrypted differently depending on its position (e.g., 'E' may become 'H' at one position and 'R' at another). This flattens the frequency distribution, making frequency analysis ineffective.

Conclusion

Monoalphabetic cipher is significantly more vulnerable because its one-to-one fixed mapping leaks the statistical patterns of the plaintext language, allowing easy cryptanalysis through frequency analysis.

---

Part B: Weak Keys in DES

Background

DES is a block cipher that encrypts 64-bit plaintext using a 56-bit key over 16 rounds, generating 16 subkeys (one per round) through a key schedule.

Definition of Weak Keys

Weak keys in DES are keys that produce identical subkeys for all 16 rounds. This means:

$$E_K(E_K(P)) = P$$

That is, encrypting twice with the same weak key returns the original plaintext, making encryption equivalent to decryption. This severely reduces security.

The 4 Weak Keys

These keys produce subkeys that are either all zeros or all ones in both halves of the key register (C and D registers), so all 16 subkeys are identical.

Semi-Weak Keys

DES also has 12 semi-weak keys (6 pairs) where:

$$E_{K_1}(P) = D_{K_2}(P)$$

Encrypting with key $K_1$ is the same as decrypting with key $K_2$. These pairs produce only two distinct subkeys alternating across 16 rounds.

Why They Are Dangerous

• Weak keys reduce the effective key space.
• An attacker who suspects a weak key is in use can test only a handful of keys rather than $2^{56}$ possibilities.
• In practice, weak keys should be detected and rejected during key generation.

---

Part C: Round Operation in IDEA

Overview

IDEA (International Data Encryption Algorithm) is a symmetric block cipher with the following parameters:

• Block size: 64 bits
• Key size: 128 bits
• Structure: 8 full rounds + 1 output transformation (half round)
• Subkeys: 52 subkeys of 16 bits each (6 per full round + 4 for output transformation)

Three Algebraic Operations

IDEA derives its strength from mixing three algebraically incompatible operations on 16-bit sub-blocks:

These three operations come from different algebraic groups, making algebraic cryptanalysis extremely difficult.

Input Division

The 64-bit plaintext block is divided into four 16-bit sub-blocks:

$$X_1, \quad X_2, \quad X_3, \quad X_4$$

Steps in One Full Round (using subkeys $K_1$ through $K_6$)

Step 1: Apply first four subkeys

$$a = X_1 \odot K_1$$ $$b = X_2 \boxplus K_2$$ $$c = X_3 \boxplus K_3$$ $$d = X_4 \odot K_4$$

Step 2: XOR cross combinations

$$e = a \oplus c$$ $$f = b \oplus d$$

Step 3: MA (Multiplication-Addition) Structure

The MA structure uses subkeys $K_5$ and $K_6$:

$$g = e \odot K_5$$ $$h = (f \boxplus g) \odot K_6$$ $$i = g \boxplus h$$

Step 4: XOR to produce round outputs

$$Y_1 = a \oplus h$$ $$Y_2 = c \oplus h$$ $$Y_3 = b \oplus i$$ $$Y_4 = d \oplus i$$

The final round output $(Y_1, Y_2, Y_3, Y_4)$ becomes the input to the next round (or, after the eighth round, to the output transformation), and the swap of the two middle blocks between rounds ensures full diffusion of the plaintext bits across the 64-bit block by the end of the cipher.

SHA Parameters Comparison & Hill Cipher Decryption

---

Part 1: SHA Parameters Comparison (SHA-1 vs SHA-2 Family)

Notes:

• SHA-1 produces a single 160-bit digest; SHA-2 is a family of hash functions with variable output sizes.
• SHA-1 is broken against collision attacks (SHAttered, 2017) and is deprecated.
• SHA-2 uses more complex round functions and better resistance to known attacks.

---

Part 2: Hill Cipher Decryption of "DRIJ"

Key: $K = \begin{pmatrix} 7 & 8 \ 11 & 11 \end{pmatrix}$, decryption uses $P = K^{-1}C \pmod{26}$.

Step 1: Convert ciphertext to numbers (A=0, ..., Z=25)

$$D=3,\ R=17,\ I=8,\ J=9$$

$$C_1=\begin{pmatrix}3\17\end{pmatrix},\quad C_2=\begin{pmatrix}8\9\end{pmatrix}$$

Step 2: Compute $K^{-1} \pmod{26}$

Determinant: $$\det(K)=(7\cdot 11)-(8\cdot 11)=77-88=-11\equiv 15\pmod{26}$$

Inverse of determinant: find $d$ with $15d\equiv 1\pmod{26}$. $$15\times 7=105=4(26)+1\equiv 1\pmod{26}\Rightarrow 15^{-1}\equiv 7$$

Adjugate: $$\text{adj}(K)=\begin{pmatrix}11 & -8\ -11 & 7\end{pmatrix}\equiv\begin{pmatrix}11 & 18\ 15 & 7\end{pmatrix}\pmod{26}$$

Inverse: $$K^{-1}=7\begin{pmatrix}11 & 18\ 15 & 7\end{pmatrix}=\begin{pmatrix}77 & 126\ 105 & 49\end{pmatrix}\equiv\begin{pmatrix}25 & 22\ 1 & 23\end{pmatrix}\pmod{26}$$

Step 3: Decrypt first pair "DR"

$$P_1=\begin{pmatrix}25 & 22\ 1 & 23\end{pmatrix}\begin{pmatrix}3\17\end{pmatrix}\pmod{26}$$

Row 1: $25\cdot3+22\cdot17=75+374=449$; $449\bmod 26 = 449-17(26)=449-442=7$ Row 2: $1\cdot3+23\cdot17=3+391=394$; $394\bmod 26 = 394-15(26)=394-390=4$

$$P_1=\begin{pmatrix}7\4\end{pmatrix}\Rightarrow H,\ E$$

Step 4: Decrypt second pair "IJ"

$$P_2=\begin{pmatrix}25 & 22\ 1 & 23\end{pmatrix}\begin{pmatrix}8\9\end{pmatrix}\pmod{26}$$

Row 1: $25\cdot8+22\cdot9=200+198=398$; $398\bmod 26 = 398-15(26)=398-390=8$ Row 2: $1\cdot8+23\cdot9=8+207=215$; $215\bmod 26 = 215-8(26)=215-208=7$

$$P_2=\begin{pmatrix}8\7\end{pmatrix}\Rightarrow I,\ H$$

Step 5: Assemble plaintext

$$H,E,I,H \Rightarrow \boxed{\textbf{HEIH}}$$

Verification (encrypt HEIH back): $K\begin{pmatrix}7\4\end{pmatrix}=\begin{pmatrix}49+32\77+44\end{pmatrix}=\begin{pmatrix}81\121\end{pmatrix}\equiv\begin{pmatrix}3\17\end{pmatrix}=DR$ ✓ $K\begin{pmatrix}8\7\end{pmatrix}=\begin{pmatrix}56+56\88+77\end{pmatrix}=\begin{pmatrix}112\165\end{pmatrix}\equiv\begin{pmatrix}8\9\end{pmatrix}=IJ$ ✓

Decrypted plaintext: HEIH

Role of Prime Numbers in Euler's Totient Function and GCD by Euclidean Algorithm

Given Data

• Euler totient function context; find role of prime numbers.
• Numbers for GCD: $a = 16$, $b = 12$.

---

Part 1: Role of Prime Numbers in Euler's Totient Function

Definition

Euler's Totient Function $\phi(n)$ counts the number of positive integers in the range $1 \le k \le n$ that are relatively prime to $n$ (i.e. $\gcd(k, n) = 1$).

Role of a Prime Number

If $n = p$ is prime, then $p$ has no divisors other than $1$ and $p$ itself. Hence every integer in ${1, 2, \dots, p-1}$ is coprime to $p$.

$$\boxed{\phi(p) = p - 1}$$

For a prime power: $$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$$

Why It Matters

1. Simplifies computation: For a prime, the totient is trivially $p-1$.
2. Multiplicative building block: Since $\phi$ is multiplicative for coprime factors, any $n$ factored into primes gives $$\phi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)$$
3. RSA cryptography: With $n = p \times q$ (product of two primes), $$\phi(n) = (p-1)(q-1)$$ which is the basis for choosing the encryption/decryption exponents.

Example

$\phi(7)$: since $7$ is prime, $\phi(7) = 7 - 1 = 6$. Check: ${1,2,3,4,5,6}$ are all coprime to $7$. Count $= 6$. ✓

---

Part 2: GCD of 12 and 16 by Euclidean Algorithm

Rule: $\gcd(a,b) = \gcd(b,, a \bmod b)$ until the remainder is $0$; the last non-zero remainder is the GCD.

Take $a = 16,\ b = 12$:

Since the remainder is now $0$, the last non-zero remainder is $4$.

$$\boxed{\gcd(12, 16) = 4}$$

Verification

• $12 = 4 \times 3$ ✓
• $16 = 4 \times 4$ ✓
• $4$ is the largest common divisor. ✓