중학교 수학으로 이해하는 시리즈 2탄은 PKI(Public Key Infrastructure)의 근간이 되는 RSA—Ron Rivest, Adi Shamir, Leonard Adleman 세 사람 이름의 두문자를 따 명명— 암호화이다.

RSA 암호화는 암호화/복호화에 서로 다른 키를 사용하는 대표적인 비대칭 키 암호화 알고리즘(asymmetric key cryptography algorithm)이다. 앞서 디피-헬만 키 교환에서 알아본 대칭 키 암호화 알고리즘은 키와 알고리즘이 서로 독립적인데 반해 비대칭 키 암호화 알고리즘은 키를 생성하는 과정과 암호화/복호화 과정이 밀접하게 연관돼 있다.

기반 지식

나머지 연산의 성질 몇 가지와 오일러 파이¹ 함수 (Euler’s phi function 또는 Euler’s totient function), 페르마 소정리 (Fermat’s little theorem)와 이의 일반화 형태인 오일러 정리 (Euler’s theorem), 중국인의 나머지 정리 (Chinese remainder theorem, CRT)에 대해 딱 RSA를 이해하는데 필요한 정도만 우선 확인하고 넘어가자.

나머지 연산의 성질

교과 과정에서는 별도의 연산으로 다루지 않지만 이미 나눗셈을 배우면서 공부했고, 개발자에게도 친숙한 나머지 연산의 몇 가지 성질에 대해 살펴보자. 연산자는 \(\bmod\)로 표기한다. 즉, \(a \bmod b\)는 \(a\)를\(b\)로 나눈 나머지를 의미한다.

두 수의 나머지가 같은 경우

\(a\)를 \(c\)로 나눈 나머지와 \(b\)를 \(c\)로 나눈 나머지가 같은 경우, 즉 \(a \bmod c = b \bmod c\)인 경우 다음을 만족한다.

$$ (b - a) \bmod c = 0 $$

간단한 숫자 몇 가지를 대입해 풀어보면 간단히 알 수 있지만 일반화한 증명은 다음과 같다.

나머지를 \(r\)이라고 하면 \(a\)와 \(b\)는 각각 다음과 같이 쓸 수 있다.

$$ a = cm +r $$

$$ b = cn +r $$

\(b\)에서 \(a\)를 빼면,

$$ \begin{matrix} b - a &=& (cn + r) - (cm + r) \\ &=& c(n - m) \end{matrix} $$

이 되기 때문에 \(c\)로 나누어 떨어진다.

나머지 연산의 곱셈

두 수 \(a\), \(b\)의 \(c\)에 대한 나머지가 각각 다음과 같으면,

$$ a \bmod c = i $$

$$ b \bmod c = j $$

\(a\)와 \(b\)의 곱에 대해서는 다음식을 만족한다.

$$ ab \bmod c \ = ij \bmod c $$

위에서처럼 \(a\), \(b\) 각각을 다음과 같이 쓸 수 있다.

$$ a = cm + i $$

$$ b = cn + j $$

\(a\)와 \(b\)의 곱은 다음과 같다.

$$\begin{matrix} ab &=& (cm + i)(cn + j) \\ &=& c ^ 2mn + cmj + cni + ij \end{matrix} $$

\(ab\)를 \(c\)로 나누면 나머지 항은 모두 나누어 떨어지고 \(ij\)를 \(c\)로 나눈 나머지만 남는다.

나머지 연산의 지수승

\(a \bmod c = i\)일 때, 나머지 연산의 지수승에 대해서는 위 곱셈 성질에 따라 다음을 만족한다.

$$ a ^ n \bmod c = i ^ n \bmod c $$

오일러 파이 함수 (Euler’s phi function)

오일러 파이 함수는 1부터 \(n\)까지의 양의 정수 중 \(n\)과 서로소인 것의 개수를 나타내는 함수이다. \(\varphi(n)\)이나 \(\phi(n)\)으로 표기한다.

예를 들면,

