Common Encryption Techniques

Notation 🔗

Z_m = {0, 1, ..., m - 1}\\ g mod p: g를 p로 나눈 나머지\\ 10 mod 3 = 1\\ 729 mod 31 = 16 (729 = 23 * 31 + 16)\\ -7 mod 26 = 19 (-7 = 26 * (-1) + 19)\\ 평문 공간 = 암호문 공간 = 알파벳 문자들 = \mathbb{Z}_{26}

Shift cipher 🔗

An encryption method that shifts each plaintext character by a fixed amount.

0 <= k <= 25\\ Enc(K, x) = (x + K) mod \;26 \;\;\;(cf. K = 3: 시저 암호)\\ Dec(K, y) = (y - K) mod \;26\\

Example: K = 9.

Encryption:

shift (18 7 8 5 19) → +9 mod 26 → (1 16 17 14 2) BQROC

Decryption:

BQROC (1 16 17 14 2) → -9 mod 26 → (18 7 8 5 19) shift

Attacks:

Brute force: There are only 26 candidate secret keys.

Known-plaintext attack: For the example pair (shift, BQROC), K = B - s = (1 - 18) mod 26 = 9.

Affine cipher 🔗

An encryption method using linear algebra and modular arithmetic.

For K = (\alpha ,\beta ) where \alpha, \beta \in \mathbb{Z}_{26} and gcd(\alpha, 26) = 1\\ Enc(K, x) = (\alpha x + \beta) mod \;26\\ Dec(K, y) = \alpha^{-1} (y - \beta) mod \;26\\

Encryption 🔗

Decryption 🔗

Attacks:

Brute force: 26 × 12 ( $\alpha$ can only be a number that is not a divisor of 26) = 312 candidate keys.
Known-plaintext attack: For the example pair (hot, AXG), form simultaneous equations.
- $7\alpha + \beta = 0\,mod\,6$
- $14\alpha + \beta = 23\,mod\,6$

Substitution cipher 🔗

An encryption method that replaces each plaintext character with another character.

Enc(K, x) = \pi(x)\\ Dec(K, y) = \pi^{-1}(y)\\

Example:

\pi = \{A(0) \rightarrow 2, B(1) \rightarrow 7, C(2) \rightarrow 9, ..., Z(25) \rightarrow 19\}\\ Enc(\pi, C) = \pi(C) = 9 = J Dec(\pi, J) = \pi^{-1}(J) = C

Attacks:

Brute force: 26! candidate keys, approximately 4 × 10^26.
Chosen-plaintext attack: Use n plaintext–ciphertext pairs to find the key → (26-n)! candidate keys.
Frequency analysis, or statistical testing: Analyze letter frequencies to find the key.

Vigenère cipher 🔗

Monoalphabetic → Polyalphabetic.

K = K_1 K_2 ... K_n where K_m \in \mathbb{Z}_{26}\\ Enc(K, x_1 x_2 ... x_m) = (x_1 + K_1) mod \;26, (x_2 + K_2) mod \;26, ..., (x_n + K_m) mod \;26\\ Dec(K, y_1 y_2 ... y_m) = (y_1 - K_1) mod \;26, (y_2 - K_2) mod \;26, ..., (y_n - K_m) mod \;26\\

Related attacks:

Brute force: $26^m$ candidate keys.
Ciphertext-only attack: Statistical analysis such as the Kasiski test.
Known-plaintext attack: Straightforward when the plaintext and m are known.

Permutation cipher 🔗

키 K=\pi\;는 {1,...,m} 의 순열\\ Enc(K, x_1 x_2 ... x_m) =( x_{\pi(1)} x_{\pi(2)} ... x_{\pi(m)})\\ Dec(K, Y_1 Y_2 ... Y_m) =( Y_{\pi^{-1}(1)} Y_{\pi^{-1}(2)} ... Y_{\pi^{-1}(m)})\\

Interpreting the encryption algorithm above:

(x_1, ...,x_m)P=(Y_1, ... ,Y_m)

P

is an invertible matrix, this becomes the Hill cipher.

Related attacks:

