RSA

RSA는 세계 최초의 실용적인 공개키 암호화 알고리즘으로, 1977년에 MIT에서 연구를 하던 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 개발된 암호 알고리즘이다. RSA라는 이름도 저 셋의 성을 순서대로 따와 붙인 것.

역사

암호는 크게 대칭 암호화 방식과 비대칭 암호화 방식의 2가지로 분류된다. 대칭 암호화 방식은 암호화와 복호화의 난이도가 동일한 것을 의미하며, 비대칭 암호화 방식은 복호화의 난이도가 암호화의 난이도보다 어려운 것을 의미한다. 좀 더 자세히 말하면, 대칭 암호화 방식은 암호화를 할 수 있으면 쉽게 복호화를 할 수 있고, 반대로 복호화를 할 수 있으면 쉽게 암호화를 할 수 있는 암호 체계를 말한다. 비대칭 암호화 방식은 암호화는 쉽게 해도 복호화는 어려운 암호 체계.

RSA 이전에는 비대칭 암호화 방식이 존재하지 않았기 때문에 대칭 암호화 방식이 대중적으로 사용되었는데, 이 대칭 암호화 방식은 제 2차 세계대전 이후로 급속도로 성장한 암호학의 기준에서 보면 뚫기가 쉽다는 문제가 있었다. 당장 독일군이 절대 뚫지 못할거라 자부했던 에니그마도 과정이 조금 복잡했을 뿐 대칭 암호화 체계였으며, 결국 연합군 측의 수학자들에게 뚫려 독일군이 전쟁에서 신나게 털리게 되는 원인이 된다. 2차 대전에서 에니그마보다도 훨씬 더 원시적인 암호표를 사용했던 일본군 역시 연합군이 자신들의 암호를 뚫지 못할 것이라 자부했으나, 에니그마보다도 훨씬 더 전에 뚫려 일본군 또한 신나게 털리게 되는 원인이 된다(...).

그리고 시대는 지나 기술은 발전하여 전자 기기의 시대가 눈 앞에 비치고 있었고, 그 시대에 맞춰 안전한 암호화 알고리즘을 개발할 필요성이 대두되고 있었다. 그동한 많은 수학자들은 추상적인 방법으로 비대칭 암호화 방식에 관한 논문을 제시하고 있었으며, 그 중 하나는 1976년에 Whitfield Diffie와 Martin Hellman이 쓴 논문이었다. 이 논문은 비대칭 암호화의 구체적인 방식을 제시하진 않았지만, 정수론을 기반으로 모듈러 산술과 소수를 응용한 공개키-비밀키 방식을 구상하였다. 한편, MIT의 컴퓨터 과학자 Ron Rivest와 Adi Shamir, 그리고 수학자 Leonard Adleman은 수년간 비대칭 암호화 방식을 연구하고 있었다. Rivest와 Shamir가 암호화 방식을 제시하면 Adleman이 수학적으로 취약점을 찾는 방식으로 연구가 진행되었으며, 그 노력의 결과는 수를 곱하는 것은 간단하지만 그걸 다시 분해하는 것은 어렵다는 아주 간단한 수학적 사실을 기반으로한 암호 체계를 완성시키는 걸로 나타났다. 그들은 이 암호 체계의 이름을 자신들의 성을 딴 RSA로 지었고, 특허를 출원하게 된다.

그런데 1997년에 새로운 사실이 발표되는데, 1973년에 이미 영국의 수학자 Clifford Cocks가 RSA와 동일한 암호 체계를 만들었다는 것. 기밀 유지 때문에 그동안 공개되지 않았던 것일 뿐(...). 다만 당시에는 그 연산을 감당할만한 연산 능력을 지닌 컴퓨터가 너무 비쌌기 때문에 그냥 수학적인 사실로만 남았다. 적어도 공개적으로는...

어쨌든 이 RSA는 그 안전성이 인정받아 지금 이순간에도 수많은 웹사이트들이 이용하고 있으며, 양자 컴퓨터의 개발이 완료된다든가 소인수 분해의 새로운 알고리즘이 발견된다든가 하는 이변이 없으면 계속해서 쓰일 것이다.

과정

