RSA 암호화 - 수학편: RSA와 소수

RSA 암호화

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

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

---

비대칭키 암호화의 기본

비대칭키 암호화는 비밀키로 공개키를 알 수는 있지만 공개키로는 비밀키를 알 수 없고, 두 키가 암복호화에 따로따로 사용돼야 하는 한 쌍의 키가 필요하다. 이는 보통 이산대수의 어려움을 통하여 구현된다.

이번 글에서 다룰 RSA는 소인수분해의 난해함을 기초로 보안이 유지된다.

 

두 소수 $p$와 $q$가 있다. 이 두 수를 곱하여 $pq$를 계산 하는 일은 누구나 쉽게 할 수 있으며 컴퓨터는 0.1초도 안 되는 시간만에 계산을 끝낸다. 하지만 두 소수가 곱해진 수 $k$를 소인수 분해하여 $p$와 $q$를 알아내는 일은 꽤 어려운 일이다.

 

이 글을 읽는 당신은 소인수분해가 뭐가 어렵냐고 반문할 수도 있다. 물론 $k=10$같이 두 소수가 매우 작은 경우 소인수분해는 전혀 어렵지 않다. 하지만 다음 수를 소인수분해해봐라.

$pq=59622151$. p=?, q=?

이 정도면 손으로 푸는 것은 어렵다. 컴퓨터를 통해 2부터 소수를 쭉 대입해서 나누어보면 이 수는 $7529 \times 7919$이다.

 

그럼 수가 더 커지면 어떨까? 다음 수를 소인수 분해해봐라.

$1341783164471=pq$. p=?, q=?

컴퓨터도 확실히 계산이 느려졌다. 위 값은 1285441과 1043831을 곱한 값이다.

수가 계속 커지면 컴퓨터도 소인수분해를 하기 힘들어진다.

 

매우 큰 소수 두 개로 만든 합성수는 소인수분해에 천문학적인 시간이 걸린다. 이 성질이 RSA를 안전하게 지킨다.

---

RSA에 사용되는 소수

RSA에는 100자리 이상의 소수가 사용된다. 이렇게 큰 소수 2개를 곱해놓은 수는 소인수 분해하는 데에만 천문학적인 시간이 걸린다. 즉, 답을 알지 않고서는 소인수분해가 불가하다.

 

RSA에는 매우 매우 큰 소수가 2개 필요하지만 현재까지 알려진 바에 따르면 소수에는 규칙이 없다. 따라서 처음 두 소수를 만들 때는 조금 막일스러운 방법을 사용한다.

 

먼저 적당히 큰 홀수 $x$를 잡는다. 그리고 거기에 2씩 더해가며 그 수가 소수인지 판별한다. 이 방법은 소수가 그리 드물게 나타나지는 않기 때문에 가능하다.

이때 일반적인 소수 판별법인 $p$가 소수인지 판별하기 위해 $\sqrt p$까지의 모든 소수로 나누는 일은 매우 오래 걸리므로 다른 방법을 사용한다.

페르마 소정리:
$p$가 소수이면 $p$를 약수로 가지지 않는 정수 $a$에 대해 $a^{p-1}$을 $p$로 나눈 나머지는 항상 1이다.
즉 $p \nmid a$일 때 $a^{p-1} \equiv 1\:(\mathrm{mod} \: p)$이다.

이 페르마 소정리에 대우를 취하면 다음과 같다.

$p$를 약수로 가지지 않는 정수 $a$에 대해 $a^{p-1} \equiv 1\:(\mathrm{mod} \: p)$이 아니라면 $p$는 소수가 아니다.

물론 이는 모든 합성수 $p$에 대해 성립하는 것이 아니다. 즉, 확률적으로 $p$가 합성수인데 소수로 판별할 수도 있다. 페르마의 소정리는 많은 합성수들이 상대적으로 시간이 오래 걸리는 "완전한 소수 판별"을 하지 않고도 합성수임을 알 수 있게 해 줄 뿐이다. 따라서 페르마의 소정리로 확인한 소수(일 가능성이 있는 정수)는 다른 "완전한 방법"으로 소수가 맞다는 확인을 한 후에 RSA에 사용될 수 있다.

 

소수를 찾는 방법을 더 명확히 하기 위해 한번 소수를 실제로 찾아보자.

우선 적당히 큰 홀수 $p_0=201$로 잡고 $p_n=p_0+2n$으로 하겠다. 그리고 모든 $p_n$을 약수로 가지지 않는 2를 $a$로 정하겠다.

이제 위의 방법대로 페르마의 소정리를 통해 한번 검사하고, 그 검사를 통과한 수에 대해 제곱근 이하의 모든 소수로 나누어본다(a%b는 a를 b로 나눈 나머지를 의미한다).

$n$	$p_n$	$a^{p-1}$를 $p$로 나눈 나머지	추가 확인
0	201	4	-
1	203	93	-
2	205	16	-
3	207	49	-
4	209	36	-
5	211	1	$\sqrt{211}=14.52\cdots$ 211%2=1 211%3=1 211%5=1 211%7=1 211%11=2 211%13=3 211은 소수가 맞음
6	213	4	-
7	215	59	-
8	217	64	-
9	219	4	-
10	221	16	-
11	223	1	$\sqrt{223}=14.93\cdots$ 223%2=1 223%3=1 223%5=3 223%7=6 223%11=3 223%13=2 223은 소수가 맞음

위의 경우에서는 운이 좋게도 페르마 소정리를 통과한 정수들이 모두 실제 소수가 맞았으며 실제로 페르마 소정리는 대부분의 합성수를 사전에 거를 수 있다. 하지만 그렇다고 추가 확인을 건너뛰고 소수겠거니 하고 사용하면 소수인줄 알고 사용한 수가 소수가 아니여서 오류는 물론 보안상 문제가 생길 수 있다.