RSA

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

역사

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

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]를 찾을 수 있고, 그 값이 개인키가 된다.

연산

공개키도 개인키도 전부 찾았으면 이제 평서문을 암호화할 차례. 암호화는 [math]\displaystyle{ m^e\pmod n }[/math]으로 계산하는데, 저렇게 터무니 없이 큰 수를 무슨 수로 계산하냐는 의문이 들 수도 있다. 공개키가 65537이라 가정하면, 영어 10글자 문장을 암호화하기 위해서는 최소 20자리 수를 65537 제곱해야 하고, 이 숫자는 터무니 없이 커서 저장하는데만 상당한 용량을 요구할 것 처럼 보인다. 하지만 이 연산은 일반적인 산술이 아니라 모듈러 산술이기 때문에 저장 공간을 많이 차지하지 않는데, 숫자가 [math]\displaystyle{ n }[/math]보다 커질 때마다 [math]\displaystyle{ n }[/math]으로 나눠서 나머지를 구하면 되기 때문이다. [math]\displaystyle{ n }[/math]이 200자리 숫자이면, 실제로 연산하는데 필요한 공간은 고작 2배인 400자리뿐.

두 번째 의문은 65537 제곱을 무슨 수로 빨리 하냐일 것이다. 이는 연속 제곱(Successive Squaring)이란 방법을 통해 해결 가능하다. 연속 제곱은 그냥 말그대로 어떤 수를 제곱하고, 그 결과를 다시 제곱하는 과정을 반복하는 것인데, 2진법의 원리를 아는 사람이라면 바로 감이 잡힐 것이다. 연속 제곱해서 나오는 중간 결과 값은 제곱해야 하는 수의 2진법 표현에 정확히 대응하고, 최종적으론 필요한 중간 결과값 끼리만 곱하면 된다. 17 제곱을 예로 들면, [math]\displaystyle{ 17=10001_{\left(2\right)} }[/math]이므로, 연속 제곱을 4번 하고 원래 수를 한 번만 곱해주면 끝. 공개키로 65537이 자주 쓰이는 이유도 여기서 기인하는데, 65537 제곱은 연속 제곱을 16번 하고 원래 수를 곱하면 끝이기 때문 ([math]\displaystyle{ 65537=2^{16}+1 }[/math]). 어떤 수를 65536번 곱하는 것에 비하면 확실히 빠르다.

이제 암호화된 문장 [math]\displaystyle{ c\equiv m^e\pmod n }[/math]을 가지고 있다고 가정하자. 이 문장을 복호화 하려면 [math]\displaystyle{ c^d\pmod n }[/math]을 계산해주면 되는데, 이는 오일러의 정리에 기반을 두고 있다. 오일러의 정리는 앞서 언급한 페르마의 소정리의 일반화된 버전으로, 자세한 명제는 다음과 같다.

[math]\displaystyle{ n }[/math]을 1보다 큰 자연수라고 하자. [math]\displaystyle{ n }[/math]과 서로소인 임의의 [math]\displaystyle{ a }[/math]에 대해, [math]\displaystyle{ a^{\phi\left(n\right)}\equiv1\pmod n }[/math]이 성립한다.

여기서 [math]\displaystyle{ \phi\left(n\right) }[/math]는 오일러 피 함수다.

이제, 복호화 과정을 수학적으로 살펴보자.

[math]\displaystyle{ c^d=\left(m^e\right)^d=m^{de}=m^{1+k\phi\left(n\right)}=m\cdot\left(m^{\phi\left(n\right)}\right)^k\equiv m\cdot1^k\equiv m\pmod n }[/math]

[math]\displaystyle{ de=1+k\phi\left(n\right) }[/math]인 이유는 바로 윗 문단을 참고하자.

보면 알겠지만, 암호문을 [math]\displaystyle{ d }[/math]제곱 해주는 것만으로 원래 문장으로 돌아온다.

안전성

앞서 말했지만, RSA의 안전성은 곱셈은 간단해도 소인수분해는 어렵다는 사실에 기반을 두고 있다. 이는 숫자가 커지면 커질수록 극대화 되는데, 상용으로 쓰이는 100자리 소수의 곱은 개인용 컴퓨터에서도 몇 초면 끝나지만, 그 반대인 200자리 숫자를 매스매티카나 MATLAB을 사용해서 소인수 분해를 시도하면 시스템이 순식간에 뻗을 것이다. 실제 사용되는 [math]\displaystyle{ n \gt 2^{2048} \simeq 10^{616.509} }[/math] 를 다시 소인수 분해하는데 걸리는 시간은 상상을 초월하며, 대충 우주가 멸망할 때 쯤 분해가 완료된다고 생각하면 된다. 물론 모든 경우에 대해 이렇게 오래 걸리는 것은 아니며, 특수한 경우에는 컴퓨터로 몇 초면 분해할 수 있다. 이에 대해서는 아래 공격 문단을 참고.

