1、密码学原理与实践(第三版) 课后习题参考答案(由华中科技大学信安 09 级提供)第二章2.1（何锐）解：依题意有：x2,12，y D，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
2、计算 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
3、 | 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
4、 | N显然符合 Bayes 定理。2.2（王新宇）证明： 由 P=C=K= zn，对于 1in,加密规则 ei(j)=L(i,j)（1jn)，且每行的加密规则不同。首先，计算 C 的概率分布。假设 izn，则)(PrrPr dKjZkynki1jnk)(Prin1dKjZk由 L 是 nn 的矩阵，且 n 个整数的每一个在 L 的每一行和每一列中恰好出现一次。则固定 j，有1)(PriKjZnk则对任意的 i z，有jr对于任意的 i，j ，由满足 ei(j)=L(i,j)的 K 是唯一的，有Pr|rn1由 Bayes 定理Pr|rjiijini1Pri所以拉丁方密码体制具有完善保密性。2.
5、3（邹超第）(a)在仿射密码中， = = 26,对于任意的 K=(a,b) x,y 26, , 加密函数 ek(x)=(ax+b)mod26.解密函数 dk(y)=a-1(y-b)mod26首先计算 的概率分布。假设 y 26，则 Pry=y= ( a,b)26 X 26=dk(y)= ( a,b)26 X 261312=dk(y)= 1312 ( a,b)26 X 26x=1(y-b)固定 y,a,则 构成 26 的一个置换。固定 y,b,1(y-b) 则 构成 26 的另一个置换。因此有1(y-b) = ( a,b)26 X 26x=1(y-b)=1 26 x=因此对于任意的 Pry=13
6、12又对于任意的 x,y，满足 ek(x)=(ax+b)mod26 的 K 是唯一的,所以Pry|x=Prk=(a,b),使得(dk(y)=a -1(y-b)mod26)=Pry=1312又由贝叶斯定理,可得:Prx|y= = Prx.PrxPry|xPry=Prx13121312因此改密码体制是完善保密性的.(b)由信息安全数学知识可以证明:a 在 26 上存在乘法逆,当且仅当 gcd（a,26）=1，并且其如果存在，则必唯一。由数学知识可知 Pra= （见课本第八页。 ）则 Pra,b= .同17 1182理可得：Pry=y= ( a,b)26 X 26=dk(y)= ( a,b)26 X
7、 261182=dk(y)= 1182 ( a,b)26 X 26x=1(y-b)=1182因此对于任意的 Pry=1182又 Pry|x=Prk=(a,b),使得(dk(y)=a -1(y-b)mod26)=Pry=1182又由贝叶斯定理,可得:Prx|y= = Prx.PrxPry|xPry=Prx11821182因此在该密钥空间上,仿射密码密是完善保密性的.2.4（李亮）解：设该密码体制为（P ，C， K，D） ，P=a1,a2,，an,K=K1,K2,Km,事先选取的固定的密钥概率分布为 PrK1,PrK2,PrKm,且一个特定的明文概率分布为Pr0a1,Pr0a2,Pran,则：因为
8、该密码体制对这个特定的明文概率分布具有完善保密性，所以对任意的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(
9、陈佳）解：分析：参考书上 定理 2.441P对于任意的 和 ，一定至少存在一个密钥 k 满足 。因此有不xCy yxek)(等式：|:)(| Kkxe又因为 ，因此|KC|:)(|kxe也就是说，不存在两个不同的密钥 和 使得 。因此对于 和12yxekk)(21 Px，刚好存在一个密钥 k 使得 。Cyyxek)(设 。设 并且固定一个密文 。设密钥为 ，|Kn:niPiCynk,.21并且 。使用 Bayes 定理，我们有iyxeik1,)(Pr r|r|ryxkKxiiiii考虑完善保密的条件 。可得， 。也就是所所有|riix niyki 1,Pr密钥都是等概率使用的，即 。nki/1
10、Pr对于任意 ，则Cy)(Pr1)(rrrydxnydxkKYKkkkkk k因为对于 和 ，刚好存在一个密钥 k 使得 ，所以PxCy yxek)( 1)(PrydxKkk即： ，每个密文都是等概率nY1r2.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=x i:1in ，并且固定一个密文 yC，设密钥
11、为 k1，k 2，.K n，且有 eki(xi)=y，1in，由贝叶斯定理得：Prxi|y=P ry|xi PrxiP ry又已知明文、密文条件下，密钥固定P ry|xi=Prk=kiP rxi|y=P rk=ki PrxiP ry由完善保密性得：Prxi|y=PrxiP rk=ki PrxiP ry=PrxiP rk=ki=Pry每个密钥等概率使用，P rk=1n每个密文都是等概率的2.6 （范郢）解：由一次一密体制可知 ()mod2yxk两式相加得 ()yxk所以有 ()mod2yx因此 ()y2.7（李渠）a. 加密矩阵000 001 010 011 100 101 110 111000
12、 000 001 010 011 100 101 110 111001 001 000 011 010 101 100 111 110010 010 011 000 001 110 111 100 101011 011 010 001 000 111 110 101 100100 100 101 110 111 000 001 010 011101 101 100 111 110 001 000 011 010110 110 111 100 101 010 011 000 001111 111 110 101 100 011 010 001 000b由一次一密有 ek(X)=（X 1+K1,X
13、n+Kn）mod2，明文、密文、密钥都是 n位二进制数，共 2n 种，所以行列数都为 2n，该矩阵为 2nX2n 矩阵。且该矩阵中每行都是 0 至 2n-1 这 2n 个二进制数。又由于该矩阵是定义在（Z 2） 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
14、+1-n 的 xi，将 i 转化成 k 位的二进制数，作为 xi 的编码 对于 x 2k+1-n 到 xn 的 xi，将 i-（2 k+1-n）转化成 k 位的二进制数，再在前面加上一位置 1，xXadebcB:当 n=6 时，H(x)= -px ipx i= 6 2.582262 3 ，故 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)故各结点编码结果如下：结
15、点 概率 p 编码 长度 la 0.32 00 2b 0.23 10 2c 0.20 11 2d 0.15 010 3e 0.10 011 3该编码最后的平均长度为：L=0.322+0.232+0.202+0.153+0.103=0.25和熵比较：H（X） = - PrxlbPrx= -（0.32lb0.32+0.23lb0.23+0.20lb0.20+0.15lb0.15+0.10lb0.10） 0.221010101010.20 0.230.150.100.320.250.570.431可以看出，编码的平均长度和熵很接近。2.10（杨波）证： 2(,)(,)log(,)ijijijHXYp
16、xypxy/ijjijij 2 2()/)l()(,)log(/)jijj ijijij ijyxypxypxy2log/jjiji ippHXY()/)HYX证毕.由定理 2.7（P47） ，当且仅当 X 和 Y 统计独立时等号成立。(,)()Y得， ，当且仅当 X 和 Y 统计独立时等号成(,)/(XYXH立。2.11（吴昊为）证明密码体制具有完善保密性当且仅当 。()=()证明：根据熵的定义，有：()=PrPrlog2Pr()=log2必要性：根据完善保密性定义，对于任意 , 有：Pr= 将代入式可得： ()= PrPrlog2Pr=log2= ()即 ，必要性得证。Pr= ()=()充
17、分性： ()=PrPrlog2Pr= Pr,log2Pr,+Pr,log2Pr=(,)() ()=()联立上式： (,)=()+ () (,)()+ ()当且仅当 ,统计独立时等号成立 对于任意 , 有：Pr= 该密码体制具有完善保密性，充分性得证 密码体制具有完善保密性当且仅当 。()=()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/61.46由于密钥是等概率选取，则PrK1= PrK2= PrK3=1/3根据加密矩阵得出密文的概率分布为Pr1=PrK1Pra+PrK3Prc=1/31/2+1/31/6=2/9Pr2=PrK1Prb+PrK2Pra=1/31/3+1/31/2=5/18Pr3=PrK1Prc+PrK2Prb+PrK3Pra
