RSA 알고리즘

powered by Guardian

1. 시작하며

RSA 알고리즘은 요즘 전자 서명에 많이 쓰이는 알고리즘이다. 이 알고리즘은 공용키/비밀키를 가지는, 비대칭 키 암호화 알고리즘의 대표주자격인 알고리즘이다. 이 RSA 는 알고리즘이 간단한 반면, 몇가지 수식이 나오기 때문에 쉽게 설명하기가 쉽지 않다. 필자도 이 글에서 되도록이면 수식을 안쓰려 했지만, 어쩔 수 없이 수많은 수식을 쓰게 되었다. 이 수식을 완전히 이해하지 못하더라도, 일단 RSA 알고리즘이 무엇이다 라는 것을 알았다면 이 강의를 들은 보람이 있을 것이다.

2. 정수론의 기초

RSA 알고리즘을 이해하기 위해서는 정수론을 반드시 알아야 한다. 복잡하게 보일지 모르지만, 하나 하나 해 나가면, 결코 어려운 일이 아님을 알 것이다.

2.1 배수

A | B : A 의 배수가 B라는 것을 의미한다.

2.2 mod

a-b가 M의 배수일때, 즉 M | a - b 일때, 즉 a - b = mk 일때 a는 법 m 에 관해서 b 와 합동이라고 하고, 기호로 이라고 쓴다.

2.3 모듈 연산의 성질

2.4 오일러 파이 함수

은 1부터 m-1까지의 정수 중에서 m과 서로 소의 관계에 있는 정수들의 갯수를 나타낸다. 만약 p가 소수라면, 이다.

2.5 오일러의 정리

임의의 양의 정수 a와 m에 대하여, a와 m 이 서로 소일 경우 다음의 식이 성립한다.

3. RSA

3.1 배경 지식

RSA 의 입력은, 블록 단위로 나누어 진다. 블럭 사이즈는 이고, 알고리즘에서 중요한 역할을 하는 n 이라는 숫자의 범위는 이다. RSA 에서는, 입력을 숫자로 본다. 예를 들어, 메시지가 512 bit이면, 그 입력을 512 bit로 보고, 이 숫자를 수학적으로 변환시켜 암호화를 하고, 다시 원래의 수를 만들어 복호화를 한다. 얼마 전에, RSA 512 bit 가 깨졌다는 말이 있었다. 이제 앞으로의 전자 상거래에서는 기본적으로 1024 bit 이상을 사용해야 하겠다. RSA 에는 공개키와 비밀키가 있다. 공개키로 암호화 한 데이타는 비밀키로 복호화 할 수 있고, 비밀키로 암호화 한 데이타는 공개키로 복호화 할 수 있다. 앞으로의 문서에서 M 은 원래의 데이타(평문)을 의미하고 C는 암호화한 데이타(암호문)를 의미한다.

3.2 알고리즘 작성 순서

3.3 암호화/복호화 과정

암호화 :
복호화 :
이 과정에서 외부에 공개되는 공개키는 e 와 n이고, 비밀키는 d와 n이다.

3.3.1 알고리즘 증명

여기에서는 이 알고리즘을 수학적으로 증명한다. 사실, 이 부분은 전문적인 부분이므로 RSA 의 개념만을 잡고 싶은 독자들은 그냥 4장으로 넘어가도 좋다.


이제 여기에서 을 증명하면 된다.
크게 두 가지로 나누어서 생각을 해 보자.

먼저 M과 n이 서로 소인 경우를 생각해 보자. 이 경우 오일러의 정리에 의하여 이라는 식이 성립한다. 이 식의 양변에 M 을 곱하면 이 된다.

두번째로, M과 n이 서로 소가 아닌 경우를 생각해 보자(단, M < n). n = pq 이므로, M은 p의 배수 아니면 q의 배수가 된다. 일반성을 잃지 않고, M을 p의 배수라고 가정해 보자. 즉 M = cp 가 된다(여기서 c는 q의 배수가 절대로 아니다). 그래서 GCD(M, q) = 1이다.

이 식의 양변에 승을 하면, 그런데 이므로

그러므로 을 만족시키는 정수 k가 존재한다. 이 식의 양변에 M, 즉 cp를 곱하면 이 성립한다.
즉, 이다.

