가장 이해하기 간단한 키 교환 방법은 RSA 암호 시스템을 이용하는 것이다.
1. Mr 블릭에게 비밀키 k를 전달하려면 우선 Mr. 블릭의 공개키로 k를 암호화한다.
2. Mr. 블릭은 자신의 비밀키를 써서 수신된 메세지 e를 푼 다음 키 k를 얻는다.
RSA 키 교환은 대칭키 암호에 필요한 키를 한 사람이 일방적으로 선택한다는 단점만 빼고는 거의 완벽하다. 그러나 상호 통신교환에 필요한 키는 서로 동의한 상태에서 사용하는 것이 바람직하다. 아니면 앞에서 말한 TA가 적절히 개입하여 키 교환을 도와 주는 방법이 서로 믿을 수 있고 간편할 것이다.
TA의 도움 없이 서로 동의할 수 있는 키 교환 프로토콜로 간단한 것은 Diffie-Hellman 키 교환이다. 이 방법은 '지수 키 교환'이라고도 부르는데, 우선 수학적으로 설명한 다음 쉽게 예를 들어 설명하겠다.
비밀키를 공유하고자 하는 두 사람은 우선 정수 p와 s < p인 s를 서로 약속한다. 이때 s는 Φ(p - 1)과 서로 소인 수로 택한다. 이 수들은 공개되어 모든 사람들이 알아도 상관없다.
1. A와 B는 정수 a, b < p를 각자 선택한 다음 A는 α ≡ s^a (mod p)를 계산하고, B는 β ≡ s^b (mod p)를 계산한다.
2. 계산 결과를 서로 교환한다.
3. 그런 다음 A와 B는 각각 β^a (mod p)와 α^b (mod p)를 계산한다.
4. α^b ≡ (s^a)^b ≡ s^(ab) (mod p)이고, β^a ≡ (s^b)^a ≡ s^(ab) (mod p)이므로 두 사람 모두 같은 수 k ≡ s^(ab) (mod p)를 공유하게 된다.
이 수 k는 직접 공통 키로 채택할 수도 있고, 사용하려는 대칭 알고리즘에 적합하도록 고쳐서 쓸 수도 있다. 예를 들어 k를 이진법 수로 고친 다음 처음 56비트만 택할 수도 있다.
Diffie-Hellman 키 교환의 안정성은 어느 정도일까? 오스카가 α, β를 알고 있다고 하자. 만약 그가 α로부터 a를, β로부터 b를 알 수 있다면, A, B가 한 것처럼 k를 계산할 수 있다. 그러나 s^a ≡ α (mod p)에서 a를 알아내기는 매우 어렵다. 이와 같이, s^a (mod p)에서 a를 알아내는 것을 이산대수 문제(discrete logarithm problem)라고 한다.
이 문제를 풀기가 얼마나 어려운지 예를 들어 보자. p = 11, s = 4라고 하자. A의 입장에서는,
s^4 ≡ 4^4 ≡ 4^2 * 4^2 ≡ 5 * 5 ≡ 3 (mod 11)
이것을 계산하는 것은 쉽다. 그러나 오스카는 단지 s^a ≡ 4^a ≡ 3 (mod 11)만 알고 있으므로, a를 알기는 상대적으로 매우 어렵다. 오스카가 아주 비범한 계산 능력을 가지고 있다고 하면, 이론적으로 α와 β를 가지고 비밀키 k를 알아낼 가능성이 있다. 하지만 아직까지 그런 방법을 발견한 사람은 없다.
이 키 교환은 p^m (p는 소수)개의 문자를 쓸 수도 있다. m > 1이면 정수 Z(p^m)을 쓰지 않고 p^m 개의 원소를 갖는 유한체, GF(p^m)을 사용한다. 최근에는 이 책의 정도를 넘는 고난도의 이산대수 문제도 나와있다. 그러나 Diffie-Hellman 키 교환 방식을 깨는 것이 이산대수 문제를 해결하는 것과 동치라는 것도 아직 증명되지 못했다.
Diffie-Hellman 키 교환의 장점은, '비밀키를 공유한 적이 없는 두 사람이, 공개적으로 논의해서 두 사람만이 비밀키를 공유할 수 있다'는 것이다. 그러나 이 프로토콜도 중간자 공격(man-in-the-middle attack)이라고 하는 오스카의 공격으로부터 안전하지 못할 수도 있다.
Reference
최병문, 이영환(2007), 암호의 세계, 경문사
1. Mr 블릭에게 비밀키 k를 전달하려면 우선 Mr. 블릭의 공개키로 k를 암호화한다.
2. Mr. 블릭은 자신의 비밀키를 써서 수신된 메세지 e를 푼 다음 키 k를 얻는다.
RSA 키 교환은 대칭키 암호에 필요한 키를 한 사람이 일방적으로 선택한다는 단점만 빼고는 거의 완벽하다. 그러나 상호 통신교환에 필요한 키는 서로 동의한 상태에서 사용하는 것이 바람직하다. 아니면 앞에서 말한 TA가 적절히 개입하여 키 교환을 도와 주는 방법이 서로 믿을 수 있고 간편할 것이다.
TA의 도움 없이 서로 동의할 수 있는 키 교환 프로토콜로 간단한 것은 Diffie-Hellman 키 교환이다. 이 방법은 '지수 키 교환'이라고도 부르는데, 우선 수학적으로 설명한 다음 쉽게 예를 들어 설명하겠다.
비밀키를 공유하고자 하는 두 사람은 우선 정수 p와 s < p인 s를 서로 약속한다. 이때 s는 Φ(p - 1)과 서로 소인 수로 택한다. 이 수들은 공개되어 모든 사람들이 알아도 상관없다.
1. A와 B는 정수 a, b < p를 각자 선택한 다음 A는 α ≡ s^a (mod p)를 계산하고, B는 β ≡ s^b (mod p)를 계산한다.
2. 계산 결과를 서로 교환한다.
3. 그런 다음 A와 B는 각각 β^a (mod p)와 α^b (mod p)를 계산한다.
4. α^b ≡ (s^a)^b ≡ s^(ab) (mod p)이고, β^a ≡ (s^b)^a ≡ s^(ab) (mod p)이므로 두 사람 모두 같은 수 k ≡ s^(ab) (mod p)를 공유하게 된다.
이 수 k는 직접 공통 키로 채택할 수도 있고, 사용하려는 대칭 알고리즘에 적합하도록 고쳐서 쓸 수도 있다. 예를 들어 k를 이진법 수로 고친 다음 처음 56비트만 택할 수도 있다.
Diffie-Hellman 키 교환의 안정성은 어느 정도일까? 오스카가 α, β를 알고 있다고 하자. 만약 그가 α로부터 a를, β로부터 b를 알 수 있다면, A, B가 한 것처럼 k를 계산할 수 있다. 그러나 s^a ≡ α (mod p)에서 a를 알아내기는 매우 어렵다. 이와 같이, s^a (mod p)에서 a를 알아내는 것을 이산대수 문제(discrete logarithm problem)라고 한다.
이 문제를 풀기가 얼마나 어려운지 예를 들어 보자. p = 11, s = 4라고 하자. A의 입장에서는,
s^4 ≡ 4^4 ≡ 4^2 * 4^2 ≡ 5 * 5 ≡ 3 (mod 11)
이것을 계산하는 것은 쉽다. 그러나 오스카는 단지 s^a ≡ 4^a ≡ 3 (mod 11)만 알고 있으므로, a를 알기는 상대적으로 매우 어렵다. 오스카가 아주 비범한 계산 능력을 가지고 있다고 하면, 이론적으로 α와 β를 가지고 비밀키 k를 알아낼 가능성이 있다. 하지만 아직까지 그런 방법을 발견한 사람은 없다.
이 키 교환은 p^m (p는 소수)개의 문자를 쓸 수도 있다. m > 1이면 정수 Z(p^m)을 쓰지 않고 p^m 개의 원소를 갖는 유한체, GF(p^m)을 사용한다. 최근에는 이 책의 정도를 넘는 고난도의 이산대수 문제도 나와있다. 그러나 Diffie-Hellman 키 교환 방식을 깨는 것이 이산대수 문제를 해결하는 것과 동치라는 것도 아직 증명되지 못했다.
Diffie-Hellman 키 교환의 장점은, '비밀키를 공유한 적이 없는 두 사람이, 공개적으로 논의해서 두 사람만이 비밀키를 공유할 수 있다'는 것이다. 그러나 이 프로토콜도 중간자 공격(man-in-the-middle attack)이라고 하는 오스카의 공격으로부터 안전하지 못할 수도 있다.
Reference
최병문, 이영환(2007), 암호의 세계, 경문사