소 개
RSA는 공개키 암호시스템의 하나로, 현재 전자 상거래 등에 광범위하게 이용되고 있다.1977
년 로널드 라이베스트, 아디 샤미르, 레오널드 애들먼이 발명하였으며, RSA라는 이름은 이 3명의 이름 앞 글자를 딴 것이다. 이
세 발명자는 이 공로로 2002년 튜링상을 수상했다. RSA 암호체계의 안정성은 큰 숫자를 소인수분해하는 것이 어렵다는 것에
기반을 두고 있다. 만약 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질
것이다. 1993년 피터쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의
정수를 다항 시간 안에 소인수분해하는 방법을 보였다. 따라서 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될
것이다. 그러나 양자 컴퓨터가 이 정도 수준으로 실용화되려면 아직 여러 해가 더 필요할 것으로 보인다.
RSA 암호화 알고리즘은 1983년에 발명자들이 소속되어 있던 매사추세츠 공과대학교에 의해 미국에 특허로 등록되었고, 2000년 9월 21일에 그 특허가 만료되었다.
개 요
RSA
는 두 개의 키를 사용한다. 여기서 키란 메시지를 열고 잠그는 상수(constant)를 의미한다. 이 중 공개키(public
key)는 모두에게 알려져 있으며, 메시지를 암호화(encrypt)하는데 쓰인다. 이렇게 암호화된 메시지는
개인(비밀)키(private key)를 가진 자만이 해독(decrypt)하여 열어볼 수 있다. 다시 말하면, 누구나 어떤 메시지를
암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람 뿐인 것이다. RSA는 소인수분해의
난해함에 기반하여, 공개키만을 가지고는 개인키를 쉽게 짐작할 수 없도록 디자인되어 있다. 보다 이해하기 쉬운 예를 들자면, A라는
사람에게 B라는 사람이 메시지를 전하고자 할 때 B는 A의 열린 자물쇠를 들고 와 그의 메시지를 봉인하고, 그런 다음 A에게
전해 주면, 자물쇠의 열쇠를 가지고 있는 A가 그 메시지를 열어보는 식이 된다. 중간에 그 메시지를 가로채는 사람은 그 열쇠를
가지고 있지 않으므로 메시지를 열람할 수 없다. 그리고 RSA의 디자인 상, 그 열쇠는 자물쇠의 형태만 보고서는 쉽게 제작할 수가
없게 되어 있다.
이와 같은 암호에 기본적인 이론을 재고하는 수학이 정수론이
다. 이런 아이디어를 수학 적으 로 말하면 암호화과정을 하나의 함수로 볼 때 암호의 해독과정은 그 함수의 역함수를 찾는 작업이다.
따라서 역함수를 구하기 매우 어려운 함수가 무궁무진하듯이 해독이 거의 불가능한 암호도 많은 것이다. 암호에 쓰이는 계산방법은
우리가 알고 있는 것과는 다르다. 하지만 모르는 사이에 우리는 메일 이런 계산을 하고 있다. 시간 계산의 예를 보자 5시에서
3시간 후는 8시이고 이것을 식으로 쓰면 3+5=8 이다. 그런데 11시에서 5시간 후는 4시이므로 11+5=4가 된다 이것을
12가법(NOD)인 계산이라고 한다. 12가 아닌 다른 것도 법이 될 수 있으며 덧셈과 뺄셈 외에도 곱셈과 나눗셈도 가능하다.
이러한 계산과 관련되어 페르마의 작은 정리
라는 것이 있다. X가 소수일 때 a의 x제곱은 x를 법으로 하는 a와 같다는 것이다. 요일계산을 예로 들면(이때 7이 법이다)
1일이 월요일인 달의 21일은 3의 7승이므로 이 정리에 의해 3일과 같은 요일 즉 수요일이 된다. 78년 미국 mit 의
리베스트 샤미르에이들만이 제안한 RSA 암호체계는 페르마의 작은 정리와 함정합수의 개념을 이용했다.
암
호화에 사용되는 법과 암호화열쇠는 공개하지만 암호문을 가로챈 제3자는 해독열쇠가 없어 암호를 읽을 수가 없도록 만든 것이다. 이 때
열쇠를 알아내는 방법은 자연수의 소인수 분해와 관련돼 있는데 수가 커지면 이것은 현실적으로 불가능하다. 예를 들어 1초에 1백만
번 연산을 할 수 있는 컴퓨터를 이용하여 현대에 알려진 가장 빠른 방법으로 계산해도 1백자리 숫자를 소인수 분해하는 데는
1백년이 걸린다고 한다. 더구나 재래식 방법으로는 우주의 역사보다도 긴 시간이 필요하다 따라서 이러한 암호체계는 소인수분해에 대한
새로운 수학적 발견 이 없다면 깨뜨리기가 불가능한 것이다.
실
제로 정수론을 전공하는 많은 수학자들이 효과적인 소수 판정방법과 소인수 분해 방법을 찾는 연구를 하고 있으며 연구결과가 군사기밀
혹은 기업비밀로 분류되기도 한다. 소수 판정방법의 연구가 안정한 암호화 열쇠를 만들기 위해 필요한 연구라면 소인수 분해방법의
연구는 이러한 암호체계를 깨뜨리기 위해 필요한 연구라고 할 수 있다. 한편 미국 버클리 대학의 렌스트라는 최근 타원곡선 이론을
써서 큰 수를 효과적으로 소인수 분해하는 기존의 방법과는 전혀 다른 새로운 방법을 발견하여 수학계에 충격과 희망을 주고 있다.
구 현
RSA 공개키 암호에 사용될 공개 키 {N,E}와 개인 키{N,D}를 생성하기 위해서는 먼저 모든 사용자들은 각각 다음의 작업을 수행하여야 한다.
① 두 개의 큰 소수 p와 q를 선정한 다음에 Modulus N = p * q와 PI(N)을 계산한다.
② 공개키 E는 PI(N) = (p - 1)(q - 1)과 서로 소의 관계가 되게 임의 로 선정한다.
③ E * D mon PI(N) = 1의 관계에 있는 개인키 D를 "확장된 유클리드 알고리즘"으로 구한다.
④ {E,N}을 공개키로 공개하고, {D,N}을 개인키로 자신이 안전하게 보관한다.
그
다음 RSA 암호의 암호화를 위해서는 먼저 암호화된 메시지를 받을 수신자의 공개키 {E, N}을 취득한 후에 암호화 할
평문M을 정수 M으로 전환하여 다음과 같은 암호화 작업을 수행한 결과인 암호문 C를 수신자에게 보내고, 수신자는 자신의 개인키를
이용한 복호화 작업을 통해서 원래의 평문M을 복원하게 된다.
RSA암호화 : E(M) = M ^ E mod N = C
RSA복호화 : D(C) = C ^ D mod N = ((M ^ E) ^ D) mod N = M
응 용
RSA
를 응용한 기술로는 전자서명 방식이 있다. 전자서명 방식에서는 송신자가 자신의 비밀키를 이용해 메시지를 복호화 알고리즘에 돌린
결과를 메시지와 함께 전송한다. 이 때 수신자 B는 송신자A의 공개키를 이용해 사인된 메시지를 암호화 알고리즘에 돌려 함께
전송되어온 메시지와의 관계로 사인의 진실 여부를 확인해 볼 수 있다.
한편, 인증 기능의 구조를 서명 등의 [본인 확인]의 케이스로 보면
① 수비 기능에서는 복호의 역할을 다한 비밀 키를 작용시켜 서명 문을 작성한다.
② 그 서명 문을 받은 사람은 서명인이 공개하고 있는 공개 키를 작용시켜 서명이 진짜인가, 어떤가를 확인한다는 것이다.
공개 키를 작용시킴으로써 만약 암호가 풀린다면 그 공개 키에 대응한 비밀 키로 서명되기 때문이어서 그 비밀 키는 서명자만의 비밀이기 때문에 본인 확인이 끝난 것으로 된다는 이론으로 된다.
참고문헌
댓글 없음:
댓글 쓰기