• 3을 기준으로 1부터 3까지의 양의 정수 1, 2, 3 중 3과 서로소인 수는 1, 2이므로 \(\varphi(3) = 2\)
• 4를 기준으로 1부터 4까지의 양의 정수 1, 2, 3, 4 중 4와 서로소인 수는 1, 3이므로 \(\varphi(4) = 2\)
• 5를 기준으로 1부터 5까지의 양의 정수 1, 2, 3, 4, 5 중 5와 서로소인 수는 1, 2, 3, 4이므로 \(\varphi(5) = 4\)
• 6을 기준으로 1부터 6까지의 양의 정수 1, 2, 3, 4, 5, 6 중 6과 서로소인 수는 1, 5이므로 \(\varphi(6) = 2\)
• 7을 기준으로 1부터 7까지의 양의 정수 1, 2, 3, 4, 5, 6, 7 중 7과 서로소인 수는 1, 2, 3, 4, 5, 6이므로 \(\varphi(7) = 6\)
• 8을 기준으로 1부터 8까지의 양의 정수 1, 2, 3, 4, 5, 6, 7, 8 중 8과 서로소인 수는 1, 3, 5, 7이므로 \(\varphi(8) = 4\)

이 된다.

특징이 보이는가? 보이지 않는다면 소수의 정의를 다시 한 번 생각해 보자. 소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 수이다. 그런데 파이 함수는 1은 포함한다. 따라서 여기서 파이 함수의 첫 번째 특징을 알 수 있다.

6의 경우를 다시 보자. 6은 1, 6 외에도 2, 3의 약수—또는 인수—를 갖는다. 따라서 \(\varphi(6)\)은 1부터 6까지 전체 6개의 숫자 중 자기 자신(6) 한 개, 2의 배수(2, 4) 두 개, 3의 배수(3) 한 개를 뺀 \(6 - (1 + 2 + 1) = 2\)가 된다.

이를 기반으로 사고를 확장해 보면, \(m\)과 \(n\)이 서로 다른 소수인 경우 \(m\)과 \(n\)을 곱한 수 \(mn\)의 파이 함수 값 \(\varphi(mn)\)은 전체 \(mn\)개의 숫자 중 \(1m\), \(2m\), …, \(nm\) 등 \(m\)의 배수 \(n\)개를 제외하고, \(1n\), \(2n\), …, \(mn\) 등 \(n\)의 배수 \(m\)개를 제외한 뒤 자기 자신(\(mn\))은 두 번 제외됐으므로 한 번 더해주는 방식으로 구할 수 있다. 여기서 두 번째 특징이 나온다.

페르마 소정리 (Fermat’s littel theorem)

페르마 소정리는 어떤 수가 소수일 필요조건에 대한 정리이다. 따라서 모든 소수는 정리를 만족하지만, 정리를 만족해도 소수가 아닐 수 있다.

페르마 소정리는 보통 합동 산술 (modular arithmetic)에서 정의한 기호로 표기하는데 이는 중학교 범위를 벗어나니 최대한 쉬운 용어로 바꿔 알아보자.

우선 첫 번째 공식이 성립한다는 가정하에 두 번째 공식이 성립함은 아래와 같이 확인할 수 있다.

나머지 연산의 성질에 따라 다음을 만족한다.

$$ \left( a^p - a \right),\bmod,p = 0 $$

즉, \(a^p - a\)를 \(p\)로 나누면 임의의 정수 \(l\)이 된다.

$$ {{a^p - a} \over p} = {{ a \left( a^{p-1} - 1 \right) } \over p} = l $$

그런데 조건에서 \(a\)는 \(p\)로 나누어 떨어지지 않고 \(p\)는 소수이므로, 위 식을 만족하려면 \( a^{p-1} - 1 \)이 \(p\)로 나누어 떨어져야 한다. 즉, \( a^{p-1} \)을 \(p\)로 나누면 나머지 1이 남는다.

위에서 언급한 것처럼 합동 산술은 중학교 수준을 벗어나지만, 대부분의 관련 자료에서 합동 산술 표기법을 사용하니 관련된 두 가지 표기법만 짚고 넘어가자.

