암호화 기법 : RSA [Rivest Shamir Adleman]

소개

공개키 알고리즘의 대표적인 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를 사용하여 Me를 계산한 다음 modular n으로 간단히 한다.
즉 암호문 C는 다음과 같다. C = Me (mod n)

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

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

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

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

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

중간자공격 [中間子攻擊, man-in-the-middle attack]