[암호학] 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}\)고를 확률은 같으므로 이 동전 던지기는 공평하다.

참고자료:

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