密码学答案.doc

密码学原理与实践(第三版)课后习题参考答案(由华中科技大学信安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 | 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 | 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显然符合Bayes定理。2.2（王新宇）证明： 由P=C=K=，对于1in,加密规则(j)=L(i,j)（1jn)， 且每行的加密规则不同。 首先，计算C的概率分布。假设i，则 由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(y-b)mod26首先计算C的概率分布。假设yz26，则Pry=y= ( a,b)z26 X z26PrK=kPrx=dk(y)= ( a,b)z26 X z261312Prx=dk(y)=1312 ( a,b)z26 X z26Prx=a-1(y-b)固定y,a,则a-1(y-b)构成z26的一个置换。固定y,b,则a-1(y-b)构成z26的另一个置换。因此有 ( a,b)z26 X z26Prx=a-1(y-b)= xz26 Prx=x=1因此对于任意的Pry= 1312又对于任意的x,y，满足ek(x)=(ax+b)mod26的K是唯一的,所以Pry|x=Prk=(a,b),使得(dk(y)=a-1(y-b)mod26)=Pry= 1312又由贝叶斯定理,可得:Prx|y=PrxPry|xPry=Prx13121312= Prx.因此改密码体制是完善保密性的.(b)由信息安全数学知识可以证明:a在z26上存在乘法逆,当且仅当gcd（a,26）=1，并且其如果存在，则必唯一。由数学知识可知Pra= 17 （见课本第八页。）则Pra,b= 1182.同理可得：Pry=y= ( a,b)z26 X z26PrK=kPrx=dk(y)= ( a,b)z26 X z261182Prx=dk(y)=1182 ( a,b)z26 X z26Prx=a-1(y-b)=1182因此对于任意的Pry= 1182又Pry|x=Prk=(a,b),使得(dk(y)=a-1(y-b)mod26)=Pry= 1182又由贝叶斯定理,可得:Prx|y=PrxPry|xPry=Prx11821182= Prx.因此在该密钥空间上,仿射密码密是完善保密性的.2.4（李亮）解：设该密码体制为（P，C，K，D），P=a1,a2,，an,K=K1,K2,Km,事先选取的固定的密钥概率分布为PrK1,PrK2,PrKm,且一个特定的明文概率分布为Pr0a1,Pr0a2,Pran,则：因为该密码体制对这个特定的明文概率分布具有完善保密性，所以对任意的xP,yC(y=ek(x),kK)有：Pr0x|y=(Pr0xPr0y|x)/Pr0y=Pr0x所以Pr0y|x=Pr0y 又Pr0y|x=Prk 所以Pr0y=Prk而密钥的概率是事先选定的 所以y的概率分布固定对任意的明文概率分布Pra1,Pra2,Pran选取任意的xP，yC且y=ek(x),kKPrx|y=(PrxPry|x)/Pry=PrxPrk/Pry因为是同一个密码体制且y的概率分布固定 所以Prk/Pry=1 即Prx|y=Prx所以对任意的明文概率分布这个密码体制仍然具有完善保密性2.5(陈佳）解：分析：参考书上 定理2.4对于任意的 和 ，一定至少存在一个密钥k满足。因此有不等式： 又因为，因此 也就是说，不存在两个不同的密钥和使得。因此对于和，刚好存在一个密钥k使得。 设。设并且固定一个密文。设密钥为，并且。使用Bayes定理，我们有 考虑完善保密的条件。可得，。也就是所所有密钥都是等概率使用的，即。 对于任意，则因为对于和，刚好存在一个密钥k使得，所以即： ，每个密文都是等概率2.5 解：由题知，对于任意的xP和yC,一定至少存在一个密钥K满足ek(x)=y,有 |C|=|ek(x):kK|K| 又|C|=|K|一定有 |ek(x):kK|=|K|不存在两个不同的密钥k1和k2，使 ek1(x)=ek2(x)=y对于xP，yC，刚好存在一个密钥K使得ek(x)=y令n=|K|，设P=xi:1in，并且固定一个密文yC，设密钥为k1，k2，.Kn，且有eki(xi)=y，1in，由贝叶斯定理得： Prxi|y=Pry|xi PrxiPry又已知明文、密文条件下，密钥固定 Pry|xi=Prk=ki Prxi|y=Prk=ki PrxiPry由完善保密性得： Prxi|y=Prxi Prk=ki PrxiPry=Prxi Prk=ki=Pry每个密钥等概率使用，Prk=1n每个密文都是等概率的2.6 （范郢）解：由一次一密体制可知两式相加得所以有因此2.7（李渠）a. 加密矩阵000001010011100101110111000000001010011100101110111001001000011010101100111110010010011000001110111100101011011010001000111110101100100100101110111000001010011101101100111110001000011010110110111100101010011000001111111110101100011010001000b由一次一密有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.8（熊磊）A:编码方案：X=x1,x2, xn-1,xn,对于x1 到x 2k+1-n的xi，将i转化成k位的二进制数，作为xi的编码 对于x 2k+1-n到xn的xi，将i-（2k+1-n）转化成k位的二进制数，再在前面加上一位置1，B:当n=6时， H(x)= -pxipxi= 62.5822623 ，故k=2,其中2k+1-n=2,x1,x2编码为00,01，x3,x4,x5,x6依次编码为100,101,110,111，L(f)= (2*2+4*3)/6=8/3=2.62.9（靳淑蕉）解： Huffman编码得到的编码树如下：（令左分支编码为1，右分支编码为0)11010.250.230.2000.151100.430.5700.32abc0.10de故各结点编码结果如下：结点概率p编码长度la0.32002b0.23102c0.20112d0.150103e0.100113该编码最后的平均长度为：L=0.322+0.232+0.202+0.153+0.103=0.25和熵比较：xXH（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（吴昊为）证明密码体制具有完善保密性当且仅当HPC=H(P)。证明：根据熵的定义，有：HPC=-yCxPPrxyPrylog2PrxyHP=-xPPrxlog2Prx必要性：根据完善保密性定义，对于任意xP,yC有：Prxy= Prx将代入式可得：HPC=-yCxPPrxPrylog2Prx=-xPPrxlog2Prx= HP即Prxy= PrxHPC=H(P)，必要性得证。充分性：HPC=-yCxPPrxyPrylog2Prxy=-yCxPPrx,ylog2Prx,y+yCxPPrx,ylog2Pry=HP,C-H(C) HPC=H(P)联立上式：HP,C=HC+ H(P) HP,CHC+ HP当且仅当P,C统计独立时等号成立 对于任意xP,yC有：Prxy= Prx 该密码体制具有完善保密性，充分性得证 密码体制具有完善保密性当且仅当HPC=H(P)。2.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+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定理计算给定密文后,明文空间上的条件概率分布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=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/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)+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（陈雕）解：作出如下假设，明文、密文、密钥元素（指密钥矩阵的每个元素Kij）都是取自126， 则mm矩阵的可能取值为26mm，即 |K| = 26mm又已知n0 = 。则n0 = 注意到 在希尔密码体系中 我们将长为 m 的串视为一个单位故希尔密码 的唯一解距离是 Ps：事实上这个解释是有缺点的。希尔密码的密钥空间并没有26mm这么大，这是因为希尔密码要求密钥矩阵是可逆矩阵。这要求m*m的矩阵中可逆矩阵的个数，这个还是别说了吧。2.17（丁洪鑫）(a) 解：由n0lb|K|RLlb|P| 且|K|n!2n(ne)n,|P|=n故 n0 lb(2n(ne)n)RLlbn（）(b)解：由题知n=26m代入式中得n0lb22mRLlb26+12RL+26mRL-26mlbemRLlb262.18（潘莹）另S1: ex=(x+k1)mod26，S2: ex=(x+k2)mod26则S1S2=(x+ k1+ k2) mod26=(x+k3)mod26= S又因为：S1、S2是密钥等概率选取的。即：k1、k2选取的概率为1/26所以k3选取的概率也为1/26所以：S1、S2和S的明文空间与密文空间一样所以：S2=S依次类推：Sn=S所以：密钥等概率选取的移位密码是幂等的。2.19（李怡）解：该乘积密码具有（S1，S2）的形式，S1，S2Z26.所以e(S1，S2)(x) = x+（S1+S2）.由表达式易看出S1*S2也是移位密码。证明：令Pi是S1*S2中的一个密码，则 说明Pi同样有可能是移位密码中的密钥所以 S1*S2也是移位密码 故 S1*S2 = S12.20（文豪、陈磊）（1）证明：显然对于维吉尼亚密码S，SS还是维吉尼亚密码，即幂等。 假设S1密钥空间K1=Z26m1，S2密钥空间K2=Z26m2.现在任取密钥空间（K2，K1）中的密钥对（k2,k1）e(k2,k1)(X)=ek2(ek1(X). （X是一明文串）将X分成长度均为m2的子串：x1,x2,x3.;将密钥k1同样分成长度均为m2的子密钥：k