펌)공개키 암호화 알고리즘

암호의 역사는 로마 시대로 까지 거슬러올라간다고 하지만 인터넷을 통해 수많은 금융 거래가 이루어지있는 요즘 처럼 암호화된 통신이 널리 사용되는 때도 아마 없을 것이다. 실제로 어떤 파일 혹은 문장을 인터넷상의 다른 사용자에게 비밀리에 전송하려고 할 때 어떤 방법을 사용할 수 있을까? 가장 먼저 생각할 수 있는 것은 우리가 흔히 zip 파일을 압축할 때 이용하는 대칭키 알고리즘(혹은 비밀키 알고리즘)이다. 이 방식에서는 암호화하는 측과 암호를 푸는 측이 같은 키를 이용한다. 그러나 인터넷 상의 정보는 언제든지 훔쳐보기가 가능하기 때문에 이 방법은 네트웍상의 통신에 적용하기에 적절하지 않다. 암호(비밀키)를 인터넷을 통해 주고 받는 것이 불가능하기 때문이다.

그리하여 나오게 된 것이 공개키 알고리즘인데 공개키 알고리즘은 암호화 할 때 사용하는 암호와 암호를 풀 때 사용하는 암호가 서로 다르다. 서로 다른 키를 사용함으로서 비밀리에 키를 교환할 필요 자체가 없어졌다. 제 3 자는 암호화키를 알고 있더라도 암호문을 풀 수 없으므로 암호화할 때 사용하는 키는 중간에 누가 가로채도 상관없다. 아니 오히려 사용하기 편하게 잘 보이는 곳에 놔두는 것이 좋을 것이다. 누구든지 이 공개키로 메시지를 암호화해서 보내면 그 메시지를 받는 사람은 숨겨둔 비밀키(혹은 개인키라고도 한다)를 이용하여 이를 풀어볼 수 있다. 얼핏 생각하면 믿기 힘든 이러한 일이 수학의 마술로 인해 가능해 졌다.


소개

공개키 알고리즘의 대표적인 RSA는 1977년에 Ron Rivest, Adi Shamir와 Leonard Adleman에 의해 개발되었다. RSA는 큰 수의 소인수 분해가 매우 어렵다는 사실을 이용한다. 현재 슈퍼컴퓨터와 복잡한 수학적 기법들을 이용해 155자리 합성수가 인수분해 되었는데(1999년 8월) 155를 2진수로 표현하면 512 비트이기 때문에 흔히 RSA에서 사용하는 키는 이보다 길이가 2배 긴 1024비트를 이용한다.


RSA의 원리

집합 ${1, 2, ... , n-1}$ 의 원소들 중에서 $n$ 과 서로소의 관계에 있는 원소들의 개수를 $φ(n)$으로 나타내고 이를 Euler의 $φ$-function이라고 한다. 특별히 소수 $p$에 대해서 $φ(p) = p-1 $이다. 큰 정수 $n$에 대해 $φ(n)$의 값을 알기 위해서는 $n$의 소인수 분해가 필수적이다. 즉, $n$이 두 소수 $p$와 $q$의 곱일 때 $φ(n) = (p-1)(q-1)$이다. 따라서 소인수 분해 없이 $φ(n)$을 구하기는 매우 어렵다. Euler의 정리란, 서로 소인 두 양의 정수 $a, n$에 대해 $a^{φ(n)} ≡ 1 $(mod n) 이 성립한다는 것이다.

Step 1
두개의 큰 소수 $p, q$를 선정하여 자신의 비밀열쇠로 한다
Step 2
$n = pq$인 $n$을 공개하고 $φ(n)$과 서로 소인 임의의 정수 $e$를 선택하여 공개키로 한다.
Step 3
$ed ≡ 1 (mod φ(n))$ 이 되는 $d$를 Euclidean Algorithm등으로 계산하여 비밀 열쇠로 한다.
즉, $p$와 $q$ 그리고 $d$는 비밀 열쇠로, $n$과 $e$는 공개키로 한다.

암호화 Step
평문 $M$을 공개키 $e$를 사용하여 $M^e$를 계산한 다음 modular $n$으로 간단히 한다.
즉 암호문 $C$는 다음과 같다. $C = M^e$ (mod n)

복호화 Step.
암호문 $C$를 비밀열쇠 $d$를 이용하여 $C^d $한 다음 modular $n$으로 간단히 한다.
다시 평문이 나오게 되는 관계식은 다음과 같다.
$C^d ≡ (M^e)^d = M^{tφ(n)+1} = M^{φ(n)t }M ≡ M$ (mod n)
여기서$ t$는 $ed ≡ 1 (mod φ(n))$에서 유도되는$ ed = tφ(n)+1 $을 만족하는 정수이다.


실제 사용 예

예를 들어 설명하면 다음과 같다. RSA 암호화 기법에는 $e$(공개키:public key), $d$(비밀키:private key), $n$(modulus)가 필요하다.
암호화하는데에는 $e$와 $n$, 복호화하는데에는 $d$와 $n$이 이용된다. 암호문을 C 평문을 M라고 하자.

암호화 :$C = M^e$ mod $n$
해독: $M = C^d$ mod $n$

단, 여기서 평문의 비트수는 (modulus)의 비트수보다 작아야 한다. 따라서 실제의 메세지를 $n$보다 작거나 같은 길이로 잘라서 입력해야 한다. 좀 더 구체적인 예를 들기 위해서 이번에는 크기가 매우(!) 작은 수를 이용하여 위의 과정을 따라가 보자. $p=7,q=17$이라고 하면 $n=119$이고 $\phi (7)=6, \phi (17)=16, \phi (119)=96$이다. $96$과 서로소인 $5$를 공개하고 $5 \times 77 =1$(mod 119)인 77을 비밀키로 정한다.
공개키(public key) $e= 5 $
비밀키(private key) $d= 77 $
modulus $n= 119 $
비밀키를 자신이 소유하고 공개키는 안전한 공개키 디렉토리에 등록한다.
그런 다음 아스키코드 한자리 $a=65$를 전송한다고 해 보자.(아스키코드는 $7$비트 이내에 있으므로 7비트 짜리 modulus로 전송할 수 있다.)

암호화 : $65^5$ mod 119 = 46
복호화 : $46^{77}$ mod 119 = 65

잘 작동한다는 것을 알 수 있다.

https://en.wikipedia.org/wiki/RSA_(cryptosystem)