[특강] RSA 암호 기법

수학 그룹이라는 페이스북 그룹에서 재미난 문제가 올라왔기에 이참에 공부하기로 하고 어제 몇시간 삽질했었다. 이번에 다룰 것은 제곧내, RSA 암호이다. 실제로 구현해보니까 꽤 재밌다. 삽질을 많이 해서 그렇지... 공부에 사용한 것은 위키이다. ( Link ) 글에서 수학을 많이 보게 될 것이다.

---

이번 글에서 수학적인 부분을 이해하려면 정수론에서 다루는 기본적인 내용들을 대충 알고 있어야된다. 소인수 분해법, 유클리드 호제법, 나머지 연산 등등이 요구된다. 그냥 이런게 있구나(?) 하고 설렁설렁 넘길 분들은 원리만 보면 된다.

RSA 암호는 꽤 널리 사용되고 있다. 현대의 컴퓨터 기술로 암호화는 빠르고 (허락되지 않은) 복호화는 시간이 오래 걸린다. 암호화는 쉽고, 복호화는 어렵다. 프로그래밍으로 구현하는 것은 둘다 어렵지 않다. 암호화 과정은 1초도 안걸리지만, 복호화는 몇 개월씩 걸려서 문제다. (계산해보진 않았지만 몇 년 단위일지도 모른다.) 물론 복호화가 허용된 사용자에겐 복호화도 쉽다. 대충 봤을때 1초가 안걸릴거다.

공개키, 비밀키 방식으로 암호화와 복호화가 이루어진다. 기본적으로는 어떤 큰 수의 소인수분해가 매우 오래 걸린다는 수학적 원리를 바탕으로 고안된 암호화 방식이다. 암호화를 어떤 키로 할 것인가 등등에 관한 문제는 실례를 살펴봐야하는데 전문가가 곁에 없으므로 독자들 몫으로 넘긴다.

방식에 대해 간단히 살펴보겠다. 

매우 큰 소수 두 개 p, q를 가져온다. N=pq를 계산한다. 

오일러 파이 함수 (pi) 를 이용해서 pi(N)를 계산한다. 이 함수는 1~N 사이의 정수 중에서 N과 서로소인 숫자의 개수를 알려준다. 정수론을 조금 배웠다면 (사실 중학 수학 정도지만...) pi(N) = (p-1)*(q-1)로 계산할 수 있다.

1~pi(N) 사이의 정수 중에서 pi(N) 과 서로소인 숫자를 임으로 선택한다. 이를 e라고 부르자.

법 pi(N)에 대해 곱셈에 대한 e의 역원 d를 구한다. 즉, ed == 1 (mod pi(N)) 인 d를 구한다. 

공개키는 N, e이다. 이 공개키를 이용해 원문(m, message)를 암호화(encrypt)할 수 있다. 법 N에 대해 원문 m의 e승을 구하면 암호문을 얻을 수 있다. m^e == c (mod N)

비밀키는 N, d이다. 이 비밀키를 이용해 암호문(c, cypher)를 복호화(decrypt)할 수 있다. 법 N에 대해 암호문 c의 d승을 구하면 원문을 얻을 수 있다. c^d == m (mod N)

잠시 e와 d를 살펴보면 둘 중 어느것을 공개하더라도 상관없다는 것을 알 수 있다. 공개키로 암호화하고 비밀키로 복호화할 수도 있고, 비밀키로 암호화하고 공개키로 복호화할 수 있다. 원리상으론 그렇다.

그리고 만약 알려진 원문과 암호문이 있다고 한들 e와 d를 동시에 유추해낼 수 없다. pi(N)이 없기 때문이다. 수학적으로 이 암호화 방식으로 된 암호문을 모두 풀려면 p, q를 알아내는 방법 뿐이다.

위키피디아에서 사용된 예시를 잠시 살펴볼 것이다. 위에서 기술한 방식을 그대로 따라내려오자.

p = 61, q = 53

N = pq = 3233

pi(N) = pi(3233) = (61-1)*(53-1) = 3120

1<e<pi(N)=3120, e = 17

ed = 17 * 2753 = 46801 == 1 (mod pi(N))

d = 2753

m = 65

c == m^e (mod N) == 65^17 (mod 3233) == 2790 (mod 3233)

m == c^d (mod N) == 2790^2753 (mod 3233) == 65 (mod 3233)

그러하다.

실질적으로 N이 매우 큰 수를 사용하기 때문에 이 계산들을 좀 더 빠르게 할 수 있도록 CRT를 사용할 수 있다. 이건 그냥 넘어가자.

---

다음 글에서 사용될 예시는 파이썬으로 다룰 것이다. 이유는 2048bit 숫자를 쉽게 다루기 위해서다. C에서 하나하나 하려니까 귀찮다...