1. 커다란 서로 다른 두 소수 [math]\displaystyle{ p,q }[/math]를 준비한다. 큰의 기준은 100자리 ([math]\displaystyle{ 10^{100}\lt p,q\lt 100^{101} }[/math]).
2. 두 소수를 곱한 값인 [math]\displaystyle{ n=pq }[/math]를 계산한다.
3. [math]\displaystyle{ n }[/math]의 오일러 피 함수 값 [math]\displaystyle{ \phi\left(n\right) }[/math]을 계산한다. [math]\displaystyle{ n=pq }[/math]일 경우, [math]\displaystyle{ \phi\left(n\right)=\left(p-1\right)\left(q-1\right) }[/math]이다.
4. [math]\displaystyle{ \phi\left(n\right) }[/math]와 서로소인 수 [math]\displaystyle{ e }[/math]를 준비한다. 당연하지만 [math]\displaystyle{ e\neq1 }[/math]이어야 한다.
5. 이제 [math]\displaystyle{ ed\equiv1\pmod{\phi\left(n\right)} }[/math]를 만족시키는 [math]\displaystyle{ d }[/math]를 찾는다.
6. [math]\displaystyle{ n }[/math]과 [math]\displaystyle{ e }[/math]를 공개하고, [math]\displaystyle{ d }[/math]는 숨겨둔다. 앞의 두 값을 공개키라 부르며, 뒤의 값을 개인키라 부른다. [math]\displaystyle{ p, q, \phi\left(n\right) }[/math]은 유출되면 보안에 문제가 생기니 보통 파기한다.
7. 이제 평서문 [math]\displaystyle{ m }[/math]을 암호화하려면, [math]\displaystyle{ m^e\pmod n }[/math]을 계산하면 된다. 이 값을 [math]\displaystyle{ c }[/math]라 하자. 복호화하려면 [math]\displaystyle{ c^d\pmod n }[/math]을 계산하면 된다.

정수론을 좀 공부해본 사람이라면 알겠지만, 매우 간단하다. 수학 경시대회를 준비한 학생이라면 중학생이라도 이해할 수 있을 정도. 이 과정에서 문제가 될만한 부분은 큰 소수를 찾는 1번과 개인키를 만드는 5번, 그리고 큰 수의 지수 계산을 하는 7번 정도. 이 문제점들을 해결하는 방법을 포함해서, RSA의 자세한 원리를 아래에서 알아보자. 아래부터는 특별한 말이 없으면 [math]\displaystyle{ p,q }[/math]는 소수, [math]\displaystyle{ n=pq }[/math], [math]\displaystyle{ e }[/math]는 공개키, [math]\displaystyle{ d }[/math]는 개인키, [math]\displaystyle{ m }[/math]은 평서문, [math]\displaystyle{ c }[/math]는 암호문으로 가정한다.

원리

소수 찾기

안타깝게도, 100%의 확률로 소수를 찾는 방법은 에라토스테네스의 체를 제외하고는 아직 존재하지 않는다. 에라토스테네스의 체도 말이 좋아 방법이지, 실제로는 어떤 수를 무작정 나눠서 소인수를 찾는 노가다라는 것을 고려하면, 소수를 확실하게 찾는 방법은 없다고 해도 무방하다. 하지만 어떤 수가 소수가 아님을 보이는 것은 매우 간단한데, 페르마의 소정리 덕분. 페르마 소정리는 다음 명제를 가리킨다.

소수 [math]\displaystyle{ p }[/math]와 서로소인 임의의 [math]\displaystyle{ a }[/math]에 대해, [math]\displaystyle{ a^{p-1}\equiv1\pmod p }[/math]가 성립한다.

우리가 관심을 가져야 할 것은, 이 명제의 대우이다.

[math]\displaystyle{ n }[/math]과 서로소인 어떤 수 [math]\displaystyle{ a }[/math]에 대해, [math]\displaystyle{ a^{n-1}\not\equiv1\pmod n }[/math]이면 [math]\displaystyle{ n }[/math]은 소수가 아니다.

만약 [math]\displaystyle{ n }[/math]이 소수라면 페르마 소정리에 의해 [math]\displaystyle{ a^{n-1}\equiv1\pmod n }[/math]이어야 하는데, 아니라고 가정했으므로 모순. 따라서 [math]\displaystyle{ n }[/math]은 소수가 아니다.

여기서 [math]\displaystyle{ a }[/math]의 값으로는 보통 2, 3, 5 등을 사용한다. 수많은 수 중 단 하나만 걸려도 소수가 아님을 판별할 수 있고, 자릿수가 100개를 넘어가면 확률적으로 소수가 아닐 확률이 매우 크기 때문에 판별하는 속도는 극히 빠르다.