"소인수가 2개 밖에 없는 수를 분해하는데 이렇게 오래 걸리니, 소인수를 더 많이 쓰면 더 안전하겠군!" ← 이런 생각을 하는 사람이 분명 존재할텐데, 결과부터 말하면 틀렸다. 가장 간단한 소인수 분해 방법은 2번째로 작은 인수를 찾는 것인데, 이 방법으로 두 소인수의 곱을 분해하는데 걸리는 시간을 [math]\displaystyle{ T }[/math]라 하면, 세 소인수의 곱을 분해하는데 걸리는 시간은 [math]\displaystyle{ 2T }[/math]. 일반적인 [math]\displaystyle{ k }[/math] 소인수의 곱을 분해하는데 걸리는 시간은 [math]\displaystyle{ \left(k-1\right)T }[/math]이며, 소인수가 100자리 가량 되는 경우에는 [math]\displaystyle{ T }[/math]든 [math]\displaystyle{ 2T }[/math]든 별 차이가 없다. 오히려 큰 수를 더 많이 사용하기 때문에 용량과 속도면에서 뒤쳐지게 되고, 실용성이 떨어지게 되는 결과를 낳는다. 반대로 생각해서, 두 소인수의 곱을 분해하는데 걸리는 시간이 매우 짧은 알고리즘이 있으면, 일반적인 수를 소인수 분해는데 걸리는 시간 역시 매우 짧을 것이다. 결국 어느쪽이든, 여러 소인수를 사용하는 것이 더 안전하다고 말할 수 없다.

"소수는 무한할지라도 100자리 소수는 유한하니 그 소수들을 전부 기록하면 되겠군!" ← 이런 생각을 하는 사람도 분명 존재할텐데, 맞는 소리긴 하지만 저 많은 소수들을 전부 기록하려면 우주를 꽉 채워야 한다(...). 소수 정리에 따르면 [math]\displaystyle{ n }[/math] 이하의 소수의 개수는 [math]\displaystyle{ \frac{n}{\ln n} }[/math]에 근사하는데, 이를 이용하면 100자리 소수의 개수는 [math]\displaystyle{ \frac{10^{101}}{101\ln{101}}-\frac{10^{100}}{100\ln{100}}\approx3.87\times10^{98} }[/math]개 정도 된다. 현대 인간의 기술로는 저 많은 소수들을 다 기록할 방법이 없기 때문에 100자리 소수를 전부 기록한다는 발상은 통하지 않는다. 설녕 저 많은 소수를 다 기록할 수 있다고 해도 자릿수를 하나 더 늘려 버리면 끝(...).

일반인이 상상할 수 있는 범위에서 RSA의 안전성과 관련된 이슈는 이정도가 끝. 여기까지만 보면 RSA가 난공불략의 요새같지만, 그러면 RSA를 쓰는 많은 웹 사이트들이 털릴 이유가 없다. 잊을만 하면 웹 사이트 하나가 털렸다는 뉴스가 나오는 이유는 RSA가 완벽한 암호 체계가 아니기 때문. 이제 RSA를 뚫는 여러 가지 공격법에 대해 살펴보자. 코렁탕 마실 준비를 하자... 읍읍!!

공격

대중적으로 쓰이는 암호 체계인 만큼, 그 취약성과 공격 방법에 대해서도 많이 알려져 있다. 물론 보안 업체들도 그 취약성과 공격 방법에 대해 잘 알고 있으며, 그것을 방어하는 방법도 잘 알고 있으므로 일반인들은 RSA의 약점에 대해 크게 걱정할 필요가 없다...고들 얘기하지만, 사용자의 패턴에 따라서도 RSA를 뚫지 않고 특정 메시지를 복호화 하는 것이 가능하다. 개인 정보에 민감한 사람이라면 RSA 취약점에 대해 알아두어서 나쁠 것은 없다. 아래 리스트는 RSA를 공격할 수 있는 여러 방법들이다.

개인키 유출

공격 방법이라고 하기에는 뭐하지만, 비공개 키에 해당하는 [math]\displaystyle{ p,q,\phi\left(n\right),d }[/math] 중 단 하나라도 유출되면 나머지 모든 개인키를 취득할 수 있다. 편의상 [math]\displaystyle{ \phi\left(n\right)=\phi }[/math]라 하자.

1. [math]\displaystyle{ p }[/math] (또는 [math]\displaystyle{ q }[/math])

   소인수중 하나를 알고 있으므로, [math]\displaystyle{ n\div p }[/math]를 계산하여 나머지 소인수를 찾을 수 있다. 두 소인수를 알고 있으므로 [math]\displaystyle{ \phi }[/math]를 구할 수 있고, 유클리드 호제법을 사용해서 [math]\displaystyle{ d }[/math]를 구할 수 있다.

2. [math]\displaystyle{ \phi }[/math]

   [math]\displaystyle{ \phi=\left(p-1\right)\left(q-1\right)=pq-p-q+1=n-p-q+1 }[/math]이므로, [math]\displaystyle{ p+q=n-\phi+1 }[/math]. 또한, [math]\displaystyle{ pq=n }[/math]. 따라서, [math]\displaystyle{ p,q }[/math]는 이차 방정식 [math]\displaystyle{ x^2-\left(n-\phi+1\right)x+n=0 }[/math]의 두 근이다. 근의 공식을 이용하면, [math]\displaystyle{ p,q=\frac{\left(n-\phi+1\right)\pm\sqrt{\left(n-\phi+1\right)^2-4n}}{2} }[/math]. 한편, [math]\displaystyle{ d }[/math]는 유클리드 호제법을 이용하면 된다.

