6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption)

튜링 코드^{Turing Code}는 앨런 튜링이 개발한, 정수론을 이용한 암호화 방법이다.

"victory"라는 메세지를 암호화하는 예시를 통해 튜링 코드를 배워보자.
우리가 암호화할 메시지를 $m$, 암호화된 메시지를 $m'$, 암호화에 사용할 키 값을 $k$로 나타낼 것이다.

"victory"는 정수로 22090320151825로 나타낼 수 있다. (v는 알파벳 22번째, i는 09번째... 와 같은 방식이다.)

튜링 코드 버전 1

소수 만들기

먼저 암호화할 숫자에 적절한 수를 붙여 소수로 만들어준다. 22090320151825에 13을 붙이면 소수가 된다.

$$m=2209032015182513$$

키 값 정하고 암호화하기

다음으로 암호화에 사용될 키^key 값을 하나 정한다. 이 키값이 있어야만 암호화와 복호화가 가능하다.
키값 역시 큰 소수를 사용한다.

이제 단순히 암호화할 메세지와 키 값을 곱해주면 암호화가 완료된다.

수학적으로, 두 소수의 곱은 복호화하기가 상당히 복잡하다. 약분이 $E\cdot k$로만 가능한데, 이를 약분하려면 무수한 수의 숫자를 하나하나 대입해가며 약분이 되는 $k$나 $E$를 찾는 수밖에 없다.

$E' = E\cdot k$

튜링 코드 버전 1의 복호화, 취약점

암호화 방법을 보면 알겠지만 튜링 코드 버전 1의 복호화는 아주 간단하다.

$$E = \frac{E'}{k}$$

단순하면서도 해킹하려면 엄청난 노가다를 해야하니 좋아보이지만, 튜링코드엔 큰 단점이 있다. 만약 같은 키로 암호화된 문장 두개가 있다면, 최대공약수를 이용해 $k$를 알아낼 수 있다.

$$E_1' = E_1\cdot k\\ E_2' = E_2\cdot k\\ k = \text{gcd}(E1', E2')$$

튜링 코드 버전 2

튜링 코드 버전 2는 두 개의 키 값을 요구한다. 공개 키^{Public Key}인 $p$와 비공개 키^{Secret Key}인 $k$이다. 두 키는 모두 소수이다.

암호화할 메세지 $m$은 0부터 $p-1$사이의 값이다. ($m \in \{0, 1, \cdots , p-1\}$)

암호화와 복호화는 다음과 같다.

$$m' = \text{rem} (m\cdot k, p)\\ m = \text{rem}(m'\cdot k^{-1} , p)$$

증명

$m' = \text{rem}(m\cdot k,p)$이므로, $m' \equiv m\cdot k(\mod p)$이다.

이때, $k^{-1} (\mod p)$가 있다면, $m'\cdot k^{-1} \equiv m\cdot k\cdot k^{-1} (\mod p)$ 이므로, $m'\cdot k^{-1} \equiv m$이다.

그러므로 $m=\text{rem} (m'\cdot k^{-1}, p)$

튜링 코드 버전 2의 취약점

만약 우리가 암호화된 데이터 중 하나라도 원문을 알고있다면, 튜링 코드 버전 2를 해킹할 수 있다. (즉, 우리가 적어도 한 쌍의 $m$, $m'$를 안다면)

$m\equiv m' \cdot k (\mod p)$이므로, $\text{gcd}(m, p)$는 1이다. ($m$과 $p$는 서로소이다.)

그러므로, $m' \cdot m^{-1} \equiv m\cdot k \cdot m^{-1} \equiv k (\mod p)$이다.

$k$가 뭔지는 모르지만, 이를 통해 $k^{-1]$을 계산할 수 있다.

튜링 코드 v2 실습

$m = 2, k = 13, p = 7$을 써서 암호화 실습을 해보자.

$$\begin{align*}m' &= \text{rem}(m\cdot k, p)\\ &=\text{rem}(2\cdot 13, 7)\\ &= 5\end{align*}$$

우리가 $k$를 안다면, 복호화는 다음과 같다.

$$m = \text{rem}(m'\cdot k^{-1}, p)$$

$k^{-1} (\mod p)$는 $k\cdot k^{-1} \equiv 1 (\mod p)$이므로,

$$13 \cdot k^{-1} \equiv 1 (\mod 7)$$

$$k^{-1} = 6$$

그러므로,

$$\begin{align*}m &= \text{rem}(5 \cdot 6, 7)\\ &= 30 \mod 7 = 2 \end{align*}$$

해킹 실습

만약 우리가 $k$는 모르고 $m=2, m'=5$만 알았다고 생각해보자. $p$는 공개키로, 7임이 알려져있다.

$m'\cdot m^{-1} \equiv k (\mod p)$이다.

$m\cdot m^{-1} = 1 (\mod p)$이므로, $m^{-1} = 4$이다.

$$5\cdot 4 \equiv k (\mod 7)$$

이제, $k^{-1}$을 계산 가능하다.

20의 $(\mod 7)$에 대한 곱셈의 역원을 구하면 된다.

$$k^{-1} = 6$$

$$\begin{align*} m &= \text{rem}(m' \cdot k^{-1}, p)\\ &= \text{rem}(5 \cdot 6, 7) = 2 \end{align*}$$