密码学答案2

《密码学原理与实践(第三版)》课后习题参考答案(由华中科技大学信安09级提供)第二章2.1（何锐）解：依题意有：x∈{2,…,12}，y∈{D，N}计算Pr[x，y]：Pr[2，D]=1/36Pr[3，D]=0Pr[4，D]=1/36Pr[5，D]=0Pr[6，D]=1/36Pr[7，D]=0Pr[8，D]=1/36Pr[9，D]=0Pr[10，D]=1/36Pr[11，D]=0Pr[12，D]=1/36Pr[2，N]=0Pr[3，N]=1/18Pr[4，N]=1/18Pr[5，N]=1/9Pr[6，N]=1/9Pr[7，N]=1/6Pr[8，N]=1/9Pr[9，N]=1/9Pr[10，N]=1/18Pr[11，N]=1/18Pr[12，N]=0计算Pr[x|y]：有Pr[D]=1/6Pr[N]=5/6Pr[2|D]=1/6Pr[3|D]=0Pr[4|D]=1/6Pr[5|D]=0Pr[6|D]=1/6Pr[7|D]=0Pr[8|D]=1/6Pr[9|D]=0Pr[10|D]=1/6Pr[11|D]=0Pr[12|D]=1/6Pr[2|N]=0Pr[3|N]=1/15Pr[4|N]=1/15Pr[5|N]=2/15Pr[6|N]=2/15Pr[7|N]=1/5Pr[8|N]=2/15Pr[9|N]=2/15Pr[10|N]=1/15Pr[11|N]=1/15Pr[12|N]=0计算Pr[y|x]：Pr[D|2]=1Pr[D|3]=0Pr[D|4]=1/3Pr[D|5]=0Pr[D|6]=1/5Pr[D|7]=0Pr[D|8]=1/5Pr[D|9]=0Pr[D|10]=1/3Pr[D|11]=0Pr[D|12]=1Pr[N|2]=0Pr[N|3]=1Pr[N|4]=2/3Pr[N|5]=1Pr[N|6]=4/5Pr[N|7]=1Pr[N|8]=4/5Pr[N|9]=1Pr[N|10]=2/3Pr[N|11]=1Pr[N|12]=0有上面的计算可得：Pr[D|x]Pr[x]=Pr[D]Pr[x|D]Pr[N|x]Pr[x]=Pr[N]Pr[x|N]显然符合Bayes定理。2.2（王新宇）证明：由P=C=K=zn，对于1≤i≤n,加密规则ei(j)=L(i,j)（1≤j≤n)，且每行的加密规则不同。首先，计算C的概率分布。假设izn，则)](Pr[i]Pr[]Pr[dKjZkKyynk)](Pr[in1dKjZnk)](Pr[in1dKjZnk由L是n×n的矩阵，且n个整数的每一个在L的每一行和每一列中恰好出现一次。则固定j，有1)](Pr[idKjZnk则对任意的izn，有nj1]Pr[对于任意的i，j，由满足ei(j)=L(i,j)的K是唯一的，有]Pr[]|Pr[Kijn1由Bayes定理]Pr[]|Pr[]Pr[]|Pr[jijijinni11]Pr[]Pr[i所以拉丁方密码体制具有完善保密性。2.3（邹超第）(a)在仿射密码中，==26,对于任意的K=(a,b)x,y26,加密函数ek(x)=(ax+b)mod26.解密函数dk(y)=a-1(y-b)mod26首先计算的概率分布。假设y26，则Pr[y=y]=]=]=]固定y,a,则构成26的一个置换。固定y,b,则构成26的另一个置换。因此有=]=1因此对于任意的Pr[y]=又对于任意的x,y，满足ek(x)=(ax+b)mod26的K是唯一的,所以Pr[y|x]=Pr[k=(a,b),使得(dk(y)=a-1(y-b)mod26)]=又由贝叶斯定理,可得:Pr[x|y]==Pr[x].因此改密码体制是完善保密性的.(b)由信息安全数学知识可以证明:a在26上存在乘法逆,当且仅当gcd（a,26）=1，并且其如果存在，则必唯一。由数学知识可知Pr[a]=（见课本第八页。）则Pr[a,b]=.同理可得：Pr[y=y]=]=]=]=因此对于任意的Pr[y]=又Pr[y|x]=Pr[k=(a,b),使得(dk(y)=a-1(y-b)mod26)]=又由贝叶斯定理,可得:Pr[x|y]==Pr[x].因此在该密钥空间上,仿射密码密是完善保密性的.2.4（李亮）解：设该密码体制为（P，C，K，ε，D），P={a1,a2,……，an},K={K1,K2,……,Km},事先选取的固定的密钥概率分布为Pr[K1],Pr[K2],……,Pr[Km],且一个特定的明文概率分布为Pr0[a1],Pr0[a2],……,Pr[an],则：因为该密码体制对这个特定的明文概率分布具有完善保密性，所以对任意的x∈P,y∈C(y=ek(x),k∈K)有：Pr0[x|y]=(Pr0[x]Pr0[y|x])/Pr0[y]=Pr0[x]所以Pr0[y|x]=Pr0[y]又Pr0[y|x]=Pr[k]所以Pr0[y]=Pr[k]而密钥的概率是事先选定的所以y的概率分布固定对任意的明文概率分布Pr[a1],Pr[a2],……,Pr[an]选取任意的x∈P，y∈C且y=ek(x),k∈KPr[x|y]=(Pr[x]Pr[y|x])/Pr[y]=Pr[x]×Pr[k]/Pr[y]因为是同一个密码体制且y的概率分布固定所以Pr[k]/Pr[y]=1即Pr[x|y]=Pr[x]所以对任意的明文概率分布这个密码体制仍然具有完善保密性2.5(陈佳）解：分析：参考书上41P定理2.4对于任意的Px和Cy，一定至少存在一个密钥k满足yxek)(。因此有不等式：|||}:)({|||KKkxeCk又因为||||KC，因此|||}:)({|KKkxek也就是说，不存在两个不同的密钥1k和2k使得yxexekk)()(21。因此对于Px和Cy，刚好存在一个密钥k使得yxek)(。设||Kn。设}1:{nixPi并且固定一个密文Cy。设密钥为nkkk,...,,21，并且niyxeiki1,)(。使用Bayes定理，我们有]Pr[]Pr[]Pr[]Pr[]Pr[]|Pr[]|Pr[yxkKyxxyyxiiiii考虑完善保密的条件]Pr[]|Pr[iixyx。可得，niyki1],Pr[]Pr[。也就是所所有密钥都是等概率使用的，即nki/1]Pr[。对于任意Cy，则)](Pr[1)](Pr[1)](Pr[]Pr[]Pr[ydxnydxnydxkKyYKkkkKkKkk因为对于Px和Cy，刚好存在一个密钥k使得yxek)(，所以1)](Pr[ydxKkk即：nyY1]Pr[，每个密文都是等概率2.5解：由题知，对于任意的x∈P和y∈C,一定至少存在一个密钥K满足ek(x)=y,∴有|C|=|{ek(x):k∈K}|≤|K|又∵|C|=|K|∴一定有|{ek(x):k∈K}|=|K|∴不存在两个不同的密钥k1和k2，使ek1(x)=ek2(x)=y∴对于x∈P，y∈C，刚好存在一个密钥K使得ek(x)=y令n=|K|，设P=｛xi:1≤i≤n｝，并且固定一个密文y∈C，设密钥为k1，k2，.........Kn，且有eki(xi)=y，1≤i≤n，由贝叶斯定理得：Pr[xi|y]=﹙Pr[y|xi]Pr[xi]﹚／Pr[y]又已知明文、密文条件下，密钥固定∴Pr[y|xi]=Pr[k=ki]∴Pr[xi|y]=﹙Pr[k=ki]Pr[xi]﹚／Pr[y]由完善保密性得：Pr[xi|y]=Pr[xi]∴﹙Pr[k=ki]Pr[xi]﹚／Pr[y]=Pr[xi]∴Pr[k=ki]=Pr[y]∴每个密钥等概率使用，Pr[k]=1／n∴每个密文都是等概率的2.6（范郢）解：由一次一密体制可知()mod2'(')mod2yxkyxk两式相加得'('2)mod2yyxxk所以有'(')mod2yyxx因此'(')mod2xxyy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到x2k+1-n的xi，将i转化成k位的二进制数，作为xi的编码对于x2k+1-n到xn的xi，将i-（2k+1-n）转化成k位的二进制数，再在前面加上一位置1，B:当n=6时，H(x)=-∑p[xi]㏒p[xi]=㏒6≈2.5822≤6≤23，故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)101010.250.570.431x∈Xadebc故各结点编码结果如下：结点概率p编码长度la0.32002b0.23102c0.20112d0.150103e0.100113该编码最后的平均长度为：L=0.32×2+0.23×2+0.20×2+0.15×3+0.10×3=0.25和熵比较：H（X）=-∑Pr[x]lbPr[x]=-（0.32lb0.32+0.23lb0.23+0.20lb0.20+0.15lb0.15+0.10lb0.10）≈0.221可以看出，编码的平均长度和熵很接近。2.10（杨波）证：2(,)(,)log(,)ijijijHXYpxypxy2(,)log[()(/)]ijjijijpxypypxy22()(/)log()(,)log(/)jijjijijijijpypxypypxypxy2()log()[(/)](/)jjijiipypypxyHXY()(/)HYHXY证毕.由定理2.7（P47）(,)()()HXYHXHY，当且仅当X和Y统计独立时等号成立。得，(,)()(/)()()HXYHYHXYHXHY，当且仅当X和Y统计独立时等号成00.100.32立。2.11（吴昊为）证明密码体制具有完善保密性当且仅当。证明：根据熵的定义，有：①②必要性：根据完善保密性定义，对于任意,有：③将③代入①式可得：即，必要性得证。充分性：联立上式：∴对于任意,有：∴该密码体制具有完善保密性，充分性得证∴密码体制具有完善保密性当且仅当。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)=-Pr[a]lbPr[a]-Pr[b]lbPr[b]-Pr[c]lbPr[c]=-1/2×lb1/2-1/3×lb1/3-1/6×lb1/6≈1.46②由于密钥是等概率选取，则Pr[K1]=Pr[K2]=P