钥交换（即用常规密码体制加密需要保密传输的消息本身，然后用公钥密码体制加密常规密码体制中使用的会话密钥，将二者结合使用）。

6－5 简述Diffie-Hellman算法实现密钥交换的原理。该算法基于什么数学难题？

答：Diffie-Helllman密钥交换原理：假设用户A和用户B希望安全地交换一个密钥，他们需要先确定并都知道两个整数：一个素数q和一个整数a，这两个整数对用户A和B是共享的，但对其他人是保密的。整数a是素数q的一个本原元。用户A选择一个随机数

XA?q，并计算：YA?aXAmodq。类似地，用户B选择一个随机数XB?q，并计算：

YB?aXBmodq。

每一方都保密存放自己的随机数XA或XB（相当于私钥），并使YA或YB（相当于公钥）的值对于另一方可以公开得到。用户A计算K?(YB)用户B计算K?(YA)XBXAmodq，并将其作为自己的密钥；

modq，并将其作为自己的密钥。通过这种方式，双方共享了一个

密钥K，相当于双方交换了一个密钥。

Diffie-Helllman密钥交换算法的有效性依赖于计算有限域中离散对数的困难性。 6－6 设Diffie-Hellman方法中，公用素数q＝11，本原元等于2。若用户A的公钥Ya＝9,则A的私钥Xa为多少？如果用户B的公钥Yb＝3，则共享的密钥K为多少？ 解：YA?aXAmodq，即9＝2Xamod11,经推算得Xa＝6（这里在公用素数很小的情况下

得出的，实际使用时公用素数应很大，这就是离散对数的难解性问题）。 如果用户B的公钥Yb＝3，则共享的密钥K＝YB6－7 RSA算法的理论基础是什么？ 答：大数因子分解的困难性。 6－8 编写程序实现RSA算法。 略。

6－9 设通信双方使用RSA加密体制，接收方的公开密钥是（5,35），接收到的密文是10，求明文。

解：据题意知：e＝5，n＝35，C＝10。 因此有：??n????35????5???7??4?6?24

Xamodq?36mod11?5。

d?e?1mod??n??5?1mod24?5

所以有：M?Cmodn?10mod35?5。

6－10 选择p＝7，q＝17，e＝5,试用RSA方法对明文m＝19进行加密、解密运算、给出签名和验证结果(给出其过程)，并指出公钥和私钥各为什么？

d5解：加密：n?pq?7?17?119

C?memodn?195mod119?66

解密：??n????119????7???17??6?16?96

d?e?1mod??n??5?1mod96?77

所以，m?Cmodn?66mod119?19 签名：y?mdmodn?1977mod119?66

验证：x?yemodn?665mod119?19?m，该签名是真实的。

6－11 在RSA体制中，给定某用户的公钥e＝31，n?3599，那么该用户的私钥等于多少？ 解：3031。

6－12 编写程序计算：1615mod4731。 程序略。

6－13 试编写程序判断2537是否为素数。 程序略。

6－14 ECC的理论基础是什么？它有何特点？

答：ECC的理论基础是椭圆曲线离散对数问题的难解性。

ECC与RSA相比的主要优点在于：它用少得多的比特大小能够取得和RSA同等强度的安全性，因此减少了处理开销，具有存储效率、计算效率和通信带宽的节约等方面的优势，特别适用于那些对计算能力没有很好支持的系统，如智能卡、手机等。

6－15 椭圆曲线E11(1,6)表示y?x?x?6mod11，求其上的所有点。对于E11(1,6)上的点G?(2,7)，计算2G的值。

解：对于x的所有可能值，计算方程右边的值。

x 0 1 2 3 4 5 6 7 x3 + x + 6 mod 11 6 8 5 3 8 4 8 4 是mod p平方根? no no yes yes no yes no yes y 4, 7 5, 6 2, 9 2, 9 23d778 9 10 9 7 4 yes no yes 3, 8 2, 9 即所有点为：(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3), (8,8),(10,2),(10,9)。

要计算 2G = (2, 7) + (2, 7), 先计算：

可得：

所以：

x3 = 82–2–2 mod 11 = 5 y3 = 8(2–5)–7 mod 11 = 2 2G = (5, 2)

? ?= (3×22 + 1)/(2×7) mod 11

= 13/14 mod 11 = 2/3 mod 11 = 8

6－16 设实数域上的椭圆曲线为y2＝x3－36x，令P＝(?3.5,9.5),Q?(?2.5,8.5)。计算

P?Q。

解：将 xP = –3.5, yP = 9.5, xQ = –2.5, yQ = 8.5 代入椭圆曲线加方程易得：

xR = 7、 yR = 1。

因此：P + Q = (7, 1)。

6－17 利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E11(1,6)，生成元G?(2,7)，接收方A的秘密密钥nA?7。求： （1）A的公开密钥PA。

（2）发送方B欲发送消息Pm?(10,9)，选择随机数k?3，求密文Cm。 （3）显示接收方A从密文Cm恢复消息Pm的计算过程。 解：（1）PA?nA?G?7??2,7???7,2?。

Cm??kG,Pm?kPA???3?2,7?,?10,9??3?7,2??

（2）???8,3?,?10,9???3,5?????8,3?,?10,2??

（3）Pm??10,2??7?8,3???10,2???3,5???10,2???3,6???10,9?。

《应用密码学》习题和思考题答案

第7章 HASH函数和消息认证

7－1 什么是HASH函数？对HASH函数的基本要求和安全性要求分别是什么？

答：HASH函数是一种单向密码体制，即它是一个从明文到密文的不可逆映射，只有加密过程，不能解密。HASH函数可以将任意长度的输入经过变换以后得到固定长度的输出。

HASH函数的基本要求：①算法公开，不需要密钥。②有数据压缩功能，能将任意长度的输入转换成一个固定长度的输出。③容易计算。即给出消息M,要计算出该消息的散列值

h?M?是容易的。

HASH函数的安全性要求：①给定消息的散列值h?M?，要求出M是计算上不可行的。 ②给定消息M和其散列值h?M?，要找到另一个与M不同的消息M?，使得它们的散列值相同是不可能的（即抗弱碰撞性）。

③对于任意两个不同的消息M和M?，它们的散列值不可能相同（即抗强碰撞性）。 7－2 安全HASH函数的一般结构是什么？ 答：安全HASH函数的一般结构如下图所示。

消息M填充，附加位长度等M1M2??MtIV即fH1f压缩函数H2??Htg输出变换H0h?M?图7-1　安全散列函数的一般结构

7－3 为什么要进行HASH填充？

答：HASH函数的处理是以分组为单位，在生成散列值之前，在对输入消息进行分组时，如果最后一块报文不足r位，就要进行填充。 7－4 HASH函数的主要应用有哪些？

答：HASH函数的主要应用有：数字签名、生成程序或文档的“数字指纹”、用于安全存储口令。

7－5 简述散列算法的设计方法及其分类。 答：散列算法的设计主要可分为三大类：