[암호학] 7. 공개 열쇠 암호체계

[암호학] 7. 공개 열쇠 암호체계

지금까지 다루었던 암호는 비밀 키 암호 체계였다. 이 암호 체계 에서 사용자 모두가 동일한 열쇠 \(K\)를 택하기 때문에 이 암호체계에서는 이 열쇠가 공격자에게 노출되면 안된다. 

그러기 위해서는 

1. 암호문 수신자는 그 근원을 확인할 수 있어야 한다.

2. 평문이 송신되는 도중 변형되지 않았는가를 확인할 수 있어야 한다. 

3. 암호문을 송신한 사람은 나중에 송신한 사실을 부인할 수 없어야 한다.

4. 열쇠가 공격자에게 노출되면 안된다.

이 4가지를 모두 충족시켜야 한다. 

고전적 비밀 키 암호 체계에서는 위 4가지를 모두 만족시키기가 어려우나 디피(Diffie)와 헬만(Hellman) 등은 공개 열쇠 암호체계를 창안해 이러한 어려움을 해결했다. 

공개 키 암호 체계에서는 평문을 암호화하는 키는 공개하나 암호문을 평문으로 복호화하는 키는 비밀로 한다. 이렇게 하면 각 사용자는 공개 열쇠와 비밀 열쇠를 가지므로, 여러 사용자 사이에 열쇠를 교환할 필요가 없게 되어 통신망을 구축하는데 필요한 키의 개수를 줄일 수 있다. 

어느 조직에서 공개 키 암호체계를 이용하려면 사용자에 따른 암호화 키(공개 키)와 복호화 키(비공개 키)가 기록된 등록부를 갖게 하여 조직원 간 비밀 통신을 가능하게 한다. 

조직원	공개 키
U	U의 공개 키
A	A의 공개 키
B	B의 공개 키
\(\vdots\)	\(\vdots\)

조직원 C가 조직원 A에게 암호문을 보내려고 한다. 공개키 암호 \(E_{A}\)를 이용하여 평문 \(a\)를 암호문 \(b\)로 암호화하여 이 암호문을 A에게 전송하고 이 암호문을 받은 A는 자기 자신만이 알고 있는 복호 함수 \(D_{A}\)(비공개)를 이용해 수신된 암호문 \(b\)를 복호화하여 평문 \(a\)를 얻는다.

공개 키 암호체계에서 암호문이 공격당하면 안되고 각 평문 \(a\)에 대하여 암호문 \(E_{A}(a)\)와 복호화된 암호문 \(D_{A}(E_{A}(a))=a\)를 안전하고 빠르게 계산할 수 있어야 하며 암호화 함수 \(E_{A}\)를 이용해 \(D_{A}\)를 알게 해서는 안된다. 또한 각 사용자는 누구나 모두 한 쪽 방향으로 쉽게 들어갈 수 있어도 특정 사용자 이외에는 되돌아올 수 없는 덫문(trapdoor)과 같은 안전 장치가 마련되어야 한다. 

두 유한집합 \(A,\,B\) 사이의 일대일 대응함수 \(f:A\,\rightarrow\,B\)에 대하여 각 원소 \(a\in A\)의 함숫값 \(f(a)\)는 쉽게 계산할 수 있으나 \(f\)의 역함수 \(f^{-1}:B\,\rightarrow\,A\)를 구하기 상당히 어려울 때, 즉 \(b\in B\)에 대하여 \(b=f(a)\)인 \(a\in A\)를 구하기가 어려울 때, 함수 \(f\)를 일방향 함수(one-way function)라고 한다.   

일방향 함수 \(f:A\,\rightarrow\,B\)에 대하여 추가적인 정보(덫문)를 가지고 있는 경우에만 \(f\)를 덫문 일방향 함수(trapdoor one-way function)라고 한다. 

*일방향 함수의 예: \(f(n)=ne^{n}-n\)은 \(n\)에 대해 증가함수이므로 역함수를 갖지만 그 역함수를 양함수로 나타낼 수 없다. 

홀수 소수 \(p\)에 대하여 법 \(p\)에 대한 원시근이 존재한다. 즉 다음의 두 조건을 만족하는 \(r\,(2\leq a\leq p-2)\)가 존재한다.

(i) \(\text{gcd}(r,\,p)=1\)

(ii) \(r^{i}\not\equiv1\,(\text{mod}\,p)\,(1\leq i<p-1)\), \(r^{p-1}\equiv1\,(\text{mod}\,p)\)

\(\mathbb{Z}_{p}^{*}=\{1,\,2,\,...,\,p-1\}\)라 하고 \(a\in\mathbb{Z}_{p}^{*}\)를 법 \(p\)에 대한 원시근이라고 하면, 체 \(\mathbb{Z}_{p}\)에서$$\mathbb{Z}_{p}^{*}=\{r^{0},\,r^{1},\,...,\,r^{p-2}\},\,r^{p-1}\equiv1\,(\text{mod}\,p)$$이고 각 \(a\in\mathbb{Z}_{p}^{*}\)에 대하여 유일한 \(k\)가 존재해서$$k=\text{ind}_{r}a\,\Leftrightarrow\,r^{k}\equiv a\,(\text{mod}\,p),\,0\leq k\leq p-2$$이다. 이러한 정수 \(k\)를 법 \(p\)에 대한(\(r\)을 밑으로 갖는) \(a\)의 이산로그(또는 지표)라고 한다. 

