암호학 - RSA 알고리즘 ( Rivest Shamir Adleman algorithm ), 공개키 암호 방식

2011. 4. 23. 02:53카테고리 없음

@ 공개키 암호 방식 ( Public key encryption system )


- 공개키 암호 방식에는 RSA, ElGamal, Merkle-Hellman의 Knapsack이 있다. 그 중 RSA에 대해서 알아 본다.




@ RSA ( Rivest Shamir Adleman)


- DES는 송신자와 수신자만이 알고 있는 동일한 대칭키를 이용하여 메시지를 암호화하고 복호화하고 있다. 이에 따른 문제점으로는


1. 키의 사전분배 문제


- 단체와 기업 같은 폐쇄적인 사용자들은 용이하나 인터넷 같은 개방형 시스템에서는 동일한 대칭키를 보유하는 것이 위험성이 있다.


2. 여러 사용자와 사용하려면 많은 수의 대칭키가 필요하게 되고 대칭키의 생성과 분배는 시스템의 효율성을 저하시키고, 많은 수의 대칭키의
유지, 관리가 어렵다.


- RSA는 서로 연관성이 있는 상이한 두 개의 키를 각각 암호화와 복호화에 이용한다.


- 송신자는 메시지 m을 공개키로 암호화하여 수신자에게 보내면 수신자는 자기만이 알고 있는 개인키로 복호화 한다.


- 모든 사용자는 자기만의 한 쌍의 공개키와 개인키를 가지며 공개키는 자기에게 메시지를 보내려는 사람에게 모두 제공해 주고, 개인키는 자신
만이 알고 있어야 한다.


- 공개키 암호 시스템은 키의 사전분배 문제를 해결하고, 디지털 서명과 같은 새로운 개념을 출현 시켰다.


- 큰 소인수의 곱을 인수분해 하는 수학적 알고리즘 이용




@ 공개키 암호 시스템은 일방향 함수를 이용


1. 일방향 함수


- x가 주어지면 y=f(x)의 계산이 용이한 반면, y가 주어졌을 때 x를 구하기 위한 f(x)의 역함수를 구하는 것이 불가능한 함수 f(x)를 말한다.

ex) 두 개의 매우 큰 소수의 곱 -> p와 q가 매우 큰 소수이면 n=p*q의 계산은 용이한 반면, 합성수인 n에서 p와q를 구하는 것은 아주 어려운 작업이다.


2. 공개키 암호 시스템은 이 일방향 함수를 이용한다. 즉 공개키로 암호화 하는 것은 f(x)는 용이하고, 수신자만이 알고 있는 비밀 키는 f(x)의 역함수를 구하는 비밀 통로의 역할을 한다.




@ RSA 공개 암호 시스템의 키 값의 구현


- RSA 공개키 암호에 사용될 공개키 {N,E}와 개인키 {N,D}를 생성하기 위해서는 먼저 모든 사용자들은 각각 다음의 작업을 수행


1. 두 개의 큰 소수 p와 q를 선정한 다음에 Modulus N = p * q와 PI(N)을 계산한다.


2. 공개키 E는 PI(N) = (p-1)(q-1)과 서로소의 관계가 되게 임의로 선정한다.


3. E*D mon PI(N) = 1의 관계에 있는 개인키 D를 “확장된 유클리드 알고리즘”으로 구한다.


4. {E,N}을 공개키로 공개하고, {D,N}을 개인키로 자신이 안전하게 보관한다.

- RSA 암호화 (암호화 하여는 수는 M)


E(M) = M ^ E mod N = C


- RSA 복호화


D(C) = C ^ D mod N = ((M^E)^D) mod N = M


ex) n = p*q = 47*71 = 3337 공개키 E는 (p-1)(q-1) = 46*70 = 3220과 서로소의 관계에 있는 임의의 정수 79로 선정한다. 따라서 개인키는 “확장된 유클리드 알고리즘”을 이용하여 d = 1019가 된다. 평문 m = 688은 암호문 c = 688^79 mod 3337 = 1570으로 암호화 된다. 개인키 d=1019를 사용하여 다시 암호문 c=1570은 평문 m=1570^1019 mod 3337로 복호화가 된다.




@ RSA의 대표적인 사용 예 -> 전자서명 (Digital Signature)




- 보통 어떠한 종이문서에 검수자의 서명이 되어 있으면 독자에게 신뢰를 줄 수 있다. 문서에 서명이 되어 있다는 것은 문서의 내용이 정확하고 누군가에 의해 검증이 되었다는 뜻이기 때문이다. 전자서명도 이와 마찬가지다. 차이점은 종이문서 대신 디지털 문서에 서명을 하는 것이다. 전자서명은 크게 서명(Signing)과 인증(Verification) 두 가지 과정으로 나뉜다. 서명은 문서가 검증되었음을 알리는 과정이고, 인증은 독자가 해당 문서에 서명이 되었는지를 확인하는 과정이다.


- 원리는 문서 데이터의 해쉬(hash)값을 비교해서 일치하는지 여부를 검증하는 것이다. 서명자는 문서의 데이터를 해쉬함수(hash function)를 통해 해쉬값을 생성하고, 생성된 해쉬값을 비밀키(Private Key)로 암호화한 후 문서에 첨부한다. 반대로 서명된 문서인지 검증하기 위해서 서명 부분을 따로 떼내어 공개키(Public Key)로 복호화하고, 문서에서 서명을 제외한 데이터를 다시 같은 해쉬함수를 통해 해쉬값을 얻어낸다. 두가지 값이 일치하는지 확인하여 일치하면 서명된 문서이고, 그렇지 않으면 서명되지 않은 문서인 셈이다.