现代密码学（第4版）—习题参考答案.docx

现代密码学（第4版）习题参考答案第1章1、设仿射变换的加密是：对明文“THE NATIONAL SECURITY AGENCY”加密，并使用解密变换验证你的解密结果。解：明文m=THE NATIONAL SECURITY AGENCY用数字表示为：m=19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24 根据E11,23(m)11*m+23(mod 26)，对明文中的每一个字符计算出相应的密文字符c=24 22 15 10 23 24 7 21 10 23 14 13 15 19 9 2 7 24 1 23 11 15 10 19 1 由此得到密文c=YWPKXYHVKXONPTJCHYBXLPKTB使用解密变换验证加密结果过程如下：由11*191 (mod 26)知11-1=19(注：求模逆元可以通过欧几里得算法或者直接穷举125)根据D11,23(c)11-1*(c-23) (mod 26)19* (c-23) (mod 26)，对密文中的每一个字符计算出相应的明文字符m=19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24 由此得到m=THE NATIONAL SECURITY AGENCY，解密结果与明文一致，正确。2、设由仿射变换对一个明文加密得到的密文为：edsgickxhuklzveqzvkxwkzzukvcuh。又已知明文的前两个字符为“if”，对该明文解密。解：设加密变换为c=Ea,b(m)a*m+b(mod 26)由题目可知，明文前两个字符为if，相应密文为ed，即有：E(i)=e，4a*8+b(mod 26) ，(i=8，e=4)，E(f)=d，3a*5+b(mod 26) ，(f=5，d=3)，由上述两式可求得，a=9，b=10因此解密变换为D9,10(c)9-1*(c-10) (mod 26)又由3*91 (mod 26)可知9-1=3密文对应的数字表示为：c=4 3 18 6 8 2 10 23 7 20 10 11 25 21 4 16 25 21 10 23 22 10 25 20 10 21 2 20 7 根据D9,10(c)9-1*(c-10) (mod 26)3*(c-10) (mod 26)，对密文中的每一个字符计算出相应的明文字符c=8 5 24 14 20 2 0 13 17 4 0 3 19 7 8 18 19 7 0 13 10 0 19 4 0 7 2 4 17 由此得到明文m=ifyoucanreadthisthankateahcer3、 设多表代换密码中加密为：对明文“PLEASE SEND ME THE BOOK,MY CREDIT CARD NO IS SIX ONE TWO ONE THREE EIGHT SIX ZERO ONE SIX EIGHT FOUR NINE SEVEN ZERO TWO”用解密变换 验证你的结果，其中解：加密时，先将明文分组，每四个一组：再代入加密变换：，得到计算结果：知密文为：NQXB BTWB DCJJ IJDT XDCF YFSG LYGD MOXN LLGN HAPC QZZQ ZCRG ZEZJ UIEB RRSQ NEMV QDJE MXNA IERP XAKM YRBY TQFM NEMV OME 同上，解密时，先将密文分组，再代入解密变换：得到明文：PLEA SESE NDME THEB OOKM YCRE DITC ARDN OISS IXON ETWO ONETHREE EIGH TSIX ZERO ONES IXEI GHTF OURN INES EVEN ZERO TWO解密验证结果与明文相符。4、设多表代换密码中，A是2×2矩阵，B是零矩阵，又知明文“dont”被加密为“elni”，求矩阵A。解：设矩阵由m=dont=(3,14,13,19)，c=elni=(4,11,13,8)可知:解得：第2章 1. 3级线性反馈移位寄存器在时可有4种线性反馈函数，设其初始状态为，求各线性反馈函数的输出序列及周期。解：设3级线性反馈特征多项式为，若则共有种可能，对应初态。4种线性反馈函数分别记为： 输出序列，由定义2-2得周期 由定义2-3得是不可约多项式，输出序列由定理2-5周期是m序列 不可约多项式，输出序列，周期 是m序列 输出序列，得周期2. 设n级线性反馈移位寄存器的特征多项式为，初始状态为，证明输出序列的周期等于的阶。 解：的阶定义为 的最小的。 因为初始状态不为零，设为序列的最小周期。又因为，所以必存在，使得。 又因为定理2-1有,则而的次数为，的次数不超过，的次数不超过。所以，是正整数，都有。设，。即周期为的阶，若是n次不可约多项式，则序列的最小周期等于的阶。生成函数，的次数不超过。 不可约，所以，。又因为，所以。3. 设，初始状态为，求此非线性反馈移位寄存器的输出序列及周期。解：由，初态为 。线性递归可得： 可以得到输出序列为，周期为。4.设密钥流是由级的LFSR产生，其前个比特是,即个01。问第m+3个比特有无可能是1，为什么？解：第m+3个比特上不可能出现1，这是由于：根据线性移位寄存器的的递推关系有：5.设密钥流是由n级LFSR产生，其周期为,是任一整数，在密钥流中考虑以下比特对 问有多少形如的比特对。试证明你的结论。解：根据p23定理2-7，在上的n长m序列在周期为的m序列中对于,长为i的游程有个，且0，1游程各半，那么就有： 1的2游程： 1的3游程： 1的n-2游程： 那么就有： /2得 -得 从而有 即共有个形如的比特对。6.已知流密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。解：由已知可得相应的密钥流序列为1110100111，又因为是3级线性反馈移位寄存器，可得以下方程：将值代入得: , 由此可得密钥流的递推关系为：。7.若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器，产生的密钥是m序列。2.5节已知，敌手若知道一段长为2n的明密文对就可破译密钥流生成器。若敌手仅知道长为2n-2的明密文对，问如何破译密钥流生成器。解：如果敌手仅仅知道长为2n-2的明密文对，他可以构造出以下的长为2n的明密文对：不妨设：明文： 密文： 其中：为已知的，为未知的。 为已知的，为未知的。 的可能取值为00,01,10,11。的可能取值为00,01,10,11。共有16种组合方案，分别破解得到密钥流，在破解的结果中符合m序列的性质密钥流即为正确的方案，有可能不唯一。8.设J-K触发器中和分别为3级和4级m序列，且，求输出序列及周期。解：由J-K触发器可知 此时和分别为3级和4级m序列，则的周期为。9.设基本钟控序列生成器中和分别为2级和3级m序列，且，求输出序列及周期。解：令基本钟控序列生成器中的周期为，的周期为，则输出序列的周期为，。记LFSR2产生，其状态向量为，可得的变化情况如下：输出序列第3章 1. (1) 设M和M的逐比特取补，证明在DES中，如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即： 如果Y=DESK(X)，那么Y=DESK(X)提示：对任意两个长度相等的比特串A和B，证明。(2) 对DES进行穷搜索攻击时，需要在由256个密钥构成的密钥空间进行，能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。（1）证明：设Li和Ri分别不是第i轮DES变换的左右部分，i=0,1,16, 则加密过程为:若将明文和密钥k同时取补，则加密过程为：其中，的作用是将数据的左、右半部分扩展后与密钥进行逐比特异或运算，因此，再经过S盒，并将输出结果进行置换运算P之后有：，而，所以有。同时有，所以明文P与密钥K同时取补后有。（2）答：根据(1)的结论进行穷搜索攻击, 可将待搜索的密钥空间减少一半，即255个。因为给定明文x，则，由(1)知，则一次搜索就包含了x和x 两种明文情况。2. 证明DES解密变换是加密变换的逆。证明：令为左右位置交换函数，,则第i次迭代变换为:,又 有,同时，,即， ,DES加密过程在密钥k作用下为:,解密过程为: ,所以，即解密变换是加密变换的逆。（得证）3.在DES的EBC模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而在CBC模式中，将有错误传播。例如在图3-11中C1中的一个错误明显地将影响P1和P2的结果。 (1) P2后的分组是否受到影响？(2) 设加密前的明文分组P1中有一个比特的错误，问这一错误将在多少个密文分组中传播？对接收者产生什么影响？答：（1）在CBC模式中，若密文分组中有一个错误C1，则解密时明文分组中都将受到影响，而后的分组都不受影响，即CBC的错误传播长度为2，具有自恢复能力。（2）若明文分组P1有错误，则以后的密文分组都将出现错误，但对接收者来说，经过解密后，除P1有错误外，其余的明文分组都能正确恢复。4. 在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远？答：在8比特CFB模式中，若密文有1比特错误，则会影响当前分组以及后续分组的解密，会使解密输出连续9组出错，即错误传播的长度为9。5. 在实现IDEA时，最困难得部分是模乘法运算。以下关系给出了实现模乘法的一种有效方法，其中a和b是两个n比特的非0整数：(1) 证明存在唯一的非负整数q和r使得；(2) 求q和r的上下界；(3) 证明;(4) 求关于q的表达式；(5) 求关于q和r的表达式；(6) 用(4)和(5)的结果求r的表达式，说明r的含义。 (1) 证明： 假设存在使得，有 因为，所以，因此，只能有。（2）解：，显然，a和b的最大值均为，则有所以，(3)证明：(4)解：根据，得(5)解：根据，得(6) 解：当时，根据及得，同理，当 时，余数r表示ab的n个最低有效位与ab右移位数n之差。6. (1) 在IDEA的模乘运算中，为什么将模乘取为而不是？(2) 在IDEA的模加运算中，为什么将模乘取为而不是？答：(1) 在IDEA模乘运算中，必须保证运算构成一个群，因此模数必须为素数，故不能取216。(2) 同一群内的分配律和结合律都成立，但IDEA算法中要保证模数的加法和模数的乘法，比特异或之间分配律和结合律不成立，因此模加运算不能和模乘运算在同一个群内，即不能选模216+1，而216在模加运算中必为一个群.7. 证明SM4算法满足对合性，即加密过程和解密过程一样，只是密钥使用的顺序相反。证明： SM4算法的加密轮函数分为加密函数G和数据交换E。其中G对数据进行加密处理，E进行数据顺序交换。即加密轮函数 Fi=GiE其中，Gi=GiXi,Xi+1,Xi+2,Xi+3,rki (i=0,1,2,31)=(XiTXi+1,Xi+2,Xi+3,rki,Xi+1,Xi+2,Xi+3)EXi+4,(Xi+1,Xi+2,Xi+3)=Xi+1,Xi+2,Xi+3,Xi+4, (i=0,1,2,31)因为， (Gi)2=Gi(XiTXi+1,Xi+2,Xi+3,rki,Xi+1,Xi+2,Xi+3,rki)=(XiTXi+1,Xi+2,Xi+3,rkiTXi+1,Xi+2,Xi+3,rki,Xi+1,Xi+2,Xi+3,rki)=Xi,Xi+1,Xi+2,Xi+3,rki=I因此，加密函数G是对合的。E变换为：EXi+4,(Xi+1,Xi+2,Xi+3)=( Xi+1,Xi+2,Xi+3, Xi+4)E2Xi+4,(Xi+1,Xi+2,Xi+3)=I显然，E是对合运算。综上，加密轮函数是对合的。根据加密框图，可将SM4的加密过程写为：SM4=G0EG1EG30EG31R根据解密框图，可将SM4的解密过程写为：SM41=G31EG30EG1EG0R比较SM4与SM4-1可知，运算相同，只有密钥的使用顺序不同。所以，SM4算法是对合的。第4章1. 证明以下关系：(1) ，则；(2) ，则；(3) ，则。解：(1)设，由题意得，且存在整数，使得，即，证得。(2)已知，则存在整数，使得，证得。(3)已知，则存在整数，使得，证得。2. 证明以下关系：(1) ；(2) 。解：(1)设，则存在整数，使得即。(2)设，则存在整数，使得即。3. 用Fermat定理求。解：因为是素数，且，则由Fermat定理可得：；又根据性质，可得：。4. 用推广的Euclid算法求的逆元。解：运算步骤如下表所示：循环次数QX1X2X3Y1Y2Y3初值1011901671101671-152211-152-121533-12154-77424-77-9161所以。5. 求。解：由Euclid算法，得：所以。6. 求解下列同余方程组：解：根据中国剩余定理求解该同余方程组，记，则有，所以方程组的解为7. 计算下列Legendre符号：(1) ；(2) ；(3) 。解：(1)(2)(3)8. 求的所有本原根。解：因为，所以的所有不同的素因子为，即对每个，只需计算。又因为，所以有8个本原根。满足且的为的本原根，即。9. 证明当且仅当是素数时，是域。证明：(1)若是域，则，均为Abel群。显然为Abel群，与n是否为素数无关；但若为Abel群，其条件之一必须保证对任意有模乘法逆元，即对任意，有，使得，所以，即，为素数。(2)若不是素数，则，即至少存在一个，使得，即无模乘法逆元，因此不能保证均为Abel群，即不是域。10. 设通信双方使用RSA加密体制，接收方的公开钥是，接收到的密文是，求明文。解：因为，则，所以，即明文。11. 已知的运行时间是，用中国剩余定理改进RSA的解密运算。如果不考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍。证明：RSA的两个大素因子的长度近似相等，约为模数的比特长度的一半，即，而在中国剩余定理中，需要对模和模进行模指数运算，这与的运行时间规律相似，所以每一个模指数运算的运行时间仍然是其模长的三次幂，即。在不考虑中国剩余定理计算代价的情况下，RSA解密运算的总运行时间为两个模指数运算的运行时间之和，即，证得改进后的解密运算速度是原解密运算速度的4倍。12. 设RSA加密体制的公开钥是(1) 用重复平方法加密明文，得中间结果为：若敌手得到以上中间结果就很容易分解，问敌手如何分解。(2) 求解密密钥。解：(1)由以上中间结果可得：。由，可知分解为。(2)解密密钥，由扩展的Eucild算法可得。13. 在ElGamal加密体制中，设素数，本原根，(1) 如果接收方B的公开钥是，发送方A选择的随机整数，求明文所对应的密文。(2) 如果A选择另一个随机整数，使得明文加密后的密文是，求。解：(1)密文，其中：。所以明文对应的密文为。(2)由，穷举法可得。所以。14. 设背包密码系统的超递增序列为，乘数，模数，试对good night加密。解：由，乘数，模数，可得。明文“good night”的编码为“00111”，“01111”，“01111”，“00100”，“00000”，“01110”，“01001”，“00111”，“01000”，“10100”，则有：所以明文“good night”相应的密文为。15. 设背包密码系统的超递增序列为，乘数，模数，试对解密。解：因为，则。所以其对应的明文分组为，由课本120页表4-7可得明文为“ADRA”。16. 已知，都是素数，其Jacobi符号都是，其中，证明：(1) 是模的平方剩余，当且仅当都是模的平方剩余或都是模的非平方剩余。(2) 是模的平方剩余，当且仅当都是模的平方剩余或都是模的非平方剩余。证明：(1)必要性：若是模的平方剩余，即存在使得，而，显然必有，所以也同时是模和模的平方剩余，即。又由题意得，即。所以：当时，有，即同时是模和模的平方剩余，也同时是模和模的平方剩余，即都是模的平方剩余；当时，有，即同时是模和模的非平方剩余，也同时是模和模的非平方剩余，即都是模的非平方剩余。充分性：若都是模的平方剩余，则也是模和模的平方剩余，即，即同时是模和模的平方剩余，所以是模的平方剩余；若都是模的非平方剩余，则它们对于模和模至少有一种情况是非平方剩余，不妨设，则有，即也都是模和模的非平方剩余。所以，同理，即同时是模和模的平方剩余，所以是模的平方剩余。(2)若是模的平方剩余，则同时是模和模的平方剩余，所以，由于勒让德符号的偶数次方肯定为（情况除外），即有，余下证明同(1)。提示：17. 在Rabin密码体制中设： (1) 确定在模下的4个平方根。(2) 求明文消息所对应的密文。(3) 对上述密文，确定可能的4个明文。解：(1)已知，由中国剩余定理可得到等价方程组：因为，所以。经组合可得到以下四个方程组：根据中国剩余定理，则有：第一个方程组的解为；第二个方程组的解为；第三个方程组的解为；第四个方程组的解为。所以，的四个平方根为。(2)对应的密文为。(3)解密即解，由中国剩余定理可得到等价方程组：因为，所以，经组合可得到以下四个方程组： 根据中国剩余定理，则有：第一个方程组的解为；第二个方程组的解为；第三个方程组的解为；第四个方程组的解为。所以，四个可能的明文为。18. 椭圆曲线表示，求其上的所有点。解：模的平方剩余有。时，无解，曲线无与这一相对应的点；时，无解，曲线无与这一相对应的点；时，无解，曲线无与这一相对应的点；时，；时，；时，；时，。所以椭圆曲线上的所有点为：。19. 已知点在椭圆曲线上，求和。解：(1)求。所以。(2)易知。所以。20. 利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是，生成元，接收方A的秘密钥。(1) 求A的公开钥。(2) 发送方B欲发送消息，选择随机数，求密文。(3) 显示接收方A从密文恢复消息的过程。解：(1)易知公开钥。求。所以。由题19可得，即。所以。(2)密文。求：。求：。所以。求：。所以。综上：。(3)从密文恢复消息的过程如下：其中：a)计算先计算。所以。计算。所以。计算。所以。计算。所以。b)计算。所以。第5章1. 在公钥体制中，每一用户U都有自己的公开钥和秘密钥。如果任意两个用户A,B按以下方式通信，A发给B消息，B收到后，自动向A返回消息，以使A知道B确实收到报文m，（1）问用户C怎样通过攻击手段获取报文m？解：当A发给B消息时，A的身份“A”并没有认证，而B在收到消息后也无法对发送者进行检验，且身份A，B均明文传输，因此用户C可通过如下手段获得报文m：当A发给B消息时，C截取该消息并将身份A替换为自己的身份C，将修改后的消息发给接收者B；B提取消息后，根据身份“C”将返回消息；C再次劫取B返回的消息，用自己的私钥解密出消息m，并用A的公钥对m加密后将消息发给A。这样，用户C获得了报文m而没有影响A,B之间的正常通信，实现了攻击。（2）若通信格式变为：A发给B消息B向A返回消息这时的安全性如何？分析这时A、B如何相互认证并传递消息m。解：根据消息格式，先对消息m进行了签名，然后再进行加密，传送的消息具有了保密性和认证性，敌手无法获得报文明文，安全性提高。A，B之间相互认证传递消息的过程如下：B收到消息时，先用B自己的私钥解密得到消息，然后根据提取的身份信息A，用A的公钥对消息m的签名的正确性进行验证，如果验证通过，则说明消息确实来自A。反之A用相同的方法可验证确实来自B，从而实现了相互认证。2. Diffie-Hellman密钥交换协议易受中间人攻击，即攻击者截获通信双方通信的内容后可分别冒充通信双方，以获得通信双方协商的密钥。详细分析攻击者如何实施攻击。解：虽然Diffie-Hellman密钥交换算法十分巧妙，但由于没有认证功能，存在中间人攻击。当Alice和Bob交换数据时，Trudy 拦截通信信息，并冒充Alice欺骗Bob，冒充Bob欺骗Alice。其过程如下：（1）Alice选取大的随机数x，并计算，Alice将g、P、X传送给Bob，但被Trudy拦截；（2）Trudy冒充Alice选取大的随机数z，并计算，Trudy将Z传送给Bob；（3）Trudy冒充Bob，再将传送给Alice；（4）Bob选取大的随机数y，并计算，Bob将Y传送给Alice，但被Trudy拦截。由（1）、（3）Alice与 Trudy 共享了一个秘密密钥，由（2）、（4）Trudy与Bob共享了一个秘密密钥。以后在通信过程中，只要Trudy作中间人，Alice和 Bob不会发现通信的异常，但 Trudy可以获取所有通信内容。3. Diffie-Hellman密钥交换过程中，设大素数p=11，a=2是p的本原根，（1）用户A的公开钥，求其秘密钥。解：满足即，所以有=6。（2）设用户B的公开钥，求A和B的共享密钥K。解：由Diffie-Hellman协议可知。4. 线性同余算法，问：（1）该算法产生的数列的最大周期是多少？解：由于模因此它没有原根，又由递推式不难得知。因此该算法产生的序列的最大周期为的最大阶l，而，但。若l=4，则不难验证，时，数列周期为4，因此该算法产生数列的最大周期是4。（2）a的值是多少？解：a必须满足，所以a在中取值。周期为4的有，即为a的取值（3）对种子有何限制？解：种子必须满足。5. 在Shamir秘密分割门限方案中，设k=3，n=5，q=17，5个子密钥分别是8、7、10、0、11，从中任选3个，构造插值多项式并求秘密数据s。解：取，构造插值多项式6. 在基于中国剩余定理的秘密分割门限方案中，设，三个子秘钥分别是6、3、4，求秘密数据s。解： 由题设可得s应满足因为，3个子密钥分别是6，3，4，那么，由， 可得=48由，可得=48由，可得= 即秘密数据s为48第6章16.1.3节介绍的数据认证算法是由CBC模式的DES定义的，其中初始向量取为0，试说明使用CFB模式也可获得相同结果。 6.1.3节用CBC模式的DES设计数据认证算法为：O2=EK(D2O1)O3=EK(D3O2)ON=EK(DNEK(DN1EK(D2EK(D1)ON=EK(DNON1) 如果改用CFB模式来实现，由于输出为64位，所以必须取，也就是每次移位寄存器左移整个64位。为了达到相同的结果，可取CFB模式中，则有： O2=D3EK(O1)O3=D4EK(O2)ON=EK(ON1)=EK(DNEK(DN1EK(D2EK(D1)ON1=DNEK(ON2)ON=0EK(ON1)比较两式，作为消息认证码，结果相同。2有很多哈希函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将消息M分成分组M1, M2,MN，H0=初值，迭代关系为(i=1,2,N),哈希值取为HN，其中E是分组加密算法。（1）设E为DES，第3章的习题已证明如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即如果Y=DESK（X），那么Y=DESK（X）。利用这一结论证明在上述哈希函数中可对消息进行修改但却保持哈希值不变。答：敌手主要是通过修改函数的输入值和来构造碰撞。H1=DESM1(H0)H0H2=DESM2(H1)H1HN=DESMN(HN)HN1利用和两个性质可知，若敌手同时对和逐比特取补，则由性质一知也被逐比特求补，由性质二知保持不变，所以也都不受影响，所以有：（2）若迭代关系Hi=EHi1(Mi)Mi，证明仍可对其进行上述攻击。答：改迭代关系为，则敌手也可同时对和逐比特取补，由性质一知也被逐比特求补，由性质二知都不受影响，故仍可进行上述攻击。3考虑用公钥加密算法构造哈希函数，设算法是RSA，将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。设一消息被分成两个分组B1和B2，其哈希值为H(B1, B2)=RSA(RSA(B1)B2)。证明对任一分组C1可选C2，使得H(C1, C2)= H(B1, B2)。证明用这种攻击法，可攻击上述用公钥加密算法构造的哈希函数。证明：对任一分组，可构造如下：，则H(C1,C2)=RSA(RSA(C1)C2)=RSA(RSA(C1)RSA(C1)RSA(B1)B2)=RSA(RSA(B1)B2)=H(B1,B2)设哈希函数的输入消息分组为，则可任取替代，并由上述方法构造替代，可得，攻击成功。4 在图6-11中，假定有80个32比特长的字用于存储每一个Wt，因此在处理信息分组前，可预先计算出这80个值。为节省存储空间，考虑有16个字的循环移位寄存器，其初值存储前16个值（即W0，W1，, W15），设计一个算法计算以后的每一个Wt。答：XORCLS1 W0W1W2W3W4W5W6W7W8W9W10W11W12W13W14W15为消息分组的16个字，初始放在移位寄存器中，如上图连接电路。的输出反馈到移位寄存器右边的输入端，则每个时钟到来时，移位寄存器从左边输出端移出一个字。5.对SHA，计算W16，W17，W18，W19答：W16=CLS1(W0W2W8W13)W17=CLS1(W1W3W9W14)W18=CLS1(W2W4W10W15)W19=CLS1(W3W5W11W16)6设a1a2a3a4是32比特长的字中的4个字节，每一给ai可看作由二进制表示的0255之间的整数，在大端方式中，该字表示整数a1224+a2216+a328+a4，在小端结构中，该字表示整数a4224+a3216+a228+a1。（1）MD5使用小端结构，因消息的摘要值不应依赖于算法所用的结构，因此在MD5中为了对以大端方式存储的两个字X=x1x2x3x4和Y=y1y2y3y4进行模2加法运算，必须要对这两个字进行调整，问如何进行？答：由于MD5使用little-endian结构，而X，Y使用的是big-endian存储结构，因此必须把X，Y转换成little-endian格式，设转换成：，则有x1224+x2216+x328+x4=x4'224+x3'216+x2'28+x1'x1'=x4,x2'=x3,x3'=x2,x4'=x1（2）SHA使用大端方式，问如何对以小端结构存储的两个字X和Y进行模2加法运算。答：由于SHA使用big-endian结构，而X，Y使用的是little-endian存储结构，因此必须把X，Y转换成big-endian格式，设转换成：，则有x4224+x3216+x228+x1=x1'224+x2'216+x3'28+x4'x1'=x4,x2'=x3,x3'=x2,x4'=x1第7章 1. 在DSS数字签名标准中，于是，若取，则。在对消息签名时，选择，计算签名并进行验证。解：(1)签名过程：为了简化，用代替，则用户对消息的签名为。计算，。所以签名。(2)验证过程：接收方收到的消息为，签名为。计算，。因为，所以认为签名有效，即验证通过。2. 在DSA签名算法中，参数泄露会产生什么后果？解：若攻击者得到了一个有效签名，并且知道了DSA签名算法中的参数，那么在签名方程中只存在一个未知数，即用户的秘密钥，所以攻击者可以求得秘密钥。因此，参数泄漏将导致签名秘密钥的泄漏，攻击者可以伪造任意消息的签名。第8章1、 假设你知道一个背包问题的解，试设计一个协议，以零知识证明方式证明你的确知道问题的解。解一：设背包向量为，证明者P知道一个背包容积的解，即，P以零知识证明方式向验证者证明自己掌握秘密的协议如下： P随机选取一向量，计算，将发给V。 V随机选，将发给P； P计算，即时，；时，将发给V。注：如果，P展示的解，即；如果，P展示被加密的的解，即。 若，V接受P的证明。协议的完备性、正确性和安全性(1) 完备性：如果P和V遵守协议，且P知道的解，则应答使得，V接受P的证明。 (2) 正确性：假冒的证明者E可按以下方式以的概率骗得V接受自己的证明： E随机选取一向量和，计算，将发给V。 V随机选，将发给E； E将发给V。V的验证方程为。当时，方程成立，V接受E的证明，E欺骗成功。因的概率是，所以E成功的概率是。另一方面，是E成功的最好概率，否则假定E以大于的概率使V相信自己的证明，那么E知道一个，对这个，他可以正确回答V的两个询问和，意味着E能计算，由此可计算，因此得秘密。(3) 安全性：根据以上的讨论知，假冒的证明者E欺骗V成功的概率为，这个概率太大了。为减少这个概率，可以将协议重复执行多次，设执行次，则欺骗成功的概率将减少到。解二：(1)构造背包问题先选大素数， ，是素数，且 也为素数，为的本原根。P随机选取个整数， (不用超递增序列)，计算式中，为秘密密钥；， 为公开。(2)零知识证明协议1)P随机选择，计算 ，并将传送给V；2)V随机选择个二进制比特序列，并将其传送给P；3)P计算，并将其传送给V。4)V验证，计算 比较是否成立，若成立，说明P了解秘密密钥，；反之，P为假冒。(3)安全性此类算法的安全威胁主要来自P欺骗V或V假冒P。假如使用的背包和离散对数没有问题，P欺骗V和V假冒P成功的概率都基于 的随机性，若每一个的选取为0或1的概率为，则假冒或欺骗成功的几率为；若该协议重复次，成功的几率为。2、 在8.1.4节，基于大数分解问题的“多传一”不经意传输协议中为什么要求？设，B选择，且想获得A的秘密，分析B是否能成功获得。解：(1) 要求是为了保证同一数在模下的两个平方根有相反的Jacobi符号。(2) B先计算Jacobi符号和，将4,1发给A。接下来A计算4 mod55的平方根，求出4在mod 5时的平方根为2，4在mod11时的平方根为2，可得以下四个方程组： 由第一个方程组的解为；第二个方程组的解为；第三个方程组的解为；第四个方程组的解为；因，A将42或53发给B。当A将42发给B时，B由得到的一个因子，从而得到的分解式，从而获得A的秘密。当A将53发给B时，因,所以B不能计算出的一个因子，没有得到任何新信息，从而不能获得A的秘密。3、 设是素数，群的元素是群的生成元，当且仅当对每一，存在一整数，使得。(1) 在中均匀、随机选取一元素，证明，如果不是的生成元，则存在一整数，使得成立的概率至多是。(2) 给出是的生成元的零知识证明。(3) 在(2)中的零知识证明中，证明者能否在多项式时间内完成证明，为什么？解：(1) 因为不是的生成元，记循环群为，显然是的子群，且，设，是一个大于1的正整数，所以。在中均匀、随机选取一元素，若，则可在上找到一个，使得成立。而的概率至多是，所以成立的概率至多是。(2) V在中任意取一个元素，发送给P。 P知道，使得。P在中随机取一个元素，计算并发送给V。 V随机选，将发给P； P计算并发送给V V验证，若成立，则接受P的证明。 P和V重复以上过程次。(3) 以上的证明可以在多项式时间内完成。因为，是一个有限值，可以在多项式时间内完成。4、 设n是两个未知大素数p和q的乘积，x0,x1Zn且其中至少一个是模n的二次剩余。又设x0,x1模n的Jacobi符号都为1，考虑下面交互证明系统，其中x0,x1和n作为输入，P为证明者，