따라서 \(\mathbb{Z}_{p-1}=\{0,\,1,\,...,\,p-2\}\)일 때 \(f(k)=r^{k}\)로 정의되는 함수 \(f:\mathbb{Z}_{p-1}\,\rightarrow\,\mathbb{Z}_{p}^{*}\)는 일대일 대응이고, 그 역함수 \(f^{-1}\)를 구하기 어렵다. 따라서 함수 \(f\)는 일방향 함수라고 할 수 있다. 

이와 같이 \(p\)와 원시근 \(r\)의 값을 알고 있을 때 \(\text{gcd}(a,\,p)=1\)인 정수 \(a\)에 대하여 \(\text{ind}_{r}a\)를 구하는 문제를 이산로그 문제(discrete logarithm problem)라고 한다.  

서로 다른 두 홀수 소수 \(p,\,q\)에 대해 \(m=pq\)를 계산하는 것은 쉬우나 \(m\)을 두 소수의 곱 \(pq\)로 인수분해하는 것은 어렵다. \(m\)의 두 소인수 \(p,\,q\)를 알면 등식$$\phi(m)=\phi(p)\phi(q)=(p-1)(q-1)$$을 이용하여 \(\phi(m)\)을 구할 수 있다. 

\(m\)과 \(\phi(m)\)의 값을 알면 \(m\)의 두 소인수 \(p,\,q\)의 값을 알 수 있고, 실제로$$\phi(m)=(p-1)(q-1)=pq-(p+q)+1$$이므로$$p+q=m+1-\phi(m),\,pq=m$$이고 따라서 \(p,\,q\)는 다음의 이차방정식의 근이다.$$x^{2}-(m+1-\phi(m))x+m=0$$그러므로 \(m,\,\phi(m)\)을 알면 이 이차방정식의 두 근 \(p,\,q\)를 구할 수 있다. 

이처럼 \(m,\,\phi(m)\)과 같은 추가적인 정보를 이용해 \(m\)의  두 소인수 \(p,\,q\)의 값을 구할 수 있는 경우, 이 추가정보가 덫문이다. 

디피-헬만 키 교환 프로토콜(Diffie-Hellman key change protocol)   

(protocol: 약정서)

두 용자 A, B는 비밀 열쇠를 교환하기 위해 충분히 큰 소수 \(p\)와 법 \(p\)에 대한 원시근 \(r\,(2\leq r\leq p-2)\)을 서로 상의하고 결정하여 \(p\)와 \(r\)을 공개한다. 

(1) 사용자 A는 \(2\leq k\leq p-2\)인 정수 \(k\)를 임의로(randomly) 선택하여$$u\equiv r^{k}\,(\text{mod}\,p),\,1<u<p$$인 정수 \(u\)를 구하고 이 정수 \(u\)를 B에게 보낸다. 

(2) 사용자 B는 \(2\leq l\leq p-2\)인 정수 \(l\)을 임의로 선택하여$$v=r^{l}\,(\text{mod}\,p),\,1<v<p$$인 정수 \(v\)를 구하고 이 값을 A에게 보낸다. 

(3) 사용자 A는$$x\equiv v^{k}\,(\text{mod}\,p),\,1<x<p$$인 정수 \(x\)를 구하여 \(x\)를 열쇠로 사용한다.

(4) 사용자 B는$$x\equiv u^{l}\,(\text{mod}\,p),\,1<x<p$$인 정수 \(x\)를 구하여 \(x\)를 열쇠로 사용한다. 

이때$$v^{k}\equiv(r^{l})^{k}\equiv r^{kl}\equiv(r^{k})^{l}\equiv u^{l}\,(\text{mod}\,p)$$이므로 (3), (4)단계에서 구한 \(x\)의 값은 일치한다.       

소수 \(p=37\)에 대하여 \(r=2\)는 법 \(p\)에 대한 원시근이고 2를 밑으로 갖는 법 37에 대한 이산로그표는 다음과 같다.

\(r\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
\(\text{ind}_{2}r\)	0	1	26	2	23	27	32	3	16	24	30	28	11	33	13	4	7
\(r\)	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34
\(\text{ind}_{2}r\)	17	35	25	22	31	15	29	10	12	6	34	21	14	9	5	20	8

\(r\)	35	36
\(\text{ind}_{2}r\)	19	18

사용자 A는 \(r=19\)를 선택하고$$u\equiv r^{k}\equiv2^{19}\equiv35\,(\text{mod}\,37)$$를 계산해 \(u=35\)를 B에게 보낸다. 

사용자 B는 \(k=11\)를 선택하고$$v\equiv r^{l}\equiv2^{11}\equiv13\,(\text{mod}\,37)$$를 계산해 \(v=13\)를 A에게 보낸다. 이때,$$v^{k}\equiv13^{19}\equiv24\,(\text{mod}\,37),\,u^{l}\equiv35^{11}\equiv24\,(\text{mod}\,37)$$이므로 A와 B는 24를 공통 열쇠로 사용한다.     

참고자료:

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