Diffie-Hellman 알고리즘

Diffie-Hellman 알고리즘은 1976년 Whitfield Diffie와 Martin Hellman에 의해 발표된 공개키 암호화 기술 중 하나입니다. 이 알고리즘은 두 개체 간에 비밀 정보를 안전하게 교환하는 방법으로 작동합니다. 이 알고리즘은 상호 작용하는 두 개체가 공유 비밀 정보를 결합하여 대칭키를 생성하는 방식을 사용합니다. 이를 통해 대칭키 암호화를 사용하여 안전한 통신을 수행할 수 있습니다. Diffie-Hellman 알고리즘은 TLS/SSL 및 VPN과 같은 보안 프로토콜에서 널리 사용됩니다. 이 알고리즘은 공개키 기술의 개념을 도입하여 대칭키 교환 문제를 해결했으며, 이후 RSA 알고리즘 등의 다른 공개키 암호화 알고리즘의 기반이 되었습니다.

 

(아래는 이해를 돕기 위한 간단한 예시로 작은 숫자를 활용해보았습니다)

공개키/개인키/비밀키 생성 과정

Diffie-Hellman 키 교환 알고리즘은 두 사람이 안전하게 비밀 키를 공유할 수 있도록 하는 방법입니다. 이 알고리즘은 공개 키 암호화 시스템을 기반으로 하며, 대칭 키 암호화 방식을 사용하여 안전한 데이터 전송을 보장합니다. 이 알고리즘은 다음과 같은 순서로 작동합니다.

1. 초기 설정

두 사람 (예: Alice와 Bob)은 먼저 공개 매개 변수를 선택해야 합니다. 이 매개 변수는 모두가 알 수 있지만 수정할 수 없는 고정값이어야 합니다. 이 매개 변수를 p와 g라고 하겠습니다. 여기서 p는 2048비트의 큰 소수이며 g는 모듈로 연산에 사용되는 원시 루트(primitive root)입니다.

p=17, g=2

2. 개인키 생성

이제 Alice와 Bob은 각자의 비밀 키를 생성합니다. 이 비밀 키는 모든 사람에게 알려지면 안 되며, 오직 Alice와 Bob만 알고 있어야 합니다. 이 비밀 키를 각각 a와 b라고 하겠습니다. 이 a와 b는 모두 p-1보다 작은 임의의 정수입니다.

Alice = 11, Bob = 13

3. 공개키 생성

Alice와 Bob은 이제 각자의 공개 키를 생성합니다. 이 공개 키는 모두에게 알려져도 상관없습니다. Alice의 공개 키는 g^a mod p이고, Bob의 공개 키는 g^b mod p입니다.

Alice_Pub = 8, Bob_Pub = 15

4. 공개 키 교환

이제 Alice와 Bob은 서로의 공개 키를 교환합니다. 즉, Alice는 Bob에게 g^a mod p를 보내고, Bob은 Alice에게 g^b mod p를 보냅니다.

Alice_Pub = 8 <---> Bob_Pub = 15

5. 비밀 키 생성

이제 Alice와 Bob은 각자 수학적인 계산을 수행하여 비밀 키를 생성합니다. Alice는 Bob이 보낸 g^b mod p에 자신의 비밀 키 a를 거듭제곱한 값을 mod p로 계산합니다. 즉, Alice의 비밀 키는 (g^b mod p)^a mod p입니다. 마찬가지로 Bob은 Alice가 보낸 g^a mod p에 자신의 비밀 키 b를 거듭제곱한 값을 mod p로 계산합니다. 즉, Bob의 비밀 키는 (g^a mod p)^b mod p입니다.

Alice_Sec = 9, Bob_Sec = 9

비밀키 검증 과정

1. 비밀 키 확인

Alice와 Bob은 이제 서로의 비밀 키를 확인합니다. 이 과정은 간단합니다. Alice는 Bob이 계산한 (g^b mod p)^a mod p와 자신이 계산한 (g^a mod p)^b mod p가 같은지 확인합니다. 만약 같다면 Alice와 Bob은 같은 비밀 키를 생성한 것입니다.

Alice와 Bob은 동일한 비밀 키 9를 가지게 됩니다