일단 용어 정리부터...
비밀키 : 일반적인 암호화에 사용되는 키. A와 B는 같은 비밀키를 공유해야 한다.
공개키 : 공개키 알고리즘에서 사용되는 키로 외부에 공개되는 키
개인키 : 공개키 알고리즘에서 사용되는 키로 개인이 소유하며 외부에 알려주지 않는 키
목적 - 공개키 알고리즘을 통해 비밀키를 생성하여 암호화에 사용한다.
DH 알고리즘의 핵심은 상대방의 공개키와 나의 개인키를 이용하여 계산을 하면 비밀키가 나온다는 것이다.
그 후 나와 상대방은 비밀키를 사용하여 데이터를 암호화한 후 전달하면 된다.
즉, A와 B 사이에서 사용할 비밀키를 생성하는 것을 식으로 나타내면 다음과 같다.
A의 비밀키 = A의 개인키 [DH연산] B의 공개키
B의 비밀키 = B의 개인키 [DH연산] A의 공개키
그리고 A의 비밀키 = B의 비밀키
위 DH연산을 사용하면 A의 비밀키와 B의 비밀키는 같은 값이 나오기 때문에 이것을 암호화에 사용할 수 있는 것이다.
그럼 DH에서 사용하는 연산은 이런 조건을 만족한다는 뜻인데 이 연산은 어떤 것일까?
여기서 이번엔 기호 정리...
p = DH연산에 사용되는 소수 (1024 bits 이상)
g = DH연산에 사용되는 베이스, 특별한 수. (x1의 값에 따라 나오는 개인키의 종류가 정해진 g는 사용할 수 없다)
s = 비밀키
A의 작업
========
1. 임의의 개인키 x1을 생성하고 다음의 식으로 공개키(y1)를 계산한다.
y1 = gx1 mod p
2. B에게 자신의 공개키 y1을 전달한다.
B의 작업
========
3. 임의의 개인키 x2를 생성하고 다음의 식으로 공개키(y2)를 계산한다.
y2 = gx2 mod p
4. 전달받은 A의 공개키(y1)와 자신의 개인키(x2)를 이용하여 비밀키(s)를 계산한다.
s = y1x2 mod p
5. A에게 자신의 공개키 y2를 전달한다.
A의 작업
========
6. 전달받은 B의 공개키(y2)와 자신의 개인키(x1)를 이용하여 비밀키(s)를 계산한다.
s = y2x1 mod p
위의 결과에서 보면 비밀키(s)가 같으려면 다음의 공식도 만족해야 한다.
y1x2 mod p = y2x1 mod p
위 공식에 y1과 y2를 생성할 때 사용했던 계산식을 넣어보자.
(gx1 mod p)x2 mod p = (gx2 mod p)x1 mod p
여기서 더 나아가려면 다른 것에 대해서 먼저 알아야되겠다.
((x mod p) * (y mod p)) mod p = xy mod p
따라서
(gx1 mod p)x2 mod p 는 (gx1)x2 mod p 가 되고
(gx2 mod p)x1 mod p 는 (gx2)x1 mod p 가 된다.
그럼 (gx1)x2 mod p = (gx2)x1 mod p 가 되는데, 이정도 왔으면 왜 같은지 알 것이다. ^^;;
지수승은 곱으로 대체할 수 있으니
gx1x2 mod p = gx2x1 mod p 가 된다.
끝났다!
아.. 제길... 이거 쓴다고 야근한 꼴이 되는구나...
((x mod p) * (y mod p)) mod p = xy mod p
이거 증명하려다가 시간 다 보냈다.. ㅠ_ㅠ
결국 증명은 제외 ㅎㅎ