前言

Diffie-Hellman:一种确保共享KEY安全穿越不安全网络的方法，它是OAKLEY的一个组成部分。

一、DH密钥交换的实现

解：
$5^1$ mod 157 = 5 mod 157
$5^2$ mod 157 = 25 mod 157
$5^4$ mod 157 = $(5^2{)}^2$ mod 157 = 154 mod 157
$5^8$ mod 157 = $(5^4{)}^2$ mod 157 = 9 mod 157
$5^{16}$ mod 157 = $(5^8{)}^2$ mod 157 = 81 mod 157

（a） $Y_A$ = ${\alpha }^{X_A}$ mod q
= $5^{15}$ mod 157
= ( $5^8•5^4•5^2•5^1$) mod 157
= ( 9 • 154 • 25 • 5) mod 157
= (1125 • 154) mod 157
= ( 26 • 154) mod 157
= 79

（b） $Y_B$ = ${\alpha }^{X_B}$ mod q
= $5^{27}$ mod 157
= ( $5^{16}•5^8•5^2•5^1$) mod 157
= ( 81 • 9 • 25 • 5) mod 157
= (729 • 25 • 5 ) mod 157
= (101 • 25 • 5 ) mod 157
= (505 • 25) mod 157
= (34 • 25) mod 157
= 65

（c） s = $(Y_B{)}^{X_A}$ mod q = $(Y_A{)}^{X_B}$ mod q

= ${\alpha }^{X_A{X}_B}$ mod q

= $5^{15•27}$ mod 157
= $5^{405}$ mod 157
= $5^{(156•2+93)}$ mod 157 （费尔马小定理）
= $5^{93}$ mod 157
= 78

二、DH算法的应用

解：

（a） 已知 $Y_B$ = ${\alpha }^{X_B}$ mod q
则 $X_B$ = ${\log }_{\alpha }(kq+Y_B)$ （$k,X_B\in Z$ 且 $X_B<q$）
= ${\log }_5(23k+10)$
通过反复实验和试错后可知， 当k = 5时，$X_B$ = 3

（b） 已知 $K$ = $(Y_A{)}^{X_B}$ mod q
= $8^3$ mod 23
= 6

（c） $\because$ 22 = 2 x 11
$\therefore$ q-1 的所有素因子为 2 和 11

$\therefore$ $5^{(22/2)}$ mod 23 = $5^{11}$ mod 23 = 22
$5^{(22/11)}$ mod 23 = $5^2$ mod 23 = 2

以上两数皆不等于1，说明 5 是模 23 的原根

总结

Diffie-Hellman 机制的巧妙在于需要安全通信的双方可以用这个方法确定对称密钥。然后可以用这个密钥进行加密和解密。但是注意，这个密钥交换协议/算法只能用于密钥的交换，而不能进行消息的加密和解密。双方确定要用的密钥后，要使用其他对称密钥操作加密算法实现加密和解密消息。

拓展：原根判定方法

如何计算大数模数