Brute force: $m!$ candidate keys.
Known-plaintext or chosen-plaintext attack: $m$
independent ciphertexts
are required to obtain $P^{-1}$ .

Linear feedback shift register (LFSR) 🔗

A shift register whose input bit is a linear function of its previous state.

Example 1: A shift register satisfying

x_{m+3}=x_{m+1}+x_m

, a linear relationship.

Example 2: Given initial values

x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 0

and

x_5 = 0

, the sequence generated using the linear relationship

x_{m+5}=x_{m}+x_{m+2} mod 2

0100010100110111100011

LFSR cipher 🔗

선형 함수 f(z_1, z_2, ..., z_m) = \sum^l_{i=1}c_iz_i에 대해, 상수 c_i들과\;\\ 키 K=(k_1, ... , k_l)가 (\mathbb{Z}_2)^l에\; 속함\\ Enc(K, x_1, x_2, ..., x_m) = (x_1, x_2, ..., x_m) + (k_1, k_2, ..., k_l)\\ Dec(K, y_1, y_2, ..., y_m) = (y_1, y_2, ..., y_m) + (k_1, k_2, ..., k_l)\\ k_j = f(k_{j-l}, k_{j-l+1}, ..., k_{j-1}) for l+1<=j<=m\\

Attacks:

Known-plaintext attack.

$(x_1, x_2, ..., x_m), (y_1, y_2, ..., y_m)에서 k_1, ... ,k_l를 찾음\\ 다음과 같이 행렬 구성:\\ \begin{bmatrix} k_1 & k_2 & ... & k_l\\ k_2 & k_3 & ... & k_{l+1}\\ ... & ... & ... & ...\\ k_{l} & k_{l+1} & ... & k_{2l-1} \end{bmatrix} \begin{bmatrix} c_1\\ c_2\\ ...\\ c_l \end{bmatrix} = \begin{bmatrix} k_{l+1}\\ k_{l+2}\\ ...\\ k_{2l} \end{bmatrix}$

If the matrix has an inverse, you can find ( $c_1, ... ,c_m$ ).

Notation 🔗

Z_m = {0, 1, ..., m - 1}\\ g mod p: g를 p로 나눈 나머지\\ 10 mod 3 = 1\\ 729 mod 31 = 16 (729 = 23 * 31 + 16)\\ -7 mod 26 = 19 (-7 = 26 * (-1) + 19)\\ 평문 공간 = 암호문 공간 = 알파벳 문자들 = \mathbb{Z}_{26}

Shift cipher 🔗

An encryption method that shifts each plaintext character by a fixed amount.

0 <= k <= 25\\ Enc(K, x) = (x + K) mod \;26 \;\;\;(cf. K = 3: 시저 암호)\\ Dec(K, y) = (y - K) mod \;26\\

Example: K = 9.

Encryption:

shift (18 7 8 5 19) → +9 mod 26 → (1 16 17 14 2) BQROC

Decryption:

BQROC (1 16 17 14 2) → -9 mod 26 → (18 7 8 5 19) shift

Attacks:

Brute force: There are only 26 candidate secret keys.

Known-plaintext attack: For the example pair (shift, BQROC), K = B - s = (1 - 18) mod 26 = 9.

Affine cipher 🔗

An encryption method using linear algebra and modular arithmetic.

For K = (\alpha ,\beta ) where \alpha, \beta \in \mathbb{Z}_{26} and gcd(\alpha, 26) = 1\\ Enc(K, x) = (\alpha x + \beta) mod \;26\\ Dec(K, y) = \alpha^{-1} (y - \beta) mod \;26\\

Encryption 🔗

Decryption 🔗

Attacks:

Brute force: 26 × 12 ( $\alpha$ can only be a number that is not a divisor of 26) = 312 candidate keys.
Known-plaintext attack: For the example pair (hot, AXG), form simultaneous equations.
- $7\alpha + \beta = 0\,mod\,6$
- $14\alpha + \beta = 23\,mod\,6$

Substitution cipher 🔗

An encryption method that replaces each plaintext character with another character.

