[암호학] 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\)를 택할 때 가장 작은 값을 피해야 한다.  

참고자료:

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