이제 증명이 끝났다. 여기서 잠깐, 한가지 생각을 해보자. 암호화를 할때는 M 의 e 승을 하고 , 복호화 할때는 C 의 d 승을 했다. 그러나, 위의 계산 과정을 잘 보면 e 와 d가 바뀌어도 된다는 것을 알 수 있다. 즉, 암호화 할때 M의 d 승을 하고, 복호화 할대 C의 e 승을 해도 원래의 메시지 M 이 나오게 되는 것이다.

3.4 RSA 알고리즘을 위해 필요한 계산들

3.4.1 지수 계산

RSA 알고리즘의 암호화와 복호화에서, 지수 계산이 필요하다. 그런데 숫자들이 너무 크면(1024 bit) 속도가 매우 느려지기 때문에, 빠른 지수 계산 알고리즘을 사용한다. 를 구한다고 하자. 평범한 방법대로 한다면, 8을 26번 곱해서 그것을 55로 나누면 그 값이 x가 된다. 이 방법으로 한다면, 최소 27번의 계산이 필요하다. 빠른 지수 계산 알고리즘은 다음과 같은 방법으로 한다. 이므로 이 된다.

그러므로, 다음과 같은 식이 성립한다.

이 경우, 계산은 4번밖에 이루어지지 않는다. 이제, 위의 알고리즘으로 을 계산하는 C 코드를 보자. 여기에서 숫자들은 모두 int 라고 가정한다. 
int FastExp(int a, int y, int m)
{
    int x = 1;
    while(y) {
        if(y % 2 == 1)
            x = (x * a) % m;
        a = (a * a) % m;
        y >>= 1;
    }
    return x;
}

3.4.2 큰 소수 찾기

RSA 알고리즘에서, 맨 먼저 두개의 소수 p와 q를 찾아야 한다. 그런데, 아주 큰 소수를 찾는 효과적인 방법은 아직 찾지 못했다고 한다. 그래서 완벽하진 않지만, 몇가지 효과적인 방법들이 고안되었다. 그 중 한가지 방법은, 어떤 수가 소수가 아닌지를 판별하는 방법이다. 만약 을 만족하는, +1 또는 -1 이 아닌 x가 존재한다면 n 은 소수가 아니다. 이런 방법으로, 소수가 아닌 수들을 제거해 나가면, 소수일 가능성이 많은 수들을 찾을 수 있다. 그 수가 정말 소수인지 아닌지는 하나 하나 약수들을 대입해 보는 방법으로 해야 할 것이다.

3.4.3 서로 소인 수 구하기

어떤 수 a와 서로 소인 수를 구하는 것은 간단하다. 임의의 자연수 2개를 뽑았을때, 두 수가 서로 소일 확률은 0.6쯤 된다고 한다. 그러므로, a와 서로 소인 수를 찾으려면 임의의 수를 택한 다음 그수와 유클리드 호제법으로 최대 공약수를 구해 최대 공약수가 1인지 검사한다. 만약 서로 소가 아니라면 임의의수 + 1 .. 에 대해서 계속 해 본다. 곧 그 수를 찾게 될 것이다.

3.4.4 역원 찾기

GCD(a, m) = 1일때, 을 만족시키는 x를 찾는 방법이다. 이 방법은 두가지가 있다. 하나는 유클리드 호제법을 이용하는 방법이고, 다른 하나는 오일러 정리를 이용하는 방법이다.

아까 오일러 정리에서 GCD(a,m) = 1일때(a와 m이 서로 소일때) 이라고 했다. 그렇다면, 위에서 x는 이 된다.

3.5 RSA 알고리즘 깨기

깨는 방법은 크게 세가지가 있다.

5. 실제 예제

  1. p = 7, q = 11 라고 하자. m = 77 을 일반에 공개한다. p, q 는 공개하지 않는다.
  2. = (7-1) x (11-1) = 60 이다. 여기서 이 되는 e를 계산한다. 여기서 e는 60과 서로 소인 수이므로, 13이라고 잡자.
  3. 원래 메시지가 18였다면, 암호문은 다음과 같이 된다.
  4. 이 암호문의 비밀키 d는 를 만족하는 x이고, 이것은 계산해보면 37이다.
  5. 이 암호문을 원래대로 복호화 하면 다음과 같다.

5. 참고 문헌

Cryptography and Network Security : Principles and Practice, 2nd (William Stallings)
이산 수학(신현식 외)