3. [math]\displaystyle{ d }[/math]: 두 가지 방법이 알려져 있다.
   1. [math]\displaystyle{ r=de-1 }[/math]이라 하자. 그럼, 적당한 홀수 [math]\displaystyle{ m }[/math]에 대해 [math]\displaystyle{ r=2^km }[/math]로 나타낼 수 있다. 이제 적당한 [math]\displaystyle{ a }[/math]에 대해, [math]\displaystyle{ b_0\equiv a^m\pmod n }[/math]이라 하자. 이제 [math]\displaystyle{ b_0 }[/math]을 연속 제곱하여 [math]\displaystyle{ b_{u+1}\equiv{b_u}^2\pmod n }[/math]를 1이 나올 때까지 구한다. [math]\displaystyle{ k }[/math]번 연속 제곱하면 반드시 1이 나오게 되어 있으므로 1이 나오지 않을 염려는 할 필요 없다 (이유는 직접 생각해보자). 만약 1이 나오지 않았다면 [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ n }[/math]이 서로소가 아니라는 뜻이므로, [math]\displaystyle{ n }[/math]의 인수를 찾은 셈. 만약 [math]\displaystyle{ b_{u+1}\equiv1\pmod n }[/math]이고, [math]\displaystyle{ b_u\equiv-1\pmod n }[/math]이면, [math]\displaystyle{ a }[/math]의 값을 바꿔 다시 시도한다. 만약 [math]\displaystyle{ b_{u+1}\equiv1\pmod n }[/math]이고 [math]\displaystyle{ b_u\not\equiv\pm1\pmod n }[/math]이면, [math]\displaystyle{ \gcd\left(b_u-1,n\right) }[/math]가 [math]\displaystyle{ n }[/math]의 한 인수가 된다. [math]\displaystyle{ n }[/math]의 한 인수를 찾았으므로 나머지 인수를 쉽게 찾을 수 있고, [math]\displaystyle{ \phi }[/math]도 쉽게 찾을 수 있다.
   2. [math]\displaystyle{ de=1+k\phi }[/math]에서, [math]\displaystyle{ k }[/math]를 찾을 수 있다면 [math]\displaystyle{ \phi }[/math]를 찾을 수 있다. 우선 양변을 [math]\displaystyle{ n }[/math]으로 나누면, [math]\displaystyle{ \frac{de}{n}=\frac{1}{n}+k\frac{\phi}{n} }[/math]인데, [math]\displaystyle{ n }[/math]이 200자리 숫자고 소인수가 2개밖에 없으므로, [math]\displaystyle{ \phi\approx n }[/math]이다. 즉, [math]\displaystyle{ \frac{de}{n}\approx k }[/math]. 이제 [math]\displaystyle{ k }[/math]를 찾았으므로 [math]\displaystyle{ \phi }[/math]를 계산할 수 있고, [math]\displaystyle{ \phi }[/math]를 알고 있으므로 [math]\displaystyle{ n }[/math]의 두 소인수를 찾을 수 있다.

RSA 암호화 과정에서 [math]\displaystyle{ p,q,\phi }[/math]를 파기한다고 되어있는데, 실제 복호화에 필요한 것은 [math]\displaystyle{ d }[/math]뿐이고, 나머지 값은 유출되면 위 서술한 방법으로 [math]\displaystyle{ d }[/math]를 찾는 것이 가능해 놔두면 위험하기 때문이다. 한편, [math]\displaystyle{ d }[/math]를 알고 있는데 왜 굳이 소인수 분해를 시도하냐고 생각할 수 있는데, RSA에서 사용하는 소수는 완전한 랜덤이 아니기 때문이다. 인간의 기술로는 완벽한 난수를 생성해낼 방법이 없으며, 뒤에 복잡한 계산식이 있는데, 결과물이 많을 수록 그 뒤의 계산식을 유추하는데 도움이 되기 때문이다. 과거 ARPANET을 사용하던 때 위성 시간을 이용해서 난수 키를 생성했던 경우가 있었는데, 시간 별로 생성된 난수키를 분석한 어떤 사람이 취약점을 발견해서 결국 난수 생성 함수가 수정된 전적이 존재한다(...). RSA에서 사용하는 소수도 언젠가는 생성 방식이 밝혀질 수도 있다는 것을 알아두자.

유사 소수

