RSA 암호의 원리

RSA는 공개키 암호화 알고리즘이다. 기존의 고전 암호나 블록 암호는 암호화와 복호화에 같은 키가 사용되는 대칭키 암호이지만 RSA는 공개키로 누구나 암호화 할 수 있지만 복호화하려면 비밀키가 필요한 비대칭키 암호화 알고리즘이다. 대칭키 암호화 알고리즘은 기본적으로 암호를 사용하는 사람과 키를 교환해야 한다. 이 과정에서 키가 외부로 유출될 가능성도 있고 사용하는 사람이 많아질수록 키를 많은 사람과 교환해야 한다. 하지만 비대칭키 암호화 알고리즘은 이러한 키 교환이 필요하지 않다. 상대방에게는 공개키만 주고 상대방이 공개키로 암호화한 데이터를 전송하면 가지고 있는 개인키로 복호화하면 된다. 키를 공유할 필요가 없으므로 대칭키 암호화 알고리즘에 비해서 안전하고 간편하다.

 

RSA는 공개키를 소인수분해해서 비밀키를 계산할 수 있다. 즉 RSA의 안정성은 수학적으로 큰 수를 소인수분해하는데 매우 오랜 시간이 걸린다는데 있다. 따라서 매우 큰 수도 빠르게 소인수분해하는 내용의 논문이 나오거나 양자컴퓨터가 개발된다면 RSA는 뚫리게 된다. 아마 그때쯤엔 현대 암호가 아니라 고전 암호로 분류될 것 같다.

 

RSA는 수학을 기반으로 동작한다. 서로 다른 키로 암호화, 복호화를 진행할 수 있는건 전부 수학의 힘이다. RSA의 암호화 복호화 과정은 간단하지만 이게 왜 되는건지 증명하고 완벽히 이해하려면 정수론 배경 지식이 필요하다. 따라서 먼저 RSA를 이해하는데 필요한 수학 개념들을 살펴보겠다.

 

유클리드 호제법

두 정수 $a, b$가 있고 $a$를 $b$로 나눈 나머지를 $r$이라고 하면 $0 \leq r \leq b$일때 $\gcd(a, b) = \gcd(b, r)$이 성립한다.

증명

먼저 $a$를 $b$로 나눈 몫을 $q$라고 하고 나머지를 $r$이라 하면 $a = bq + r$이고 이항하면 $r = a - bq$이다.

그리고 $\gcd(a, b)$를 $G$라고 두면 $a = Ga', b = Gb'$로 나타낼 수 있다. 여기서 $a', b'$은 무조건 서로소이다.

 $r = a - bq$에다가 $a = Ga', b = Gb'$를 대입해보면 $r = Ga' - Gb'q = G(a'-b'q)$이고 $r = G(a'-b'q)$임을 알 수 있다. 지금까지 정리한 $b$와 $r$에 대한 식을 보면 $b = Gb'$, $r = G(a'-b'q)$이고 $G$는 $\gcd(a, b)$이므로

$b$와 $r$은 공약수 $G$를 가지고 있다. 따라서 $\gcd(a, b) = \gcd(b, r)$을 증명하려면 $b'$과 $a'-b'q$가 서로소임을 증명하면 된다.

 

귀류법을 이용해서 위 사실을 증명할 수 있다. $b'$과 $a'-b'q$가 서로소가 아니라고 가정한다면 공약수 $t$를 가지게 된다.

따라서 $a'-b'q = mt, b' = nt$이러한 꼴로 나타낼 수 있고 $a'-b'q$에 $nt$를 대입해보면 $a'-ntq = mt$가 된다.

식을 조금 더 변형해보면 $a' = mt+ntq = t(m+nq)$이므로 $a' = t(m+nq)$이고 $b' = nt$이므로 $a'$과 $b'$는 서로소여아 하지만 $t$라는 공통 약수를 가지기 때문에 모순이 발생한다.

따라서 $b'$과 $a'-b'q$가 서로소가 아니라는 가정은 틀렸고 $b'$과 $a'-b'q$는 서로소임이 증명된다.

 

베주 항등식

둘 중 하나는 0이 아닌 두 정수 $a, b$가 있을 때 아래 3가지 명제가 성립한다.

 