• \(b\)가 \(a\)로 나누어 떨어진다. 또는, \(b\)가 \(a\)로 나누어 떨어지지 않는다. $$ a \mid b\ ,\ a \nmid b $$
• \(a\)를 \(n\)으로 나눈 나머지와 \(b\)를 \(n\)으로 나눈 나머지가 같다. $$ a \equiv b \pmod{n} $$

특히 두 번째 항목을 \(a\)와 \(b\)는 법 \(n\)에 대해 합동이다. (\(a\) is congruent to \(b\) modulo \(m\)) 라고 표현한다.

페르마 소정리는 아래 오일러 정리의 특수한 경우에 해당하니 증명은 오일러 정리의 증명으로 대신하자.

오일러 정리 (Euler’s theorem)

오일러 정리는 페르마 소정리에 대한 일반 형태로 페르마 소정리에서의 소수 \(p\)를 일반 정수 \(n\)으로 확장한 형태이다. 합동 산술 표기법으로 표현하면 \(n\)에 대한 조건이 완화되지만 RSA를 이해하는데는 문제가 없기 때문에 제한적 상황만 고려하자.

\(n\)이 소수인 경우 오일러 파이 함수의 첫 번째 특징에 의해 페르마 소정리의 두 번째 식과 같아진다.

오일러 정리에 대한 증명은 다음과 같다.

1부터 \(n\)까지의 정수 중 \(n\)과 서로소인 \(\varphi(n)\)개의 수들을 \( r _ 1, \cdots, r _ {\varphi(n)} \)라고 하면, 각각에 \( a \)를 곱한 \( ar _ 1, \cdots, ar _ {\varphi(n)} \) 역시 \( n \)과 서로소인 수들의 곱이므로 \(n \)과 서로소이다. 또, 이 수들을 \( n \)으로 나눈 나머지들을 모두 서로 다르다.

왜냐하면,

만약 나머지가 같은 \( ar _ i,\ ar _ j\ (0 < r _ i < r _ j < n) \)가 있다면, \( ar _ j - ar _ i = a( r _ j - r _ i)\)는 \(n\)으로 나누어 떨어진다. 그런데 \(a\)는 \(n\)과 서로소이므로 \(r _ j - r _ i \)가 \(n\)으로 나누어 떨어져야 한다. 하지만 \( n > r _ j > r _ i \)이므로 \( r _ j - r _ i \)가 \(n\)으로 나누어 떨어질 수 없다. 따라서 가정이 거짓이고, 이에 따라 나머지는 모두 다르다.

각 \(r _ i\ (1 \le i \le \varphi(n))\)에 \(a\)를 곱한 수를 살펴보자. 이 수는 다음과 같이 쓸 수 있다.

$$ ar _ i = nq _ i + m _ i\ (1 \le i \le \varphi(n)) $$

\(n\)으로 나눴을 때 몫이 \(q_i\), 나머지가 \(m_i\)라는 뜻이다. 위에서 이미 나머지들은 모두 서로 다르다는 것을 밝혔으니 나머지의 경우의 수 역시 \(\varphi(n)\)가지이다. 그리고 \(m _ i\)들은 모두 \(n\)과 서로소이다.

왜냐하면,

만약 \(m_i\)와 \(n\)이 서로소가 아니고 1이 아닌 공약수 \(d\)를 갖는다면, \(m_i = dl_i\), \(n = dk\)라 할 수 있고, \(ar_i\)는 다음과 같이 쓸 수 있다.

$$ \begin{matrix} ar_i &=& nq_i + m_i \\ &=& dkq_i + dl_i \\ &=& d(kq_i + l_i) \end{matrix} $$

이 경우 \(ar_i\)와 \(n\)은 1이 아닌 공약수 \(d\)를 갖게 되기 때문에 서로소가 아니게 된다. 따라서 \(m_i\)와 \(n\)은 서로소이다.

정리하면, \(m_i\)는 \(n\)으로 나눈 나머지이므로 \(n\)보다는 작고, \(n\)과 서로소인 \(\varphi(n)\)개의 수이다. 즉, \(r_i\)와 순서만 다른 같은 수들의 집합이다.

