密码学原理与实践课后习题参考答案2修订

1、密码学原理与实践(第三版)课后习题参考答案(由华中科技大学信安09级提供，名单略)第二章2.1解：依题意有：x2,12，yD，N 计算Prx，y：Pr2，D=1/36 Pr3，D=0 Pr4，D=1/36 Pr5，D=0 Pr6，D=1/36 Pr7，D=0 Pr8，D=1/36 Pr9，D=0 Pr10，D=1/36 Pr11，D=0 Pr12，D=1/36Pr2，N=0 Pr3，N=1/18 Pr4，N=1/18 Pr5，N=1/9Pr6，N=1/9 Pr7，N=1/6 Pr8，N=1/9 Pr9，N=1/9Pr10，N=1/18 Pr11，N=1/18 Pr12，N=0 计算Prx |

2、y：有PrD=1/6 PrN=5/6Pr2 | D=1/6 Pr3 | D=0 Pr4 | D=1/6 Pr5 | D=0 Pr6 | D=1/6 Pr7 | D=0 Pr8 | D= 1/6 Pr9 | D=0 Pr10 | D= 1/6 Pr11 | D=0 Pr12 | D=1/6 Pr2 | N=0 Pr3 | N=1/15 Pr4 | N=1/15 Pr5 | N=2/15 Pr6 | N=2/15 Pr7 | N=1/5 Pr8 | N=2/15 Pr9 | N=2/15 Pr10 | N=1/15 Pr11 | N=1/15 Pr12 | N=0 计算Pry | x：PrD |

3、2=1 PrD | 3=0 PrD | 4=1/3 PrD | 5=0 PrD | 6=1/5 PrD | 7=0 PrD | 8=1/5 PrD | 9=0 PrD | 10=1/3 PrD | 11=0 PrD | 12=1 PrN | 2=0 PrN | 3=1 PrN | 4=2/3 PrN | 5=1 PrN | 6=4/5 PrN | 7=1 PrN | 8=4/5 PrN | 9=1 PrN | 10=2/3 PrN | 11=1 PrN | 12=0 有上面的计算可得： PrD | xPrx = PrDPrx | D PrN | xPrx = PrNPrx | N显然符合Bay

