[암호학] 8. RSA 암호체계

[암호학] 8. RSA 암호체계

RSA 암호체계는 1978년에 라이베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)이 고안한 것으로 폴리그-헬만 암호체계를 약간 변형시킨 것이고, 다음의 정리에 기반을 두고 있다. 

정리. 서로 다른 두 홀수 소수 $p,\,q$에 대하여 $m=pq$라고 할 때 $$\text{gcd}(e,\,\phi(m))=1,\,1<e<\phi(m)$$ 인 정수 $e$에 대해 $d$를 $$ed\equiv1\,(\text{mod}\,\phi(m)),\,1<d<\phi(m)$$ 인 정수라 하고, 가환환 $\mathbb{Z}_{n}=\{0,\,1,\,...,\,n-1\}$위의 두 함수 $E,\,D$를 다음과 같이 정의하자. $$\begin{align*}E:\mathbb{Z}_{n}\,\rightarrow\,\mathbb{Z}_{n}&\,E(x)=x^{e}\\D:\mathbb{Z}_{n}\,\rightarrow\,\mathbb{Z}_{n}&\,D(x)=x^{d}\end{align*}$$ 이때 모든 $x\in\mathbb{Z}_{n}$에 대하여 $D(E(x))=x$이고 따라서 $E$와 $D$는 $\mathbb{Z}_{n}$위의 일대일 대응이고 $E^{-1}=D$이다. 

증명: 가정에 의해 $\text{gcd}(e,\,\phi(m))=1$이므로 $$ed\equiv1\,(\text{mod}\,\phi(m))\,1<d<\phi(m)$$ 인 정수 $d$는 존재하고 $\phi(m)|(ed-1)$이므로 양의 정수 $k$가 존재해서 $d=\phi(m)k+1$이다. 

$a\in\mathbb{Z}_{n}$, $\text{gcd}(a,\,n)=1$이라 하자. 오일러의 정리에 의해 $a^{\phi(m)}\equiv1\,(\text{mod}\,m)$이므로 $$a^{ed}\equiv a^{\phi(m)k+1}\equiv(a^{\phi(m)})^{k}a\equiv1^{k}a\equiv a\,(\text{mod}\,m)$$ 이고 따라서 $D(E(a))=a^{ed}=a$이다. $a=0$이면 $D(E(0))=0^{ed}=0$이다. 

다음으로 $a\in\mathbb{Z}_{n}$, $a\neq0$, $\text{gcd}(a,\,n)\neq1$이라 하자. $m=pq$이므로 다음 중 하나가 성립한다. $$(\text{i})\,p|a,\,\text{gcd}(a,\,q)=1,\,(\text{ii})\,\text{gcd}(a,\,p)=1,\,q|a$$ $\phi(m)|(ed-1)$, $\phi(m)=(p-1)(q-1)$이므로 다음이 성립한다. $$(p-1)|(ed-1),\,(q-1)|(ed-1)$$ (i)의 경우, $a\equiv0\,(\text{mod}\,p)$이므로 $$a^{ed}\equiv0^{ed}\equiv0\equiv a\,(\text{mod}\,p)$$ 이고 $\text{gcd}(a,\,q)=1$이므로 페르마 정리에 의해 $a^{q-1}\equiv1\,(\text{mod}\,q)$이고 또한 양의 정수 $s$가 존재해서 $ed=(q-1)s+1$이므로 다음이 성립한다. $$a^{ed}\equiv a^{(q-1)s+1}\equiv(a^{q-1})^{s}a\equiv1a\equiv a\,(\text{mod}\,q)$$ $p,\,q$는 서로소이므로 위의 두 결과와 중국인의 나머지 정리에 의해 $$a^{ed}\equiv a\,(\text{mod}\,m)$$ 이고 따라서 가환환 $\mathbb{Z}_{n}$에서 $D(E(a))=a^{ed}=a$이다.

마찬가지로 (ii)의 경우에도 가환환 $\mathbb{Z}_{n}$에서 $D(E(a))=a^{ed}=a$이다. 

위의 증명에 의해 모든 $a\in\mathbb{Z}_{n}$에 대해 $D(E(a))=a$이므로 두 함수 $E,\,D$는 일대일 대응이고 $E^{-1}=D$이다. 

RSA 암호체계 프로토콜

1단계. 수신자 A는 충분히 큰 서로 다른 두 소수 $p,\,q$를 선택하여 $m=pq$를 계산하고 $m$은 공개, $p,\,q$는 비공개한다. 그리고 A는 $m$의 오일러-피 함수값 $\phi(m)=(p-1)(q-1)$의 값을 구한다.

2단계. 수신자 A는 $\text{gcd}(e,\,\phi(m))=1$, $1<e<\phi(m)$인 정수 $e$를 선택하고 $$ed\equiv1\,(\text{mod}\,\phi(m))\,1<d<\phi(m)$$ 인 정수 $d$를 구해서 $e$를 공개하고 $d$는 비공개한다. 즉, A의 공개 키는 $m,\,e$이고 비밀 키는 $p,\,q,\,d$이다. 

3단계. 송신자 U는 송신하려는 평문을 $0\leq a<m$인 정수 $a$로 나타낸다. 이때 1의 자리수 앞에 0을 붙인다. 

