인터넷 은행, 메신저, 전자서명은 모두 정수론 위에 서 있다. 가장 유명한 공개키 암호인 RSA는 ‘큰 두 소수를 곱하기는 쉽지만, 곱을 다시 소인수분해하기는 매우 어렵다’는 사실과 오일러 정리를 이용한다.
핵심 개념
- 공개키 암호: 암호화 열쇠는 모두에게 공개하고, 복호화 열쇠는 주인만 가진다.
- RSA 열쇠 만들기
- (1단계) 큰 소수 $p$, $q$를 고르고 $n=pq$, $\varphi(n)=(p-1)(q-1)$을 계산한다.
- (2단계) $\varphi(n)$과 서로소인 $e$를 고른다. 공개키 $(n,e)$
- (3단계) $ed\equiv1\pmod{\varphi(n)}$인 $d$를 구한다(유클리드 호제법). 개인키 $d$
- 암호화: $c\equiv m^e\pmod n$, 복호화: $m\equiv c^d\pmod n$
핵심 정리
$\gcd(m,n)=1$이면 $(m^e)^d\equiv m\pmod n$이다. 즉 복호화하면 원래 메시지가 나온다.
증명 보기
$ed\equiv1\pmod{\varphi(n)}$이므로 $ed=1+k\varphi(n)$인 정수 $k$가 있다. 오일러 정리에 의해 $m^{\varphi(n)}\equiv1\pmod n$이므로
$$(m^e)^d=m^{ed}=m^{1+k\varphi(n)}=m\cdot\left(m^{\varphi(n)}\right)^k\equiv m\cdot1^k=m\pmod n$$
이다. ($\gcd(m,n)>1$인 경우도 중국인의 나머지 정리로 법 $p$, 법 $q$에서 따로 확인하면 성립한다.) $\blacksquare$
왜 안전한가? 공격자는 $n$과 $e$를 알지만 $d$를 구하려면 $\varphi(n)=(p-1)(q-1)$이 필요하고, 그러려면 $n$을 소인수분해해야 한다. $n$이 600자리 이상이면 현재 알려진 방법으로는 사실상 불가능하다.
예제 (작은 수로)
$p=5$, $q=11$이면 $n=55$, $\varphi(n)=40$이다. $e=3$을 고르면 $3d\equiv1\pmod{40}$에서 $d=27$ ($81=2\cdot40+1$)이다.
- 메시지 $m=7$의 암호화: $7^3=343=6\cdot55+13$이므로 $c=13$
- 복호화: $13^{27}\bmod55$. $13^2=169\equiv4$이므로 $13^{27}=13\cdot(13^2)^{13}\equiv13\cdot4^{13}$. $4^5=1024\equiv34$, $4^{10}\equiv34^2=1156\equiv1$이므로 $4^{13}\equiv4^3=64\equiv9$. 따라서 $13\cdot9=117\equiv7$. 원래 메시지 $7$이 나온다.
확인 문제
$n=33$, $e=7$인 공개키가 있다. 개인키 $d$를 구하시오.
풀이 보기
$33=3\times11$이므로 $\varphi(33)=2\times10=20$이다. $7d\equiv1\pmod{20}$에서 $7\times3=21\equiv1$이므로 $d=3$이다. 작은 $n$은 바로 소인수분해되므로 안전하지 않다는 것도 알 수 있다.
정리
- RSA: 암호화 $m^e$, 복호화 $c^d$, $ed\equiv1\pmod{\varphi(n)}$
- 안전성은 큰 수의 소인수분해가 어렵다는 데에서 나온다.
