《密码学原理与实践(第三版)》课后习题参考答案

(由华中科技大学信安09级提供)

第二章

2.1（何锐）

解：依题意有：x∈{2,?,12}，y∈{D，N} 计算Pr[x，y]：

Pr[2，D]=1/36 Pr[3，D]=0 Pr[4，D]=1/36 Pr[5，D]=0 Pr[6，D]=1/36 Pr[7，D]=0 Pr[8，D]=1/36 Pr[9，D]=0 Pr[10，D]=1/36 Pr[11，D]=0 Pr[12，D]=1/36

Pr[2，N]=0 Pr[3，N]=1/18 Pr[4，N]=1/18 Pr[5，N]=1/9 Pr[6，N]=1/9 Pr[7，N]=1/6 Pr[8，N]=1/9 Pr[9，N]=1/9 Pr[10，N]=1/18 Pr[11，N]=1/18 Pr[12，N]=0 计算Pr[x | y]：

有Pr[D]=1/6 Pr[N]=5/6

Pr[2 | D]=1/6 Pr[3 | D]=0 Pr[4 | D]=1/6 Pr[5 | D]=0 Pr[6 | D]=1/6 Pr[7 | D]=0 Pr[8 | D]= 1/6 Pr[9 | D]=0 Pr[10 | D]= 1/6 Pr[11 | D]=0 Pr[12 | D]=1/6

Pr[2 | N]=0 Pr[3 | N]=1/15 Pr[4 | N]=1/15 Pr[5 | N]=2/15 Pr[6 | N]=2/15 Pr[7 | N]=1/5 Pr[8 | N]=2/15 Pr[9 | N]=2/15 Pr[10 | N]=1/15 Pr[11 | N]=1/15 Pr[12 | N]=0 计算Pr[y | x]：

Pr[D | 2]=1 Pr[D | 3]=0 Pr[D | 4]=1/3 Pr[D | 5]=0 Pr[D | 6]=1/5 Pr[D | 7]=0 Pr[D | 8]=1/5 Pr[D | 9]=0 Pr[D | 10]=1/3 Pr[D | 11]=0 Pr[D | 12]=1

Pr[N | 2]=0 Pr[N | 3]=1 Pr[N | 4]=2/3 Pr[N | 5]=1 Pr[N | 6]=4/5 Pr[N | 7]=1 Pr[N | 8]=4/5 Pr[N | 9]=1 Pr[N | 10]=2/3 Pr[N | 11]=1 Pr[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?Pr[y?y]?

k?zn，则

?Pr[K?k]Pr[i?dZn

K(j)]

?

1Pr[i?dK(j)]?k?Znn?

1Pr[i?dK(j)]?nk?Zn

由L是n×n的矩阵，且n个整数的每一个在L的每一行和每一列中恰好出现一次。

则固定j，有

k??Pr[i?dZnK(j)]?1

则对任意的i?zn，有

Pr[j]?i1n

对于任意的i，j，由满足

e(j)=L(i,j)的K是唯一的，有

Pr[j|i]?Pr[K]

? 由Bayes定理

1n

Pr[i]Pr[j|i]Pr[j]

Pr[i|j]?

Pr[i]?

1n1n

?Pr[i]

所以拉丁方密码体制具有完善保密性。 2.3（邹超第）

(a)在仿射密码中，

= =

26,对于任意的K=(a,b)

x,y

26,

加密函数ek(x)=(ax+b)mod26.解密函数dk(y)=a-1(y-b)mod26 首先计算

的概率分布。假设y

26，则

Pr[y=y]=

]

]

=

=

构成

]

26的一个置换。固定

固定y,a,则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∈K

Pr[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(陈佳）解： 分析：参考书上P41 定理2.4

对于任意的等式：

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。使用Bayes定理，我们有

Pr[y|xi]Pr[xi]Pr[y]

Pr[K?ki]Pr[xi] ?Pr[y]Pr[xi|y]? 考虑完善保密的条件Pr[xi|y]?Pr[xi]。可得，Pr[ki]?Pr[y],1?i?n。也就是所所有密钥都是等概率使用的，即Pr[ki]?1/n。 对于任意y?C，则

Pr[Y?y]??Pr[K?k]Pr[x?dk(y)]k?K1??Pr[x?dk(y)]k?Kn1??Pr[x?dk(y)]nk?K

因为对于x?P和y?C，刚好存在一个密钥k使得ek(x)?y，所以即： Pr[Y?y]?k?K?Pr[x?dk(y)]?1

1，每个密文都是等概率 n2.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 （范郢）

解：

由一次一密体制可知

y?(x?k)mod2y'?(x'?k)mod2两式相加得

y?y'?(x?x'?2k)mod2

所以有

y?y'?(x?x')mod2

因此

x?x'?(y?y')mod2

2.7（李渠）