유사 소수(Pseudo-prime)란, 어떤 수에 대해 페르마의 소정리가 성립해서 소수처럼 보이는 수를 말한다. 좀 더 자세히 말하면, 서로소인 두 수 [math]\displaystyle{ n }[/math]과 [math]\displaystyle{ a }[/math]에 대해, [math]\displaystyle{ a^{n-1}\equiv1\pmod n }[/math]이 성립하면, [math]\displaystyle{ n }[/math]를 [math]\displaystyle{ a }[/math]에 관한 유사 소수(Pseudo-prime Base a)라 부른다. 만약 [math]\displaystyle{ n }[/math]이 [math]\displaystyle{ n }[/math]과 서로소인 모든 [math]\displaystyle{ a }[/math]에 관해 유사 소수라면, [math]\displaystyle{ n }[/math]을 카마이클 숫자(Carmichael Number)라 부른다. 유사 소수와 카마이클 숫자는 매우 희귀하지만, 무한히 많음이 알려져 있다. 문제는, 어떤 수가 유사 소수면 그 수를 소인수 분해하는 있는 방법이 알려져 있다는 것. 이를 밀러-라빈 알고리즘(Miller-Rabin Algorithm)이라 부르며, 자세한 방법은 다음과 같다.

[math]\displaystyle{ n }[/math]을 1보다 큰 홀수라 하자. 그럼, 적당한 홀수 [math]\displaystyle{ m }[/math]에 대해 [math]\displaystyle{ n-1=2^km }[/math]로 나타낼 수 있다. 이제 적당한 정수 [math]\displaystyle{ a }[/math]를 고르고, [math]\displaystyle{ b_0\equiv a^m\pmod n }[/math]이라 하자. 이제, 연속 제곱으로 [math]\displaystyle{ b_{u+1}\equiv {b_u}^2\pmod n }[/math]을 1이 나올 때까지 반복한다. 연속 제곱을 [math]\displaystyle{ k }[/math]번 하면 반드시 1이 나오게 되어있는데, 만약 1이 나오지 않았다면 [math]\displaystyle{ a }[/math]가 [math]\displaystyle{ n }[/math]과 서로소가 아니라는 뜻이므로 인수를 하나 찾은 것이다. 만약, [math]\displaystyle{ b_{u+1}\equiv1\pmod n }[/math]이고, [math]\displaystyle{ b_u\equiv\pm1\pmod n }[/math]이면, [math]\displaystyle{ a }[/math]를 바꿔 다시 시도한다. 만약 [math]\displaystyle{ b_{u+1}\equiv1\pmod n }[/math]이고 [math]\displaystyle{ b_u\not\equiv\pm1\pmod n }[/math]이면, [math]\displaystyle{ \gcd\left(b_u-1,n\right) }[/math]이 [math]\displaystyle{ n }[/math]의 한 인수이다.

보면 알겠지만, 바로 위에서 [math]\displaystyle{ d }[/math]가 유출 되었을 때 [math]\displaystyle{ p,q }[/math]를 찾는 방법과 동일한 방법이다. 구체적인 예시를 통해 유사 소수가 어떻게 소인수 분해 되는지 확인보자.

561을 소인수 분해 하고 싶다고 가정하자. 참고로 561은 2에 관한 유사 소수이다 ([math]\displaystyle{ 2^{560}\equiv1\pmod{561} }[/math]). 이제 [math]\displaystyle{ 561-1=560=2^{4}\cdot35 }[/math]이므로, [math]\displaystyle{ m=35 }[/math]이다. [math]\displaystyle{ a=2 }[/math]에 대해, [math]\displaystyle{ b_0\equiv a^m\equiv2^{35}\equiv263\pmod{561} }[/math]이고, 연속 제곱으로 계속 값을 구하면, [math]\displaystyle{ b_1\equiv166\pmod{561},b_2\equiv67\pmod{561},b_3\equiv1\pmod{561} }[/math]이다. 1이 튀어나왔으므로, 그 바로 전 수인 67을 살펴보자. [math]\displaystyle{ 67\not\equiv\pm1\pmod{561} }[/math]이므로, [math]\displaystyle{ \gcd\left(67-1,561\right)=33 }[/math]이 561의 한 인수이다.

보면 알겠지만, 컴퓨터를 사용하면 유사 소수를 소인수 분해하는데 오랜 시간이 걸리지 않는다. 이는 곧 RSA에서 사용할 공개키 [math]\displaystyle{ n }[/math]이 유사 소수면 털리게 될 것이라는 것을 의미한다. 카마이클 숫자면 더더욱(...).

p-1 공격

이와 관련한 내용은 폴라드 p-1 소인수분해법에서 볼 수 있습니다.

[math]\displaystyle{ p }[/math]를 직접 찾는게 어려우면, [math]\displaystyle{ p-1 }[/math]를 이용하는 것이 어떨까? [math]\displaystyle{ p }[/math]가 큰 소수면, [math]\displaystyle{ p-1 }[/math]은 필연적으로 짝수인 합성수이기 때문에 여러 작은 소인수들을 가질 것이고, 그 작은 소인수들을 전부 포함시킬 수 있다면 [math]\displaystyle{ p-1 }[/math]을 찾을 수 있을 것이고, 이어서 [math]\displaystyle{ p }[/math]를 찾을 수 있을 것이다. 이 아이디어를 이용한게 [math]\displaystyle{ p-1 }[/math] 공격이며, 자세한 방법은 다음과 같다.

1보다 큰 적당한 자연수 [math]\displaystyle{ a }[/math]를 고른다. 보통 2를 사용한다. 이제 상한 [math]\displaystyle{ B }[/math]를 정한다. 이제, [math]\displaystyle{ b\equiv a^{B!}\pmod n }[/math]을 다음과 같이 재귀적으로 계산한다.

