디피-헬만 키 생성 프로그램(1) - 이론

오우! RSA 암호화 프로그램을 개발하던 중, 디피 헬만 암호화 프로그램을 구현해 보라는 학교 과제가 생겼다.

 

먼저, 디피헬만 알고리즘은 

이산대수의 복잡성을 보안 기법으로 사용한다.

소수 q와 q의 원시근 a을 사용해서 복잡도가 증가하는데,

키를 만드는 방법은 아래와 같다. (엘리스와 밥으로 예시를 들어서 설명하겠다.)

 

1. 엘리스는 개인키($X_A$)와 공개키($Y_A$)를 생성한다.

$X_A < q$

$Y_A \equiv a^{X_A} \pmod{q}$

 

2. 밥은 개인키($X_B$)와 공개키($Y_B$)를 생성한다.

$X_B < q$

$Y_B \equiv a^{X_B} \pmod{q}$

 

3. 엘리스와 밥은 공개키를 서로 교환한다.

 

4. 엘리스는 밥의 공개키($Y_B$)로 비밀키($K_A$)를 생성한다.

$K_A = Y_B^{X_A} \pmod{q}$

 

5. 밥은 엘리스의 공개키($Y_A$)로 비밀키($K_B$)를 생성한다.

$K_B = Y_A^{X_B} \pmod{q}$

 

6. 엘리스와 밥의 비밀키는 알고보면 서로 같은 값이다.

$K_A = Y_B^{X_A} \pmod{q} = (a^{X_B}\mod{q})^{X_A} \pmod{q} = (a^{X_B})^{X_A}\pmod{q}$

$K_B = Y_A^{X_B} \pmod{q} = (a^{X_A}\mod{q})^{X_B} \pmod{q} = (a^{X_A})^{X_B}\pmod{q}$

$K_A = K_B = a^{X_AX_A}\pmod{q}$