암호학 - Public Key Cipher :: RSA 알고리즘 및 예제

Rivest Shamir Adleman

RSA 암호는 1978년 MIT의 리베스트, 샤미르, 에이들먼이 제안한 공개키 암호 알고리즘으로,
소인수분해 문제의 어려움에 이론적 기초를 둔 암호 알고리즘입니다.

※ 왼쪽부터 ... 샤미르, 리베스트, 에이들먼
※ 이 분들의 사진은 요기에서 ... http://www.ams.org/featurecolumn/archive/internet.html

RSA 암호의 기반이 되는 소인수분해 문제(Integer Factorization Problem)란 ...

간단히 말해서 임의의 소수를 이용하여 합성수를 만드는 것은 쉽지만,
합성수를 소인수분해 하여 소수로 만드는것은 어렵다는 거지요 ...

소인수분해 문제는 NP(비결정론적 다항식 시간)의 의미에서 어려운 문제라 알려져 있는데

간단히 예를 들면, 소수 19와 17의 곱으로 323 이라는 합성수를 만들긴 쉽지만
323 이라는 합성수를 보고 어떤 수의 곱으로 이루어졌는지 찾기위해서는 시간이 필요하다는것이지요

하물며 이런 작은 숫자가 아니라 300자리 이상의 소수의 곱으로 이루어진 RSA시스템에서
그 소인수분해를 하기란 시간적으로 매우 오래 걸린다는 것입니다

아무튼 이런 간단한(?) 원리를 이용하면서도 안전성이 높아 ...
(정확히 말하면 계산학적으로 풀기 어려운게 아니라 ... 시간적으로 오래 걸리기 때문에)

현재 널리 사용되고 있습니다 ...

사용되는 용도는 .... ... 현대인이라면 누구나 하나쯤 가지고 있다는 그 ... 공인인증서 ! ...
(은행 인터넷 뱅킹 페이지 등에 가시면 ... 본 사이트는 RSA 2048bit 으로 암호화 되어있습니다 와 같은 문구를 보실 수 있습니다)

여러가지 배경은 여기까지로 압축 하기로 하고,
본격적으로 알고리즘은 다음과 같습니다.

▷ 키 생성
  - 두 개의 큰 소수 p와 q를 선택하고, 이들의 곱 n=pq를 계산한다.
  - φ(n) = (p-1)(q-1)
  - n과 서로소인 e를 선택하고 de=1mod φ(n) 를 만족하는 수 d를 계산한다.
  - (n, e)는 공개키로 공개하고, d는 개인키로 보관한다. 

▷ 암호화
  - 메시지 m을 공개키(n,e)를 이용하여 c=m^e·mod n 로 암호화 한다.
 
▷ 복호화
  - 암호문 c를 자신의 비밀키 d를 이용하여 m = c^d·mod n 으로 복호화 한다.


그럼 RSA의 간단한 예를 들어보도록 하겠습니다.

▶ 키 생성
  p = 2357, q = 2551, n = pq = 6012707
  φ(n) = (p-1)(q-1) = 6007800
  e = 36749911 로 결정하면 유클리드 알고리즘을 이용하여 d = 422191로 구할 수 있습니다.
 여기서 n과 e 즉, 6012707과 36749911을 공개하고,  d = 422191을 개인키로 보관합니다.

▶ 암호화
  메시지 m = 5234673 이라면
  암호문  c=m^e·mod n = 5234673^3674911 mod 6012707 = 3650502
  즉, 메시지 m = 5234673을 공개키 n과 e를 이용하여 암호화 하면 암호문 c = 3650502를 얻습니다.

▶ 복호화
  메시지 m = c^d·mod n = 3650502^422191 mod 6012707 = 5234673
  암호문 c = 3650502를 개인키 d를 이용하여 복호화 하면 원래의 메시지 m = 5234673을 얻을 수 있습니다.

Reference
  [1] 한국전자통신연구원, "암호학의 기초", 1999

출처 - http://reinliebe.tistory.com/