4、es定理。2.2证明： 由P=C=K=，对于1in,加密规则(j)=L(i,j)（1jn)， 且每行的加密规则不同。 首先，计算C的概率分布。假设i，则 )(PriPrPrdKjZkKjnk 由L是nn的矩阵，且n个整数的每一个在L的每一行和每一列中恰好出现一次。则固定j，有 则对任意的i，有 对于任意的i，j，由满足(j)=L(i,j)的K是唯一的，有 由Bayes定理 所以拉丁方密码体制具有完善保密性。 2.3 (a)在仿射密码中，P= C=z26,对于任意的K=(a,b) ,x,yz26,加密函数ek(x)=(ax+b)mod26.解密函数dk(y)=a-1首先计算C的概率分布。假设yz

5、26又由贝叶斯定理,可得:Prx|y= QUOTE PrxPry|xPry=Prx13121因此该密码体制是完善保密性的.(b)因此在该密钥空间上,仿射密码密是完善保密性的.2.4解：若对特定明文分布完善保密，则有： 该等式与明文分布无关，因此对任意明文分布都成立，所以对任意明文分布都是完善保密的。2.5解：分析：参考书上 定理2.4对于任意的 和 ，一定至少存在一个密钥k满足。因此有不等式： 又因为，因此 也就是说，不存在两个不同的密钥和使得。因此对于和，刚好存在一个密钥k使得。 设。设并且固定一个密文。设密钥为，并且。使用Bayes定理，我们有 考虑完善保密的条件。可得，。也就是所所有密钥

6、都是等概率使用的，即。 对于任意，则因为对于和，刚好存在一个密钥k使得，所以即： ，每个密文都是等概率。（注：可直接用定理2.4的结论证明。）解：由一次一密体制可知两式相加得所以有因此2.7加密矩阵000001010011100101110111000000001010011100101110111001001000011010101100111110010010011000001110111100101011011010001000111110101100100100101110111000001010011101101100111110001000011010110110111100101

7、010011000001111111110101100011010001000b由一次一密有ek(X)=（X1+K1,Xn+Kn）mod2，明文、密文、密钥都是n位二进制数，共2n种，所以行列数都为2n，该矩阵为2nX2n矩阵。且该矩阵中每行都是0至2n-1这2n个二进制数。又由于该矩阵是定义在（Z2）n上的“一次一密”密码体制加密矩阵，所以对于ekm(Xn)而言，不会存在eki(Xn)或者ekm(Xj)等于ekm(Xn)，即对于矩阵中第m行、第n列的密文在该行与该列内没有与其相同的密文。所以该矩阵是2nX2n矩阵，2n个元素在每一行和每一列恰好出现一次的阶为2n的拉丁方。2.8A:编码方案：

8、X=x0,x1, xn-1 对于x0 到x 2k+1-n-1的xi，将i转化成k位的二进制数，作为xi的编码 (0=2k+1-n-12k)对于x 2k+1-n到xn-1的xi，将i+2k+1-n转化成k+1位的二进制数作为xi的编码.其中2(2k+1-n)=i+2k+1-n2k+1-1,因此i+2k+1-n的左边k位大于或等于2k+1-n，与x0 到x 2k+1-n-1的编码不会相等。整体是一个无前缀编码。平均编码长度为：(k(2k+1-n)+(k+1)(n-(2k+1-n)/n=k+2-2k+1/n.B:当n=6时， H(x)= -pxipxi= 62.5822623 ，故k=2,其中2k+

9、1-n=2,x0,x1编码为00,01X2,x3,x4,x5依次编码为100,101,110,111，L(f)= 2+2-8/6=8/32.672.9解： Huffman编码得到的编码树如下：（令左分支编码为1，右分支编码为0)111010.230.201100.431010.230.201100.430.570.5700abcabc0.250.0.250.320de0de0.150.150.10故各结点编码结果如下：结点概率p编码长度la0.32002b0.23102c0.20112d0.150103e0.100113该编码最后的平均长度为：L=0.322+0.232+0.202+0.153

10、+0.103=0.25和熵比较：H（X） = - PrxlbPrx= -（0.32lb0.32+0.23lb0.23+0.20lb0.20+0.15lb0.15+0.10lb0.10 0.221可以看出，编码的平均长度和熵很接近。2.10证：证毕.由定理2.7（P47），当且仅当X和Y统计独立时等号成立。得， ，当且仅当X和Y统计独立时等号成立。2.11证明密码体制具有完善保密性当且仅当HP证明：根据熵的定义，有：HPCHP=-必要性：根据完善保密性定义，对于任意xP,yC有：Prxy将代入式可得：H=即Prx充分性：H= H联立上式：H 对于任意xP,yC有：Prx 该密码体制具有完善保密性

11、，充分性得证 密码体制具有完善保密性当且仅当HP2.12因为H(K,P,C)=H(P|K,C)+H(K,C)H(K,C)所以H(K,C)H(P,C)而H(K|C)=H(K,C)-H(C)H(P|C)=H(P,C)-H(C)所以H(K|C)H(P|C)2.13解： H(P)=-PralbPra-PrblbPrb-PrclbPrc =-1/2lb1/2-1/3lb1/3-1/6lb1/6 1.46 由于密钥是等概率选取，则 PrK1= PrK2= PrK3=1/3 根据加密矩阵得出密文的概率分布为 Pr1=PrK1Pra+PrK3Prc=1/31/2+1/31/6=2/9 Pr2=PrK1Prb+

12、PrK2Pra=1/31/3+1/31/2=5/18Pr3=PrK1Prc+PrK2Prb+PrK3Pra=1/31/6+1/31/3+1/31/2=1/3Pr4=PrK2Prc+PrK3Prb=1/31/6+1/31/3=1/6 所以 H(C)=-Pr1lbPr1-Pr2lbPr2-Pr3lbPr3-Pr4lbPr4 =-2/9lb2/9-5/18lb5/18-1/3lb1/3-1/6lb1/6 1.95 由于密钥是等概率选取,所以H(K)=lb31.85 根据定理2.10，H(K|C)=H(K)+H(P)-H(C) 1.85+1.46-1.95 =1.36 根据Bayes定理计算给定密文后

13、,明文空间上的条件概率分布Pra|1=(PraPrK1)/Pr1=(1/21/3)/(2/9)=3/4Prb|1=0Prc|1=(PrcPrK3)/Pr1=(1/61/3)/(2/9)=1/4Pra|2=(PraPrK2)/Pr2=(1/21/3)/(5/18)=3/5Prb|2=(PrbPrK1)/Pr2=(1/31/3)/(5/18)=2/5Prc|2=0Pra|3=(PraPrK3)/Pr3=(1/21/3)/(1/3)=1/2Prb|3=(PrbPrK2)/Pr3=(1/31/3)/(1/3)=1/3Prc|3=(PrcPrK1)/Pr3=(1/61/3)/(1/3)=1/6Pra|4

14、=0Prb|4=(PrbPrK3)/Pr4=(1/31/3)/(1/6)=2/3Prc|4=(PrcPrK2)/Pr4=(1/61/3)/(1/6)=1/3 由公式H(X|Y)=-PryPrx|ylbPrx|y得 H(P|C)=-Pr1(Pra|1lbPra|1+Prb|1lbPrb|1 +Prc|1lbPrc|1)-Pr2(Pra|2lbPra|2+Prb|2lbPrb|2 +Prc|2lbPrc|2) -Pr3(Pra|3lbPra|3+Prb|3lbPrb|3 +Prc|3lbPrc|3) -Pr4(Pra|4lbPra|4+Prb|4lbPrb|4 +Prc|4lbPrc|4) =-2

15、/9(3/4lb3/4+1/4lb1/4) -5/18(3/5lb3/5+2/5lb2/5) -1/3(1/2lb1/2+1/3lb1/3+1/6lb1/6) -1/6(2/3lb2/3+1/3lb1/3) 1.092.14对于仿射密码，y=(ax+b)mod 26，(a,26)=1。密钥a，b等概率选取，概率为1/312 ，所以密钥的熵H(K)=-lb(1/312)=8.29明文等概率选取，所以明文的熵H(P)=-lb(1/26)=4.70所以密文的熵H(C)= -lb(1/26)=4.70又因为仿射密码的完善保密性，所以H(P|C)= H(P)=4.70由定理2.10，H(K|C)=H(K

16、)+H(P)-H(C)= H(K) =8.29；H(K|P,C)= H(K,P,C)- H(P,C)= H(K,P)- H(P,C)= H(K)+H(P)-H(P,C)= H(K)+H(P)-H(P|C)-H(C)=8.29-4.70=3.59.2.15证明： 又因为加密算法是密钥字长为m的维吉尼亚密码 所以有 所以（注：实际是将m个字符看作一个新的字符，形成一种新的语言，根据定义，新的语言的冗余度不变。）2.16解：由15题的结论，等号仅当m=1时成立。2.17(a) 解：由n0lb|K|R 且|K|n!2n故 n0 lb(2n(b)解：由题知n=26m代入式中得n0lb2（注：自己算算）2

17、.18解：令S: ek(x)=(x+k)mod26是密钥等概率选取的移位密码（1）SS中的密码算法是密钥等概率选取的移位密码算法对于任意密钥k1,k2，ek2(ek1(x)= ek1+k2(x).又因为：k1、k2是密钥等概率选取时，k1+k2也等概率选取，所以结论成立。（2）任意一个密钥等概率选取的移位密码算法，都在SS中。令ek3(x)=(x+k3)mod26，构造ek1(x)=(x+k1)mod26，和ek3-k1(x)=(x+ k3-k1)mod26,当k1等概率选取，k3-k1也是等概率选取。且ek3-k1(ek1(x)=ek3(x)综上：SS=S，即密钥等概率选取的移位密码是幂等的。2.19解：移位密码的加密算法为 ek(x)=(x+k)mod26设S1和S2的密钥空间分别为K1和K2.（1）S1S