[암호학] 11. 영지식 증명(2)

[암호학] 11. 영지식 증명(2)

앞에서 다음의 두 정리들을 증명했다.

정리 1. 서로 다른 홀수 소수 $p,\,q$에 대하여 $m=pq$라 하고 $a$를 $\text{gcd}(a,\,m)=1$ 즉 $\text{gcd}(a,\,p)=\text{gcd}(a,\,q)=1$인 정수라고 하자. 

이때, 이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$이 해를 가질 필요충분조건은 다음의 두 이차합동식 $$x^{2}\equiv a\,(\text{mod}\,p),\,x^{2}\equiv a\,(\text{mod}\,q)$$ 가 모두 해를 갖는 것이다. 즉 $$(a/p)=(a/q)=1$$ 일 때 해를 갖는다. 

이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$이 해를 가질 때 이 이차합동식은 $$\begin{align*}&x\equiv x_{1}\,(\text{mod}\,m)&&x\equiv x_{2}\,(\text{mod}\,m)\\&x\equiv-x_{1}\equiv m-x_{1}\,(\text{mod}\,m)&&x\equiv-x_{2}\equiv m-x_{2}\,(\text{mod}\,m)\end{align*}$$ 과 같은 4개의 해를 갖고 이들 해에 대해 다음이 성립한다. 

(1) 두 최대공약수 $\text{gcd}(x_{1}+x_{2},\,m)$, $\text{gcd}(x_{1}-x_{2},\,m)$중 하나는 $p$이고 또 하나는 $q$이다. 

(2) $p\equiv q\equiv3\,(\text{mod}\,4)$이면, 이들의 해 중에는 $(x_{0}/p)=(x_{0}/q)=1$인 해 $x\equiv x_{0}\,(\text{mod}\,m)$즉, 법 $m$에 대해 2차잉여인 해가 존재하고 이러한 해는 유일하다. 

정리 2. 홀수 소수 $p$에 대하여 $p\equiv3\,(\text{mod}\,4)$일 때, $\text{gcd}(a,\,p)=1$인 정수 $a$에 대하여 $(a/p)=1$이면 즉, 2차합동식 $x^{2}\equiv a\,(\text{mod}\,p)$의 해가 존재하면 이 2차합동식의 두 해는 다음과 같다. $$x\equiv\pm a^{\frac{p+1}{4}}\,(\text{mod}\,p)$$ 양의 정수 $m$이 서로 다른 두 홀수 소수 $p,\,q$의 곱으로 인수분해 됨을 알 때, 2차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 4개의 해를 구할 수 있으면 앞의 정리 1의 (1)을 이용하여 $m$의 소인수 $p,\,q$의 값을 구할 수 있다. 

비밀 정보 자체를 노출시키지 않고 보유하고 있음을 타인에게 확신시킬 때 이용하는 증명 방법을 영지식 증명(zero-knowledge proof)이라고 한다.

영지식 증명에서 비밀 정보를 가지고 있음을 증명하는 사람(proofer)과 이러한 사실을 확인하는 사람(verifier)이 있게 된다. 영지식 증명을 사용하는 경우, 비밀 정보를 모르는 제 3자가 증명하는 사람 행세를 하여 확인하는 사람을 속일 확률은 충분히 작고, 확인하는 사람은 충분히 작은 정보를 갖고 있기 때문에 제 3자에게 자기가 이 비밀 정보를 알고 있는 것처럼 확신시켜 줄 수 는 없다.

영지식 증명 프로토콜

P가 $p\equiv3\,(\text{mod}\,4)$, $q\equiv3\,(\text{mod}\,4)$인 서로 다른 두 소수 $p,\,q$를 선택해 이 두 소수 $p,\,q$를 비공개로 한 상태로 이 두 소수를 알고 있다는 사실을 V에게 확신시키려고 할 때 다음의 절차를 따른다.

1단계: P는 V에게 $p,\,q$의 곱인 $m$의 값을 알려 준다.

2단계: V는 $\text{gcd}(c,\,m)=1$, $1\leq c<m$인 정수 $c$를 임의로 선택해 $$a\equiv c^{4}\,(\text{mod}\,m),\,1\leq a<m$$ 인 정수 $a$를 구한 다음 이 값을 P에게 송신한다.

3단계: P는 V로부터 받은 $a$의 값을 이용해 2차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 해 중에서 법 $m$에 대한 2차잉여일 때 $$x\equiv b\,(\text{mod}\,m),\,1\leq b<m$$ 를 구해 $b$를 V에게 송신한다. 

4단계: V는 $b\equiv c^{3}\,(\text{mod}\,m)$인지 확인한다. 

앞의 3단계에서 V는 $m$의 소인수 $p,\,q$의 값을 이용해 2차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 해를 구하고 $(b/p)=(a/p)=1$임을 밝힘으로써 정리 1로부터 $b$가 법 $m$에 대한 2차잉여임을 판정한다. 그러나 $p,\,q$의 값을 모르는 경우, 합리적인 시간 안에 $b$를 구할 수 없다. 

4단계에서 V는 두 소인수 $p,\,q$의 값을 알지 못하면서 자신이 이미 고른 $c$의 값을 이용하여 $b$의 값을 판정할 수 있다. 실제로 $$a\equiv c^{4}\equiv(c^{2})^{2}\,(\text{mod}\,m)$$ 이므로 $x\equiv c^{2}\,(\text{mod}\,m)$은 2차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 해인 동식에 법 $m$에 대한 2차잉여이다. 그리고 이러한 해는 유일하므로 $b\equiv c^{2}\,(\text{mod}\,m)$이다.