1. $ax + by = \gcd(a, b)$를 만족하는 해 $x, y$가 반드시 존재한다.

2. $d$는 정수 $x, y$에 대하여 $ax+by$꼴로 표현될 수 있는 가장 작은 자연수이다.

3. 정수 $x, y$에 대하여 $ax+by$꼴로 표현 되는 모든 정수는 $d$의 배수이다.

증명

먼저 다음과 같은 집합 $S$를 정의한다.

$S = \{ax+by\;|\;ax+by > 0, x\in \mathbb{Z}, y \in \mathbb{Z}\}$

집합 $S$는 자연수의 부분집합이다.

$\begin{cases}a\times{(-1)}+b\times{0}\in{S} & \text{if }a \lt{0}\\a\times{1}+b\times{0}\in{S}& \text{if }a \gt{0}\\b\neq{0}, |b|\in{S}& \text{if }a=0\end{cases}$

위와 같이 집합 $S$는 $|a|$와 $|b|$중 하나는 원소로 가지고 음수를 원소로 가질 수 없으므로 공집합이 아닌 자연수의 부분집합이다. 따라서 자연수의 정렬성에 의해서 집합 $S$에는 최소 원소가 존재하고 이것을 $d$라고 하자.

$d$는 집합 $S$의 원소이므로 $ax+by=d$를 만족시키는 정수 $x, y$가 존재한다.

그리고 나눗셈 정리에 의해 $a = dq+r$을 만족시키는 정수 $q, r$이 유일하게 존재하고 $0 \le{r} \lt{d}$이다.

나눗셈 정리의 식을 이항해서 $r = a - dq$로 바꿔쓸 수 있다.

 

이제 $d$에다 식을 대입하면 $r = a-dq = a-(ax+by)q = a-qax-qby = a(1-qx)+b(-qy)$가 된다.

위 식의 결과를 보면 $r = ax + by$형태로 나타낼 수 있고 $r \gt{0}$이라고 하면 집합 $S$의 정의에 의해서 $r \in{S}$이고, 나눗셈 정리에 의해서 $0 \le{r} \lt{d}$여야 하기 때문에 이는 $d$가 집합 $S$의 최소 원소라는 가정에 모순이 발생한다.

따라서 $r = 0$이므로 $d \mid{a}$이고 같은 방법으로 $d \mid{b}$임을 알 수 있다. 즉 $d$는 $a, b$의 공약수이고 $d \mid{\gcd(a, b)}$이다.

 

마지막으로 $a$와 $b$의 공약수 $g$가 있다고 하면 $a = ga', b = gb'$이라 놓을 수 있고 이걸 $d = ax+bx$에 대입해보면 $d = ga'x+gb'y = g(a'x + b'y)$임을 알 수 있다. 따라서 최종 결론은 $g \mid{d}$이고 $d \mid{\gcd(a, b)}$이므로 $d = \gcd(a, b)$이고 $ax+ay=d$를 만족하는 두 정수 $x, y$가 존재한다. 그리고 $d$는 집합 $S$의 최소 원소이므로 위 3가지 명제가 모두 참임을 알 수 있다.

 

확장 유클리드 알고리즘

베주 항등식에 의해 두 정수 $a, b$에 대해 $ax+by=\gcd(a, b)$를 만족하는 정수해 $x, y$는 항상 존재하고 정수 $x$와 $y$의 값을 구하는 알고리즘이 확장 유클리드 알고리즘이다.

 

먼저 $a$를 $b$로 나눈 나머지를 $r$이라 두고 몫을 $q$라 둔 후에 유클리드 호제법을 응용해서 $ax+by=\gcd(a, b)$를 $bx'+ry'=\gcd(b, r)$로 변환시켜 본다.

나머지 정리에 의해 $r = a-qb$이고 이걸 식에 대입하면

$\gcd(a, b) = \gcd(b, r) = bx'+ry' = bx'+(a-qb)y' = bx'+ay'-qby' = ay'+b(x'-qy')$이므로 $bx'+ry'=\gcd(b, r)$에서 $x'$과 $y'$을 알고있으면 $ax+by = \gcd(a, b)$를 만족하는 정수해 $x, y$를

$x = y', y = x'-qy'$이러한 식으로 구할 수 있다.

 

def gcd(a, b):
    if(not b):
        return a
    return gcd(b, a%b)

