암호에의 응용

인터넷 은행, 메신저, 전자서명은 모두 정수론 위에 서 있다. 가장 유명한 공개키 암호인 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)}$
  • 안전성은 큰 수의 소인수분해가 어렵다는 데에서 나온다.
알림: 보호된 콘텐츠입니다.