4단계. 송신자 U는 공개된 $m,\,e$를 이용하여 평문 $a$에 대하여 $$b\equiv a^{e}\,(\text{mod}\,m)\,0\leq b<m$$ 인 정수 $b$를 구해서 암호문 $b$를 A에게 전송한다. 

5단계. 수신자 A는 암호문 $b$와 자신의 비밀 열쇠 $d$를 이용하여 $$a\equiv b^{d}\,(\text{mod}\,m)\,0\leq a<m$$ 인 정수 $a$를 구함으로써 평문 $a$를 얻는다.

RSA 암호체계의 안전성은 정수의 인수분해가 어렵다는 점에 있다. 앞의 단계 (1), (2)에서 A가 상당히 큰 서로 다른 두 소수 $p,\,q$를 택하면 합당한 시간 안에 정수 $m$의 두 소인수 $p,\,q$를 구하는 일은 대단히 어렵고 따라서 $\phi(m)$의 값을 계산하는 일은 어렵게 되고, 공개된 $e$의 값을 이용하여 $1<d<\phi(m)$인 $d$를 구하는 일은 어렵다. 

이때 두 소수 $p,\,q$는 다음과 같은 조건을 만족해야 한다. 

(1) $p,\,q$는 서로 다르고 상당히 커야 한다. 

(2) $p,\,q$는 자리수가 거의 같아야 한다. 

(3) $p-1$과 $q-1$은 각각 큰 소인수를 가져야 한다. 

(4) $p-1$과 $q-1$의 최대공약수는 작아야 한다.

보통 RSA 암호체꼐에서는 $p,\,q$를 100자리 정도의 소수로 택하여 $m=pq$를 이용한다.     

공격자가 $m$과 $\phi(m)$의 값을 알면 이차방정식 $$x^{2}-(m+1-\phi(m))x+m=0$$ 의 두 근을 구하여 $m$의 두 소인수 $p,\,q$를 구할 수 있다. 

앞의 3단계에서 $a\geq m$일 때는 적당한 함수 $h$를 사용해서 $$0\leq h(a)<m$$ 인 정수 $h(a)$를 정하여 $a$ 대신 $h(a)$를 사용하거나 또는 $m$이 $n$자리의 수인 경우, $a$를 $$a=\underbrace{\bigcirc\cdots\bigcirc}_{a_{1}}\underbrace{\bigcirc\cdots\bigcirc}_{a_{2}}\cdots\underbrace{\bigcirc\cdots\bigcirc}_{a_{k}}$$ 와 같이 처음부터 차례로 그 길이가 $n-1$인 블록으로 나누어 이들 블록이 나타내는 양의 정수 $a_{1},\,a_{2},\,...,\,a_{k}$가 모두 $m$보다 작도록 하고 필요하다면 평문에 적당한 문자를 추가한다.  

서로 다른 두 홀수 소수 $p=1733$, $q=2347$에 대하여 $$\begin{align*}m&=pq=4067351\\ \phi(m)&=(p-1)(q-1)=1732\cdot2346\end{align*}$$ 이다. $e=31$일 때 $\text{gcd}(e,\,\phi(m))=1$이므로 유클리드의 알고리즘을 이용하여 $$ed\equiv1\,(\text{mod}\,\phi(m)),\,1<d<\phi(m)$$ 인 정수 $d$를 구하면 $d=3145759$이다. 

평문 'public key cryptography'를 알파벳-숫자 표에 따라 정수 $a$로 나타내고 이를 길이가 6인 블록으로 나누면 다음과 같이 나타낼 수 있다. $$a=\underbrace{152001}_{a_{1}}\vdots\underbrace{110802}_{a_{2}}\vdots\underbrace{100424}_{a_{3}}\vdots\underbrace{021724}_{a_{4}}\vdots\underbrace{151914}_{a_{5}}\vdots\underbrace{061700}_{a_{6}}\vdots\underbrace{150724}_{a_{7}}$$ 다음으로 각 $i\,(1\leq i\leq 7)$에 대하여 $$b_{i}\equiv a_{i}^{31}\,(\text{mod}\,m)\,(0\leq b_{i}<m)$$ 인 정수 $b_{i}$를 구하여 이들을 차례로 늘어놓은 정수를 $b$라고 하면 다음과 같다. $$b=\underbrace{2721372}_{b_{1}}\vdots\underbrace{3969831}_{b_{2}}\vdots\underbrace{2416419}_{b_{3}}\vdots\underbrace{1795753}_{b_{4}}\vdots\underbrace{2110079}_{b_{5}}\vdots\underbrace{0242624}_{b_{6}}\vdots\underbrace{0889174}_{b_{7}}$$ 수신한 암호문 $b=b_{1}b_{2}\cdots b_{7}$과 비밀 키 $d$를 이용하여 각 $b_{i}$에 대하여 다음과 같이 $a_{i}$를 구하면 평문 $a$를 얻을 수 있다. $$a_{i}\equiv b_{i}^{3145759}\,(\text{mod}\,m)\,0\leq a_{i}<m$$ RSA 암호체계에서 다음에 유의해야 한다.

1. 여러 수신자가 동일한 정수 $m$을 이용하는 것을 피해야 한다.

2. 암호화 함수에서 지수 $e$를 택할 때 가장 작은 값을 피해야 한다.  

참고자료:

암호학과 부호이론, 박승안, 경문사