출처 : http://terms.naver.com/entry.nhn?docId=2270499&cid=51173&categoryId=51173
Diffie와 Hellman의 공개키 암호 개념을 기반으로 MIT 공대 연구팀 소속의 세 학자 Rivest, Shamir, Adleman은 ‘공개키로 암호화하고, 그와 다른 비밀키로만 열 수 있는’ 암호화 알고리즘을 고안해내고자 하였다.
RSA 암호화 방식은 이런 아이디어를 구체화한 최초의 방식으로, 미국의 대중잡지 「사이언티픽 아메리칸(Scientific American)」의 1977년 8월호에 선보이게 된다. RSA란 세 학자 이름의 머리글자를 따서 만든 명칭이다. 이들은 연구 결과가 나오기 전까지 40개가 넘는 알고리즘을 만들었다가 폐기했다고 한다. 때로는 공개키, 비밀키의 개념을 실제로 구현할 수 없을 것 같다는 절망적 회의에 빠지기도 했다. 매우 힘든 과정들이었지만 끝까지 포기하지 않았기에 결국 단순 명료하면서도 깊이가 있는 알고리즘을 만들어낼 수 있었다. 현재 디지털 서명 시스템은 RSA 알고리즘에 상당 부분 의존하고 있다.
그러면 RSA 암호화 방식의 동작 원리를 알아보도록 하자. 이 방식은 두 개의 큰 소수들의 곱과 추가 연산을 통해 공개키와 비밀키를 구한다. 이 과정을 거쳐 키들이 생성되면 처음의 두 소수는 더 이상 중요하지 않고 버려도 무방하다. 공개키는 모두에게 공개되는 키지만, 비밀키는 자신만이 가지고 있는 키로 남에게 공개되어서는 안 된다. 이런 비밀키는 공개키에 의해 암호화된 메시지를 복호화하는 데 사용된다.
철수가 영희에게 암호문을 보내는 상황을 가정해보자.
철수는 누구에게나 공개된 영희의 공개키를 이용해 보내고자 하는 메시지를 암호화한다. 그리고 영희에게 암호화된 메시지를 보낸다. 암호문을 받은 영희는 자신의 비밀키를 이용해 암호화된 메시지를 복호화한다. 이때 암호문을 제3자가 가로챈다 하더라도 영희의 비밀키가 없으므로 암호문을 해독하지 못하게 된다.
이 외에도 철수 자신의 비밀키를 사용해서 디지털 서명을 암호화하여 함께 보내준다면 철수가 보낸 메시지임을 더욱 확신시켜 줄 수 있다. 메시지를 받은 영희는 철수의 공개키를 사용해 암호화된 서명을 복호화할 수 있다. 즉 ‘발신자 도장’을 찍어 보냄으로써 신뢰를 줄 수 있는 것이다.
이제까지 RSA의 대략적 모습을 살펴보았다면 앞으로는 좀더 구체적으로 수학적인 면을 함께 보도록 하겠다. RSA는 상당히 큰 정수의 소인수 분해가 힘들다는 점을 이용해 만든 공개키 시스템 알고리즘으로, 수학적 이해가 뒤따르는 알고리즘이다.
우선 공개키와 비밀키를 생성하는 과정을 살펴보자.
① 적당히 비슷하고 큰 소수 p, q를 선택한다. 계산을 쉽게 하기 위해 간단한 소수 13(=p)과 11(=q)을 선택한다.
② 다음 공식에 의해 공개키 n을 생성한다.
n=p*q ➞ 143 = 13*11
③ 다음 공식에 의해 ø(n)를 구한다.
ø(n)=(p-1)(q-1) ➞ 120 = 12*10
④ 다음 조건을 만족하는 e를 선택한다.
gcd(e, ø(n))=1, 1＜e＜ø(n)
➞ gcd(e, 120)=1과 1＜e＜120을 만족하는 23 선택
⑤ 다음 조건을 만족하는 d를 선택한다(수식 e*d≡1 (mod ø(n))은 “e*d를 ø(n)로 나누었을 때 나머지가 1이 된다.”는 의미다).
e*d≡1 (mod ø(n)), 1＜d＜ø(n)
➞ 23*d≡1 (mod 120)과 1＜d＜120을 만족하는 47 선택
⑥ {n, e}가 공개키고, {n, d}가 비밀키다. p, q, ø(n)은 공개되지 않도록 한다. {143, 23}이 공개키가 되고, {143, 47}이 비밀키가 된다.
공개키와 비밀키를 생성하는 방법을 알았으니 암호화하는 방법과 복호화하는 방법을 알아보자.
평문 문자가 m일 때, 공개키 {n, e}를 이용해 암호 문자 c를 구하는 수식은 다음과 같다.
c = me mod n
그리고 암호 문자 c를 비밀키 {n, d}를 이용해 복호화하는 수식은 다음과 같다.
m = cd mod n
그러면 앞의 예에 이어 철수는 문자 ‘J’를 암호화해서 영희에게 보내고, 영희는 복호화하는 과정을 살펴보자.
① 문자 ‘J’의 아스키코드 값은 1001010(= 10진수 74)이고, 영희의 공개키 {n, e}는 {143, 23}이므로 철수는 암호화 수식에 대입하여 암호 문자 94를 구한다.
7423 mod 143
= 94
② 철수는 영희에게 암호 문자 94를 보낸다.
③ 암호 문자 94를 받은 영희는 자신의 비밀키 {n, d}가 {143, 47}이므로 복호화하는 수식에 대입하여 74를 구해 평문 문자 ‘J’를 얻게 된다.
9447 mod 143
= 74
제3자가 암호 문자 94를 가로챈다고 해도 영희의 공개키인 {143, 23}만 가지고는 복호화할 수가 없다.
[네이버 지식백과] RSA 암호화 방식 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))