def eea(a, b):
  if(not b):
    return 1, 0
  x, y = eea(b, a%b)
  return y, x - (a//b) * y
  
a, b = 10, 20
x, y = eea(a, b)

assert a*x + b*y == gcd(a, b)

print(x, y)

 

최종적으로 나온 식을 이용해서 python으로 확장 유클리드 알고리즘을 구현한 코드이다. 잘못된 해가 나올 경우 assert에 걸릴텐데 돌려보면 assert안걸리고 베주 항등식의 정수해가 잘 찾아지는걸 볼 수 있다.

 

위에서 설명한 방법 말고도 유클리드 호제법의 점화식에 $ax+by$를 대입해서 확장 유클리드 알고리즘의 점화식을 얻어낼 수도 있다.

 

Modular Inverse

$ax \equiv 1 \mod n$을 만족하는 $x$를 $a$의 $n$에 대한 모듈러 역원이라고 부른다. 잉여역수라고 부르기도 하고 일반적으로 $a^{-1}$이라고 표기한다. $a$의 $n$에 대한 모듈러 역원은 확장 유클리드 알고리즘을 이용해서 구할 수 있다.

$ax \equiv 1 \mod n$은 $ax = ny+1$이라고 볼 수 있다.  이항하면 $ax-ny=1$이 되고 $ax+ny'=1$로 바꿔쓸 수 있다. 이 형태는 베주 항등식이므로 확장 유클리드 알고리즘으로 $x$를 구할 수 있다. 또한 $ax+by=\gcd(a, b)$이므로 $a$와 $n$이 서로소일 경우에만 $a$의 $n$에 대한 모듈러 역원이 존재한다. 정수해 $x$값이 음수로 나올 경우 $n$을 더해줘서 양수로 만들어주면 된다.

 

페르마의 소정리

소수 $p$와 서로소인 정수 $a$에 대하여 $a^{p-1} \equiv 1 \pmod{p}$가 성립한다.

증명

$p$는 소수이므로 $p$의 기약잉여계 $S$는 $S = \{1, 2, 3, \text{...}, p-1\}$이다.

그리고 정수 $a$를 집합 $S$의 모든 요소에 곱한 또 다른 집합 $aS = \{a, 2a, 3a, \text{...}, (p-1)a\}$를 정의한다.

집합 $S$와 $aS$에 $\pmod{p}$를 적용하면 집합 $S$의 원소는 변함이 없고 집합 $aS$의 원소는 전부 $p$보다 작아진다.

집합 $S$에서 서로 다른 값 $i$와 $j$에 대해 $ai = aj$라고 가정하면 $ai-aj \equiv 0 \pmod{p}$이고

$a(i-j) \equiv 0 \pmod{p}$가 되는데 이 합동식을 만족하려면 $i = j$여야 하므로 모순이 발생한다.

즉 집합 $aS$에 $\pmod{p}$를 적용하면 집합 $aS$의 모든 원소는 $p-1$보다 작고 전부 다른 값이므로 $\pmod{p}$를 적용했을때 집합 $aS$는 $p$의 기약잉여계인 $S$와 같다고 볼 수 있다. 따라서 $\pmod{p}$위에서 $S$의 모든 원소를 곱한 값은 $aS$의 모든 원소를 곱한 값과 같다.

 

위 사실에 기반해서 이제 집합 $S$와 $aS$를 가지고 합동식을 세워보면

$a\times{2a}\times{3a}\text{...}, (p-1)a \equiv 1\times{2}\times{3}\text{...}, p-1 \pmod{p}$이고 $a$만 빼서 따로 곱해주면

$a^{p-1}(1\times{2}\times{3}\text{...}, p-1) \equiv 1\times{2}\times{3}\text{...}, p-1 \pmod{p}$이다. 여기서 양변을 나눠주면

$a^{p-1} \equiv 1 \pmod{p}$가 된다.

 

오일러의 정리

페르마의 소정리를 일반화한 정리이다.

두 정수 $a$와 $n$이 서로소일때 $a^{\phi(n)} \equiv 1 \pmod{n}$이 성립한다.

($\phi(n)$은 오일러 피 함수라고 불리고 $n$보다 작은 자연수중에 $n$과 서로소인 자연수의 개수를 반환하는 함수이다.)

증명

정수 $n$의 기약잉여계 $S$는 $S = \{p_{1}, p_{2}, p_{3}, \text{...}, p_{\phi(n)}\}$ 이다.

그리고 집합 $S$의 모든 원소에 $n$과 서로소인 정수 $a$를 곱한 집합은 $aS = \{ap_{1}, ap_{2}, ap_{3}, \text{...}, ap_{\phi(n)}\}$이다.

 

이후 페르마의 소정리와 같은 방법으로 정수 $n$의 기약잉여계 $S$와 집합 $aS$가 $\pmod{n}$을 적용했을때 같은 집합인지 귀류법으로 증명하고 두 집합으로 합동식을 만든 후 양변을 나눠주면 증명이 된다.

 

RSA의 원리

RSA를 이해하는데 필요한 수학 개념들을 살펴보았으니 이제 구체적으로 RSA가 어떻게 동작하는지 알아보도록 하겠다.

 

키 생성

1. 두 소수 $p, q$를 준비한다.

2. $N = pq$를 계산한다.

3. $\phi(N) = (p-1)(q-1)$임을 이용해서 $\phi(N)$을 계산한다.

4. $\phi(N)$과 서로소인 $e$를 $1 \lt{e} \lt{\phi(N)}$범위 내에서 정한다.

5. $ed \equiv 1 \pmod{\phi(N)}$을 만족하는 정수 $d$를 찾는다. (확장 유클리드 알고리즘으로 Modular Inverse구하기)

6. $p, q$는 더이상 필요 없고 유출되면 개인키를 알아낼 수 있으므로 파기한다.

($N$값을 소인수분해하면 $p, q$를 얻을 수 있고 $\phi(N)$을 계산할 수 있으므로 $d$값을 구할 수 있다.)

 

암호화

공개키 $N$과 $e$를 이용해서 $m \lt N$을 만족하는 평문 $m$에 대하여 $c = m^e \mod{N}$을 계산한다.

$C$가 암호문이다.

 

복호화

비밀키 $d$를 이용해서 암호문 $c$에 대하여 $m = c^d \mod{N}$을 계산한다.

$m$이 복호화된 평문이다.

 

증명

복호화 식을 정리해보면 $m = c^d \mod{N} = (m^e \mod{N})^d \mod{N} = m^{ed}\mod{N} = m^{ed}\equiv m\pmod{N}$이다.

따라서 RSA검증을 위해서는 $m^{ed}\equiv m\pmod{N}$을 증명하면 된다.

$N = p\times{q}$이므로 위 합동식이 $\mod{p}$일때와 $\mod{q}$일때 모두 성립하면 $\mod{N}$일때도 성립한다.

따라서 $\mod{N}$대신 $\mod{p}$를 사용하도록 한다.

그리고 $ed = 1\pmod{\phi(N)} = k\times{\phi(N)}+1 = k(p-1)(q-1)+1$이렇게 식을 변형할 수 있다.

이제 이걸 검증해야하는 합동식에 대입하면

$m^{ed}\equiv m\pmod{p}$

$= m^{k(p-1)(q-1)+1}\equiv m\pmod{p}$

$= m^{k(p-1)(q-1)}\times{m}\equiv m\pmod{p}$

$= (m^{p-1})^{k(q-1)}\times{m}\equiv m\pmod{p}$

이런 식이 만들어진다. 여기서 $m$이 $p$의 배수가 아닐때와 $m$이 $p$의 배수일때 두 가지 경우의 수로 나뉜다.

먼저 $m$이 $p$의 배수가 아닐때는 $p$가 소수이므로 $m$과 서로소가 된다. 따라서 페르마의 소정리를 적용할 수 있고

$(m^{p-1})^{k(q-1)}\times{m}\equiv m\pmod{p} = 1^{k(q-1)}\times{m}\equiv m\pmod{p} = m\equiv m\pmod{p}$이므로 합동식이 성립한다.

$m$이 $p$의 배수일 경우에는 양변이 $p$의 배수여서 0과 동치가 되면서 합동식이 성립한다.

 

 

연습문제 : https://www.acmicpc.net/problem/13618

13618번: RSA

위 내용을 전부 이해했다면 쉽게 풀 수 있는 문제이다.