[암호학] 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를 공통 열쇠로 사용한다.     

참고자료:

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