이제 \(ar_i\)들을 모두 곱하면,

$$ ar _ 1 \times \cdots \times ar _ {\varphi(n)} $$

$$ = (nq _ 1 + m _ 1) \times \cdots \times (nq _ {\varphi(n)} + m _ {\varphi(n)}) $$

이 되는데, 이 식을 전개하면 모든 항에 \(n\)이 한 개 이상 포함되고, 마지막 항 \(m _ 1 \times \cdots \times m _ {\varphi(n)}\)만 \(n\)을 포함하지 않는다. 위에서 \(m_i\)는 순서만 바뀐 \(r_i\)와 같은 수들의 집합이라는 것을 밝혔으니 \(n\)이 포함되지 않은 마지막 항은 \(r _ 1 \times \cdots \times r _ {\varphi(n)}\)과 같다. 따라서 \(ar_i\)들을 모두 곱한 수를 \(n\)으로 나눈 나머지는 \(r_i\)들을 모두 곱한 수를 \(n\)으로 나눈 나머지와 같다.

$$ ar _ 1 \times \cdots \times ar _ {\varphi(n)} $$

$$ = b _ 1 n ^ {\varphi(n)} + b _ 2 n ^ {\varphi(n) - 1} + \cdots + (m _ 1 \times \cdots \times m _ {\varphi(n)}) $$

$$ = b _ 1 n ^ {\varphi(n)} + b _ 2 n ^ {\varphi(n) - 1} + \cdots + (r _ 1 \times \cdots \times r _ {\varphi(n)}) $$

$$ \therefore (ar _ 1 \times \cdots \times ar _ {\varphi(n)}),\bmod,n $$

$$ \quad = (r _ 1 \times \cdots \times r _ {\varphi(n)}),\bmod,n $$

두 곱한 수를 \(n\)으로 나눴을 때 나머지가 같으므로 \(ar_i\)들의 곱에서 \(r_i\)들의 곱을 뺀 수는 \(n\)으로 나누어 떨어진다. 즉,

$$ (ar _ 1 \times \cdots \times ar _ {\varphi(n)} - r _ 1 \times \cdots \times r _ {\varphi(n)}) ,\bmod,n = 0 $$

$$ (a ^ {\varphi(n)} - 1)(r _ 1 \times \cdots \times r _ {\varphi(n)}),\bmod,n = 0 $$

이 중 \(r _ 1 \times \cdots \times r _ {\varphi(n)}\)는 \(n\)과 서로소인 수들의 곱이므로 역시 \(n\)과 서로소이다. 따라서 위 식을 만족하려면 \(a ^ {\varphi(n)} - 1\)이 \(n\)으로 나누어 떨어져야 한다. 즉,

$$ (a ^ {\varphi(n)} - 1),\bmod,n = 0 $$

$$ \therefore a ^ {\varphi(n)},\bmod,n = 1 $$

중국인의 나머지 정리 (Chinese remainder theorem)

중국인의 나머지 정리는 연립 합동 산술의 해의 존재성과 유일성을 증명하는 정리인데, RSA 절차를 증명하는데 필요한 부분만 발췌해 간단히 기술하면 다음과 같다.

\(a \bmod p = b\)이므로 나머지 연산의 첫 번째 성질 - 두 수의 나머지가 같은 경우에 의해 \(a - b\)는 \(p\)로 나누어 떨어진다. 그리고 같은 이유로 \(a - b\)는 \(q\)로도 나누어 떨어진다.

\(p\)와 \(q\)는 서로소이므로 \(a-b\)가 \(p\), \(q\)로 모두 나누어 떨어지려면 다음 관계를 만족해야 한다.

$$ a - b = kpq $$

따라서 \(a\)를 \(pq\)로 나눈 나머지는 \(b\)를 \(pq\)로 나눈 나머지와 같다.

키 생성 절차

RSA 키 생성 절차는 다음과 같다.