문제는 [math]\displaystyle{ a^{n-1}\equiv1\pmod n }[/math]인 경우. 페르마 소정리의 역은 성립하지 않기 때문에, 이것만으로는 [math]\displaystyle{ n }[/math]이 소수라고는 단언할 수 없다. 다만 이 경우에는 높은 확률로 [math]\displaystyle{ n }[/math]이 소수라고 추측할 수 있을 뿐. 만약 [math]\displaystyle{ n }[/math]과 서로소인 모든 [math]\displaystyle{ a }[/math]에 대해 [math]\displaystyle{ a^{n-1}\equiv1\pmod n }[/math]가 성립한다면, 매우 높은 확률로 [math]\displaystyle{ n }[/math]이 소수라고 추측할 수 있다. 물론 어느쪽이든, 그 수가 소수라는 보장은 없다. 하지만 확률적인 면에서는 소수라고 단정해도 크게 상관없기 때문에 그냥 쓴다(...). 매스매티카 같은 프로그램에서 소수를 찾는 원리도 바로 이것으로, 2, 3, 5같이 작은 몇 개의 수를 가지고 지수 계산을 해서 모듈러 값이 1인지 체크하고, 전부 1로 나오면 그냥 소수로 간주한다.

그럼 몇 번의 연산을 해야 소수 하나를 찾을 수 있는가 하는 의문이 들 수 있다. 소수는 무한히 많이 존재하지만, 소수의 분포는 수가 커질수록 줄어듦이 알려져 있다. 특히 자릿수가 100개를 넘어가면 소수의 분포는 매우 희박해져서 소수 하나를 찾는데 매우 많은 시간이 걸릴 것처럼 보인다. 하지만 소수 정리에 따르면, 자릿수가 100개인 두 소수 사이의 범위는 대략 [math]\displaystyle{ \ln{10^{100}}=100\ln{10}\approx230 }[/math]이라 230번 정도만 연산을 하면 된다. 손으로는 터무니 없이 오래 걸릴 계산이지만, 현대의 컴퓨터라면 1초도 안걸린다. 당장 매스매티카를 키고 NextPrime 명령어를 입력한 뒤 얼마나 걸리는지 체크해보라.

오일러 피 함수

오일러 피 함수란, 어떤 수보다 작은 자연수 중에서 그 수와 서로소인 자연수의 개수를 나타내는 함수이다. 정수론을 공부하지 않은 사람이라면 두 수가 서로소임을 보이기 위해 두 수를 소인수 분해하고 공약수가 있는지 찾아보는 방법을 사용할텐데, 실제로 이러면 함수 값 구하는데 터무니 없이 많은 시간이 걸린다(...).

두 수가 서로소라는 것은 두 수의 최대공약수가 1이라는 것과 동치이며, 두 수의 최대공약수는 유클리드 호제법을 이용해서 소인수분해 없이 매우 빠른 속도로 계산할 수 있다. 물론 [math]\displaystyle{ n }[/math]이 약 200자리의 수라는 것을 고려하면 유클리드 호제법도 오래 걸릴 것 같지만, RSA를 쓰는 사람 입장에서는 유클리드 호제법이고 뭐고 없이 [math]\displaystyle{ n=pq }[/math]임을 이용해서 함수값을 매우 쉽게 구할 수 있다. 그냥 [math]\displaystyle{ \left(p-1\right)\left(q-1\right) }[/math]를 계산하면 끝이기 때문. 자세한 수학적 이론을 살펴보자.

[math]\displaystyle{ p }[/math]가 소수라면, [math]\displaystyle{ \phi\left(p\right)=p-1 }[/math]임을 쉽게 알 수 있고, 이는 역도 성립하는 명제이다. 한편, 오일러 피 함수는 곱셈적 함수임이 알려져 있다. 즉, [math]\displaystyle{ \phi\left(n\right)=\phi\left(pq\right)=\phi\left(p\right)\phi\left(q\right)=\left(p-1\right)\left(q-1\right) }[/math]. 이를 일반화시키면, [math]\displaystyle{ n=\prod_{i=1}^k{p_i}^{e_i} }[/math]([math]\displaystyle{ p_i }[/math]는 서로 다른 소수, [math]\displaystyle{ e_i }[/math]는 1 이상의 자연수)에 대해 [math]\displaystyle{ \phi\left(n\right)=\prod_{i=1}^k\left(1-\frac{1}{p_i}\right) }[/math]임이 알려져 있다. 이 일반화에 대한 증명은 곱셈적 함수임을 이용하거나, 포함과 배제의 원리를 이용해서 증명할 수 있다.

어쨌든 RSA 사용자 입장에서 중요한 것은, [math]\displaystyle{ \phi\left(n\right) }[/math]의 계산이 간단하다는 것 뿐(...).

유클리드 호제법

