공개키 암호화 방식

1 개요

가우스가 보면 화낼지도 모르는 것 아니, 그 반대이려나?[1]

현재 SSL/TLS에 가장 많이 사용되는 공개키 암호화 알고리즘이다. 현재 나무위키도 HTTPS에 RSA2048bit 인증서를 사용하고 있다.

암호화할 때에는 마음대로였겠지만 해독할 때에는 아니란다를 기본 모토로 한 공개키 암호체계 중 하나이다. 공개키와 개인키가 한 쌍을 이루며, 공개키로 암호화한 내용은 개인키로만, 개인키로 암호화한 내용은 공개키로만 해독할 수 있다.[2] 엄청 큰 숫자는 소인수분해하기가 힘들다는 것을 이용한다. 1977년[3] 이 체제를 개발한 Ron Rivest, Adi Shamir, Leonard Adleman 세 사람의 성을 따서 지어진 암호 방식이다.

참고로 맞춤법에 대해 공개 키라고 쓰는 것이 더 적절하다. 다만 이 단어는 공개키라는 단어 자체도 전공자들 사이에서는 많이 쓰이기 때문에 이 문서의 제목이 공개키로 되어 있다.

2 과정

RSA 방식으로 암호화를 하기 위해선 먼저 키를 만들어야 한다. 그 과정은 다음과 같다.

1. 두 소수 [math] p , q [/math] 를 준비한다.[4]

2. [math] p - 1,\ q - 1 [/math]과 각각 서로소인 정수 [math]e[/math][5]를 준비한다.[6]
3. [math]ed[/math]를 [math](p - 1)(q - 1)[/math]으로 나눈 나머지가 1이 되도록 하는 [math]d[/math][7]를 찾는다.[8][9]
4. [math]N = pq[/math]를 계산한 후, [math]N[/math]와 [math]e[/math]를 공개한다. 이들이 바로 공개키이다. 한편 [math]d[/math]는 숨겨두는데, 이 수가 바로 개인키이다.

여기서부터는 [math]p, q, (p-1)(q-1)[/math] 모두가 필요 없거니와 있어 봐야 보안에 오히려 문제를 일으킬 수 있으니, 파기한다.

한편 소수 [math]p[/math]와 [math]q[/math]를 구하는 과정은 여전히 완전한 방법이 없다고 봐야 한다. 일단 에라토스테네스의 체를 이용한 방식을 생각해 볼 수 있는데, [math]\sqrt{p}[/math]보다 작은 소수들 모두로 나눠 봐야 알 수 있다는 점에서 이 방법은 현실적으로 불가능한 방법이다. 문제는 100% 확실한 소수 판정법이 아직까지 이것 하나 뿐이라는 것이다. 그래서 대신에 확률적으로 소수인지 아닌지를 판별하는 방법을 쓴다. 기본적으로 쓰는 방식이 아래에 소개할 페르마 소정리를 근거로 한 것인데, 이 정리의 대우명제인 '임의의 정수 [math]a[/math]에 대해 [math]a^{p - 1}[/math]를 [math]p[/math]로 나눈 나머지가 1이 아니면 [math]p[/math]는 소수가 아니다'라는 사실을 이용한 것이다. 이 방법을 쓰면 상당 확률로 소수를 걸러낼 수 있다고 한다. 하지만 물론 완전하진 않으며 이 때문에 다른 소수 판정법을 같이 쓰기도 한다.

공개키를 이용해 RSA 방식으로 암호화를 하는 과정은 다음과 같다.

보내려는 평서문 [math] a [/math]를 [math] x = a^e\ mod\ N [/math]으로 암호화한다. (여기서 [math]a \lt N[/math]이어야 한다.)

예를 들어 앨리스가 공개키를 만들어 뿌렸고, 밥이 앨리스한테 메세지를 비밀리에 주고 싶다고 하자.[10] 밥은 이렇게 암호화가 된 내용([math]x[/math])을 앨리스한테 준다. 그러면 앨리스는 자신이 가지고 있는 개인키를 이용해 원래 평서문을 얻을 수 있다. RSA 방식으로 암호화를 하는 과정은 다음과 같다.

받은 암호문 [math]x[/math]를 [math]a' = x^d\ mod\ N [/math]으로 복호화한다.

그러면 [math]a' = a[/math]가 되어 앨리스는 밥의 메세지를 무사히 받을 수 있게 된다.

