Diffie–Hellman key exchange 이론 및 중간자 공격

서론

사실 크립토는 하고싶지 않았다...

근데 어쩔 수 없이 해야겠다 ㅠㅠ

 

디피-헬먼 키 교환은 공개 키 교환 알고리즘의 시조새이다.

기본 중의 기본이라는 소리.

 

Diffie–Hellman key exchange 이론

뭐 이산 대수(이산 로그)니 뭐니,

에서 g, x, p를 알면 y를 구할 수 있지만, g, p, y를 알때 x를 구하기 어렵다는

이런 복잡한 문제는 일단 제껴두고, 저 공식을 풀어서 이야기하자면

를 이야기한다.

 

일단 그렇다치고, 최종적으로 서로 가질 키의 공식은

이다.

 

1. 기본 값 교환.

왜인지 모르겠지만 allice와 bob이 그 대상이다.

외국판 철수와 영희인가보다.

 

앨리스는 소수 p 그리고 정수 g를 선택해서 밥에게 공유한다.

이때 g는

인 수이다.

여기서 g와 p는 공개되어도 무관하다.

왜냐하면 결국 계산되는 값은 위 공식에서 a와 b에 달렸기 때문이다.

 

2. 각자 값 계산.

앨리스는 이산로그에서 x를 임의로 정해서 y를 계산한다.

여기서 앨리스의 x를 a, y를 A라고 하자.

즉

는 곧

가 된다.

 

마찬가지로 밥도 x를 임의로 정해서 y를 계산한다.

여기서 밥의 x를 b, y를 B라고 하자.

 

3. 결과값의 교환 및 재 계산.

이렇게 계산된 A와 B를 서로에게 전송한다.

그리고난 뒤 받은 값을 g 값으로 사용해 다시 한번 계산해준다.

 

그러므로 앨리스는 

를 가지게되고,

 

밥은 

를 가지게 된다.

 

여기서 A와 B는 다시 한번 값을 치환할 수 있기 때문에 최종적으로

앨리스는

밥은

를 가지게된다.

즉

로 같은 값을 가지게 되며, 암호화된 값을 이 키 값으로 복호화할 수 있다.

 

 

중간자 공격

앞서 이야기한 것과 같이 다른 값들을 알아도 앨리스와 밥이 가진 a와 b는 알기 어렵다.(고 한다.)

그러므로 서로 값을 주고 받는 과정에서 도청을 통해 g, p, A, B 값을 알 수 있겠지만 결국 a와 b 값은 알아낼 수 없으며, 이로 인해 K 값을 구할 수 없게 된다.

 

하지만, 서로 값을 주고 받는 과정에서 개입할 수 있게 되면 어떻게될까.

 

공격자 W가 앨리스와 밥의 통신 과정을 도청한다고 가정하자.

g와 p는 공개된 값이기에 공격자도 

와 같은 꼴의 값을 만들 수 있다.

이를 

라고 가정하자.

 

앨리스가 밥에게 보낼 A 값을 공격자가 가로채서 애초에 앨리스가 돌려받아야할 값 B가 아닌 W를 전달 했다고 가정하면

앨리스와 공격자는 서로

의 키 값을 가지게 된다.

마찬가지로 밥도

의 값을 서로 가지게 된다.

공격자는 이를 통해 중간에서 도청할 수 있다.

 

결론

어렵다.

 

참고자료

https://ko.wikipedia.org/wiki/%EB%94%94%ED%94%BC-%ED%97%AC%EB%A8%BC_%ED%82%A4_%EA%B5%90%ED%99%98

디피-헬먼 키 교환 - 위키백과, 우리 모두의 백과사전

실제 계산하는 부분을 참고하면 이해하기 좋다.