'Algorithm'에 해당되는 글 1건

  1. 2007.09.14 디피 헬만(Diffe-Hellman) 알고리즘 이해하기
정보기술2007. 9. 14. 10:10

Diffie& Hellman & Merkle


디피-헬만(
DiffieHellman) 알고리즘은 왠지 호감이 가는(?) 인상의

아저씨들이 1976년에 만든 알고리즘입니다.

(사진은 1977년의 것입니다. 왼쪽부터 Ralph Merkle, Martin Hellman, Whitfield Diffie)

원리는 간단히 이야기하자면,

 --- 아주 큰 2 개의 소수를 양쪽(peer)에서 공유하면서 시작합니다. ---

 소수(prime number)는 자신과 1 로만 나누어 지는 수를 말합니다. (2, 3, 5, 7, ...)

 일단 소수 1개(N)를 정의하여 두 노드간에 값을 공유합니다.

 소수 N의 크기가 매우 클수록 암호화 수준이 올라갑니다.

 G는 1부터 N-1 사이의 자연수입니다.

-- 여기까지는 이해가 물론 가시죠? --

 그러면 이상태에서, 

 한쪽(1번측이라고 봅시다)에서 공개키(public key)인 R1을 생성합니다.

 R1 = G^x mod N 입니다.

  (^는 승수를 의미하고, mod는 나머지를 의미합니다. 2^3=8 이고 10 mod 3 = 1 입니다.)

  이 때,  x 는 물론 1번측의 비밀키(private key)입니다. 

  비밀키(private key)는 공개키와 다르게 외부에 노출되면 안되는 값입니다.

  그리고 이 공개키인 R1 을 다른측(2번측)으로 전송합니다.

  R1은 통신(전송)을 할 경우 값이 외부로 값이 노출 될 수 있습니다.

  --- 여기까지는 이해가 가시죠? ---

   그리고 다른쪽(=2번측)에서도 마찬가지로 2번측의 공개키인 R2를 만듭니다.

   R2 = G^y mod N 입니다.

   이 때, y 는 2번측의 비밀키(private key)입니다. 당연히 y는 공개되면 안되죠.

   그리고 R2를 2번측에서 1번측으로 전송합니다.

   이제 양쪽은 다른 쪽이 전송한 수(R1,R2)를 서로서로 알고 있습니다.

   즉, 1번측에서는 2번측이 전송한 R2 를 알고 있고요, 

   반대로, 2번측에서는 1번측이 전송한 R1 을 알고 있습니다.

   단, 상대방의 비밀키(x, y)는 모릅니다. 비밀키는 자신만이 알고 있습니다.

  --- 여기까지도 이해가시리라 믿고요 ---

   그 상태에서 1번측은 

   전송받은 수 R2 를 가지고 K1 = R2^x mod N 값을 계산합니다.

   그리고 마찬가지로, 

   2번측도 전송받은 수 R1 으로 K2 = R1^y mod N 값을 계산합니다.

   그러면, 이때 K1 = K2 은 관계가 성립합니다!

  (둘은 수학적으로 동일하게 증명됩니다.)

   그리고, K1 = K2 = K = G^(xy) mod N 의 관계도 성립하게 됩니다.

   K는 1번측과 2번측 모두가 알 수 있는 키값입니다.

   --- 이제 서로 키 교환과 연산은 끝났습니다. ---

   마지막으로 생성된 키 K 를 이용하여서

  일반적인 세션키 알고리즘(AES, SEED 등)의 키로

  이용하는 것이 일반적인 사용방법입니다.

  --- 이해되시나요? 설명이 별로죠. 죄송합니다. ㅋ ---

   예전에는 귀찮아서 대충 라이브러리 함수로 대충 코딩했는데

   지금 정리해보니까 대충 이런 내용이군요 ㅎ





Posted by 어쩌다보니 Jay Two

댓글을 달아 주세요