[math]\displaystyle{ \phi\left(n\right) }[/math]도 찾았고 공개키로 쓸 [math]\displaystyle{ e }[/math]도 정했다고 가정하자. 문제는 개인키인 [math]\displaystyle{ d }[/math]를 찾는 과정이다. [math]\displaystyle{ d }[/math]는 [math]\displaystyle{ de\equiv1\pmod{\phi\left(n\right)} }[/math]를 만족해야 하는데, 수학적 직관이 있는 사람이 있는 사람이라면 저 합동식의 해가 존재하는지 의문을 가질 것이다. 일차 합동식 [math]\displaystyle{ ax\equiv b\pmod n }[/math]은 [math]\displaystyle{ \gcd\left(a,n\right)\mid b }[/math]여야 해가 존재하므로, 저 합동식의 해가 존재하려면 [math]\displaystyle{ \gcd\left(e,\phi\left(n\right)\right)\mid1 }[/math]이어야 한다. 이를 만족하려면 [math]\displaystyle{ \gcd\left(e,\phi\left(n\right)\right)=1 }[/math]이어야만 하고, 이는 [math]\displaystyle{ e }[/math]를 [math]\displaystyle{ \phi\left(n\right) }[/math]과 서로소인 수를 골라야하는 이유가 된다. 물론 [math]\displaystyle{ e=1 }[/math]이어도 조건은 만족하지만, 이러면 평서문과 암호문이 똑같아져서 암호화하는 이유가 없어진다(...). 가장 대중적으로 쓰이는 [math]\displaystyle{ e }[/math]값은 65537이며, 이 수는 소수이므로 [math]\displaystyle{ \phi\left(n\right) }[/math]의 값에 상관없이 쓸 수 있다는 장점이 있다. 사실 RSA 기본 설정에서 공개키는 저 값으로 되어 있고, 특별한 이유가 없으면 바꾸지 말라고 권고하고 있다. 구글을 비롯한 많은 웹 사이트가 저 값을 공개키로 사용하고 있으니 관심있으면 직접 체크해보자.

이제 [math]\displaystyle{ d }[/math]가 존재할 수 있음을 알았다. 그럼 이 값을 어떻게 찾을까? 바로 이 문단의 이름이기도 한 유클리드 호제법을 응용한다. 전 문단에서 유클리드 호제법을 이용해서 최대공약수를 구한다고 했는데, 거기서 조금 더 나아가면 [math]\displaystyle{ d }[/math]를 찾을 수 있다. 일단 유클리드 호제법이 뭔지 알아보자.

두 정수 [math]\displaystyle{ a,b }[/math]([math]\displaystyle{ a\gt b }[/math])에 대해, [math]\displaystyle{ b=aq+r }[/math]([math]\displaystyle{ 0\leq r\lt b }[/math])이라 하면, [math]\displaystyle{ \gcd\left(a,b\right)=\gcd\left(a,r\right) }[/math].

위 연산을 계속 반복하여 [math]\displaystyle{ r }[/math]에 해당하는 값이 0이 되면, 그 바로 전 단계의 나머지가 최대공약수가 된다.

자세한 예시를 통해 확인해보자.

23과 7의 최대공약수를 찾고 싶다고 하자. 위 알고리즘을 반복 적용하면,

[math]\displaystyle{ \begin{align*}23&=7\times3+2\\7&=2\times3+1\\2&=1\times2+0\end{align*} }[/math]

이 되고, 마지막 단계 바로 전의 나머지가 1이므로 두 수의 최대공약수는 1이다.

이제 여기서 조금 더 나아가 [math]\displaystyle{ 7x\equiv1\pmod{23} }[/math]을 만족하는 [math]\displaystyle{ x }[/math]를 찾아보자.

우선 저 합동식은 [math]\displaystyle{ 7x+23y=1 }[/math]과 동치이다. 한편, 유클리드 호제법에서,

[math]\displaystyle{ 1=7-2\times3=7-3\times(23-7\times3)=7-3\times23+9\times7=10\times7-3\times23 }[/math]

이므로, [math]\displaystyle{ x=10 }[/math]이다.

뭔가 복잡해보이지만, 유클리드 호제법으로 튀어나온 나머지를 재귀적으로 계속 거꾸로 대입해서 [math]\displaystyle{ \gcd\left(a,b\right)=ax+by }[/math]의 형태로 바꾸는 것 뿐이다. 즉, RSA의 경우에는 이 방법을 이용해 [math]\displaystyle{ ed+\phi\left(n\right)k=1 }[/math]를 만족하는 [math]\displaystyle{ d }[/math]를 찾을 수 있고, 그 값이 개인키가 된다.