📂정수론

골드바서-미칼리 확률 키 암호체계 증명

빌드업

왼쪽부터 순서대로 앨리스 , 밥 , 이브라 하자. 앨리스와 밥은 메세지를 주고받을 당사자고, 이브는 메세지에 관심이 있는 소극적 공격자다. 주황색 상자는 앨리스만 알고 있는 정보를, 하늘색 상자는 밥만 알고 있는 정보를, 검은색 상자는 공개된(이브도 알고 있는) 정보를 나타낸다.

앨리스는 밥에게 받아야할 메세지 $m \in \left\{ 0 , 1 \right\}$ 이 있다. $\displaystyle \left( {{ x } \over { y }} \right)$ 는 야코비 기호를 의미한다.

알고리즘 ¹

키 설정: 앨리스가 큰 소수 $p$, $q$ 의 곱 $N=pq$ 와 $\displaystyle \left( {{ a } \over { p }} \right) = \left( {{ a } \over { q }} \right) = -1$ 을 만족하는 $a$ 를 선택해서 공개한다.

---

암호화: 밥이 랜덤한 $1 < r < N$ 을 선택하고 $c \equiv \begin{cases} r^2 &, m=0 \\ a r^2 &, m=1 \end{cases}$ 를 계산해서 공개한다.

---

복호화: 앨리스는 $\displaystyle m = \begin{cases} 0 &, \left( {{ c } \over { p }} \right) = 1 \\ 1 &, \left( {{ c } \over { p }} \right) = -1 \end{cases}$ 을 계산하면 된다. 이브는 현실적으로 $p$ 를 알 수 없기 때문에 $m$ 을 알 수 없다.

설명

골드바서-미칼리 확률 키 암호체계는 샤피 골드바서^{shafi Goldwasser} 와 실비오 미칼리^{silvio Micali}에 의해 개발된 암호체계로써, 두 사람은 이 업적으로 2012년 튜링상을 수상한다.

암호체계가 무엇이든 평문의 집합이 작으면 암호를 해독하는 게 아니라 직접 암호를 만들어보면서 뚫릴 수도 있는데, 그런 약점에 대처하기 위해 고안 되었다. 가령 메세지로 예상되는 것이 ‘공격’, ‘방어’, ‘도주’ 정도라면 그냥 셋 다 넣어보면서 암호문을 만들고 비교하면 뚫린다.

물론 이는 극단적인 예시고, 평문이 어떤 유형일지 짐작갈 때의 공격을 차단하는 정도로 받아들이면 된다. 하지만 ‘그 정도’로 암호체계는 놀라울 정도로 견고해진다. 평문의 집합은 자연수와 일대일대응이 가능하며, 자연수는 이진법으로 나타낼 수 있기 때문에 1비트짜리 평문 $m \in \left\{ 0 , 1 \right\}$ 에 대한 증명만 있으면 충분하다.

이름의 확률^{probabilistic}이란 사실 수학에서 말하는 엄밀한 의미의 확률을 말하는 건 아니다. 공격자 입장에서는 답이 고작 $0$ 과 $1$ 둘 중 하나기 때문에 $p$ 를 알든 모르든 대략 $\displaystyle {{1} \over {2}}$ 확률로 답을 맞출 수 있다. 그러나 $n$ 비트짜리 평문에 대해서는 확률이 $\displaystyle {{1} \over {2^n}}$ 으로 떨어진다. 공격자의 입장에선 맞출 수 없는 게 아니라 맞춰도 맞았는지 알 수 없기 때문에 확률이라는 말이 붙은 것이다. 그렇다고 $N=pq$ 를 계산하기엔 소인수분해 문제 자체가 만만하지 않다. 이러니 좋은 암호체계가 되는 것이다.

증명은 상당히 충격적인데, 어렵고 복잡해서가 아니라 쉽고 간단해서다. 정수론을 공부해본 사람이라면 누구나 르장드르 심볼과 가우스의 이차상호 법칙을 접해보았겠지만 거기서 이런 실용적인 아이디어가 나올 수 있다는 사실은 알고도 믿기 힘든 일이다. 수학자라는 족속이 원래 머리가 좋고 응용수학이 특히 기발한 건 맞지만, 이건 정말 천재라는 감탄이 절로 나올 정도의 걸작이다.

증명

복호화

앨리스는 $N$ 의 소인수분해 $N = pq$ 를 알고 있으므로 $\displaystyle \left( {{ c } \over { p }} \right)$ 를 계산할 수 있다.

---

Case 1. $m=0$

$$ \begin{align*} \displaystyle \left( {{ c } \over { p }} \right) =& \left( {{ r^2 } \over { p }} \right) \\ =& \left( {{ r } \over { p }} \right) \left( {{ r } \over { p }} \right) \\ =& 1 \end{align*} $$

---

Case 2. $m=1$

$$ \begin{align*} \displaystyle \left( {{ c } \over { p }} \right) =& \left( {{ a r^2 } \over { p }} \right) \\ =& \left( {{ a } \over { p }} \right) \left( {{ r } \over { p }} \right) \left( {{ r } \over { p }} \right) \\ =& \left( {{ a } \over { p }} \right) \\ =& -1 \end{align*} $$

■

암호화

Case 1. $m=0$

$$ \begin{align*} \displaystyle \left( {{ c } \over { N }} \right) =& \left( {{ r^2 } \over { N }} \right) \\ =& \left( {{ r } \over { N }} \right) \left( {{ r } \over { N }} \right) \\ =& 1 \end{align*} $$

---

Case 2. $m=1$

$$ \begin{align*} \displaystyle \left( {{ c } \over { N }} \right) =& \left( {{ a r^2 } \over { N }} \right) \\ =& \left( {{ a } \over { N }} \right) \left( {{ r } \over { N }} \right) \left( {{ r } \over { N }} \right) \\ =& \left( {{ a } \over { N }} \right) \\ =& \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right) \\ =& (-1) \cdot (-1) \\ =& 1 \end{align*} $$

---

이브도 $N$ 은 알고 있으므로 $\displaystyle \left( {{ c } \over { N }} \right)$ 를 계산할 수는 있다. 하지만 $m$ 이 무엇이든 그 결과는 $\displaystyle \left( {{ c } \over { N }} \right) = 1$ 이므로 $m$ 이 무엇인지는 알 수가 없다. 따라서 소인수분해 문제 $N=pq$ 를 풀어서 $\displaystyle \left( {{ c } \over { p }} \right)$ 를 계산해야한다. 이는 아주 어려우므로, 밥은 앨리스에게 메세지 $m$ 을 안전하게 전달할 수 있다.

■

같이보기

• 소인수분해

소인수분해 문제의 어려움을 이용한 보안 알고리즘

• RSA 공개 키 암호체계
• 골드바서-미칼리 확률 키 암호체계

소인수분해 문제에 대한 공격 알고리즘

• 폴라드 p-1 소인수분해 알고리즘
• 준소수의 소인수분해 문제가 쉽게 풀리는 조건