[math]\displaystyle{ b_1\equiv a\pmod n }[/math], [math]\displaystyle{ b_k\equiv{b_{k-1}}^k\pmod n }[/math]

그럼 [math]\displaystyle{ b_B\equiv b\pmod n }[/math]이 된다. 이제, [math]\displaystyle{ d=\gcd\left(b-1,n\right) }[/math]을 계산한다. 만약 [math]\displaystyle{ 1\lt d\lt n }[/math]이면, [math]\displaystyle{ d }[/math]가 한 소인수이다.

원리는 페르마의 소정리와 [math]\displaystyle{ p-1 }[/math]의 소인수에 있다. 만약 [math]\displaystyle{ p-1 }[/math]이 작은 소인수만을 가지고 있으면, 적당히 큰 [math]\displaystyle{ B }[/math]에 대해 [math]\displaystyle{ \left(p-1\right)\mid B! }[/math]일 것이다 ([math]\displaystyle{ B! }[/math]은 [math]\displaystyle{ B }[/math]보다 작은 모든 소인수를 약수로 가지고 있다). 그러면 [math]\displaystyle{ B!=\left(p-1\right)k }[/math]로 쓸 수 있을 것이고, 페르마 소정리에 의해 [math]\displaystyle{ b\equiv a^{B!}\equiv a^{\left(p-1\right)k}\equiv\left(a^{p-1}\right)^k\equiv1^k\equiv1\pmod p }[/math]가 된다. 즉, [math]\displaystyle{ p\mid\left(b-1\right) }[/math]. 곧, [math]\displaystyle{ b-1 }[/math]과 [math]\displaystyle{ n }[/math]은 [math]\displaystyle{ p }[/math]를 공약수로 가지게 되는 것이다. 여기서 주의할 점은 [math]\displaystyle{ B }[/math]가 너무 커서는 안 된다는 것이다. [math]\displaystyle{ B }[/math]가 너무 크게 되면 [math]\displaystyle{ p,q\mid\left(b-1\right) }[/math]이 되고, [math]\displaystyle{ \gcd\left(b-1,n\right)=n }[/math] 또는 1이 되어 아무런 정보도 얻지 못하기 때문. 구체적인 예시를 한 번 들어보자.

1357을 소인수 분해 하고 싶다고 하자. 상한을 [math]\displaystyle{ B=15 }[/math]로 정하고, [math]\displaystyle{ b\equiv2^{B!}\pmod{1357} }[/math]을 구하면, 300이 나온다. 이제, 300-1=299와 1357의 최대공약수를 구하면, 23이 튀어나오고, 1357=23×59임을 쉽게 알 수 있다. 이는 23-1=22의 가장 큰 소인수가 11이고, 15!에 포함되기 때문에 가능한 결과이다. 만약 상한을 [math]\displaystyle{ B=30 }[/math]으로 정했다면, [math]\displaystyle{ \gcd\left(b,1357\right)=1 }[/math]이 되어 아무런 정보도 얻지 못한다.

그럼 어떤 소수를 써야 [math]\displaystyle{ p-1 }[/math] 공격에서 자유로울까? 이는 [math]\displaystyle{ p-1 }[/math]과 [math]\displaystyle{ q-1 }[/math]이 둘 다 큰 소인수를 가지게 하는 것으로 해결된다. 여기서 큰 소인수의 기준은 약 40자리. 문제는 [math]\displaystyle{ p-1 }[/math]이 40자리의 큰 소인수를 가지게 하면서 동시에 [math]\displaystyle{ p }[/math]를 소수로 만드는 방법일 것이다. 다행히 이 조건을 만족하는 소수 [math]\displaystyle{ p }[/math]는 무한히 많다. 이를 디레클레 정리라고 하며, 더 정확한 명제는 다음과 같다.

[math]\displaystyle{ a,d }[/math]를 서로소인 두 정수라 가정하자. 그럼, 수열 [math]\displaystyle{ \left\{a+nd\right\}_{n=0}^\infty }[/math]은 무한히 많은 소수를 포함한다.

여기서 [math]\displaystyle{ a=1 }[/math]이고, [math]\displaystyle{ d }[/math]를 40자리의 어떤 큰 소수라 가정하면, 디레클레 정리에 의해 [math]\displaystyle{ 1+nd }[/math] 꼴의 소수를 무한히 만들 수 있고, 그 중에서 100자리 정도 되는 소수를 찾기만 하면 된다. 그 소수를 [math]\displaystyle{ p }[/math]라 하면 [math]\displaystyle{ p-1=nd }[/math]이므로, [math]\displaystyle{ p-1 }[/math]은 40자리의 큰 소인수를 가져 [math]\displaystyle{ p-1 }[/math] 공격에서 안전해지게 된다. 물론 [math]\displaystyle{ q }[/math]도 비슷한 방식으로 생성해야 한다.

이차 체

이와 관련한 내용은 이차 체에서 볼 수 있습니다.

