RSA 공개 키 암호체계 증명
빌드업
왼쪽부터 순서대로 앨리스 , 밥 , 이브라 하자. 앨리스와 밥은 메세지를 주고받을 당사자고, 이브는 메세지에 관심이 있는 소극적 공격자다. 주황색 상자는 앨리스만 알고 있는 정보를, 하늘색 상자는 밥만 알고 있는 정보를, 검은색 상자는 공개된(이브도 알고 있는) 정보를 나타낸다.
앨리스는 밥에게 받아야할 메세지 $m \in \mathbb{N}$ 이 있다.
알고리즘 1
키 설정: 앨리스가 큰 소수 $p$, $q$ 의 곱 $N=pq$ 와 $\gcd \left( e , (p-1)(q-1) \right) = 1$ 을 만족하는 $e$ 를 선택해서 공개한다.
암호화: 밥이 $c \equiv m^{e} \pmod{N}$ 를 계산해서 공개한다.
복호화: 앨리스가 $de \equiv 1 \pmod{(p-1)(q-1)}$ 를 만족하는 $d$ 를 구해서 $x \equiv c^{d} \equiv m \pmod{N}$ 를 계산하면 $x=m$ 을 얻는다. 이브는 현실적으로 $d$ 를 알 수 없기 때문에 $m$ 을 알 수 없다.
설명
RSA 공개 키 암호체계는 로널드 라이베스트ronald Rivest, 아디 샤미르adi Shamir, 레너드 애들먼leonard Adleman에 의해 개발된 암호체계로써, 이름의 앞글자를 따서 RSA 로 줄여 부른다. 세 사람은 이 업적으로 2002년 튜링상을 수상한다.
이산로그 문제의 어려움에만 기반한 엘가말 공개 키 암호체계와 달리 소인수분해 문제의 어려움에도 기반하고 있으며, 그 견고함만으로도 큰 소수를 구할 가치가 있게 된다. 게다가 이론적이기만 하거나 이미 구닥다리가 된 방법이 아니라 실제로 지금, 전세계에서 사용하고 있다는 점에서 공부하는 재미가 있는 체계다. 치명적인 공격법으로는 양자 컴퓨터를 기반으로 한 쇼어 알고리즘shor Algorithm이 있으나, 양자 컴퓨터 상용화는 요원하기 때문에 당분간은 현역에 있을 것으로 보인다.
증명
복호화
앨리스는 $N$ 의 소인수분해 $N = pq$ 를 알고 있으므로 $\gcd \left( e , (p-1)(q-1) \right) = 1$ 을 만족하는 $e$ 를 찾을 수 있다.
확장된 유클리드 정리: 두 정수 $a,b$ 에 대해 $aX + bY = \gcd (a,b)$ 는 반드시 정수해를 가진다.
두 정수 $e$, $(p-1)(q-1)$ 에 대해 $$ e X + (p-1)(q-1) Y = 1 $$ 를 만족하는 정수해 $\begin{cases} X=d \\ Y = - k \end{cases}$ 가 존재하므로 $$ de = 1 + k (p-1)(q-1) $$ 이는 다시 말해 $de \equiv 1 \pmod{(p-1)(q-1)} $, 즉 $d$ 가 링 $\mathbb{Z}_{(p-1)(q-1)}$ 에서 $e$ 의 역원이라는 뜻이고 앨리스는 $p$, $q$ 를 알고 있으므로 $d$ 를 쉽게 찾을 수 있다. [ NOTE: 링에서 곱셈에 대한 역원의 존재성은 결코 당연하지 않다는 점을 생각해보면 $\gcd \left( e , (p-1)(q-1) \right) = 1$ 이라는 조건이 필수적임을 알 수 있다. ]
오일러 토션트 정리: $$ \gcd(a,m) = 1 \implies a^{ \phi (m) } \equiv 1 \pmod{m} $$
$\gcd \left( e , (p-1)(q-1) \right) = 1$ 이므로 $e$ 의 역원 $d$ 는 다음과 같이 구해진다. $$ d = e^{-1} = e^{\phi \left( (p-1)(q-1) \right) -1} $$ 이는 단순히 $e$ 를 거듭제곱할 뿐이므로, 연속제곱법으로 쉽고 빠르게 계산할 수 있다. $\gcd ( c , pq ) = 1$ 가 성립하는 경우와 아닌 경우로 나누어서 생각해보자.
Case 1. $\gcd ( c , pq ) = 1$
합동방정식의 거듭제곱근을 구하는 문제로 귀결된다.
토션트 함수의 곱셈적 성질: $$ \gcd (p , q) =1 \implies \phi ( p q ) = \phi (p) \phi (q) $$
$\phi (p) = p-1$ 이고 $\phi (q) = q-1$ 이므로 $$ \phi (pq) = \phi (p) \phi (q) = (p-1)(q-1) $$
오일러 토션트 정리: $$ \gcd(c,N) = 1 \implies c^{ \phi (N) } \equiv 1 \pmod{N} $$
$c^{(p-1)(q-1)} = c^{ \phi (pq ) }$ 이므로 $$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv c^{1 + k (p-1)(q-1)} \\ & \equiv c \cdot \left( c^{(p-1)(q-1)} \right)^{k} \\ & \equiv c \cdot 1^{k} \\ & \equiv c \pmod{pq} \end{align*} $$
Case 2. $\gcd ( c , pq ) \ne 1$
$$ C \equiv c^{(p-1)(q-1)} \pmod{pq} $$ $c$ 가 $pq$ 의 배수면 $x^{e} \equiv 0$ 이므로 $x = 0$ 이어야하고 아무 의미가 없다. 따라서 $c$ 는 $p$ 혹은 $q$ 둘 중 하나의 배수라고 가정할텐데, $p$ 와 $q$ 중 무엇의 배수가 되는지는 전혀 상관 없으므로 $q$ 만의 배수라고 해보자. 그러면 어떤 $n_{0} \in \mathbb{Z}$ 와 $p$ 의 배수가 아닌 어떤 $K \in \mathbb{Z}$ 에 대해 $$ \begin{align*} C =& c^{(p-1)(q-1)} + (pq) \cdot n_{0} \\ =& \left[ qK \right]^{(p-1)(q-1)} + p \cdot q n_{0} \end{align*} $$ 위 식을 만족시키는 $q n_{0}$ 가 존재하므로 $$ c^{(p-1)(q-1)} \equiv \left[ (qK)^{q-1} \right]^{p-1} \pmod{p} $$
Part 1. $\left( c^{d} \right)^{e} \equiv c \pmod{p}$
페르마의 소정리: 소수 $p$ 와 서로소인 정수 $a$ 에 대해, $a^{p-1} \equiv 1 \pmod{p}$
$K$ 는 $p$ 의 배수가 아니므로 $\left[ (qK)^{q-1} \right]$ 는 $p$ 와 서로소고, $$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv c^{1 + k (p-1)(q-1)} \\ & \equiv c \cdot \left[ (qK)^{k(q-1)} \right]^{p-1} \\ & \equiv c \cdot 1 \pmod{p} \end{align*} $$
Part 2. $\left( c^{d} \right)^{e} \equiv c \pmod{q}$
$$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv \left[ qK \right]^{de} \\ & \equiv 0 \\ & \equiv qK \\ & \equiv c \pmod{q} \end{align*} $$
Part 3. $\left( c^{d} \right)^{e} \equiv c \pmod{pq}$
모듈로끼리의 곱: $\gcd ( m_{1} , m_{2} ) = 1$ 이면 $\begin{cases} a \equiv b \pmod{ m_{1} } \\ a = b \pmod{ m_{2} } \end{cases} \implies a \equiv b \pmod{ m_{1} m_{2} }$
Part 1, 2에서 $\begin{cases} \left( c^{d} \right)^{e} \equiv c \pmod{p} \\ \left( c^{d} \right)^{e} \equiv c \pmod{q} \end{cases}$ 이었으므로 다음을 얻는다. $$ \left( c^{d} \right)^{e} \equiv c \pmod{pq} $$
따라서 $x=c^{d}$ 는 어떤 경우든 $x^{e} \equiv c \pmod{pq}$ 의 해로써 존재한다. 또한 다른 해 $u$ 가 있다고 해도 항상 $u \equiv c^{d} \pmod{pq}$ 와 같이 나타남을 쉽게 보일 수 있다.
■
암호화
이브는 $e$ 는 알고 있지만 역원 $d$ 를 찾기 위해서는 소인수분해 문제 $N=pq$ 를 풀어야한다. 이는 아주 어려우므로, 밥은 앨리스에게 메세지 $m$ 을 안전하게 전달할 수 있다.
■
같이보기
소인수분해 문제의 어려움을 이용한 보안 알고리즘
소인수분해 문제에 대한 공격 알고리즘
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p115~122. ↩︎