RSA

이번엔 배낭암호체계에 이어 표준 공개키 암호화 체계인 RSA 암호체계에서 대해서 알아보겠다.

RSA라는 이름도 다른 유명한 공개키 암호체계처럼 이를 발명한 사람,
즉, 리베스트, 샤미르, 애들맨의 이름을 딴 것이다.

사람이 큰 수들의 인수분해에 그렇게 많은 관심을 갖는 이유는 RSA의 보안성이 이러한 형태의 인수분해가 매우 어렵다는 사실에 근거를 두고 있기 때문이다. 그러나 인수분해 문제는 세일즈맨의 여행 문제처럼 확실하게 어려운 문제인지 여부는 알려져 있지 않다.

세일즈맨의 여행 문제
많은 수의 도시가 있고 한 도시에서 다른 도시로의 여행 경비를 알고 있을 때, 각 도시를 한번씩만 방문한 후 출발한 도시로 되돌아오는데 가장 비용이 적게 드는 여행 경로를 찾는 것이다. Traveling Salesman Problem(TSP)로 알려져 있는데, 계산복잡도 이론 가운데 풀기 어려운 문제의 전형적인 예로 사용. 

RSA의 공개키와 개인키 쌍을 생성하기 위해 두 개의 큰 소스 p와 q를 선택하고 그 둘의 곱 N = pq를 계산한다.
다음 (p-1)(q-1) 에 서로 소인 e를 선택하고 "e mod (p-1)(q-1)" 에 대한 역곱수를 계산한다.
이 e의 역수를 d로 표기하자.
이제 N = pq, ed = 1 mod (p-1)(q-1)을 만족하는 e와 d를 가진다.

N은 계수, e는 암호화 지수, d는 복호화 지수
공개키: (N,e), 개인키 : d

암호화
C = M^e mod N 

복호화
M = C^d mod N

RSA 예제
A는  p = 11, q = 3 선정
계수 N = 11 * 3 = 33
(p-1) * (q-1) = 20
20과 서로 소가 되는 암호화 지수 e = 3 선정
e^-1 mod (p-1)(q-1) = 3^-1 mod 20 = 7 = d

공개키 : (33,3), 개인키 : 7

B가 A에게 메시지 M = 15 보내려고 함.
B는 A의 공개키인 (33,3)을 사용해 암호화 함.

C = M^e mod N = 15^3 mod 33 = 9

A는 받은 C = 9를 캐인키 d = 7을 사용해 복호화
M = C^d mod N = 9^7 mod 33 = 15  ( 복호화 성공 )

문제를 푸는 것을 보면 큰 지수승을 계산해야하는데 이를 쉽게 처리하는 방법이 있다.
제곱의 반복 기법을 사용하는 것이다. 

예를 들어 5^20 mod 35를 계산해보자.
보통 제곱의 반복 기법을 사용하지 않으면 mod 연산을 하기 전에 5를 20번 곱하고 있어야한다.
그러면 수가 엄청 커지면서 계산하는데 많은 비용이 들어간다.
( 5^20 = 95,367,431,640,625 )

제곱의 반복 기법
5^20 에서 지수 20은 2진수로 10100(2)이다.
이제 10100은 한 번에 한 비트씩 다음과 같이 만들어 질 수 있다.

(0, 1, 10, 101, 1010, 10100) = (0, 1, 2, 5, 10, 20)

이제 5^20 을 계산하기 위한 절차는 다음과 같다.
5^1 = 5 mod 35
5^2 = 25 mod 35
5^5 = (5^2)^2 * 5^1 = 25^2 * 5 = 3125 = 10 mod 35 
5^10 = (5^5)^2 = 10^2 = 100 = 30 mod 35
5^20 =  (5^10)^2 = 30^2 = 900 = 25 mod 35

각 단계는 단순하며 더욱 중요한 것은 계수의 세제곱보다 큰 수는 다룰 필요가 없다는 것이다.