a. 加密矩阵 000 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 001 001 000 011 010 101 100 111 110 010 010 011 000 001 110 111 100 101 011 011 010 001 000 111 110 101 100 100 100 101 110 111 000 001 010 011 101 101 100 111 110 001 000 011 010 110 110 111 100 101 010 011 000 001 111 111 110 101 100 011 010 001 000 b． 由一次一密有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 2对于x 2置1，

k+1

-n的xi，将i转化成k位的二进制数，作为xi的编码

k+1k+1

-n到xn的xi，将i-（2-n）转化成k位的二进制数，再在前面加上一位

B:当n=6时，

H(x)= -∑p[xi]㏒p[xi]= ㏒6≈2.58 22≤6≤23 ，故k=2,

其中2

k+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.6

2.9（靳淑蕉）

解： Huffman编码得到的编码树如下：（令左分支编码为1，右分支编码为0)

0.43 1 0 1 1 1 0 0.57

0 0.32 a 0.10 e d

c

b

故各结点编码结果如下： 结点 概率p a b c d e 编码 00 10 11 010 011 长度l 2 2 2 3 3 0.32 0.23 0.20 0.15 0.10 该编码最后的平均长度为：

L=0.32×2+0.23×2+0.20×2+0.15×3+0.10×3=0.25 和熵比较：

H（X） = - ∑ Pr[x]lbPr[x]

x∈X = -（0.32lb0.32+0.23lb0.23+0.20lb0.20+0.15lb0.15+0.10lb0.10）

≈ 0.221

可以看出，编码的平均长度和熵很接近。

2.10（杨波） 证：

H(X,Y)????p(xi,yj)log2p(xi,yj)

ij

????p(xi,yj)log2[p(yj)p(xi/yj)]

ij????p(yj)p(xi/yj)log2p(yj)???p(xi,yj)log2p(xi/yj)

ijij???p(yj)log2p(yj)[?p(xi/yj)]?H(X/Y)

ii?H(Y)?H(X/Y)

证毕.

由定理2.7（P47）H(X,Y)?H(X)?H(Y)，当且仅当X和Y统计独立时等号成立。 得， H(X,Y)?H(Y)?H(X/Y)?H(X)?H(Y)，当且仅当X和Y统计独立时等号成

立。

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]= Pr[K3]=1/3

根据加密矩阵得出密文的概率分布为

Pr[1]=Pr[K1]Pr[a]+Pr[K3]Pr[c]=1/3×1/2+1/3×1/6=2/9 Pr[2]=Pr[K1]Pr[b]+Pr[K2]Pr[a]=1/3×1/3+1/3×1/2=5/18

Pr[3]=Pr[K1]Pr[c]+Pr[K2]Pr[b]+Pr[K3]Pr[a]

=1/3×1/6+1/3×1/3+1/3×1/2=1/3

Pr[4]=Pr[K2]Pr[c]+Pr[K3]Pr[b]=1/3×1/6+1/3×1/3=1/6

所以

H(C)=-Pr[1]lbPr[1]-Pr[2]lbPr[2]-Pr[3]lbPr[3]-Pr[4]lbPr[4]

=-2/9×lb2/9-5/18×lb5/18-1/3×lb1/3-1/6×lb1/6 ≈1.95

③由于密钥是等概率选取,所以

H(K)=lb3≈1.85

④根据定理2.10，

H(K|C)=H(K)+H(P)-H(C) ≈1.85+1.46-1.95 =1.36

⑤根据Bayes定理计算给定密文后,明文空间上的条件概率分布

Pr[a|1]=(Pr[a]×Pr[K1])/Pr[1]=(1/2×1/3)/(2/9)=3/4 Pr[b|1]=0

Pr[c|1]=(Pr[c]×Pr[K3])/Pr[1]=(1/6×1/3)/(2/9)=1/4

Pr[a|2]=(Pr[a]×Pr[K2])/Pr[2]=(1/2×1/3)/(5/18)=3/5 Pr[b|2]=(Pr[b]×Pr[K1])/Pr[2]=(1/3×1/3)/(5/18)=2/5 Pr[c|2]=0

Pr[a|3]=(Pr[a]×Pr[K3])/Pr[3]=(1/2×1/3)/(1/3)=1/2 Pr[b|3]=(Pr[b]×Pr[K2])/Pr[3]=(1/3×1/3)/(1/3)=1/3 Pr[c|3]=(Pr[c]×Pr[K1])/Pr[3]=(1/6×1/3)/(1/3)=1/6

Pr[a|4]=0

Pr[b|4]=(Pr[b]×Pr[K3])/Pr[4]=(1/3×1/3)/(1/6)=2/3 Pr[c|4]=(Pr[c]×Pr[K2])/Pr[4]=(1/6×1/3)/(1/6)=1/3

由公式H(X|Y)=-??Pr[y]Pr[x|y]lbPr[x|y]得

yx H(P|C)=-Pr[1](Pr[a|1]lbPr[a|1]+Pr[b|1]lbPr[b|1]

+Pr[c|1]lbPr[c|1])

