[암호학] 디피-헬만 키 교환 개념 설명 및 예제(Diffie-Hellman), 중간자 공격

 

 

디피-헬만 (Diffie-Hellman) 

디피-헬만(이하 DH)은 대칭키를 키 분배 센터(KDC, Key Distribution Center)없이 대칭키를 생성할 수 있는 암호 프로토콜을 의미합니다. KDC가 뭐냐하면 키를 분배하고 관리해주는 센터를 의미하는데요. 수 많은 호스트가 있는데 암호화 통신을 하려면 그 호스트들의 대칭키를 모두 가지고 있어야하니, KDC에게 키를 얻습니다. KDC는 물론 신뢰성이 큰 센터여야겠지요.  DH는 KDC없이도 대칭키를 서로 합의할 수 있도록 만들어줍니다. 아래의 그 과정을 봅시다.

우선 Alice와 Bob(암호학에서는 Alice와 Bob 이름에 친숙해지셔야합니다.)이 먼저 거쳐야 할 과정이 있습니다.

1) Alice와 Bob은 p와 g를 정하는데요. 매우 큰 300자리가 넘는 매우 큰 소수 p를 정합니다. 그리고 \(1 <= g <= p-1\)인 g를 정합니다. p와 g는 공개되어도 상관없습니다. 누구나 알아도 됩니다.

2) 그 후 Alice는 \(0 <= x < p-1\)인 x를 선택합니다. 이 사이의 수면 아무거나 상관없습니다. 그 후 R1=\(g^{x}\) mod p를 계산합니다. 여기서 mod는 모듈러 연산으로 \(g^{x}\)를 p로 나눈 나머지를 의미합니다. Alice가 정한 x는 Alice 본인만 알아야하는 값입니다. 절대 공개해서는 안되는 값입니다.

3) Bob도 역시 Alice와 마찬가지로 \(0 <= y < p-1\)인 y를 선택합니다. 그 후 R2=\(g^{y}\) mod p를 전달합니다.  y는 Bob만 알고 있어야합니다.

4) 이제 서로 R1과 R2를 당사자들에게 보냅니다. 

5) Alice는 R2\(^{x}\) mod p를 계산합니다. \((g^{y}\) mod p)\(^{x}\) mod p = \((g^{y})^{x}\) mod p = \(g^{yx}\) mod p로 이 값이 결국 대칭키 K가 됩니다.  

6) Bob도 역시 R1\(^{y}\) mod p 를 계산합니다. \((g^{x}\) mod p)\(^{y}\) mod p = \((g^{x})^{y}\) mod p = \(g^{xy}\) mod p로 이 값이 결국 대칭키 K가 됩니다.

결국 둘은 K=(g^{xy}\) mod p 인 대칭키를 갖고 있게 됩니다. 아래의 그림은 그 과정을 나타냅니다.(오타가 있네요. 아래 그림에 Bob이 생성한것은 R1이 아니라 R2입니다.) 

Diffie-Hellman

 

예제

이게껏 설명만 했는데 실제로 계산하는 과정을 보도록 하겠습니다.

Alice와 Bob은 p와 g는 11과 7로 설정했습니다. Alice는 x를 5로 선택하고 Bob은 y를 3으로 선택했다고 치겠습니다. R1=\(g^{5}\) mod p를 보내고, Bob은 R2=\(g^{3}\) mod p으로 하여 서로에게 보냅니다. 이제 Alice는 \((7^{3}\) mod 11)\(^{5}\) mod 11 = \((7^{3})^{5}\) mod 11 = \(7^{15}\) mod 11 의 값 K=10입니다. 이제 Bob도 역시 그렇게 계산을 하는데요. \((7^{5}\) mod 11)\(^{3}\) mod p = \((7^{5})^{3}\) mod 11 = \(7^{15}\) mod 11의 값은 역시 동일한 값으로 10임을 확인할 수 있습니다.

 

 

중간자 공격(Man-In-The-Middle-Attack)

만약 Alice와 Bob 사이에 공격자가 있다면 어떻게 될까요? 어찌 저찌 되어서 Alice가 Bob과 통신해야하는 것을 Eve로 착각했다고 합니다. Bob 역시 Alice와 통신을 해야하는데 Eve가 Alice로 알고 있다고 해봅시다. 그러면 Alice는 R1을 계산해서 Eve에게 주고, Bob도 R2를 계산해서 Eve에게 줍니다. Eve는 자신도 z를 정해서 R3를 양쪽 모두에게 전달해줍니다. 

이렇게 되면 Alice는 R3를 가지고 키 K1을 구할 수 있고 Eve 역시 위의 방법대로 K1을 구할 수 있습니다. Bob도 역시 R3를 가지고 K2를 구할 수 있게 되고 Eve 역시 K2를 구할 수 있습니다. 이제 공격자는 Alice와도 통신할 수 있고 Bob과도 통신할 수 있는 상황이 되었습니다. 공격자가 중간에 위치해서 민감한 정보를 모두 볼 수 있군요. 이런 공격 방식이 중간자 공격이라고 합니다.

man-in-the-middle attack

 

이산대수 공격

만약 Eve가 R1, R2를 가로챌 수 있다고 해봅시다. R1에서 x를 구하고, R2에서 y를 구할 수 있으면 K를 구하는 것을 쉽습니다. 그런 이산대수 공격에 대해서 안전하려면 p를 아주 매우 큰 소수로 정해놓아야합니다. 그래야 x,y를 구하기가 어렵거든요. p-1이 적어도 하나의 큰 소인수(60자리의 10진수 이상)을 가져야합니다. Alice와 Bob은 x,y를 사용 즉시 폐기하는 것이 좋습니다.

 

이상으로 디피-헬만 암호 프로토콜에 대해서 알아보았는데요. 모듈러 연산을 모르신다면 조금 어려울 수가 있는데요. 모듈러 연산에 대해서는 따로 시간을 내어 공부하시는 것이 좋을 듯 합니다. 쉽게 계산하는 규칙들도 존재하거든요. 디피-헬만은 ECC 암호화 알고리즘과 결합하여 사용하기도 합니다. ECDH라고도 하지요. 

DH에서 키를 구하는 문제가 이전 2016년 정보보안 기사 시험에 나온적이 있습니다.