공개키암호화 RSA 알고리즘 : 암호화의 혁명

공개키 암호화는 현대사회 암호화에 혁명을 가져온 알고리즘이다.

존 맥코닉은 이를 가르켜 페인트 트릭이라고 했다.

각각의 기본 페인트에 공개 페인트를 섞은 후 교체,
다시 교체한 페인트통에 자신의 기본 페인트를 섞어서 총 3개의 혼합색을 만들어내고
그 3개의 혼합색이 같은 경우 두 명은 암호를 공유할 수 있다는 개념

어떻게 이렇게 완벽한 비유를 할 수 있는지..
책을 다시 읽어봐도 놀라움을 금할 수 없다.

컴퓨터가 진짜 페인트를 섞을리는 없고,
그럼 어떻게 위와같은 알고리즘을 구현하는 것일까?

조금 더 이론적인 부분으로 들어가보자.

우선 RSA의 유래부터 알아봐야 한다.
RSA(공개키 암호화)는 리베스트, 샤미르, 에이들맨 3명 개발자의 이름을 본따서 만들어졌다

그런데 그들이 수년간의 고민을 거쳐 개발한 RSA의 알고리즘을 알고나면
허무하리만큼 간단하다.
Simple is the Best를 여실히 보여주는 부분이다.

자, 이제 상황을 가정해보자.

p=11, q=3 일때 위 알고리즘을 따라가보자.

① n = 33
② ø = (11-1) * (3-1) = 20
③ 여기부터 조금 집중해야 할 것이다.
gcd(e,ø)는 곧 gcd(e, (p-1)(q-1))과 동일하다.
이때 이 결과가 1이라는 것은 곧 gcd(e, p-1) = 1, gcd(e, q-1) = 1이라는 것을 의미한다.

생각해보자.
3, 5, 7이 있다.
3이 e, 5가 p-1, 7이 q-1이라고 가정해보면 매우 간단하다.
3과 5의 gcd(최대공약수)는 1이다.
3과 7의 gcd 또한 1이다.

따라서 3과 35는 당연히 최대공약수가 1이게 된다.

이 원리에 의해서 ③을 풀어낼 수가 있다.

e가 1과 20 사이에서 가장 작은 소수인 3이라고 가정해보면 문제는 간단해진다.
gcd(3, 10) = 1
gcd(3, 2) = 1
두 개가 모두 1을 리턴하므로 gcd(e,n) = 1이 되고 조건은 충족된다.

④ 가장 어려운 부분이다.  그러나 기호의 의미만 이해한다면 간단하게 풀린다.
ed = 1 (mod ø) 라는 것은
ed를 ø로 나눴을 때 나머지가 1이라는 뜻이다.

mod는 나머지를 의미한다.

이를 가르켜 백준은 '기호는 매크로와 같다.' 고 설명한다.
복잡한 설명을 기호 하나로 해결하기 때문이다.
얼마나 적절한 비유인가.

아무튼 다시 본론으로 들어와서
ed = 1(mod ø)는 이렇게 다시 쓸 수 있다.

(ed - 1) / ø = 0  (mod)
이때 e가 3이고 ø = 20이므로
(3d - 1)/20 = 0 (mod)
d = 7

즉, 공개키 (n,e)는 (33, 3)이 되고
개인키 (n,d)는 (33, 7)이 된다.

다시 위의 페인트 트릭을 빗대어 설명하자면
7이 개인 페인트, (나만 알 수 있는)
3이 공개 페인트가 되는 것이다. (남들이 봐도 되는)