-Pr[2](Pr[a|2]lbPr[a|2]+Pr[b|2]lbPr[b|2] +Pr[c|2]lbPr[c|2])

-Pr[3](Pr[a|3]lbPr[a|3]+Pr[b|3]lbPr[b|3]

+Pr[c|3]lbPr[c|3])

-Pr[4](Pr[a|4]lbPr[a|4]+Pr[b|4]lbPr[b|4]

+Pr[c|4]lbPr[c|4])

=-2/9×(3/4×lb3/4+1/4×lb1/4) -5/18×(3/5×lb3/5+2/5×lb2/5)

-1/3×(1/2×lb1/2+1/3×lb1/3+1/6×lb1/6) -1/6×(2/3×lb2/3+1/3×lb1/3) ≈1.09

2.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（杨洁勇） 证明： 由

sn?|p||k|?1可知 nRL 令

sn?0，则有

|p||k|?1?0nRL

又因为加密算法是密钥字长为m的维吉尼亚密码 因此每个明文和每个密钥都是有由m个字母组成 所以有

|p?|26,k|?|26

mm 所以

26R26mnm?1?0L

所以

n?1/RL

即唯一解距离是1/

RL

2.16（陈雕）

解：作出如下假设，明文、密文、密钥元素（指密钥矩阵的每个元素Kij）都是取自1~26，

××

则m×m矩阵的可能取值为26mm，即 |K| = 26mm

又已知n0 =

lb|K|。

RLlb|P|lb26m?mm2?则n0 =

RLlb26RL注意到 在希尔密码体系中 我们将长为 m 的串视为一个单位 故希尔密码 的唯一解距离是

m RL

×

Ps：事实上这个解释是有缺点的。希尔密码的密钥空间并没有26mm这么大，这是因为希尔密码要求密钥矩阵是可逆矩阵。这要求m*m的矩阵中可逆矩阵的个数，这个??还是别说了吧。

2.17（丁洪鑫）

(a)

解：由n0≈

,|P|=n

且|K|＝n!≈

(b)

故 n0

??（①）

解：由题知n=26m代入①式中得 n0＝

2.18（潘莹）

另S1: ex=(x+k1)mod26，S2: ex=(x+k2)mod26 则S1×S2=(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，S2∈Z26. 所以e(S1，S2)(x) = x+（S1+S2）.

由表达式易看出S1*S2也是移位密码。 证明：令Pi是S1*S2中的一个密码，则

i?0?2511Pi?2626i?0?Pi?251 26说明Pi同样有可能是移位密码中的密钥 所以 S1*S2也是移位密码 故 S1*S2 = S1

2.20（文豪、陈磊）

（1）证明：显然对于维吉尼亚密码S，S×S还是维吉尼亚密码，即幂等。

假设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的子密钥：k1,1 ,k1,2 ,k1,3……..

则加密过程对X用S2×S1密码加密的过程可以理解为对每一个xi子串，先用密钥k2加密，然后再用子密钥k1,i加密，得到密文串yi，最后将yi按序拼接在一起。 e(xi)=xi+k2+k1,i

= xi+(k2+k1,i) = xi+k3,i; 注意：其中的xi,k2,k1,i均为串，其相加过程为串中每一个对应的字符或者数字相加的过程。K3,i也是字串。

由于维吉尼亚密码是幂等的，所以，由（k2，k1,i）到k3,i的映射是一个双射。

将所有明文子串加密的过程连在一起考虑，那么(m1/m2)个k3,i拼接在一起得到长度为m1的密钥k3。

（k2，k1）到k3的映射是一个双射。

密钥空间（K2，K1）则被映射到密钥空间K3= Z26m1

所以密码S2×S1即为密钥空间为K3的维吉尼亚密码，所以S2×S1= S1

（2）证明：考虑一下情况： 2m1=3m2 （m2是偶数）

则[m1, m2]=2 m1 , 见如下图

m2

m1

根据（1）中的结论，可以看出（3 k2，2 k1）到k3是一个双射

（3 k2，2 k1）表示先对明文串用S2加密3次，然后再用S1加密2次。

k3是密钥长度为[m1, m2]=2 m1的密码。 假设明文长度为（2t+1）m1 t是整数 则对于明文前面的2t m1长度的子串，都可以认为由长度为[m1, m2]=2 m1的密钥k3进行加密。 而对于最后一个长度为m1的子串，其加密过程为：

对子串p先用k2和k2的前m2/2部分连接在一起进行加密，然后再用k1加密一次。根据维吉尼亚密码的幂等性，这个过程就相当于用密钥长度为m1的k3’进行加密。

然后对于整个明文，既有密钥长度为2m1的密钥对其加密，又有密钥长度为m1的密钥k3。因此不是从（3 k2，2 k1）到k3是一个双射。所以S3不一定是一个密钥长度为[m1, m2]的维吉尼亚密码。