암호의 역사는 로마 시대로 까지 거슬러올라간다고 하지만 인터넷을 통해 수많은 금융 거래가 이루어지있는 요즘 처럼 암호화된 통신이 널리 사용되는 때도 아마 없을 것이다. 실제로 어떤 파일 혹은 문장을 인터넷상의 다른 사용자에게 비밀리에 전송하려고 할 때 어떤 방법을 사용할 수 있을까?
가장 먼저 생각할 수 있는 것은 우리가 흔히 zip 파일을 압축할 때 이용하는 대칭키 알고리즘(혹은 비밀키 알고리즘)이다. 이 방식에서는 암호화하는 측과 암호를 푸는 측이 같은 키를 이용한다. 그러나 인터넷 상의 정보는 언제든지 훔쳐보기가 가능하기 때문에 이 방법은 네트웍상의 통신에 적용하기에 적절하지 않다. 암호(비밀키)를 인터넷을 통해 주고 받는 것이 불가능하기 때문이다.
그리하여 나오게 된 것이 공개키 알고리즘인데 공개키 알고리즘은 암호화 할 때 사용하는 암호와 암호를 풀 때 사용하는 암호가 서로 다르다. 서로 다른 키를 사용함으로서 비밀리에 키를 교환할 필요 자체가 없어졌다. 제 3 자는 암호화키를 알고 있더라도 암호문을 풀 수 없으므로 암호화할 때 사용하는 키는 중간에 누가 가로채도 상관없다. 아니 오히려 사용하기 편하게 잘 보이는 곳에 놔두는 것이 좋을 것이다. 누구든지 이 공개키로 메시지를 암호화해서 보내면 그 메시지를 받는 사람은 숨겨둔 비밀키(혹은 개인키라고도 한다)를 이용하여 이를 풀어볼 수 있다. 얼핏 생각하면 믿기 힘든 이러한 일이 수학의 마술로 인해 가능해 졌다.
소개
공개키 알고리즘의 대표적인 RSA는 1977년에 Ron Rivest, Adi Shamir와 Leonard Adleman에 의해 개발되었다. RSA는 큰 수의 소인수 분해가 매우 어렵다는 사실을 이용한다. 현재 슈퍼컴퓨터와 복잡한 수학적 기법들을 이용해 155자리 합성수가 인수분해 되었는데(1999년 8월) 155를 2진수로 표현하면 512 비트이기 때문에 흔히 RSA에서 사용하는 키는 이보다 길이가 2배 긴 1024비트를 이용한다.
RSA의 원리
집합 1,2,...,n−11,2,…,n−1 의 원소들 중에서 nn 과 서로소의 관계에 있는 원소들의 개수를 φ(n)φ(n)으로 나타내고 이를 Euler의 φφ-function이라고 한다. 특별히 소수 pp에 대해서 φ(p)=p−1φ(p)=p−1이다. 큰 정수 nn에 대해 φ(n)φ(n)의 값을 알기 위해서는 nn의 소인수 분해가 필수적이다. 즉, nn이 두 소수 pp와 qq의 곱일 때 φ(n)=(p−1)(q−1)φ(n)=(p−1)(q−1)이다. 따라서 소인수 분해 없이 φ(n)φ(n)을 구하기는 매우 어렵다. Euler의 정리란, 서로 소인 두 양의 정수 a,na,n에 대해 aφ(n)≡1aφ(n)≡1(mod n) 이 성립한다는 것이다.
Step 1
두개의 큰 소수 p,qp,q를 선정하여 자신의 비밀열쇠로 한다
Step 2
n=pqn=pq인 nn을 공개하고 φ(n)φ(n)과 서로 소인 임의의 정수 ee를 선택하여 공개키로 한다.
Step 3
ed≡1(modφ(n))ed≡1(modφ(n)) 이 되는 dd를 Euclidean Algorithm등으로 계산하여 비밀 열쇠로 한다.
즉, pp와 qq 그리고 dd는 비밀 열쇠로, nn과 ee는 공개키로 한다.
암호화 Step
평문 MM을 공개키 ee를 사용하여 MeMe를 계산한 다음 modular nn으로 간단히 한다.
즉 암호문 CC는 다음과 같다. C=MeC=Me (mod n)
복호화 Step.
암호문 CC를 비밀열쇠 dd를 이용하여 CdCd한 다음 modular nn으로 간단히 한다.
다시 평문이 나오게 되는 관계식은 다음과 같다.
Cd≡(Me)d=Mtφ(n)+1=Mφ(n)tM≡MCd≡(Me)d=Mtφ(n)+1=Mφ(n)tM≡M (mod n)
여기서tt는 ed≡1(modφ(n))ed≡1(modφ(n))에서 유도되는ed=tφ(n)+1ed=tφ(n)+1을 만족하는 정수이다.
실제 사용 예
예를 들어 설명하면 다음과 같다. RSA 암호화 기법에는 ee(공개키:private key), dd(비밀키:public key), nn(modulus)가 필요하다.
암호화하는데에는 ee와 nn, 복호화하는데에는 dd와 nn이 이용된다. 암호문을 C 평문을 M라고 하자.
암호화 :C=MeC=Me mod nn
해독: M=CdM=Cd mod nn
단, 여기서 평문의 비트수는 (modulus)의 비트수보다 작아야 한다. 따라서 실제의 메세지를 nn보다 작거나 같은 길이로 잘라서 입력해야 한다. 좀 더 구체적인 예를 들기 위해서 이번에는 크기가 매우(!) 작은 수를 이용하여 위의 과정을 따라가 보자. p=7,q=17p=7,q=17이라고 하면 n=119n=119이고 ϕ(7)=6,ϕ(17)=16,ϕ(119)=96ϕ(7)=6,ϕ(17)=16,ϕ(119)=96이다. 9696과 서로소인 55를 공개하고 5×77=15×77=1(mod 119)인 77을 비밀키로 정한다.
공개키(public key) e=5e=5
비밀키(private key) d=77d=77
modulus n=119n=119
비밀키를 자신이 소유하고 공개키는 안전한 공개키 디렉토리에 등록한다.
그런 다음 아스키코드 한자리 a=65a=65를 전송한다고 해 보자.(아스키코드는 77비트 이내에 있으므로 7비트 짜리 modulus로 전송할 수 있다.)
암호화 : 655655 mod 119 = 46
복호화 : 46774677 mod 119 = 65
잘 작동한다는 것을 알 수 있다.
