RSA 암호화
1. 개요
현재 SSL/TLS에 가장 많이 사용되는 공개키 암호화 알고리즘이다. 현재 나무위키도 HTTPS에 RSA-2048 인증서를 사용하고 있으며, 전세계 대부분의 인터넷 뱅킹(대한민국 포함)이 이 RSA-2048 암호화를 사용한다. 지금 GPG는 RSA-4096으로 키를 암호화 하지만...
'''암호화할 때에는 마음대로였겠지만 해독할 때에는 아니란다'''를 기본 모토로 한 공개키 암호체계 중 하나이다.[1] 공개키와 개인키가 한 쌍을 이루며, 공개키로 암호화한 내용은 개인키로만, 개인키로 암호화한 내용은 공개키로만 해독할 수 있다.[2] 엄청 큰 숫자는 소인수분해하기가 힘들다는 것을 이용한다. 1977년[3] 이 체제를 개발한 Ron '''R'''ivest, Adi '''S'''hamir, Leonard '''A'''dleman 세 사람의 성을 따서 RSA 라고 이름이 붙은 암호 방식이다.
참고로 맞춤법에 대해 '''공개 키'''라고 쓰는 것이 더 적절하다. 다만 이 단어는 '''공개키'''라는 단어 자체도 전공자들 사이에서는 많이 쓰이기 때문에 여러 문서의 제목이 '''공개키'''로 되어 있다. '''비대칭형키'''로 기억하면 좀더 직관적으로 내용을 받아들일 수 있다.
2. 과정
RSA 방식으로 암호화를 하기 위해선 먼저 키를 만들어야 한다. 그 과정은 다음과 같다.
- 두 소수 $$ p , q $$ 를 준비한다.[4]
- $$ p - 1,\ q - 1 $$과 각각 서로소인 정수 $$e$$[5]를 준비한다.[6]
- $$ed$$를 $$(p - 1)(q - 1)$$으로 나눈 나머지가 1이 되도록 하는 $$d$$[7]를 찾는다.[8][9]
- $$N = pq$$를 계산한 후, $$N$$과 $$e$$를 공개한다. 이들이 바로 공개키이다. 한편 $$d$$는 숨겨두는데, 이 수가 바로 개인키이다.
- 이제 $$p, q, (p-1)(q-1)$$는 필요 없거니와 있어 봐야 보안에 오히려 문제를 일으킬 수 있으니, 파기한다.
한편 소수 $$p$$와 $$q$$를 구하는 과정은 여전히 완전한 방법이 없다고 봐야 한다. 일단 에라토스테네스의 체를 이용한 방식을 생각해 볼 수 있는데, $$\sqrt{p}$$보다 작은 소수들 모두로 나눠 봐야 알 수 있다는 점에서 이 방법은 현실적으로 불가능한 방법이다. 그래서 대신에 확률적으로 소수인지 아닌지를 판별하는 방법을 쓴다. 기본적으로 쓰는 방식이 아래에 소개할 페르마 소정리를 근거로 한 것인데, 이 정리의 대우명제인 '임의의 정수 $$a$$에 대해 $$a^{p - 1}$$를 $$p$$로 나눈 나머지가 1이 아니면 $$p$$는 소수가 아니다'라는 사실을 이용한 것이다. 이 방법을 쓰면 상당 확률로 소수를 걸러낼 수 있다고 한다. 하지만 물론 완전하진 않으며 이 때문에 다른 소수 판정법을 같이 쓰기도 한다.
공개키를 이용해 RSA 방식으로 암호화를 하는 과정은 다음과 같다.
예를 들어 앨리스가 공개키를 만들어 뿌렸고, 밥이 앨리스한테 메세지를 비밀리에 주고 싶다고 하자.[12] 밥은 앨리스의 공개키를 통해 암호화된 내용($$x$$)를 앨리스한테 준다. 그러면 앨리스는 자신이 가지고 있는 개인키를 이용해 원래 평서문을 얻을 수 있다. RSA 방식으로 암호화를 하는 과정은 다음과 같다.보내려는 평서문 $$ a $$를 $$ x ≡ a^e\ \pmod N $$으로 암호화한다. (여기서 $$a < N$$이어야 한다.[10]
[11])
그러면 $$a' = a$$가 되어 앨리스는 밥의 메세지를 무사히 받을 수 있게 된다.받은 암호문 $$x$$를 $$a' ≡ x^d\ \pmod N $$으로 복호화한다.
프로그래밍을 어느 정도 해 본 사람이라면 $$a^e\bmod N$$나 $$x^d \bmod N$$ 같은 걸 어떻게 계산하나 싶을 것이다. $$a^e$$ 같은 걸 계산하는 걸 곱셈을 $$e$$ 번 하는 식의 터무니없이 막대한 연산을 수행할 수는 없는 노릇이고 그렇다고 pow 같은 걸 쓰자니 자릿수가 턱없이 모자를 것이기 때문이다.[13]
이렇게 보면 RSA 방식이 필요로 하는 연산이 불가능해 보이지만 사실 가능하며 의외로 간단한데다 연산량도 그리 크지가 않다. 어느 수의 제곱을 구할때 밑의 수를 계속 곱하면 지수가 1씩 증가해서 시간복잡도가 $$O(n)$$이지만, 기존의(우리가 구해놓은) 제곱한 수를 제곱하게 되면 지수가 2배씩 증가해서 시간복잡도가 $$O(\log n)$$이 되기 때문이다.
이 방식을 설명하는 것은 간단한 예를 하나 드는 것이 빠를 것 같다. 예를 들어 $$x$$의 23제곱을 $$N$$으로 나눈 나머지를 계산하고 싶다고 하자. 그러면 $$ab\bmod N = (a\bmod N)(b\bmod N)\bmod N$$, $$a^b\bmod N = (a\bmod N)^b\bmod N$$로부터 다음을 얻는다.
$$x^{23}\bmod N = x^{2^0 + 2^1 + 2^2 + 2^4}\ mod\ N = (x \cdot x^2 \cdot (x^2)^2 \cdot (((x^2)^2)^2)^2)\ mod\ N$$
$$= ((x\ mod\ N) ((x\ mod\ N)^2\ mod\ N) (((x\ mod\ N)^2\ mod\ N)^2\ mod\ N) (((((x\ mod\ N)^2\ mod\ N)^2\ mod\ N)^2\ mod\ N)^2\ mod\ N)\ mod\ N.$$
뭔가 복잡해 보인다. 여기서 $$x_0 = x\ mod \ N$$, $$x_{i + 1} = x_i^2\ mod\ N$$이라 표기하면 사실 위 식은 이렇게 깔끔하게 정리된다.
$$x^{23}\ mod\ N = (x_0 x_1 x_2 x_4)\ mod\ N.$$
즉 $$x_i$$들을 계산해 놓고 이들을 활용하면 엄청난 계산량이라든가 저장 공간 같은 것 없이 저렴하게 $$x^d\ mod\ N$$ 등을 계산할 수 있다. 이걸 다음과 같은 알고리즘으로 정리할 수 있다.
- $$y ≡ x\ mod\ N$$을 계산한다.
- $$m = 1, r = 1$$로 둔다.
- 만약 $$d$$의 (2진법에서) $$m$$번째 자릿수가 1이라면 $$ry\ mod\ N$$을 계산한 다음 $$r$$에 저장한다.
- $$y$$에 $$y^2\ mod\ N$$을 저장한다.
- $$m$$에 $$m + 1$$를 저장한다.
- 만약 $$m$$가 $$d$$의 자릿수보다 크지 않으면 3으로 돌아가고 그렇지 않으면 종료한다.
대학에서 이산수학을 수강할시 기말고사로 풀라고 문제가 나오는 경우도 있다.
3. 원리
이 방식에는 페르마의 소정리[14]가 중추적인 역할을 한다. 간단하게 써 보자.
여기서 $$\varphi(N)$$의 일반적인 꼴을 다루진 않을 것이다. 다만, 이때 두 소수 $$p, q$$가 있어 $$N = pq$$라면, $$\varphi(N)$$의 값은 $$(p - 1)(q - 1)$$로 주어진다는 것 정도는 알아야 한다.$$\gcd(a,N)=1$$인 임의의 정수 $$a$$와 $$N$$에 대해 항상 $$\displaystyle a^{\varphi(N)} \equiv 1 \pmod N$$[15]
이 성립한다.여기서 $$\varphi(N)$$은 오일러-phi 함수로, 1부터 $$N$$까지의 수들 중에서 $$N$$과 서로소인 수들의 개수이다.
이 정리를 이용하면 RSA 암호화 방식이 작동하는 이유가 놀랄 만큼 간단하다는 것을 알 수 있다. 일단 다른 건 몰라도 $$a$$와 $$a'$$가 같아야 한다는 것만 있으면 된다는 걸 염두해 두자. 이제, $$ed = b(p - 1)(q - 1) + 1 = b \varphi(N) + 1$$ ($$b$$는 어떤 정수)이라는 것과 $$ab\ mod\ N = (a\ mod\ N)(b\ mod\ N)\ mod\ N$$, $$a^b\ mod\ N = (a\ mod\ N)^b\ mod\ N$$이라는 사실로부터, 다음을 얻을 수 있다.
$$a' = x^d\ mod\ N = (a^e\ mod\ N)^d\ mod\ N$$
$$ = (a^e)^d\ mod\ N = a^{ed}\ mod\ N$$
$$ = a^{b \varphi(N) + 1}\ mod\ N = (a^{\varphi(N)}\ mod\ N)^b \cdot a\ mod\ N$$
$$ = 1^b \cdot a\ mod\ N = a.$$
이는 암호문을 복호화한 내용이 원래 평서문과 일치함을 말해 준다.
RSA 암호 체계의 작동 원리는 이 동영상을 보면 이해할 수 있다.[16]
4. 기타
정수론에 대해 많은 기본적인 지식만 갖고 있어도 쉽게 이해할 수 있고 보안성이 뛰어나 많이 사용되고 있다. 하지만 만약 소인수분해를 다항식 시간 내에 수행할 수 있는 알고리즘이 개발되어 쉽게 소인수분해가 가능하다면 당연히 RSA 암호체계는 위기를 맞을 것이다. 양자컴퓨터를 사용하면 소인수분해를 $$O(\log^3 n)$$으로 풀 수 있는 쇼어 알고리즘이란게 있는데 문제는 이게 성공률이 100%가 아니다.[17] 이런 실패확률은 어떤 N에 대해서도 5/8을 넘지 않는다는 것이 증명되었기에 그냥 여러번 하면 풀리긴 풀린다. 다만, 컴퓨터의 성능이 높아지면 높아질 수록 현재 사용되는 RSA 2048bit는 깨질 수 있다. 일단 RSA 768bit는 2009년도에 깨졌기 때문에, 더이상 사용되지 않는다. 다만 미래에 RSA 2048bit가 깨질 정도로 컴퓨터의 성능이 상승했다면 그 미래에는 이미 RSA 8192bit따위를 쓰고 있을 것이다.[18][19]
RSA 알고리즘은 구현방법에 따라 부채널 공격의 일종인 Timing Attack에 취약할 수 있다. 정확히는 $$e$$를 left-to-right 또는 right-to-left 알고리즘으로 계산할 때 부채널 분석에 대해 어떤 키 길이에 대해서도 취약하다. 다만 이는 좀 반칙에 가까운지라 암호가 뚫렸다고 보긴 어렵고...[20] 하드웨어에 대한 접근을 강력히 제한하면 그만이다.
코나미의 BEMANI 시리즈의 게임 데이터가 이 암호화 방식을 채용하고 있다. 기존의 자신들의 작품이 PC기반으로 나온 뒤 매번 크래킹의 대상이 되어 채용했지만, 기존의 암호화가 뚫린 데이터를 크래커들이 가지고 있는 이상 무용지물에 가깝게 되었다. 이외에도 닌텐도 DS의 전용 OS, 모토로라의 안드로이드 스마트폰용 부트로더가 RSA를 채용했다.
5. 예시
두 소수 p와 q를 11과 37이라 하자. 그리고, 10과도 36과도 서로소인 정수 e을 7로 정하자. '''우리가 공개하는 것은 N=11*37=407과 e=7이다.'''
다음으로 7*'''103''' - 360*2 = 1 임을 이용해서 '''103''' 을 '''d''' 로 보관한다.
이제, 어떤 평서문 240을 암호화 해 보자. 240의 7제곱을 407로 나눈 나머지는 235이다. 235=240^7(mod 407) 235를 407의 소인수를 아는 상대방에게 보낸다. 참고로 여기서 N은 407이니, 평서문은 406 이하의 숫자만 가능하다.
이제, 이걸 받은 사람은 암호를 푼다.
받은 사람은 N과 d의 값이 각각 407 과 103 임을 알고 있으므로, 전달받은 235의 103제곱을 407로 나누면 나머지가 평서문이 된다. 240 = 235^103(mod 407)
암호가 풀리는 과정을 더 상세히 설명하자면, 먼저 암호를 풀기 위해서는 407의 오일러 함수[21] 값을 알아야 한다. 오일러함수값은 어떤 수 x에 대해서 x와 같거나 작은 수들 중에서 x와 서로소인 수의 개수이다. 소인수들을 안다면 쉽게 알 수 있지만, 모른다면 구하기 힘들다. 407의 오일러함수값은 360이다. 407은 11, 37 두 소수를 곱한 수이므로, 407보다 작은 수들 중에 407과 서로소가 아닌 수는 각 소수의 배수들밖에 없다. 즉 407-(11-1)-(37-1)-1=360.[22][23]
다음으로 7*'''103''' - 360*2 = 1 임을 이용해서 235의 103제곱을 407로 나누면 나머지가 평서문이 된다. 240 = 235^103(mod 407)[24]
언뜻 보면 위의 예시의 경우엔 시행착오 사백번 정도만 해도 풀리니 간단해 보인다. 하지만 실제로는 작은 수가 아닌 적기도 힘든 큰 수를 쓴다. 숫자의 목록은 여기를 참조하자.(한국어)[25]
여담으로 연산량이 많기 때문에 암호화 통신의 경우[26] 처음의, 그리고 일정 주기[27]마다의 암호키 교환(key exchange)에 쓰이고, 키를 교환한 뒤부터는 AES등의 블록 사이퍼를 사용한다. 암호 알고리즘 문서 참고.
정말로 간단하게 비유를 하자면, 위의 밥과 앨리스의 경우 앨리스가 자물쇠(공개키)와 그것을 열 수 있는 유일한 열쇠(개인키)를 가지고 있을 때 자물쇠만 남들에게 공개한다. 그걸 본 밥이 비밀 메시지를 쓰고 그걸 상자에 담아 해당 자물쇠로 잠그고(암호화) 전달하면, 누가 그걸 도중에 손에 넣더라도 열쇠가 없으니 열어보지를 못하고, 오직 앨리스만 열쇠로 열 수 있는 것이다. 저 자물쇠로 잠그는 행위는 앨리스가 뿌린 자물쇠가 있으니 누구나 할 수 있는데도 말이다. 이러면 '자물쇠 모양에서 열쇠 모양을 유추해낼 수 있지않냐'고 하겠지만, RSA 방식에서는 '''적어도 현대 수학으로는 자물쇠에서 열쇠 모양을 알아내는데 너무 많은 시간과 자원이 필요하다.''' 그렇기에 보안이 가능한 것.
6. 여담
RSA-896, RSA-1024, RSA-1536, RSA-2048 같은 수에는 소인수분해에 현상금이 걸려 있었다. 가장 자리수가 많은 RSA-2048은 소인수분해를 성공할 경우 20만 달러(대략 2억원)의 상금이 걸려 있었으나, 현재는 상금이 폐지되었다.
참고로 RSA-2048 은 617자리 수이다.
컴퓨터로 쉽게 다루기 힘들 정도의 큰 수이다.
RSA 암호화을 골자로 하는 언어 모의고사가 출제 된 적이 있다. 위 내용을 그대로 적지는 않았고 아주 쉽게 간략화해서 출제하였다.
7. 위협
RSA 암호화는 양자 컴퓨터가 등장하면 깨진다는 보안 위협에 직면해 있다. 1994년 피터 쇼어가 제안한 양자 알고리즘(쇼어 알고리즘)은 소인수 분해를 다항 시간안에 할 수 있는 양자 알고리즘이다. 따라서 RSA 암호화에 사용된 비트 수를 계산할 수 있을 정도의 충분한 큐비트 수를 가진 양자 컴퓨터가 개발되면 RSA 암호화 체계는 붕괴될 수 있다.
[1] 해쉬를 포함한 단방향 암호화와 유사하지만, RSA는 양방향 암호이므로 복호화할 수단을 남겨놓는 것이 차이점이다.[2] 개인키로 암호화하면 공개키로 누구나 해독할 수 있어 무슨 의미가 있냐는 생각을 할 수 있는데 이 특성은 전자서명에 매우 유용하게 활용된다. 개인키는 자기만 알고 있으니 개인키로 암호화한 메시지는 본인인증의 효과를 낸다. 공인인증서의 인증 원리도 이거다.[3] 사실 이것보다 4년 정도 더 빨리 GCHQ의 모 수학자가 개발했으나, GCHQ에선 이를 1998년까지 이를 기밀처리하게 된다.[4] 이들은 보통 굉장히 큰 홀수를 일단 랜덤하게 만든 다음, 소수를 얻을 때까지 2씩 더해 가며 찾는다. 소수의 분포가 그리 희박하진 않기에 가능한 방식이다. 참고로 해당 수가 소수인지 아닌지 판별하는 방법(primarily test)이 다소 골때리는데, 이에 대해선 아래 내용 참고.[5] e는 encryption에서 딴 것이다.[6] 공개키는 비교적 선택이 자유롭기에 보통 1의 비트가 2개인, 3(11)이나 65537(10000000000000001) 같은 소수를 쓴다. 물론 (p - 1)(q - 1)와 서로소인 걸로만.[7] d는 decryption에서 딴 것이다.[8] 확장된 유클리드 호제법을 이용하면 금방 구할 수 있다.[9] e가 (p - 1)(q - 1)와 서로소가 아니라면 이를 만족하는 d는 존재하지 않기 때문에 2번 과정이 필요하다.[10] 만약 보내려는 평서문의 길이가 N보다 길면, 모종의 복잡한 변환법을 통해 분할하여 N보다 짧게 만든다. 당연하지만 해당 변환법은 보내는 측과 받는 측 모두 알고 있어야 한다.[11] $$ x ≡ a^e\ \pmod N $$ 는 $$x$$를 $$N$$으로 나눴을 때 나머지가 $$a^e$$가 된다는 뜻이다. $$\mathrm{mod}$$는 나머지 연산(모듈러 연산)을 의미한다.[12] 대부분의 암호학 문서에서 메세지를 주고 받는 사람의 이름으로 '앨리스'와 '밥'을 쓴다.[13] $$e = 3$$ 같은 경우라면 모를까 일반적으로 $$d$$는 몇 백에 달하는 자릿수를 가진 어마어마한 수일 것이고 $$x^d$$ 같은 걸 정확하게 계산하려면 '''전 세계에 있는 메모리를 다 모아도 부족할 정도로''' 어마어마한 저장 공간이 필요할 것이다.[14] 그보다는 이 정리에 대한 오일러의 일반화[15] $$a$$의 $$\varphi(N)$$ 제곱을 $$N$$으로 나눈 나머지가 항상 1이라는 뜻이다.[16] RSA 암호화 뽀개기: 말할 수 있는 비밀[17] N과 서로소인 a로부터 $$ a^b -1 = (a^{b/2}+1)(a^{b/2}-1) = mN $$인 b를 찾아서 $$ gcd(N,a^{b/2} +1),gcd(N,a^{b/2} -1) $$를 찾는데 b가 홀수라거나 공약수가 N이라거나 하는 경우가 있다.[18] 컴퓨터의 성능이 높아진다고 암호화가 쉽게 뚫릴 것이라는 생각 자체는 사실상 어불성설인게 그 좋은 컴퓨터를 해커만 가지고 있는 것이 아니므로 당연히 더 복잡한 암호체계가 나와서 결국 뚫기 힘든것은 매한가지다. 지금 이보다 더 높은 수준의 암호화를 사용하지 않는 것은 기술이 없어서가 아니라 단지 암/복호화가 굉장히 비효율적이기 때문이다. 컴퓨터 성능이 올라서 현재의 암호화가 쉽게 뚫린다? 그러면 그 컴퓨터로 더 복잡한 암호체계를 적용하면 그만이다.[19] 다만 양자컴퓨터의 경우처럼 계산 복잡도에서 암/복호화의 차이를 줄여버린다면 뚫기 어려울 정도로 복잡한 암호를 만들었다간 암호화하는 데도 너무 오래걸려서 무쓸모가 될 가능성이 높다. [20] 현실에 비유하자면, 수학문제를 푸는데 어쩌다가 답지를 훔쳐와서 보고 푸는 꼴이다.[21] 오일러 피 함수[22] (11-1)은 407을 제외한 37의 배수, (37-1)은 407을 제외한 11의 배수, 마지막 -1은 407 자신.[23] 예로 든 백단위의 작은 수는 손으로도 쉽게 찾을 수 있지만, 실제 암호화에 사용하는 200자리가 넘어가는 수라면, 소인수를 알면 쉽게 풀 수 있지만 모를 경우 답이 없다(...)는 것을 알 수 있다.[24] 즉 103을 d 값으로 보관한가는 것은 오일러함수값을 찾아야하는 중간계산 절차를 넘기게 된다는 의미와 같다.[25] 보통 100자리 이상의 소수의 곱을 사용한다. 200자리 이상의 합성수를 소인수 분해하는 것은 현대의 기술로는 거의(!) 불가능하다고 생각되어 왔지만 2013년엔 210자리 수가 개인 사용자에게 뚫리는 등 이제 CPU의 발달과 함께 소인수분해 가능한 수도 점점 커지고 있다.[26] 다른 경우로는 전자서명을 들 수 있다.[27] SSH의 경우 1시간, 또는 1GB의 데이터가 오갈 때 마다 키를 갱신한다.