[암호에 관하여...]네번째 - RSA

작성자 : 푸른하늘위로
편집자: 엔시스(sis@sis.pe.kr)

이번 주는 조금 늦었습니다. 어찌하다보니 마감일도 넘겼네요.
벌써 Posting을 시작한지 3주를 넘어 4주째에 이르고 있습니다. 부족한 실력으로, 글 솜씨로 여러 모로 고생하고 있습니다. 힘을 주시는 분들께 새삼 감사의 말을 드리면서.......



오늘은 공개키 암호 알고리즘인 RSA에 대해 쓰고자 합니다. 그럼 잠깐 공개키 암호 방식에 대해 알아보고 가겠습니다. 지금까지의 DES, AES의 경우에는 대칭(관용)암호 방식으로 공개키 암호 알고리즘과는 다른 방식이었습니다. 기본적으로 대칭 암호 방식은 하나의 Key를 사용하는 것에 비해, 공개키는 두 개의 서로 다른 Key(Public Key-공개키, Private Key-개인키)를 사용합니다. 주로 공개키는 암호화에, 개인키는 복호화에 사용됩니다.(몇몇 알고리즘의 경우 반대로 사용되는 경우도 있습니다.)

<공개키 알고리즘의 조건>
1. 키 쌍의 생성이 쉽다.
2. 암호문 생성과 암호문의 복호화가 쉽다.
3. 공개키로부터 개인키를 결정하는 것은 어렵다.
4. 공개키와 암호문으로부터 메시지의 복구가 어렵다.

그럼 이제 RSA에 대해 알아보겠습니다.

1997년 Rivest, Shamir, Adleman이 공동으로 개발한 이 알고리즘은 위의 조건을 만족하는 최초의 방식입니다.
평문과 암호문은 0과 n-1사이의 정수를 사용합니다.

 (n은 1024bit또는 309자리의 십진수를 사용합니다. n = p * q (p와 q는 소수))
평문은 블록으로 암호화 되는데, 각 블록의 크기는 log2(n)보다 작거나 같은 값을 가집니다.

M을 평문, C를 암호문이라고 하고, public key(공개키)는 {e(= (p-1, n}, private key(개인키)는 {d, n}이라 했을 때,

암호화 : C = Me mod n
복호화 : M = Cd mod n = (Me)d mod n = Med mod n
( a mod b : a를 b로 나누었을 때 나머지 )
( e는 (p-1)(q-1)와 서로소인 수, ed = 1 mod (p-1)(q-1) ) 

그럼 예를 들어 아주 짧은 key와 평문으로 public key와 private key의 생성, 암호화, 복호화 과정을 보겠습니다.

1) 2개의 소수를 선택합니다. ( p=17, q=11 )
2) n을 계산 합니다. ( n=17*11=187 )
3) (p-1)*(q-1)=16*10=160
4) 187과 서로소인 수 중, 하나를 선택하여 e의 값을 정합니다. ( e=7 )
5) d를 결정합니다. ( d*e=1 mod ((p-1)*(q-1))= 1 mod 160 ) ( d=23 )
6) 각각의 Key : public key(KUa) = {e, n} = {7, 187}
                      private key(KRa) = {d, n} = {23, 187} 

AES에 비하면 비교적 간단해 보입니다만, 실제로 개인키의 암호를 해독하려면 슈퍼컴퓨터로도 오랜 시간이 걸린다고 합니다. 그러나 단점으로 계산 량이 많아 휴대용 단말기 등에는 사용하기 어렵고 대신에 타원곡선 알고리즘이 사용된다고 합니다.