프로그래밍을 어느 정도 해 본 사람이라면 [math]a^e\ mod \ N[/math]나 [math]x^d\ mod \ N[/math] 같은 걸 어떻게 계산하나 싶을 것이다. [math]a^e[/math] 같은 걸 계산하는 걸 곱셈을 [math]e[/math] 번 하는 식의 터무니없이 막대한 연산을 수행할 수는 없는 노릇이고 그렇다고 pow 같은 걸 쓰자니 자릿수가 턱없이 모자를 것이기 때문.[11]

이렇게 보면 RSA 방식이 필요로 하는 연산이 불가능해 보이지만 사실 가능하며 의외로 간단한데다 연산량도 그리 크지가 않다.

이 방식을 설명하는 것은 간단한 예를 하나 드는 것이 빠를 것 같다. 예를 들어 [math]x[/math]의 23제곱을 [math]N[/math]으로 나눈 나머지를 계산하고 싶다고 하자. 그러면 [math]ab\ mod\ N = (a\ mod\ N)(b\ mod\ N)\ mod\ N[/math], [math]a^b\ mod\ N = (a\ mod\ N)^b\ mod\ N[/math]로부터 다음을 얻는다.

[math]x^{23}\ mod\ 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[/math]
[math]= ((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.[/math]

뭔가 복잡해 보인다. 여기서 [math]x_0 = x\ mod \ N[/math], [math]x_{i + 1} = x_i^2\ mod\ N[/math]이라 표기하면 사실 위 식은 이렇게 깔끔하게 정리된다.

[math]x^{23}\ mod\ N = (x_0 x_1 x_2 x_4)\ mod\ N.[/math]

즉, [math]x_i[/math]들을 계산해 놓고 이들을 활용하면 엄청난 계산량이라든가 저장 공간 같은 것 없이 저렴하게 [math]x^d\ mod\ N[/math] 등을 계산할 수 있다. 이걸 다음과 같은 알고리듬으로 정리할 수 있다.

1. [math]y = x\ mod\ N[/math]을 계산한다.

2. [math]m = 0, r = 1[/math]로 둔다.
3. 만약 [math]d[/math]의 (2진법에서) [math]m[/math]번째 자릿수가 1이라면 [math]ry\ mod\ N[/math]을 계산한 다음 [math]r[/math]에 저장한다.
4. [math]y[/math]에 [math]y^2\ mod\ N[/math]을 저장한다.
5. [math]m[/math]에 [math]m + 1[/math]를 저장한다.
6. 만약 [math]m[/math]가 [math]d[/math]의 자릿수보다 크지 않으면 3으로 돌아가고 그렇지 않으면 종료한다.

알고리듬이 종료하면 원하는 결과가 [math]r[/math]에 저장되어 있을 것이다. 이렇게 하면 기껏해야 [math]N[/math]의 자릿수의 두 배 정도를 저장할 수 있는 공간에 [math]d[/math]의 자릿수 정도만큼 반복하는 연산 만으로도 [math]x^d\ mod\ N[/math]를 계산할 수 있다. 다만 [math]N[/math]의 자릿수의 두 배에 달하는 용량을 가진 두 정수 변수의 곱셈과 나눗셈은 기본적으로 하드웨어에서 지원하지 않는데다 이 사칙연산들마저도 연산량이 장난 아니다. 그래서 이런 알고리듬을 써도 상당한 연산을 요구하며 이 때문에, 후술하겠지만, RSA만으로 모든 암호화를 하진 못 하고 대신 다른 암호화 방식과 연동하여 쓰는 것이 보통이다.

3 원리

이 방식에는 페르마의 소정리[12]가 중추적인 역할을 한다. 간단하게 써 보자.

임의의 정수 [math]a[/math]와 [math]N[/math]에 대해 항상 다음이 성립한다.

[math]\displaystyle a^{\varphi(N)} \equiv 1\ (mod\ N).[/math][13]
여기서 [math]\varphi(N)[/math]은 오일러-phi 함수로, 1부터 [math]N[/math]까지의 수들 중에서 [math]N[/math]과 서로소인 수들의 개수이다.

여기서 [math]\varphi(N)[/math]의 일반적인 꼴을 다루진 않을 것이다. 다만, 이때 두 소수 [math]p, q[/math]가 있어 [math]N = pq[/math]라면, [math]\varphi(N)[/math]의 값은 [math](p - 1)(q - 1)[/math]로 주어진다는 것 정도는 알아야 한다.

이 정리를 이용하면 RSA 암호화 방식이 작동하는 이유가 놀랄 만큼 간단하다는 것을 알 수 있다. 일단 다른 건 몰라도 [math]a[/math]와 [math]a'[/math]가 같아야 한다는 것만 있으면 된다는 걸 염두해 두자. 이제, [math]ed = b(p - 1)(q - 1) + 1 = b \varphi(N) + 1[/math] ([math]b[/math]는 어떤 정수)이라는 것과 [math]ab\ mod\ N = (a\ mod\ N)(b\ mod\ N)\ mod\ N[/math], [math]a^b\ mod\ N = (a\ mod\ N)^b\ mod\ N[/math]이라는 사실로부터, 다음을 얻을 수 있다.

[math]a' = x^d\ mod\ N = (a^e\ mod\ N)^d\ mod\ N[/math]
[math] = (a^e)^d\ mod\ N = a^{ed}\ mod\ N[/math]
[math] = a^{b \varphi(N) + 1}\ mod\ N = (a^{\varphi(N)}\ mod\ N)^b \cdot a\ mod\ N[/math]
[math] = 1^b \cdot a\ mod\ N = a.[/math]

이는 암호문을 복호화한 내용이 원래 평서문과 일치함을 말해 준다.

4 기타

정수론에 대해 많은 기본적인 지식만 갖고 있어도 쉽게 이해할 수 있고 보안성이 뛰어나 많이 사용되고 있다. 하지만, 만약 소인수분해를 다항식 시간 내에 수행할 수 있는 알고리즘이 개발되어 쉽게 소인수분해가 가능하다면 당연히 RSA 암호체계는 위기를 맞을 것이다. 일각에서는 양자컴퓨터 시대가 도래하면 가장 크게 위기를 맞을 암호 체계라고도 한다. 일단 RSA 768bit는 2009년도에 깨졌다.

RSA 알고리즘은 구현방법에 따라 부채널 공격의 일종인 Timing Attack에 취약할 수 있다. 정확히는 [math]e[/math]를 left-to-right 또는 right-to-left 알고리즘으로 계산할 때 부채널 분석에 대해 어떤 키 길이에 대해서도 취약하다. 다만 이는 좀 반칙에 가까운지라 암호가 뚫렸다고 보긴 어렵고... 하드웨어에 대한 접근을 강력히 제한하면 그만이다.

코나미의 BEMANI 시리즈의 게임 데이터가 이 암호화 방식을 채용하고 있다. 기존의 자신들의 작품이 PC기반으로 나온 뒤 매번 크래킹의 대상이 되어 채용했지만, 기존의 암호화가 뚫린 데이터를 크래커들이 가지고 있는 이상 무용지물에 가깝게 되었다. 이외에도 닌텐도 DS의 전용 OS, 모토로라의 안드로이드 스마트폰용 부트로더가 RSA를 채용했다.

5 예시

두 소수를 11과 37이라 하자. 그리고, 10과도 36과도 서로소인 정수 7을 정하자.
우리가 공개하는 것은 407(=11*37)과 7이다.

이제, 어떤 평서문 240을 암호화 해 보자.
240의 7제곱을 407로 나눈 나머지는 235이다. 235=240^7(mod 407)
235를 407의 소인수를 아는 상대방에게 보낸다.

이제, 이걸 받은 사람은 암호를 푼다.

먼저 암호를 풀기 위해서는 407의 오일러함수값을 알아야 한다. 오일러함수값은 어떤 수 x에 대해서 x와 같거나 작은 수들 중에서 x와 서로소인 수의 개수이다. 소인수들을 안다면 쉽게 알 수 있지만, 모른다면 구하기 힘들다. 407의 오일러함수값은 360이다. 407은 11, 37 두 소수를 곱한 수이므로, 407보다 작은 수들 중에 407과 서로소가 아닌 수는 각 소수의 배수들밖에 없다. 즉 407-(11-1)-(37-1)-1=360.[14][15]

다음으로 7*103 - 360*2 = 1 임을 이용해서 235의 103제곱을 407로 나누면 나머지가 평서문이 된다. 240 = 235^103(mod 407)

실제로는 작은 수가 아닌 적기도 힘든 큰 수를 쓴다. 숫자의 목록은 여기를 참조하자.[16]

여담으로 연산량이 많기 때문에저 제곱과 모듈러의 향연을 보라.. 암호화 통신의 경우[17] 처음의, 그리고 일정 주기[18]마다의 암호키 교환(key exchange)에 쓰이고, 키를 교환한 뒤부터는 AES등의 블록 사이퍼를 사용한다. 암호 알고리즘 문서 참고.

6 여담

RSA-896, RSA-1024, RSA-1536, RSA-2048 같은 수에는 소인수분해에 현상금이 걸려 있었다. 가장 자리수가 많은 RSA-2048은 소인수분해를 성공할 경우 20만 달러를 상금으로 받을 수 있었다.

이 문서의 내용 중 전체 또는 일부는 RSA문서에서 가져왔습니다.</div></div>
  1. ↑ 가우스는 생전에 정수론을 가리켜 그 무용성 때문에 수학의 여왕이라고 칭하기도 했다. 가우스 개인의 편견이 아니라 응용과 동떨어진 순수한 교양(Liberal arts)일 수록 고상하게 여기던 당시의 문화를 반영한 것이지만, 과연 가우스가 오늘날 암호학의 필요 때문에 무섭게 발전한 정수론을 보고 무슨 반응을 보일는지...
  2. ↑ 개인키로 암호화하면 공개키로 누구나 해독할 수 있어 무슨 의미가 있냐는 생각을 할 수 있는데 이 특성은 전자서명에 매우 유용하게 활용된다. 개인키는 자기만 알고 있으니 개인키로 암호화한 메시지는 본인인증의 효과를 낸다. 공인인증서의 인증 원리도 이거다.
  3. ↑ 사실 이것보다 4년 정도 더 빨리 GCHQ의 모 수학자가 개발했으나, GCHQ에선 이를 1998년까지 이를 기밀처리하게 된다.
  4. ↑ 이들은 보통 굉장히 큰 홀수를 일단 랜덤하게 만든 다음, 소수를 얻을 때까지 2씩 더해 가며 찾는다. 소수의 분포가 그리 희박하진 않기에 가능한 방식이다. 참고로 해당 수가 소수인지 아닌지 판별하는 방법(primarily test)이 다소 골때리는데, 이에 대해선 아래 내용 참고.
  5. ↑ e는 encryption에서 딴 것이다.
  6. ↑ 공개키는 비교적 선택이 자유롭기에 보통 3이나 65537 같은 소수를 쓴다. 물론 [math](p - 1)(q - 1)[/math]와 서로소인 걸로만.
  7. ↑ d는 decryption에서 딴 것이다.
  8. ↑ 확장된 유클리드 호제법을 이용하면 금방 구할 수 있다.
  9. ↑ [math]e[/math]가 [math](p - 1)(q - 1)[/math]와 서로소가 아니라면 이를 만족하는 [math]d[/math]는 존재하지 않기 때문에 2번 과정이 필요하다.
  10. ↑ 대부분의 암호학 문서에서 메세지를 주고 받는 사람의 이름으로 '앨리스'와 '밥'을 쓴다.
  11. ↑ [math]e = 3[/math] 같은 경우라면 모를까 일반적으로 [math]d[/math]는 몇 백에 달하는 자릿수를 가진 어마어마한 수일 것이고 [math]x^d[/math] 같은 걸 정확하게 계산하려면 전 세계에 있는 메모리를 다 모아도 부족할 정도로 어마어마한 저장 공간이 필요할 것이다.
  12. ↑ 그보다는 이 정리에 대한 오일러의 일반화
  13. ↑ [math]a[/math]의 [math]\varphi(N)[/math] 제곱을 [math]N[/math]으로 나눈 나머지가 항상 1이라는 뜻이다.
  14. ↑ (11-1)은 407을 제외한 37의 배수, (37-1)은 407을 제외한 11의 배수, 마지막 -1은 407 자신.
  15. ↑ 예로 든 백단위의 작은 수는 손으로도 쉽게?? 찾을 수 있지만, 실제 암호화에 사용하는 200자리가 넘어가는 수라면, 소인수를 알면 쉽게 풀 수 있지만 모를 경우 답이 없다(...)는 것을 알 수 있다.
  16. ↑ 보통 100자리 이상의 소수의 곱을 사용한다. 200자리 이상의 합성수를 소인수 분해하는 것은 현대의 기술로는 거의(!) 불가능하다고 생각되어 왔지만 2013년엔 210자리 수가 개인 사용자에게 뚫리는 등 이제 CPU의 발달과 함께 소인수분해 가능한 수도 점점 커지고 있다.
  17. ↑ 다른 경우로는 전자서명을 들 수 있다
  18. ↑ SSH의 경우 1시간, 또는 1GB의 데이터가 오갈 때 마다 키를 갱신한다