디피헬만 알고리즘

 

■디피-헬만(Diffie-Hellman) 키 교환 알고리즘

 

[개념]

- 디피-헬만(DH)은 1976년에 Whitefield Diffie와 Martin Hellman이 고안

- 대칭키 암호를 쓰려면 양쪽이 같은 비밀키를 가져야하는데, 이 키를 사전에 안전하게 전달하지 않아도 공유할 수 있게 해주는 알고리즘

- 키교환만 가능 , 실제 데이터 암호화는 하지 않는다.

 

[동작원리]

핵심 아이디어 : 이산 로그문제의 어려움에 기반

 

1. 공개 파라미터 선택

● 두 당사자 A와 B는 큰 소수 p와 그에 대한 원시근(기저) g를 공개값으로 공유한다.

● 이 값들은 누구나 알아도 안전한다.

 

2. 개인 키 선택

●  A는 비밀정수 a, B는 비밀정수 b를 각각선택

● 이값들은 외부에 절대 공개되지 않는다..

 

3. 공개 키 계산 및 교환

● A는 A_pub = g^a mod p 계산 -> B에게 보냄

● B는 B_pub = g^b mod p 계산 -> A에게 보냄

 

4. 공유키 계산

● A는 수신한 B_pub를 이용해

    K = (B_pub)^a  mod p  = g^ab mod p

● B는 수산힌 A_pub를 이용해

    K = (A_pub)^b  mod p  = g^ab mod p

 

5. 보안성 

● 공격자는 p , g , A_pub , B_pub를 모두 알아도  a,b를 직접 구하려면 이산로그 문제를 풀어야하는데, 큰 수일경우 현실적으로 불가능하다.

 

[실제 예시]

예시로 매우 작은 값들을 사용한다. 실제 환경에서는 훨씬 큰(예:2048비트) 소수p와 적절한 기반 g를 써야 안전합니다.

 

●소수 p =23

●원시근 g= 5

● Alice(A)의 비밀 a = 6

● Bob(B)의 비밀 b = 15

 

1) A의 공개값 A_pub = g^a mod p

● 5^1 mod 23 = 5

● 5^2 = 25 mod 23 = 2

● 5^4 = (5^2)^2 = 2^2 = 4 mod 23

● 5^6 = (5^4)^2 = 4x2 = 8 mod 23

===> A_pub = 8 

 

2) B의 공개값 B_pub  = g^b mod p

===> B_pub = 19

 

3) 공유키 계산(Alice와 Bob이 독립적으로 동일한 값을 얻는지 확인)

Alice 계산: K = (B_pub)^a mod p = 19^6 mod 23

19^1 mod 23 = 19

19^2 = 361 mod 23 = 361 - 15*23 = 361 - 345 = 16

19^4 = (19^2)^2 = 16^2 = 256 mod 23 = 256 - 11*23 = 256 - 253 = 3

19^6 = 19^4 * 19^2 = 3*16 = 48 mod 23 = 48 - 46 = 2

===> K=2

 

Bob도 동일하게 계산 

===> K=2

 

실제 보안에서는 매우 큰 소수 p와 안전한 기반 g를 사용해야 한다. (작은수는 금방개짐)

또한 인증(예: 디지털 서명 , PKI) 이 결합되지 않으면 중간자 공격(MITM)에 취약하니 실제 프로토콜에서는 인증과 함께 사용