지난 글 : [알고리즘/알고리즘 도감] - 하이브리드 암호 방식
디피-헬만 키 교환법(Diffie-Hellman key exchange)은 양자 간에 안전히 키를 교환하기 위한 기법이다. 두 명이 공유하는 비밀의 수를 공개된 수와의 연산에 사용해 양자 간의 공통 키를 안전히 교환할 수 있다.
1
1. 두 개의 키를 합성하는 특별한 방법이 있다고 하자. 이 합성 방법으로 키 P와 S를 합성해 키 P-S가 만들어진다.
2. 이 합성 방법에는 세 가지 특성이 있다.
3. 첫 번째는 키 P와 P를 이용해 합성한 P-S가 있다해도 S를 추출하는 것은 불가능하다.
4. 두 번째는 합성된 키를 새로운 키와 합설할 수 있다는 것이다. P를 P-S와 합성해 P-P-S가 만들어진다.
5. 세 번째는 키의 합성 결과는 순서에 상관 없으며, 어떤 키를 사용했는지가 중요하다.
2
위 합성 방법을 사용해 A와 B 사이에 키를 안전히 교환해보자.
1. 먼저 A가 키 P를 준비한다.
2. A가 B에게 키 P를 전달한다.
3. 다음으로 A와 B가 각각 비밀키 SA와 SB를 준비한다.
4. A는 P와 SA로부터 새로운 키 P-SA를 합성한다.
5. B도 P와 SB로부터 새로운 키 P-SB를 합성한다.
6. A가 B에게 키 P-SA를 보낸다. B도 A에게 키 P-SB를 보낸다.
7. A는 비밀키 SA와 B에게서 받은 P-SB를 합성해 새로운 키 SA-P-SB를 얻는다.
8. B도 비밀키 SB와 A에게서 받은 P-SA를 합성해 새로운 키 SB-P-SA를 얻는다. A, B 모두 P-SA-SB를 갖는다.
이 키를 암호키, 복호키로 사용할 수 있다.
3
이 키 교환법의 안전성을 검증해보자.
1. 키 P, P-SA, P-SB는 인터넷을 경유해 전송되기에 제삼자 X가 훔쳐볼 가능성이 있다.
2. 하지만 X가 얻은 키로는 P-SA-SB를 합성할 수 없기에 이 키 교환법은 안전하다 볼 수 있다.
4
이 키 교환법을 수식으로 표현해보자. 우선 준비할 것은 키 P로, 수식에서는 P와 G라는 두 개의 정수로 표현된다. P는 매우 큰 소수이고, G는 소수 P에 대응하는 '생성자(또는 원시근(primitive root))'라고 하는 숫자로부터 하나 선택한다.
1. 먼저 A가 소수 P와 생성자 G를 준비한다. 이들은 제삼자에게 노출되어도 괜찮다.
2. A가 소수 P와 생성자 G를 B에게 전달한다.
3. 다음으로 A와 B가 비밀값 X와 Y를 준비한다. 비밀값 X와 Y는 P - 2보다 작아야 한다.
4. A와 B는 '(G를 비밀값으로 제곱)mod P'를 계산한다. mod는 나눗셈의 나머지를 구하는 연산이다.
'G mod P'는 G를 P로 나누었을 때 나머지 값을 구한다. 이 계산은 이론상의 '합성'에 해당한다.
5. A와 B는 계산 결과를 서로 교환한다.
6. A와 B는 서로에게서 받은 수를 자신의 비밀키로 제곱하고 mod P를 계산한다.
A와 B의 계산 결과가 같다.
5
이 키 교환법의 안정성을 검증해보자.
1. 제삼자가 통신을 훔쳐본다 해도 발견한 숫자로는 A와 B가 공유하는 숫자를 계산할 수 없다.
2. 또한, 비밀값 X나 Y를 구하는 것도 불가능하다.
3. 따라서 디피-헬만 키 교환법은 이 상태에서는 안전하다 볼 수 있다.
디피-헬만 키 교환법은 Diffie와 Hellman이 고안해 이름이 이처럼 붙여졌다 한다. 디피=헬만 키 교환법은 키를 실제로 교환하는 것이 아니라 공개해도 괜찮은 정보를 양자 간 교환하면 키가 교환되는 기법이다. 아마도 생성자(G)를 교환해 생성하는 것 같다.
참고 서적 :