이차 체(Quadratic Sieve)는 합동식의 간단한 성질을 이용해서 소인수를 찾는 방법이다. 기본 원리는 다음 명제를 바탕으로 한다.

적당한 두 정수 [math]\displaystyle{ x,y }[/math]에 대해 [math]\displaystyle{ x^2\equiv y^2\pmod n }[/math]이고 [math]\displaystyle{ x\not\equiv\pm y\pmod n }[/math]이라 가정하자. 그럼 [math]\displaystyle{ \gcd\left(x-y,n\right) }[/math]은 [math]\displaystyle{ n }[/math]의 인수이다.

증명은 간단하다.

[math]\displaystyle{ x^2\equiv y^2\pmod n }[/math]이므로, [math]\displaystyle{ n\mid\left(x^2-y^2\right)=\left(x-y\right)\left(x+y\right) }[/math]이다. 그런데 [math]\displaystyle{ x\not\equiv\pm y\pmod n }[/math]이므로, [math]\displaystyle{ n\not\mid\left(x+y\right),n\not\mid\left(x-y\right) }[/math]이다. 결국 이를 만족하려면 [math]\displaystyle{ n }[/math]의 적당한 소인수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ p\mid n }[/math]이고 [math]\displaystyle{ p\mid\left(x-y\right) }[/math]이어야 함을 의미한다.

간단한 예시를 들어보자.

670726081을 소인수 분해하고 싶다고 하자. 그런데 마침 [math]\displaystyle{ 33335^2\equiv{670705093}^2\pmod{670726081} }[/math]이다. 분명히 [math]\displaystyle{ 33335\not\equiv670705093\pmod{670726081} }[/math]이므로, [math]\displaystyle{ \gcd\left(670705093-33335,670726081\right)=54323 }[/math]이 한 인수이다 (체크해보면 알겠지만 소인수이다). 나머지 소인수는 12347임을 쉽게 알 수 있다.

한편, [math]\displaystyle{ 3^2\equiv{670726078}^2\pmod{670726081} }[/math]인데, [math]\displaystyle{ 3\equiv-670726078\pmod{670726081} }[/math]라서 여기선 아무런 정보도 얻을 수 없다.

문제는 이 조건을 만족하는 두 정수를 어떻게 찾냐일텐데, 자세한 내용은 이차 체 문서에 소개되어 있다.

부분 취득

[math]\displaystyle{ p }[/math] 전체를 알지는 못해도, 그 일부분을 알 수 있다면 어떨까? [math]\displaystyle{ p }[/math]의 자릿수를 [math]\displaystyle{ m }[/math]이라 할 때, 앞 [math]\displaystyle{ m/4 }[/math]이나 뒤 [math]\displaystyle{ m/4 }[/math]자리를 알고 있다면 [math]\displaystyle{ n }[/math]을 빠르게 소인수 분해할 수 있음이 알려져 있다. 여기서 조금 더 발전하여, RSA의 개인키 [math]\displaystyle{ d }[/math]의 자릿수를 [math]\displaystyle{ m }[/math]이라 했을 때, 끝 [math]\displaystyle{ m/4 }[/math]자리를 알고 있으면 [math]\displaystyle{ d }[/math]를 [math]\displaystyle{ e\log_2e }[/math]에 관한 선형 시간내에 찾을 수 있음이 알려져 있다. 일반인들을 위해 간단히 설명하면, 개인키의 일부분만 찾을 수 있어도 RSA를 털 수 있다는 뜻이다.

다만, 그 일부분을 찾는 것은 절대 쉽지 않고, 특별한 경우에만 빠르게 찾을 수 있다. 그 중에서도 가장 위험한 케이스는 두 소인수 [math]\displaystyle{ p,q }[/math]의 값이 크게 차이나지 않을 때. 만약 두 소인수의 값이 비슷하면, [math]\displaystyle{ p\approx\sqrt{n}\approx q }[/math]가 되고, [math]\displaystyle{ \sqrt{n} }[/math]의 값을 구하는 것은 매우 빠르기 때문에 [math]\displaystyle{ p }[/math]의 앞 자릿수를 근사하게 유추할 수 있다. 다행히 두 소인수의 차이를 크게 벌리는 것으로 이 방법은 쉽게 막힌다.

낮은 지수 공격

낮은 지수 공격(Low Exponent Attack)은 공개키 [math]\displaystyle{ e }[/math]의 값이 작을 때 사용할 수 있는 방법이다. 지수가 작으면 암호화하는데 시간이 짧게 걸려 효율성이 좋아지지만, 안타깝게도 빠르게 뚫는 방법이 알려져 있다. 자세한 명제는 다음과 같다.

[math]\displaystyle{ q\lt p\lt 2q }[/math]라 하자. 만약 [math]\displaystyle{ d\lt \frac{1}{3}n^{1/4} }[/math]이면, [math]\displaystyle{ d }[/math]를 [math]\displaystyle{ \log_2n }[/math]에 관한 다항식 시간 내에 찾을 수 있다.

RSA에서 [math]\displaystyle{ e }[/math]의 값으로는 보통 3과 65537을 사용했는데, 컴퓨터가 좋아짐에 따라 낮은 지수 공격을 효율적으로 행할 수 있게 되어 3은 더이상 쓰이지 않게 되었다.