1. 서로 다른 소수 \(p\), \(q\)를 고른다.
2. \((p-1), (q-1)\)과 각각 서로소인 \(e\)를 고른다.
3. \(ed\)를 \((p-1)(q-1)\)로 나눴을 때 나머지가 1이 되는 \(d\)를 찾는다.
4. \(N = pq\)를 구한다.
5. \((N, e)\)가 공개키, \((N, d)\)가 개인키가 된다.
6. 공개키는 원문을 암호화할 때 사용하고 개인키는 암호문을 복호화할 때 사용하므로, 이름 그대로 공개키는 모두에게 공개하고, 개인키는 별도로 안전하게 보관한다.

RSA의 핵심은 \(N\)만 가지고는 \(p, q\)를 찾기 어렵고—소인수분해가 어렵고—, \(p, q\)를 모르는 상태에서는 \(e\)를 알아도 \(d\)를 특정할 수 없다는데 있다.

암호화 및 복호화

키의 길이, 원문을 작은 단위로 나누는 방법 등에 따라 차이가 있기는 하지만 RSA의 기본적인 암호화/복호화 방법은 정해진 하나의 규칙을 따른다. 원문이 \(N\)보다 작다는 가정하에 간단한 절차를 알아보자.

암호화 절차

• 정보 수신자의 공개키를 확보한다.
• 원문을 \(o\)라 하면, \(c=o ^ e \bmod N\)을 계산한다.
• 계산된 \(c\)—암호문—를 수신자에게 전송한다.

복호화 절차

• 수신한 \(c\)를 이용해, \(o ^ \prime = c ^ d \bmod N\)을 계산한다.
• 계산한 \(o ^ \prime\)이 원문 \(o\)이다.

---

RSA를 사용하는 일반적인 절차를 도식화하면 다음과 같다. Alice가 정보를 보내는 사람, Bob이 정보를 받는 사람이다.

암호화 및 복호화 검증

\(o\)와 \(o ^ \prime\)이 왜 같아지는지 알아보자.

나머지 연산의 지수승 성질에 따라 \(o ^ \prime\)의 계산식은 다음과 같은 관계를 갖는다.

$$ c ^ d \bmod N = (o ^ e) ^ d \bmod N $$

\(ed\)는 \((p-1)(q-1)\)로 나눴을 때 나머지가 1이 되는 수이므로 다음과 같이 쓸 수 있다.

$$ (o ^ e) ^ d = o ^ {ed} = o ^ {k(p-1)(q-1) + 1} $$

결국 위 식은 다음 관계를 만족한다.

$$ \begin{matrix} c ^ d \bmod N &=& o ^ {ed} \bmod N \\ &=& o ^ {k(p-1)(q-1) + 1} \bmod N \\ &=& ((o ^ k) ^ {(p-1)(q-1)} \times o) \bmod N \end{matrix} $$

마지막 식은 나머지 연산의 곱셈 성질에 따라 나누어 쓸 수 있다.

$$ ((o ^ k) ^ {(p-1)(q-1)} \times o) \bmod N $$

$$ = ((o ^ k) ^ {(p-1)(q-1)} \bmod N)(o \bmod N)\bmod N$$

만약 \(o\)와 \(N\)이 서로소라면 \(o ^ k\)와 \(N\)도 서로소가 된다. 따라서 이 경우에는 오일러 정리에 따라,

$$ ((o ^ k) ^ {(p-1)(q-1)} \bmod N)(o \bmod N)\bmod N$$

$$ = (1 \times (o \bmod N)) \bmod N = o $$

의 관계를 만족한다.

\(o\)와 \(N\)이 서로소가 아닌 경우는 \(o\)가 \(p\)나 \(q\) 중 하나를 인수로 갖는 경우이다. \(o\)는 \(N\)보다 작게 나눈 단위이기 때문에 \(p\)와 \(q\)를 동시에 인수로 가질 수는 없다. \(q\)가 \(o\)의 인수라 가정하고 \(N\) 대신 \(p\), \(q\)로 각각 나눈 경우를 생각해 보자.

$$ ((o ^ k) ^ {(p-1)(q-1)} \times o) \bmod p $$

$$ = ((o ^ {k(q-1)}) ^ {(p-1)} \bmod p)(o \bmod p) \bmod p$$

