习题_09.md

P9 在这个习题中，我们探讨 Diffie-Hellman(DH) 公钥加密算法，该算法允许两个实体协商一个共享的密钥。该 DH 算法利用一个大素数 p 和另一个小于 p 的大数 g。p 和 g 都是公开的（因此攻击者将知道它们）。在 DH 中，Alice 和 Bob 每人分别独立地选择秘密密钥 Sa 和 Sb。Alice 则通过将 g 提高到 Sa 并以 p 为模来计算她的公钥 Ta。类似滴，Bob 则通过将 g 提高到 Sb 并以 p 为模来计算他的公钥 Tb。此后 Alice 和 Bob 经过因特网交换他们的公钥。Alice 则通过将 Tb 提高到 Sa 并以 p 为模来计算出共享密钥 S。类似地，Bob 则通过将 Ta 提高到 Sb 并以 p 为模来计算出共享密钥 S'。

a. 证明在一般情况下，Alice 和 Bob 得到相同的对称密钥，即证明 S = S'

b. 对于 p = 11 和 g = 2，假定 Alice 和 Bob 分别选择私钥 Sa = 5 和 Sb = 12，计算 Alice 和 Bob 的公钥 Ta 和 Tb。显示所有计算过程。

c. 接着 (b)，现在计算共享对称密钥 S。显示所有计算过程。

d. 提供一个时序图，显示 Diffie-Hellman 是如何能够受到中间人攻击的。该时序图应当具有 3 条垂直线，分别对应 Alice、Bob 和攻击者 Trudy。

• a.

  • 1、A 和 B 共享素数 p 和 p 的本原根 g
  • 2、A 选随机数 A 计算 g^A mod p = Ya 然后发送给 B
  • 3、B 选随机数 B 计算 g^B mod p = Yb 然后发送给 A
  • 4、A 收到 Yb 后，计算 Yb^A mod p = Ka
  • 5、B 收到 Ya 后，计算 Ya^B mod p = Kb
  • 由于 Ka = Yb^A mod p = (g^B mod p)^A mod p = g^(AB) mod p
  • 由于 Kb = Ya^B mod p = (g^A mod p)^B mod p = g^(AB) mod p
  • 综上所述 Ka = Kb

• b.

  • 1、对于 p = 11 和 g = 2，A 和 B 选取的随机数应该在 1 ~ p-2 的闭区间中。
  • 2、A 选取随机数 A = 5，那么 Ya = g^A mod p = 2^5 mod 11 = 10
  • 3、B 选取随机数 B = 8，那么 Yb = g^B mod p = 2^8 mod 11 = 3
  • 4、A 收到 B 的随机数后计算 Ka = 3^5 mod 11 = 1
  • 5、B 收到 A 的随机数后计算 Kb = 10^8 mod 11 = 1

• c.

  • 见上

• d.

  •