RSA 암호화 - 수학편: 나머지 계산

RSA 암호화

• RSA 암호화 - 개념편
• RSA 암호화 - 수학편: RSA와 소수
• RSA 암호화 - 수학편: 나머지 계산
• RSA 암호화 - RSA의 동작 방식
• RSA 암호화 - RSA의 작동 원리

[알림] 이 글은 RSA 암호화 시리즈의 3편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다!

---

특수한 형태의 나머지 연산의 필요성

RSA암호는 나머지 연산을 매우 자주 활용한다. 어떤 정수를 다른 정수로 나누었을 때의 나머지를 구하는 것이다.

컴퓨터 입장에서 나머지 연산은 매우 쉬운 일이다. C언어에서 $a$를 $b$로 나눈 나머지를 계산해서 $c$에 저장하는 코드는 다음 한 줄이면 된다.

c=a%b;

이 방법은 매우 효과적이지만 RSA에 사용하기에는 적절하지 못하다.

 

RSA에는 $a^b \equiv m\:(\mathrm{mod}\: N)$에서 $m$의 값을 계산하는 일을 매우 자주 한다. 여기서 $a$와 $b$, $N$은 대략 수십에서 백자리를 넘는 수이기도 하다. 여기서 $a^b$을 직접 계산하고 그걸 $N$으로 나눈 나머지를 뺄셈을 활용하여 계산하는 것은 말이 안 된다. 시간도 시간이고 메모리도 전 세계의 메모리를 긁어모아도 부족할 것이다.

따라서 이러한 특수한 꼴을 가진 수의 나머지를 빠르고 간단하게 계산하는 방법이 필요하다.

---

나머지의 성질

나머지를 쉽게 계산하기 위해 다음 성질을 생각하자. $a\:\mathrm{mod}\:b$는 $a$를 $b$로 나눈 나머지를 의미한다.

증명도 할 것이지만 사실 증명 없이 직관적으로 이해 된다.

정리 1
$ab\:\mathrm{mod}\:N$$=(a\:\mathrm{mod}\:N)(b\:\mathrm{mod}\:N)\:\mathrm{mod}\:N$

증명: $a=xN+p$, $b=yN+q$라고 하자(모든 문자는 정수이고, $p < N$, $q < N$이다).
$ab=(xN+p)(yN+q)$$=xyN^2+pyN+qxN+pq$이고 $pq$를 제외하고는 모두 $N$을 가지고 있으니 $ab \equiv pq\:(\mathrm{mod}\:N)$이다. 따라서 $ab$를 $N$으로 나눈 나머지는 $pq$를 $N$으로 나눈 나머지로 $pq\:\mathrm{mod}\:N$이다.
한편 $a\:\mathrm{mod}\:N=p$, $b\:\mathrm{mod}\:N=q$이므로 우변도 $pq\:\mathrm{mod}\:N$이므로 좌우변이 같다.

거창하게 설명했지만 한마디로 두 수의 곱의 나머지는 각각의 수의 나머지를 먼저 구하고 그 나머지를 곱한 수의 나머지를 구해도 된다는 것이다.

지수법칙에 따르면 $b=p+q$일 때 $a^b=a^{p+q}=a^p \times a^q$로 쓸 수 있다.

 

여기서 위의 정리를 활용하면 다음과 같이 정리된다.

$a^b\:\mathrm{mod}\:N$$=a^pa^q\:\mathrm{mod}\:N$$=(a^p\:\mathrm{mod}\:N)(a^q\:\mathrm{mod}\:N)$

 

이를 활용하면 $a^b$의 계산을 획기적으로 줄일 수 있다.

 

정리 2
$a^b\:\mathrm{mod}\:N$$=(a\:\mathrm{mod}\:N)^b \:\mathrm{mod}\:N$

$a=pN+q$라고 하면 $a^b \equiv q^b\:(\mathrm{mod}\:N)$이다. N을 가진 모든 항은 N으로 나눈 나머지가 0이기 때문이다. 우변의 $a\:\mathrm{mod}\:N=q$이므로 좌우변이 같아진다.

정리 2를 이용하면 큰 수를 거듭제곱한 이후 나머지를 계산하는 것이 아니라 나머지를 먼저 계산해서 밑을 작게 한 후 거듭제곱하여 연산 용량을 줄일 수 있다.

 

---

계산 방법

구체적인 수를 가지고 계산법을 설명해보겠다. $x$의 10제곱을 $N$으로 나눈 나머지를 구해보자.

10을 이진수로 나타내면 $1010_{(2)}$이다. 즉 $10=2^3+2^1$인 것이다.