\(o\)는 \(q\)의 배수이고, \(p\)를 인수로 포함하지 않기 때문에 \(o ^ {k(q-1)}\)은 \(p\)로 나누어 떨어지지 않는다. 페르자 소정리를 적용해 정리하면 다음과 같다.

$$ ((o ^ {k(q-1)}) ^ {(p-1)} \bmod p)(o \bmod p) \bmod p$$

$$ = 1 \times (o \bmod p) \bmod p = o \bmod p$$

이 풀이는 나누는 수를 \(q\)로 변경해도 그대로 성립한다. \(o\)가 \(q\)의 배수이기 때문에 \(q\)로 나누면 양변이 모두 0이 되기 때문이다. 즉, 다음 관계를 만족한다.

$$ ((o ^ k) ^ {(p-1)(q-1)} \times o) \bmod p = o \bmod p $$

$$ ((o ^ k) ^ {(p-1)(q-1)} \times o) \bmod q = o \bmod q $$

중국인의 나머지 정리를 이용해 최종적으로 다음과 같이 정리할 수 있다.

$$\begin{matrix} ((o ^ k) ^ {(p-1)(q-1)} \times o) \bmod N &=& o \bmod N \\ &=& o \end{matrix}$$

전자 서명

위 절차에 대한 검증을 자세히 이해하면 사실 공개키, 개인키의 구분이 무의미하다는 사실을 알 수 있다. 암호화하는 방법, 복호화하는 방법이 정해져 있고, 키가 두 개 있는데, 둘 중 어느 하나를 이용해 암호화하면 다른 하나를 이용해 복호화할 수 있는 것이다.

이런 특징으로 인해 내 개인키로 정보를 암호화하면 내 공개키로 복호화하는 것이 가능하다.

아무나 풀 수 있는 암호가 무슨 의미가 있지?

계약서나 서류 등에 서명하는 경우를 생각해 보자.

1. 계약서나 서류를 모두 읽고 이해한다.
2. 계약서나 서류에 서명한다.

2 단계를 지나면 서류에 서명한 당사자는 해당 서류의 내용을 모두 이해했고, 동의했다는 의미가 된다. 서명의 대상은 서명할 당시의 내용이다. 즉, 서명 후 내용을 수정하면 서명의 효력을 잃어야 마땅하고 이를 위배하면—서명 후 내용을 변경하고도, 서명이 변경된 내용에 대한 것처럼 속이면— 중대한 위법이 된다.

개인키를 이용한 암호화는 바로 이 용도로 사용할 수 있다.

원문을 가진 Alice는 원문과 함께 원문을 자신의 개인키로 암호화한 암호문²을 Bob에게 전달하고, Bob은 Alice의 공개키로 암호문을 복호화해 해당 내용이 원문과 같은지 비교해 볼 수 있다. 원문과 복호화한 정보가 같다면 이 내용은 Alice가 최종적으로 확인한 내용과 같은 것이다. 즉, Alice가 원문과 함께 전달한 암호문이 바로 Alice의 서명이 되는 것이다.

이 과정에는 숨겨진 정보가 하나 더 필요하다.

복호화에 사용한 공개키 = Alice의 것

서류에 하는 자필 서명도 단순히 낙서처럼 끄적여 둔 일종의 표식이 한 특정인의 것이라는 보장이 있어야 의미가 있듯, 전자 서명도 복호화에 사용한 공개키가 Alice의 것임을 특정할 수 있어야 의미를 가질 수 있다.

하지만 RSA는 키 소유자를 특정하는 기능까지는 제공하지 않는다.

• 공개키A로 암호화한 내용은 개인키A를 가지고 있어야 복호화할 수 있다.
• 공개키A로 복호화할 수 있는 암호문은 개인키A로만 만들 수 있다.

위 두 가지가 RSA의 두 가지 중요한 성질이다.

우리가 사용하는 공인인증서는 이러한 성질에 정부 또는 은행, 증권사 등이 공개키의 보유자를 특정할 수 있도록 보증하는 기능을 더한 것이다. 따라서 서명 용도로 사용이 가능하다.