Enc(K, x) = \pi(x)\\ Dec(K, y) = \pi^{-1}(y)\\

Example:

\pi = \{A(0) \rightarrow 2, B(1) \rightarrow 7, C(2) \rightarrow 9, ..., Z(25) \rightarrow 19\}\\ Enc(\pi, C) = \pi(C) = 9 = J Dec(\pi, J) = \pi^{-1}(J) = C

Attacks:

Brute force: 26! candidate keys, approximately 4 × 10^26.
Chosen-plaintext attack: Use n plaintext–ciphertext pairs to find the key → (26-n)! candidate keys.
Frequency analysis, or statistical testing: Analyze letter frequencies to find the key.

Vigenère cipher 🔗

Monoalphabetic → Polyalphabetic.

K = K_1 K_2 ... K_n where K_m \in \mathbb{Z}_{26}\\ Enc(K, x_1 x_2 ... x_m) = (x_1 + K_1) mod \;26, (x_2 + K_2) mod \;26, ..., (x_n + K_m) mod \;26\\ Dec(K, y_1 y_2 ... y_m) = (y_1 - K_1) mod \;26, (y_2 - K_2) mod \;26, ..., (y_n - K_m) mod \;26\\

Related attacks:

Brute force: $26^m$ candidate keys.
Ciphertext-only attack: Statistical analysis such as the Kasiski test.
Known-plaintext attack: Straightforward when the plaintext and m are known.

Permutation cipher 🔗

키 K=\pi\;는 {1,...,m} 의 순열\\ Enc(K, x_1 x_2 ... x_m) =( x_{\pi(1)} x_{\pi(2)} ... x_{\pi(m)})\\ Dec(K, Y_1 Y_2 ... Y_m) =( Y_{\pi^{-1}(1)} Y_{\pi^{-1}(2)} ... Y_{\pi^{-1}(m)})\\

Interpreting the encryption algorithm above:

(x_1, ...,x_m)P=(Y_1, ... ,Y_m)

P

is an invertible matrix, this becomes the Hill cipher.

Related attacks:

Brute force: $m!$ candidate keys.
Known-plaintext or chosen-plaintext attack: $m$
independent ciphertexts
are required to obtain $P^{-1}$ .

Linear feedback shift register (LFSR) 🔗

A shift register whose input bit is a linear function of its previous state.

Example 1: A shift register satisfying

x_{m+3}=x_{m+1}+x_m

, a linear relationship.

Example 2: Given initial values

x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 0

and

x_5 = 0

, the sequence generated using the linear relationship

x_{m+5}=x_{m}+x_{m+2} mod 2

0100010100110111100011

LFSR cipher 🔗

선형 함수 f(z_1, z_2, ..., z_m) = \sum^l_{i=1}c_iz_i에 대해, 상수 c_i들과\;\\ 키 K=(k_1, ... , k_l)가 (\mathbb{Z}_2)^l에\; 속함\\ Enc(K, x_1, x_2, ..., x_m) = (x_1, x_2, ..., x_m) + (k_1, k_2, ..., k_l)\\ Dec(K, y_1, y_2, ..., y_m) = (y_1, y_2, ..., y_m) + (k_1, k_2, ..., k_l)\\ k_j = f(k_{j-l}, k_{j-l+1}, ..., k_{j-1}) for l+1<=j<=m\\

Attacks:

Known-plaintext attack.

$(x_1, x_2, ..., x_m), (y_1, y_2, ..., y_m)에서 k_1, ... ,k_l를 찾음\\ 다음과 같이 행렬 구성:\\ \begin{bmatrix} k_1 & k_2 & ... & k_l\\ k_2 & k_3 & ... & k_{l+1}\\ ... & ... & ... & ...\\ k_{l} & k_{l+1} & ... & k_{2l-1} \end{bmatrix} \begin{bmatrix} c_1\\ c_2\\ ...\\ c_l \end{bmatrix} = \begin{bmatrix} k_{l+1}\\ k_{l+2}\\ ...\\ k_{2l} \end{bmatrix}$

If the matrix has an inverse, you can find ( $c_1, ... ,c_m$ ).