소수 $p=103,\,q=239$에 대하여 $m=pq$라 하자. 이때 $m=24717$이고 2단계에서 V가 $c=9134$를 고르면 $$a\equiv c^{4}\equiv9134^{4}\equiv20682\,(\text{mod}\,24617)$$ 이므로 V는 $a=20682$를 P에게 보낸다.

3단계에서 P는 2차합동식 $x^{2}=20682\,(\text{mod}\,24617)$의 해를 구하기 위해 다음의 연립합동식의 해를 구한다. $$\begin{cases}x^{2}\equiv20682\equiv82\,(\text{mod}\,103)\\x^{2}\equiv20682\equiv67\,(\text{mod}\,239)\end{cases}$$ $103\equiv3\,(\text{mod}\,4)$, $239\equiv3\,(\text{mod}\,4)$이므로 정리 2에 의해 합동식 $$x^{2}\equiv82\,(\text{mod}\,103),\,x^{2}\equiv67\,(\text{mod}\,239)$$ 의 해는 각각 다음과 같다. $$\begin{align*}&x\equiv\pm82^{\frac{103+1}{4}}\equiv\pm82^{26}\equiv\pm59\,(\text{mod}\,103)\\&x\equiv\pm67^{\frac{239+1}{4}}\equiv\pm67^{60}\equiv\pm75\,(\text{mod}\,239)\end{align*}$$ 르장드르 기호의 성질에 의해 $$\begin{align*}(59/103)&=-(103/59)=-(44/59)=-(11/59)=(59/11)=(4/11)=1\\(75/239)&=(3/239)=(239/3)=-(2/3)=1\end{align*}$$ 이므로 따라서 2차합동식 $x^{2}\equiv20682\,(\text{mod}\,24717)$의 해 중에서 법 $24717$에 대해 2차잉여인 해는 다음의 연립1차합동식의 해이다. $$\begin{cases}x\equiv59\,(\text{mod}\,103)\\x\equiv75\,(\text{mod}\,239)\end{cases}$$ 중국인의 나머지 정리를 이용해 해를 구하면 $x\equiv2943\,(\text{mod}\,24717)$이므로 $b=2943$이다. 

4단계에서 V는 다음이 성립함을 밝혀 P가 보낸 값이 옳은지 확인한다. $$c^{2}\equiv9134^{2}\equiv2943\equiv b\,(\text{mod}\,24617)$$ 동전 던지기 프로토콜

장거리에 위치한 A, B 두 사람이 전화 또는 전자계산기를 이용하여 승패를 결정하는 경우를 고려하자. B가 동전 던지기를 해서 얻은 결과를 A에게 통보한다면, A는 B는 서로를 불신해서 서로 잘못된 정보를 전달하거나 정보전달을 아예 안할 수 있다. 블럼(Blum)은 이러한 문제를 해결하는 방안을 제시했다. 

1단계: A는 상당히 큰 홀수 소수를 선택해서 $p\equiv q\equiv3\,(\text{mod}\,4)$인 $p,\,q$를 선택해서 $m=pq$의 값을 구하고 B에게 $m$의 값만을 알려 준다. 

2단계: B는 $\text{gcd}(x_{1},\,m)=1$, $1\leq x_{1}<m$인 정수 $x_{1}$을 임의로 선택해서 $$x_{1}^{2}\equiv a\,(\text{mod}\,m),\,1\leq a<m$$ 인 정수 $a$를 구한 다음 A에게 $a$의 값만을 알려 준다.

3단계: A는 이미 알고 있는 두 소수 $p,\,q$의 값과 B로부터 통보받은 $a$의 값을 이용하여 2차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 4개의 해 $$\begin{align*}&x\equiv x_{1}\,(\text{mod}\,m)&&x\equiv m-x_{1},\,(\text{mod}\,m),1\leq x_{1}<m\\&x\equiv x_{2}\,(\text{mod})&&x\equiv m-x_{2}\,(\text{mod}\,m),\,1\leq x_{2}<m\end{align*}$$ 를 구하고 이 중 한개만을 B에게 알려준다. 

4단계: B가 A로부터 통보받든 값을 이용하여 $p,\,q$의 값을 구하여 그 값을 A에게 알려줄 수 있을 때 B가 이기는 것으로 정하고, 그 반대로 $p,\,q$의 값을 알려줄 수 없을 때 A가 이기는 것으로 한다. 

그리고 B는 A로부터 받은 값의 제곱을 $m$으로 나눈 나머지를 구하여 그 나머지가 $a$와 일치하는지 확인함으로써, A가 잘못 계산했는지 아니면 속였는지를 알 수 있다. 

4단계에서 B가 A로부터 $x_{2}$, 또는 $x_{2}(1-t)$를 받는 경우, B는 $x_{1}$의 값을 이용해 $(a+a_{p})$ 또는 $\text{gcd}(x_{1}+x_{2},\,m)$ 또는 $$\text{gcd}(x_{1}+m-x_{2},\,m)=\text{gcd}(x_{1}-x_{2},\,m)$$ 의 값을 구하면 $p$ 또는 $q$이다. 

B가 A로부터 $x_{1}$ 또는 $m-x_{1}$을 받는 경우 B는 이 정보로부터 $p,\,q$의 값을 구할 수 없다. 그런데 A가 $x_{1,}\,m-x_{1}$을 고를 확률과 $x_{2},\,m-x_{2}$고를 확률은 같으므로 이 동전 던지기는 공평하다.

참고자료:

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