第二章 离散对数与Diffie-Hellman （练习题）

Section 2.2 The Discrete Logarithm Problem

2.3

假设  为  下的原根。

（a）假设同余式  的解为 ，证明 ，且解释为什么映射

是well-defined function。

证：已知 ，我们有 ，由于  为原根，所以其阶为 ，即 ，因此  ： This means the  is well-defined up to adding or subtracting multiples of p − 1, so the map (2.1) is well-defined.

（b） 证明 

证： 我们有

因此 ，更准确些： 

（c）证明 

证： 我们有

因此 

2.4

计算下列离散对数问题

（a） **

答： 

（b）

答： 

（c）

答： 

2.5

设  为奇素数， 为模  下的原根。证明当且仅当离散对数  在模  下为偶数时  为模  下的二次剩余。

证：证明取自命题 3.61，设 

显然如果 ，那么  为二次剩余。

另外，如果  为奇数，，并假设  为二次剩余，即 ，根据费马小定理（定理1.24），我们有

然后  等价于

根据费马小定理，

所以我们会有 

但这与  为原根这一假设相矛盾，因此所有  的奇数幂次都为二次非剩余。

Section 2.3 Diffie–Hellman key exchange

2.6

  Alice 和 Bob 在Diffie-Hellman密钥交换协议中使用素数  和基数 。Alice 向 Bob 发送值 。Bob 请求您的帮助，因此您告诉他使用秘密指数 。Bob应向Alice发送什么值 ，以及他们的秘密共享值是什么？你能找出 Alice 的秘密指数吗？

答： Bob 应该发送  给 Alice，这样他们的秘密共享值为  。而对于 Alice 的秘密指数，我们没有一个直接的方法去求解，但是可以用 babystep–giantstep 方法去求解，最终我们可以计算出 ，所以 Alice 的秘密指数为 。

2.7

  设  为素数， 为整数。Diffie–Hellman决策问题如下。假设给你三个数字 ，并且假设  和  满足

  在你不一定知道指数  和  的值的情况下，判断  是否等于  。请注意，这与前面描述的 Diffie–Hellman 计算问题不同。Diffie-Hellman 计算问题要求您实际计算  的值。

（a） 证明求解 Diffie-Hellman 计算问题的算法可用于求解 Diffie-Hellmman 决策问题。

证： 显然，如果能够解决 Diffie-Hellman 问题，就能够实际的计算出 ，直接检查是不是等于  即可。

（b） 你认为Diffie-Hellman决策问题是难还是容易？为什么？

答： 如果不解决 Diffie-Hellman 计算问题，至少目前没有人知道如何解决 Diffie-Hellmin 决策问题。

Section 2.4. The Elgamal Public Key Cryptosystem

2.8

  Alice 和 Bob 协商在 Elgamal 公钥密码系统中使用素数 ，基 

（a）Alice 选择  作为她的私钥，那么她的公钥  是什么？

答：

（b）Bob 选择  作为她的私钥，那么他的公钥是 ，Alice 使用临时密钥  加密消息 ，那么 Alice 要发送给 Bob 的密文为？

答：

（c）Alice 使用新的私钥  和公钥 ，Bob 给 Alice 发送了密文 ，请解密。

答：

（d）Bob 又生成了一个新的私钥，并且公开了他的公钥 ，Alice 使用该公钥加密并发送密文  给 Bob。Eve 拦截到了该消息，请帮助 Eve 解决这个离散对数问题 ，并使用  解密获取原消息。

答： 同余式  的解为 ，即 Bob 的私钥，所以解密：

2.9

  假设Eve能够解决Diffie–Hellman计算问题。更准确地说，假设 Eve 得到两个值 ，并且她能够计算。请说明 Eve 能够打破 Elgamal 公钥密码系统。

答：在Elgamal 公钥密码系统中，Alice 的公钥为 ，密文：，其中  是 Bob 的临时密钥。由于 ，因此如果 Eve 获取了  能够计算  的话，那么他就能够通过计算  来解密密文，获得明文。

2.10

  这道题描述了一种公钥密码系统，要求 Bob 和 Alice 交换多条消息。我们用一个例子来说明这个系统。

  Alice 和 Bob 确定一个公开素数 ，而其他使用的数值都是私密的。Alice 准备传输她的消息  ，她选择一个随机指数 ，计算并发送 ，Bob 选择一个随机指数  并发送  给 Alice。Alice 随后计算  并发送给Bob，Bob最后计算  即可恢复 Alice 想要传输给 Bob 的消息：。

（a）解释为什么这个算法可行，Alice使用了  作为指数，他们有何相关；同样的， Bob 的指数  又有何关联？

答：Bob 和 Alice 的指数满足 

（b）使用变量表述该系统，并证明其在一般情况下有效。

答：Alice 选择一个满足  的整数 ，并计算 ，发送给Bob

Bob 选择一个满足  的整数 ，并计算 ，发送给Alice

Alice计算  在模  下的逆元  并计算 ，发送给Bob

Bob 计算  在模  下的逆元  并计算 

为了证明最后一个等式成立：

由于  在模  下互为逆元，  在模  下互为逆元。根据费马小定理我们有 

（c）与Elgamal相比，这种密码系统的缺点是什么？（提示：Alice和Bob必须交换多少次数据？）

答：ElGamal 只要求 Alice 给 Bob 发送一条消息。这个新密码系统要求 Alice 向 Bob 发送两条消息，Bob 将消息发送回 Alice。因此，这种新密码系统比起 ElGamal 需要更多次沟通。

（d）这个密码系统比Elgamal有什么优势吗？特别是，如果 Eve 能解决离散对数问题，她能破解它吗？如果 Eve 能解决Diffie–Hellman计算问题，她能破解它吗？

答：这种新密码系统的优点是比起 ElGamal，Alice 和 Bob 透露的信息要少一些。当然，如果 Eve 能解DLP，那么既然她知道  和，她就能解  并恢复 ，然后她就可以计算  来恢复 。

  然而，如果 Eve 知道如何解决 Diffie-Hellman 计算问题，她似乎没有一个简单的方法来打破这个系统。因此，如果 DHP 比 DLP 更容易求解，这种新密码系统可能比 ElGamal 更安全。