CYG Chapter 3 Cryptanalysis of Classical Systems

Access to the decryption function for any ciphertext

1. CO and 2. KP

1. CP and 2. CC // All but Vernam fail

Monoalphabetic ciphers

1. Determine frequencies of characters, diagrams and trigrams of the cipher

2. Identify frequencies to characters, diagrams and trigrams of the NL

Get half of the text with identifying six most frequent characters in English language // E,T,A,O,I,N make 51.75% of all frequencies

Colonel Friedmann 1891-1969

Determine if a cryptogram was encrypted by a monoalphabetic cipher

1. Alphabet X:={1,…,m}

2. Random variables C=(C₁,…,C_n) with P(C_i=l)=q_l and iid

3. Number of components equal to l N_l = |{i| C_i=l}|

4. Strong law of large numbers q_l = lim_n→inf N_l/n

1. I_C = 1 ↔ C₁ = … = C_n

2. I_C = 0 ↔ All C_i are different

I_C ~ Sum_l=1^m q_l² =: K_C with strong law of large numbers

Y_ij = {1 if C_i=C_j; 0 otherwise}

1. I_c = I(C₁,…,C_n) = |{(i,j)| C_i=C_j, i<j}| / (n over 2)

2. I_c = 1/n*(n-1) Sum_l=1^m N_l*(N_l-1)

3. I_C = Sum_i<j Y_ij / (n over 2)

E(I_C) = K

1. E(Y_ij) = 1*P(Y_ij=1) + 0*P(Y_ij=0)

2. = P(C_i=C_j)

3. = Sum_l=1^m P(C_i=l, C_j=l)

4. = Sum_l=1^m q_l^²

5. = K

1. Compute I_C

2. If I_c~K_L of language L then we have monoalphabetic cipher over L

3. If I_C~0.0385=K_U then we have a polyalphabetic cipher

1. Vigenère is not monoalphabetic but can still be broken with low effort

2. Estimate keylength k

3. Use that length is probably a divisor of the distance of equal sequences

1. Alphabet X:={0,…,m-1}

2. Plaintext M=(M₁,…,M_n) with P(M_i=l)=pl, iid and k|n

3. Keyword K=(K₀,…,K_k-1) with P(K_i=l)=1/m and iid on X

4. Ciphertext C=(C₁,…,C_n) with C_i=(M_i+K_{(i-1)mod k}) mod m

5. Y_ij = {1 if C_i=C_j; 0 otherwise}

6. k = n(K_M – 1/m) / (n-1)*E(I_C)+K_M-(n/m) // If E(I_C)=K_M then k=1

1. If i~j ↔ i=j (mod k) then E(Y_ij) = K_M

2. If i!~j then E(Y_ij) = 1/m

E(I_C) = 1/k(n-1) * ((n-k)*K_M + n(k-1)*1/m)

1. E(I_C) = Sum_i<j E(Y_ij) / (n over 2)

2. = [Sum_i<j,i~j E(Y_ij) + Sum_i<j,i!~j E(Y_ij)] / (n over 2)

3. = [Sum_i<j,i~j K_M + Sum_i<j,i!~j 1/m] / (n over 2)

4. = [n/2 * (n/k -1) * K_M + n/2 * (n- n/k) * 1/m] * 2/n(n-1)

1. Estimate E(I_C) by 1/n(n-1) * Sum_l=0^m-1 n_l(n_l-1)

2. Further perform frequency analysis on the obtained rows

1. Avoid by using key chosen randomly

2. Avoid by never using same key twice

Else simply use frequency analysis for the combination of the most frequent characters // P(M_i,K_i from {E,T,A,O,I,N,S}~57%²~33%

Else compute c_i-d_i mod m = m_i-n_i mod m