따라서 $x^{10}$은 $x^{2^3+2^1}$으로 쓸 수 있고, 이는 지수법칙에 따라서 $x^{2^3} \times x^{2^1}$이다.

 

여기에 나머지를 붙이고 지수부분을 분리해서 다음과 같이 쓸 수 있다. 이는 2절의 정리 1에 따라 가능하다.

$(x^2 \times ((x^2)^2)^2)\:\mathrm{mod}\:N$

 

여기에 2절의 정리 2를 사용해서 x를 N으로 나눈 나머지를 x의 자리에 넣고, 중간중간 나머지연산을 또 넣으면 다음과 같다.

$(((x\:\mathrm{mod}\:N)^2\:\mathrm{mod}\:N)$$(((x\:\mathrm{mod}\:N)^2$$\:\mathrm{mod}\:N)^2\:\mathrm{mod}\:N)^2\:\mathrm{mod}\:N)$

 

이건 뭐 괄호장난도 아니고 괄호가 참 많다. 하지만 여기서 다음과 같은 수열을 도입하면 식을 간단히 계산할 수 있다.

$x_0=x\:\mathrm{mod}\:N$, $x_n=x_{n-1}^2\:\mathrm{mod}\:N$

 

$x^{10}\:\mathrm{mod}\:N=(x_1x_3)\:\mathrm{mod}\:N$

이 방법을 활용하면 시간과 메모리를 획기적으로 적게 사용하여 계산이 가능하다.

 

시간적 이익:

$a^n$을 반복 곱셈으로 계산하면 시간복잡도는 $O(n)$이다.

하지만 위의 방법을 쓰면 지수를 이진법으로 썼을 때 자릿수가 1개 늘어나야 거듭제곱을 1번 더하니 시간복잡도는 $O(\log_2 n)$이다.

 

공간적 이익

어떤 수를 한번 제곱할 때마다 약 2배, 혹은 2배보다 한 자리 적게 결과가 나온다. 예를 들어 40을 제곱하면 1600으로 자리수가 2배 늘어난다.

$a^n$을 계산할 때 $a$가 $x$자리 정수라면 결과값은 최대 $2^nx$자리가 나온다. 무려 지수함수꼴로 자리수가 늘어나는 것이다.

하지만 위의 방법으로 계산하면 가장 자릿수가 길어질 때가 $x$를 $N$으로 나눈 나머지를 제곱할 때이다. $x$는 $N-1$이하이므로 $N$과 같은 자리수라고 하면 길어야 $N$의 자릿수의 2배까지 저장하면 된다.

---

구현

#include <stdio.h>

int main() {
	int a, b, n, r=1, y;
	printf("a^b equiv x (mod n). input a, b, n\n");
	scanf("%d %d %d", &a, &b, &n);

	y=a%n;
	while(1) {
		if(b%2==1) {
			b=(b-1)/2;
			r=(r*y)%n;	
		}
		else b/=2;	
		if(b==0) break;
		y=(y*y)%n;
	}
	printf("x=%d", r);
	return 0;
}

위 코드는 이상의 설명을 C언어 코드로 구현한 것이다. $a^b\:\mathrm{mod}\:n=x$를 계산한다.

 

우선 $b$를 이진수로 쪼개어 계산하기 위해 $b$를 2로 나눈 나머지를 확인한다. 나머지가 1이면 $b$를 이진수로 썼을 때 마지막 자리가 1이란 것이므로 계산에 포함을 하고, 아니면 포함하지 않는다.

매 반복마다 $b$를 2로 나누는 것은 $b$를 이진수로 썼을 때 방금 처리한 마지막 자리수를 날리기 위함이다(왜 시프트 연산을 쓰지 않았는지 묻지 마라). 그렇게 $b$가 0이 되면 계산을 끝낸다.

 

y는 3절의 설명에서 수열 $x$의 역할을 하며 처음엔 $a$를 $n$으로 나눈 나머지를 가지고 있다. 매 반복마다 y의 제곱을 $n$으로 나눈 나머지를 y에 대입하는 것은 수열의 다음 항을 계산해서 y에 저장하는 것이다.

 

r은 결과값을 저장하는 변수이다. 처음엔 1을 가지고 있다가 b를 이진수로 표현했을 때 1인 숫자가 있으면 그 때에 해당하는 y의 값을 지금까지의  r(지금까지의 나머지)에 곱한 후 그를 $n$으로 나누어 나머지를 계속 계산한다.

 

이러한 계산을 마치면 마지막에 $r$에 우리가 원하는 값이 저장되어 있다.