짧은 평서문

"지수를 작게 만들 수 없다면 평서문을 짧게 만들면 되지!"라는 발상에서 나온 공격법. 방법은 매우 간단하다.

1. 짧은 평서문을 준비한다.
2. 공개키를 이용해서 암호화한다.
3. 암호문을 계속 거듭제곱하여 평서문이 나오길 바란다(...).
4. 평서문이 튀어나오면 [math]\displaystyle{ d }[/math]를 찾았다는 소리이므로 RSA를 뚫을 수 있다.

매우 간단하고 원시적인 방법이지만, [math]\displaystyle{ n }[/math]의 값이 작으면 빠른 시간내에 돌파가 가능하다. 근데 그 짧다는게 대충 17자리 정도(56bit). 현대에는 200자리 [math]\displaystyle{ n }[/math]을 사용하기 때문에 사실상 사용 불가능한 방법이다. 물론, 컴퓨터가 좋아짐에 따라 연산 속도가 계속 빨라지고 있기 때문에, 영원히 사용 불가능하진 않다. 다만 시간과 고성능 컴퓨터가 필요할 뿐.

타이밍 공격

1995년에 스탠포드 대학교의 학부생이었던 Paul Kocher에 의해 발견된 방법. 복호화하는데 걸리는 시간을 측정하여 복호화 지수(=[math]\displaystyle{ d }[/math])를 추측할 수 있다는 것이 기본 내용이며, 수학적인 이론이 아니라 연산에 걸리는 시간의 차이를 이용해서 RSA를 뚫는 일종의 편법이다. 이 학생이 쓴 논문은 여기서 확인할 수 있다 (영어).

다중 공개키 취득

한 공개키 [math]\displaystyle{ \left(n,e\right) }[/math]로 뚫을 수 없다면 여러 공개키를 이용할 수도 있다. 두 공개키 쌍을 [math]\displaystyle{ \left(n_1,e_1\right),\left(n_2,e_2\right) }[/math]라 하자.

• [math]\displaystyle{ n_1 }[/math]과 [math]\displaystyle{ n_2 }[/math]가 서로소가 아닌 경우

  유클리드 호제법으로 두 공개키의 소인수를 찾을 수 있으므로, 두 RSA 체계를 동시에 뚫을 수 있다. 다만 100자리 소수의 수를 생각해보면 이런 일이 벌어질 가능성은 매우 희박하다.

• [math]\displaystyle{ n_1=n_2 }[/math]인데, [math]\displaystyle{ e_1 }[/math]과 [math]\displaystyle{ e_2 }[/math]가 서로소인 경우

  조금 특수한 경우이긴 한데, 한 사람이 동일한 평서문 [math]\displaystyle{ m }[/math]을 두 공개키를 이용해 암호화하고, 그 두 암호문을 취득할 수 있다면 개인키를 찾지 않고서도 평서문을 복구할 수 있다. 우선, [math]\displaystyle{ n_1=n_2=n,\;\;c_1\equiv m^{e_1}\pmod n\;\;c_2\equiv m^{e_2}\pmod n }[/math]이라 가정하자. [math]\displaystyle{ e_1 }[/math]과 [math]\displaystyle{ e_2 }[/math]가 서로소이므로, 유클리드 호제법을 이용해서 [math]\displaystyle{ e_1x+e_2y=1 }[/math]을 만족하는 정수 [math]\displaystyle{ x,y }[/math]를 찾을 수 있다. 그러면 [math]\displaystyle{ {c_1}^x{c_2}^y\equiv m^{e_1x+e_2y}\equiv m^1\equiv m\pmod n }[/math]이 되어 평서문이 복구된다.

  이런 공격법을 어디서 써먹냐고 할 수 있는데, 이 방법 때문에 공개키를 65537에서 바꾸지 말라고 권고하는 것이다. 같은 보안 업체의 RSA 체계를 사용하면 여러 사이트에서 [math]\displaystyle{ n }[/math]이 같은 경우가 분명히 존재하는데, 공개키를 바꿔버리면? 게다가 한 사용자가 여러 사이트에서 같은 아이디와 비밀번호를 사용한다면? 이런 경우가 바로 이 특수한 경우에 맞아 떨어지게 되는 것이다. 비슷한 계열의 사이트, 특히 SNS에서는 대부분의 사람이 같은 아이디와 같은 비밀번호를 사용하는데, 이는 평서문이 똑같다는 것을 의미하고, 정말 우연히 저 조건이 맞아떨어지게 되면 당신의 타임라인이 ♚♚히어로즈 오브 더 스☆톰♚♚로 도배되는 것이다(...). 저~ 위에서 말했던 사용자의 패턴에 따른 공격법이 바로 이 경우. 보안에 정말 신경쓰는 사람이라면, 비슷한 계열의 사이트에서는 서로 다른 아이디와 비밀번호를 사용하도록 하자. 그나마 위안인 점은 이런 경우 자체가 거의 발생하지 않는다는 것.

  흔히 보안을 위해 귀찮더라도 로그인, 로그아웃을 매번 하라고 하는데, 일부는 맞고 일부는 틀린 내용이다. 로그인을 반복하면 똑같은 평서문을 반복해서 보낸다는 뜻이고, 재수가 없으면 위 특수한 조건에 맞아 떨어지게 되고, 더 재수가 없으면 당신의 개인 정보를 매의 눈으로 노리고 있는 대륙의 해커들이 그 순간을 캐치해 해킹에 성공하게 된다. 다만 현실적으로 보면 로그인, 로그아웃을 매번 하는 것이 더 안전한데, 당신의 컴퓨터나 핸드폰이 물리적으로 강탈당할 가능성이 더 높기 때문(...). 제일 좋은 방법은 매번 로그인, 로그아웃을 하고, 비밀번호를 정기적으로 바꾸는 것이다.

기타 방법

1. 돈지랄을 해서 고성능 컴퓨터를 여러대 구입하고, 병렬 연산으로 무작정 나눈다(...)
2. 큰 소수를 고르고 나누어떨어지길 빈다(.....)
3. 보안 업체 직원이 된다(........)
4. 보안 업체를 물리적으로 턴다(..........)
5. 털고자하는 사람을 관찰해 아이디와 비밀번호를 훔쳐본다(..........)

뭔가 전부 농담같지만, 위 방법들이 가장 현실적이고 가장 실현 가능성이 높은 방법이다. 특히 5번. 남이 자기 모니터와 키보드를 쳐다보지 못하게 가드를 철저히 하도록 하자. 키로그를 해킹이 5번에 가장 가까운 방법으로 어떤 키보드를 눌렀는지 해커에게 전송하면 사실상 모니터와 키보드에 카메라를 설치한 것과 마찬가지 효과가 난다.

결론

안전한 RSA를 사용하려면, 위 공격법들을 하나씩 방어하면 된다. 즉,

1. [math]\displaystyle{ p,q,\phi }[/math]를 파기하고,
2. [math]\displaystyle{ n }[/math]이 유사 소수인지 체크하고,
3. [math]\displaystyle{ p-1,q-1 }[/math]이 큰 소인수를 갖는지 체크하고,
4. 이차잉여에서 안전한지 체크하고,
5. 두 소인수의 차이를 크게하고,
6. 개인키의 그 어느 일부분이라도 노출되지 않게 하고,
7. [math]\displaystyle{ e }[/math]값을 적당히 크게 하고,
8. [math]\displaystyle{ n }[/math]값도 적당히 크게 하고,
9. 복호화하는 하드웨어에 대한 접근도 강화하고,
10. RSA를 사용하는 다른 웹 사이트들의 공개키와 서로소인지 체크하고,
11. 만약 [math]\displaystyle{ n }[/math]값이 같다면 [math]\displaystyle{ e }[/math]값이 서로소인지 체크까지

하면 된다. 참 쉽죠?

물론 제일 중요한 것은 사용자 자신의 패턴임을 잊지 말자. 세상에 완전한 암호 체계는 없다.

RSA가 뚫리면?

RSA가 뚫린다고 해서 크게 걱정할 필요는 없다. RSA를 대체할 공개키 암호화 방식은 많이 개발되었으며, 그 중 가장 잘 알려진 것이 타원곡선 암호화 방식(Elliptic Curve Cryptosystem, ECC). 다만 ECC는 RSA와 다르게 기본 내용을 이해하는데만 석사 레벨의 정수론 지식이 필요하다는 단점이 있다.

하지만 어느쪽이든 양자 컴퓨터의 시대가 도래하면 끝난다(...). RSA를 다항식 시간 내에 분해하는 양자 알고리즘은 이미 1994년에 발견되었으며, 현대의 입지와는 다르게 양자 컴퓨터에선 ECC가 RSA보다 먼저 뚫릴 것으로 추측되고 있다. 관심있는 사람은 Wikipedia:Shor's algorithm을 읽어보자 (영어).

그럼 양자 컴퓨터 시대가 오면 암호는 다 박살나냐는 생각을 할 수 있는데, 양자 컴퓨터에서 안전한 암호 체계 역시 많이 연구되었다. 역시 관심있는 사람은 Wikipedia:Post-quantum cryptography 참고 (영어).

기타

RSA를 비롯한 공개키 암호화 방식을 사용하는 웹 사이트의 공개키는 쉽게 확인할 수 있다. 우선 아무데서나 마우스 오른쪽 클릭을 하고, 페이지 정보를 확인한다. 보안 탭에 들어가 인증서 보기를 클릭하면, 해당 보안 업체의 인증서를 볼 수 있는데, 세부 항목의 공개키 정보에서 암호화 방식과 공개키를 확인할 수 있다. 용량 절약을 위해 공개키는 보통 16진법으로 표시되어 있다. 리브레 위키의 보안 정보를 보면 클라우드 플레어의 ECC를 사용하고 있다는 것을 알 수 있다.

같이 보기

• 정수론

  소인수분해

  모듈러 산술

  페르마의 소정리 - 오일러의 정리

  오일러 피 함수

• 공개키 암호화 방식

  타원곡선 암호화 방식

• 양자 컴퓨터