2024年2月20日发(作者：后女)
NCUT 密码学 – 习题与答案 2010
（ 声 明：非 标 准 答 案，仅 供 参 考 ）
一、古典密码 （1,2,4）
字母
数字
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 6171819 20 21 22 232425
1. 设仿射变换的加密是 E11,23(m)≡11m+23 (mod 26)，对明文“THE NATIONAL SECURITY
AGENCY”加密，并使用解密变换D11,23(c)≡11-1(c-23) (mod 26) 验证你的加密结果。
解：明文用数字表示：M=[19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24]
密文 C= E11,23(M)≡11*M+23 (mod 26)
=[24 22 15 10 23 24 7 21 10 23 14 13 15 19 9 2 7 24 1 23 11 15 10 19 1]
=
YWPKXYHVKXONPTJCHYBXLPKTB
，或者直接穷举1~25)
∵ 11*19 ≡ 1 mod 26
(说明：求模逆可采用第4章的“4.1.6 欧几里得算法”∴ 解密变换为 D(c)≡19*(c-23)≡19c+5 (mod 26)
对密文C进行解密：
M’=D(C)≡19C+5 (mod 26)
=[19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24]
= THE NATIONAL SECURITY AGENCY
2. 设由仿射变换对一个明文加密得到的密文为 edsgickxhuklzveqzvkxwkzukvcuh，又已知明文的前两个字符是“if”。对该密文解密。
解： 设解密变换为 m=D(c)≡a*c+b (mod 26)
由题目可知 密文 ed 解密后为 if，即有：
D(e)=i ： 8≡4a+b (mod 26) D(d)=f ： 5≡3a+b (mod 26)
由上述两式，可求得 a=3，b=22。
因此，解密变换为 m=D(c)≡3c+22 (mod 26)
密文用数字表示为：
c=[4 3 18 6 8 2 10 23 7 20 10 11 25 21 4 16 25 21 10 23 22 10 25 20 10 21 2 20 7]
则明文为 m=3*c+22 (mod 26)
=[8 5 24 14 20 2 0 13 17 4 0 3 19 7 8 18 19 7 0 13 10 0 19 4 0 7 2 4 17]
=
ifyoucanreadthisthankateahcer
A是2×2矩阵，B是0矩阵，又知明文“dont”4. 设多表代换密码 Ci ≡ AMi + B (mod 26) 中，被加密为“elni”，求矩阵A。
解： dont = (3,14,13,19) => elni = (4,11,13,8)
设
A=⎢⎡ab⎤，
⎥⎣cd⎦⎡4⎤⎣⎦⎡a⎣b⎤⎡3⎤⎢14⎥(mod26)，
d⎥⎦⎣⎦⎡13⎤⎡ab⎤⎡13⎤⎢8⎥=⎢cd⎥⎢19⎥(mod26)
⎣⎦⎣⎦⎣⎦则有：
⎢⎥=⎢11c 可求得
A=⎢⎡1013⎤
⎥⎣923⎦第 1 页
NCUT 密码学 – 习题与答案 2010
二、流密码 （1,3,4）
1. 3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。
解：设反馈函数为 f(a1,a2,a3) = a1⊕c2a2⊕c1a3
当c1=0，c2=0时，f(a1,a2,a3) = a1，输出序列为101101…，周期为3。
当c1=0，c2=1时，f(a1,a2,a3) = a1⊕a2，输出序列如下10…，周期为7。当c1=1，c2=0时，f(a1,a2,a3) = a1⊕a3，输出序列为11…，周期为7。
当c1=1，c2=1时，f(a1,a2,a3) = a1⊕a2⊕a3，输出序列为10101010…，周期为2。
3. 设n=4，f(a1,a2,a3,a4)=a1⊕a4⊕1⊕a2a3，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。
解：列出该非线性反馈移位寄存器的状态列表和输出列表：
状态(a1,a2,a3,a4)f(a1,a2,a3,a4)
输出
1
0
1
1
…
(1,1,0,1)
1 1
(1,0,1,1) 1
(0,1,1,1) 1
(1,1,1,1) 0
(1,1,1,0) 1
(1,1,0,1)
…
1 1
…
因此，输出序列为11011 11011 …，周期为5。
4. 密钥流由m=2s级的LFSR产生，前m+2个比特是(01)s+1，即s+1个01，请问第m+3个比特有无可能是1，为什么？
解： 根据题目条件，可知初始状态s0为：
s0=(a1,a2,L,am−1,am)=(0,1,...,0,1) 注：s个01
设该LFSR的输出序列满足如下递推关系：
则第m+1, m+2个比特为：
am+k=c1am+k−1+c2am−1+Lcmak, k≥1
am+1=c1am+c2am−1+Lcma1=∑c2j−1=0
j=1ss
am+2=c1am+1+c2am+Lcma2=∑c2j=1j=1
而第m+3比特应为：
am+3=c1am+2+c2am+1+c3am+c4am−1+L+cm−1a4+cma3 =c1⋅1+c2⋅0+c3⋅1+c4⋅0+LL+cm−1⋅1+cm⋅0 =∑c2j−1=0j=1s
即第m+3比特为0，因此不可能为1.
M的散列值相同。
第 2 页
NCUT 密码学 – 习题与答案 2010
三、分组密码 （1,2,3,4）
1. (1) 设M’是M的逐比特取补，证明在DES中，如果对明文分组和密文分组都逐比特取补，那么得到的密文也是原密文的逐比特取补，即
如果 Y = DESK(X)，那么 Y’=DESK’(X’)
提示：对任意两个长度相等的比特串A和B，证明(A⊕B)’=A’⊕B。
证：
(i) 容易验证，在DES中所有的置换操作，包括初始置换IP、逆初始置换IP-1、选择扩展算法E、置换运算P以及置换选择PC1、置换选择PC2，都满足如下性质：
如果N=PO(M)，则N’=PO(M’)，其中PO是某种置换操作
即有 (PO(M))’= PO(M’)
(ii) 容易验证，密钥生成过程中的左循环移位LS满足如下性质：
如果N=LS (M)，那么N’=LS(M’)，
即有 (LS (M))’=LS(M’)
结合(1)可知，如果记子密钥为(K1,…,K16)，K为初始密钥，KG为密钥生成算法，则有如下性质：
如果 (K1,…,K16)=KG(K)，那么 (K1',…,K16')=KG(K’)
(iii)
对于任意两个比特a和b，有 (a⊕b)’= a⊕b⊕1=(a⊕1)⊕b=a’⊕b（= a⊕(b⊕1)=a⊕b’），因此对任意两个长度相等的比特串A和B，有(A⊕B)’=A’⊕B=A⊕B’成立。
(iv)
DES的轮变换为⎨⎧⎪Li=Ri−1，其中轮函数F可写为⎪⎩Ri=Li−1⊕F(Ri−1,Ki)F(R,K)=P(S(E(R)⊕K))。 因此有如下推理：
Y=DESK(X)⇒Y'=DESK'(X')⇔ Ri=Li−1⊕F(Ri−1,Ki) ⇒ Ri'=L'i−1⊕F(Ri'−1,Ki')
根据(i)(ii)⇔
(Li−1⊕F(Ri−1,Ki))' =(Li−1⊕F(Ri'−1,Ki')
)'
根据(iii)⇔ F(Ri−1,Ki) =F(Ri'−1,Ki')
⇔ P(S(E(Ri−1)⊕Ki))=P(S(E(Ri'−1)⊕Ki'))⇔ E(Ri−1)⊕Ki=E(Ri'−1)⊕Ki'根据(iii)可知
E(Ri−1)⊕Ki=(E(Ri−1)⊕Ki')'=(E(Ri−1))'⊕Ki⇔ (E(Ri−1))'⊕Ki=E(Ri'−1)⊕Ki'⇔ (E(Ri−1))'=E(Ri'−1) 由(i)知此式成立
(2) 对DES进行穷举搜索攻击时，需要在由256个密钥构成的密钥空间进行。能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。
解：(1) 根据取补的性质，密钥空间K可分成两部分K1/2和K’1/2，即K= K1/2∪K’1/2
对于任意一个k∈K1/2，它的取补k’∈K’1/2；对于任意一个k∈K’1/2，它的取补k’∈K1/2。即，K1/2和K’1/2是一一对应的；它们的空间大小都是
256/2=255。
其中x、y分别为明文和密文，E为DES加密算法，(2) 选择明文攻击时，假设有Ek0(x)=y，k0为真实的密钥。
第 3 页
NCUT 密码学 – 习题与答案 2010
穷举搜索密钥空间K1/2，对于某个k∈K1/2，假设
(i) Ek(x)=y1，如果 y1=y，则说明 k0=k 而且 k0∈K1/2。
(ii) Ek(x’)=y2，如果y2=y’，则说明k= k0’，即k0= k’ 而且 k0∈K’1/2。
综上可知：对于选定的明文密文对(x,y)，只需遍历K1/2中的所有密钥即可，此时密钥空间大小少为255。
2. 证明DES的解密变换是加密变换的逆。
证明：定义T是把64位数据左右两半交换位置的操作，即T(L,R)=(R,L)，则T2(L,R)=(L,R)，即T2=I，其中I为恒等变换。
定义DES中第i轮的主要运算为fi，即
fi(Li−1,Ri−1)=(Li−1⊕F(Ri−1,Ki),Ri−1)
则有，
fi2(Li−1,Ri−1)=(Li−1⊕F(Ri−1,Ki),Ri−1)=fi(Li−1⊕F(Ri−1,Ki),Ri−1)=((Li−1⊕F(Ri−1,Ki))⊕F(Ri−1,Ki),Ri−1)=(Li−1,Ri−1) 即
fi2=I。
DES的加密为：
c=DES(m)=IP−1⋅f16⋅(T⋅f15)⋅L⋅(T⋅f1)⋅IP(m) … (*)
解密为：DES−1(c)=IP−1⋅f1⋅(T⋅f2)⋅L⋅(T⋅f16)⋅IP(c)… (#)
把(*)式代入(#)式，可得
DES−1(DES(m))=m，由此可知DES的解密变换是加密变换的逆。
3. 在DES的ECB模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而在CBC模式中，将有错误传播。例如在图3-11中C1中的一个错误明显地将影响到P1和P2的结果。
(1) P2后的分组是否受到影响?
(2) 设加密前的明文分组P1中有1比特的错误，问这一错误将在多少个密文分组中传播?对接收者产生什么影响?
解： CBC的加密： C0=IV, Ci=DESK[Pi⊕Ci-1], i≥2
解密： Pi=DESK-1[Ci]⊕Ci-1 , i≥1
(1) 如果解密过程中C1有错误，由于P2=DESK-1[C2]⊕C1，所以P2将受到影响；但是当i≥3时，Pi=DESK-1[Ci]⊕Ci-1，与C1无关，因此Pi≥3不会受到影响。
则加密后C1也是错误的；(2) 加密前P1有错误，由于Ci=DESK[Pi⊕Ci-1], i≥2，因此Ci≥2也都是错误的，即P1中这一个比特的错误会在加密过程中传递到每一个密文分组。
由加密和解密的方式可知，如果密文Ci在从发送者到接收者的传递过程中没有改变（出错），那么密文解密后必然等于加密时输入的明文。因此对于接收者来说，由于加密前的明文分组P1中有l比特的错误，那第 4 页
CBC模式示意图
NCUT 密码学 – 习题与答案 2010
么解密后的P1跟加密前一样，同样有一个比特的错误，而对于Ci≥2能够解密得到无错误的明文。
4. 在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远。
解： 该错误将传播到后面的⎢⎣(64+8-1)/8⎥⎦= 8个单元， 共9个单元解密得到错误的明文。
CFB模式示意
第 5 页
NCUT 密码学 – 习题与答案 2010
四、公钥密码
1. 3. 用Fermat定理求3201 mod 11 。
解：对于模运算，有结论 (a×b) mod n = [ (a mod n)×(b mod n)] mod n
由Fermat定理，可知 310≡1 mod 11，因此有 (310)k
≡1 mod 11
所以 3201 mod 11= [(310)20×3] mod 11 = [( (310)20
mod 11)×(3 mod 11)] mod 11 = 3。
Fermat定理：若p是素数，a是正整数且gcd(a, p)=1，则ap-1≡1 mod p。
若gcd(a, p)=1，则aϕ≡1 mod p。
(p)
4. 用推广的Euclid算法求67 mod 119的逆元。
解：
q g u v
~ 119 1 0
~ 67 0 1
1 52 1 -1
1 15 -1 2
3 7 4 -7
2 1 -9
16
(
注： 1 = 119×(-9) + 67×16 )
所以 67-1 mod 119 = 16
5.
求gcd(4655, 12075)
。
解：12075 = 2×4655 + 2765
4655 = 1×2765 + 1890
2765 = 1×1890 + 875
1890 = 2×875 + 140
875 = 6×140 + 35
140 = 4×35+0
所以gcd(4655, 12075)=35。
⎧x≡2mod3⎪6. 求解下列同余方程组
⎨x≡1mod5。⎪x≡1mod7⎩
解：根据中国剩余定理求解该同余方程组，
记 a1=2, a2=1, a3=1, m1=3, m2=5, m3=7, M=m1×m2×m3=105,
M1=M/m1=35, M1-1 mod m1 = 35-1 mod 3 = 2,
M2=M/m2=21, M2-1 mod m2
= 21-1 mod 5 = 1,
M3=M/m3=15, M3-1 mod m3 = 15-1 mod 7 = 1
所以方程组的解为 x≡(M1M1-1a1 + M2M2-1a2 + M3M3-1a3) mod M
≡(35×2×2+21×1×1+15×1×1) mod 105
≡176 mod 105≡71 mod 105
10. 设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是C=10，求明文M
第 6 页
NCUT 密码学 – 习题与答案 2010
解： n=35 -> p=5, q=7
ϕ(n)=(p-1)(q-1)=24
d≡e-1 mod ϕ(n)≡5-1 mod 24≡5 mod 24 .... (因为 5×5≡1 mod 24)
所以，明文M ≡ Cd mod n ≡ 105 mod 35 ≡ 5
快速指数算法求模幂 105 mod 35：
5 = 4 + 1 = (101)2
bi=0, d <- d*d
d <- d*d*底
bi - 1 0 1 bi=0,
d 1 10 30 5
12. 设RSA加密体制的公开钥是(e,n)=(77, 221)。
(1) 用重复平方法加密明文160，得中间结果为：
k 2 4 8 16 32 64 72 76 77
160k mod 221 185 191 16 35 120 35 118 217 23
若敌手得到以上中间结果就很容易分解n，问敌手如何分解n？
(2) 求解密密钥d。
解：(1) 由16016 ≡16064 mod 221，可知 (16064 - 16016) mod 221 = 0
即 16016(16048 – 1) mod 221 = 0，从而有 16048 = 1 mod 221。
由Euler定理及定理4-7，猜测：
ordn(160) | 48 且 48 | ϕ(n)，即存在整数k满足ϕ(n)=48k
由 ϕ(n) 的定义可知， ϕ(n) 比 n 略小。
而当取k=4时，ϕ(n)=192为<221且与221最接近，因此猜测 ϕ(n)=192。
由ϕ(n)=(p-1)(q-1), n=pq，可知 p+q = n - ϕ(n) + 1 = 221 - 192 + 1 = 30
所以 p、q为一元二次方程 X2 - 30X + 221 = 0 的两个根，求得为13、17。
或： p-q = sqrt((p+q)2- 4n), 从而p = ((p+q) + (p-q) )/2, q =((p+q) - (p-q) )/2
所以，可得n的分解为： n = 221 = 13×17
(2) 解密密钥d为：d≡e-1 mod ϕ(n) = 77-1 mod 192 = 5
(∵ 77×5 - 192×2 = 1 )
13. 在ElGamal加密体制中，设素数p=71，本原根g=7，
(1)如果接收方B的公开钥是yB=3，发送方A选择的随机整数k=2，求明文M=30所对应的密文。
(2)如果A选择另一个随机整数k，使得明文M=30加密后的密文是C=(59, C2)，求C2。
解： (1) C1≡gk mod p = 72 mod 71 = 49， C2≡yBk M mod p = (32×30) mod 71= 57
所以密文为 C=(C1, C2)=(49, 57)。
(2)由 7k mod 71 = 59 ，穷举k可得k=3 。
所以 C2 = (3k×30) mod 71 = (33×30) mod 71 = 29。
18. 椭圆曲线E11(1,6)表示y≡x+x+6 mod 11，求其上的所有点。
第 7 页
23
NCUT 密码学 – 习题与答案 2010
解：
x
x3+x+6 mod 11
是否为mod 11的平方剩余
0 1 2 3 4 5 6 7 8 9 10
6 8 5 3 8 4 8 4 9 7 4
No No yes yes No yes No yes yes No yes
4, 7 5, 6 2, 9 2, 9 3, 8 2, 9
所以，E11(1, 6)上点为
{ O, (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7,2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9) }
y
x ≡ c mod p
要确定c是否是一个模p的平方剩余，可以用Euler准则来判断，即(p-1)/2≡1 mod p.
如果p是一个奇素数，则c是模p的平方剩余当且仅当c(p+1)/2
当p≡3 mod 4时，如果c是一个模p的平方剩余，则±c mod p，(p+1)/2(p+1)/2和p- c，就是c的两个模p的平方根。
即c
19. 已知点G=(2, 7) 在椭圆曲线E11(1,6)上，求2G和3G。
解： a=1, b=6, p=11, y2≡x3+x+6 mod 11
∵ 2G = G + G,
λ=(3×22+1)/(2×7)
mod 11=13/14 mod 11 = 2/3 mod 11 = 8
(∵ 3-1 mod 11 = 4)
x3=(82-2-2) mod 11=5, y3= [8(2-5)-7] mod 11=2
∴ 2G = (5, 2)
∵ 3G = 2G + G = (5, 2) + (2, 7),
λ=(7−2)/(2−5) mod 11=5/(-3) mod 11=5/8 mod 11=5*7 mod 11= 2
(∵
8*7=1 mod 11)
x3=(22-5-2) mod 11 = (-3) mod 11 = 8
y3=[2(5-8)-2] mod 11 = (-8) mod 11 = 3
∴ 3G = (8, 3)
2
20. 利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E11(1,6)，生成元G=(2,7)，接收方A的秘密钥nA=7。
(1) 求A的公开钥PA。
(2) 发送方B欲发送消息Pm=(10,9)，选择随机数k=3，求密文Cm。
(3) 显示接收方A从密文Cm恢复消息Pm的过程。
解： (1) A的公开钥 PA = nAG = 7G = (7, 2)
(2) C1=kG = 3G = (8, 3)
C2=Pm
+ kPA=(10,9) + 3(7, 2) = (10,9) + (3, 5) = (10, 2)
所以密文 Cm={C1, C2} = { (8,3), (10, 2) }
(3) 解密过程为
C2 - nAC1= (Pm
+ kPA) – nA
(kG) = (10, 2) – 7(8,3) = (10, 9) = Pm
第 8 页
NCUT 密码学 – 习题与答案 2010
五、消息认证与杂凑函数
1. 6.1.3节的数据认证算法是由CBC模式的DES定义的，其中初始向量取为0，试说明使用CFB模式也可获得相同结果。
（图1）
解：CFB模式中的加密部分的框图如下：
（图2）
如果要使 CFB模式输出结果和CBC模式的相同，那就要选择适当参数和输入。
假设消息为 M=D1D2…DN，则按如下思路考虑：
(1) CBC中DES加密算法输入输出都为64位，所以CFB中的参数j应取64。此时的CFB模式变为：
（图3）
(2)比较图1和图2中开始几个分组的处理，考虑DES加密的输入和输出，可知，
IV → D1, P1 → D2, ...
(3)CBC中最后一个DES加密的输出为消息认证符，即ON=EK(DN⊕ON-1)，因此在CFB中，，这样有CM=EK(CM-1)⊕Z64=EK(CM-1)。此时，应取 PM-1
=
应取PM为Z64（64比特都为0的分组）DN。
综上可知：对于消息 DN, 如果采用DES/CFB的数据认证算法，那么，当其参数取如下值时，
参数j=64, 参数IV=D1，输入消息M'=DNZ64
其输出与采用DES/CBC的数据认证算法的输出相同。
第 9 页
NCUT 密码学 – 习题与答案 2010
2. 有很多散列函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将消息M分成分组M1,M2,…,MN，H0=初值，迭代关系为Hi=EMi(Hi-1)⊕Hi-1
(i=1,2,…,N)，杂凑值取为HN，其中E是分组加密算法。
(1) 设E为DES，我们知道如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即如果Y=DESK(X)，那么Y’=DESK’(X’)。利用这一结论证明在上述散列函数中可对消息进行修改但却保持杂凑值不变。
(2) 若迭代关系改为Hi=EHi-1(Mi)⊕Mi，证明仍可对其进行上述攻击。解：(1) Hi=EMi(Hi-1)⊕Hi-1
Æ EMi(Hi-1)= Hi⊕Hi-1
Æ EMi’(H’i-1)= (Hi⊕Hi-1)' = Hi⊕H’i-1
即 Hi =EMi’(H’i-1)⊕H’i-1
则有H1 =EM1’(H’0)⊕H’0，
因此，构造消息M’1M2…Mn，同时初始向量取为原先的初始向量的补，则可得到相同的杂凑值。
(2) Hi=EHi-1(Mi)⊕Mi
Æ EHi-1(Mi)= Hi⊕Mi
Æ EH’i-1(M’i)= Hi⊕M’i
则有H1 =EH0’(M’1)⊕M’1
因此，构造消息M’1M2…Mn，同时初始向量取为原先的初始向量的补，则可得到相同的杂凑值。
3. 考虑用公钥加密算法构造散列函数，设算法是RSA，将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。设一消息被分成两个分组B1和B2，其杂凑值为H(B1,B2)=RSA(RSA(B1)⊕B2)。证明对任一分组C1可选C2，使得H(C1,C2)=H(B1,B2)。证明用这种攻击法，可攻击上述用公钥加密算法构造的散列函数。
证明： (1) 对任一分组C1，设RSA算法中加密公钥为e。
若取C2为
C2 = (C1e mod n)⊕(B1e mod n)⊕B2
则有
RSA(C1)⊕C2
= (C1e mod n)⊕[(C1e mod n)⊕(B1e mod n)⊕B2]
= (B1e mod n)⊕B2
= RSA(B1)⊕B2
从而有 H(C1,C2) = H(B1,B2) 成立。
(2) 对于消息M，设其分组为M1, M2, M3, ..., Mn，则 RSA-Hash(M) 为：
H = HRSA(M) = RSA(... (RSA(RSA(M1)⊕M2)⊕...)⊕Mn)
攻击过程如下：
2024年2月20日发(作者：后女)
NCUT 密码学 – 习题与答案 2010
（ 声 明：非 标 准 答 案，仅 供 参 考 ）
一、古典密码 （1,2,4）
字母
数字
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 6171819 20 21 22 232425
1. 设仿射变换的加密是 E11,23(m)≡11m+23 (mod 26)，对明文“THE NATIONAL SECURITY
AGENCY”加密，并使用解密变换D11,23(c)≡11-1(c-23) (mod 26) 验证你的加密结果。
解：明文用数字表示：M=[19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24]
密文 C= E11,23(M)≡11*M+23 (mod 26)
=[24 22 15 10 23 24 7 21 10 23 14 13 15 19 9 2 7 24 1 23 11 15 10 19 1]
=
YWPKXYHVKXONPTJCHYBXLPKTB
，或者直接穷举1~25)
∵ 11*19 ≡ 1 mod 26
(说明：求模逆可采用第4章的“4.1.6 欧几里得算法”∴ 解密变换为 D(c)≡19*(c-23)≡19c+5 (mod 26)
对密文C进行解密：
M’=D(C)≡19C+5 (mod 26)
=[19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24]
= THE NATIONAL SECURITY AGENCY
2. 设由仿射变换对一个明文加密得到的密文为 edsgickxhuklzveqzvkxwkzukvcuh，又已知明文的前两个字符是“if”。对该密文解密。
解： 设解密变换为 m=D(c)≡a*c+b (mod 26)
由题目可知 密文 ed 解密后为 if，即有：
D(e)=i ： 8≡4a+b (mod 26) D(d)=f ： 5≡3a+b (mod 26)
由上述两式，可求得 a=3，b=22。
因此，解密变换为 m=D(c)≡3c+22 (mod 26)
密文用数字表示为：
c=[4 3 18 6 8 2 10 23 7 20 10 11 25 21 4 16 25 21 10 23 22 10 25 20 10 21 2 20 7]
则明文为 m=3*c+22 (mod 26)
=[8 5 24 14 20 2 0 13 17 4 0 3 19 7 8 18 19 7 0 13 10 0 19 4 0 7 2 4 17]
=
ifyoucanreadthisthankateahcer
A是2×2矩阵，B是0矩阵，又知明文“dont”4. 设多表代换密码 Ci ≡ AMi + B (mod 26) 中，被加密为“elni”，求矩阵A。
解： dont = (3,14,13,19) => elni = (4,11,13,8)
设
A=⎢⎡ab⎤，
⎥⎣cd⎦⎡4⎤⎣⎦⎡a⎣b⎤⎡3⎤⎢14⎥(mod26)，
d⎥⎦⎣⎦⎡13⎤⎡ab⎤⎡13⎤⎢8⎥=⎢cd⎥⎢19⎥(mod26)
⎣⎦⎣⎦⎣⎦则有：
⎢⎥=⎢11c 可求得
A=⎢⎡1013⎤
⎥⎣923⎦第 1 页
NCUT 密码学 – 习题与答案 2010
二、流密码 （1,3,4）
1. 3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。
解：设反馈函数为 f(a1,a2,a3) = a1⊕c2a2⊕c1a3
当c1=0，c2=0时，f(a1,a2,a3) = a1，输出序列为101101…，周期为3。
当c1=0，c2=1时，f(a1,a2,a3) = a1⊕a2，输出序列如下10…，周期为7。当c1=1，c2=0时，f(a1,a2,a3) = a1⊕a3，输出序列为11…，周期为7。
当c1=1，c2=1时，f(a1,a2,a3) = a1⊕a2⊕a3，输出序列为10101010…，周期为2。
3. 设n=4，f(a1,a2,a3,a4)=a1⊕a4⊕1⊕a2a3，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。
解：列出该非线性反馈移位寄存器的状态列表和输出列表：
状态(a1,a2,a3,a4)f(a1,a2,a3,a4)
输出
1
0
1
1
…
(1,1,0,1)
1 1
(1,0,1,1) 1
(0,1,1,1) 1
(1,1,1,1) 0
(1,1,1,0) 1
(1,1,0,1)
…
1 1
…
因此，输出序列为11011 11011 …，周期为5。
4. 密钥流由m=2s级的LFSR产生，前m+2个比特是(01)s+1，即s+1个01，请问第m+3个比特有无可能是1，为什么？
解： 根据题目条件，可知初始状态s0为：
s0=(a1,a2,L,am−1,am)=(0,1,...,0,1) 注：s个01
设该LFSR的输出序列满足如下递推关系：
则第m+1, m+2个比特为：
am+k=c1am+k−1+c2am−1+Lcmak, k≥1
am+1=c1am+c2am−1+Lcma1=∑c2j−1=0
j=1ss
am+2=c1am+1+c2am+Lcma2=∑c2j=1j=1
而第m+3比特应为：
am+3=c1am+2+c2am+1+c3am+c4am−1+L+cm−1a4+cma3 =c1⋅1+c2⋅0+c3⋅1+c4⋅0+LL+cm−1⋅1+cm⋅0 =∑c2j−1=0j=1s
即第m+3比特为0，因此不可能为1.
M的散列值相同。
第 2 页
NCUT 密码学 – 习题与答案 2010
三、分组密码 （1,2,3,4）
1. (1) 设M’是M的逐比特取补，证明在DES中，如果对明文分组和密文分组都逐比特取补，那么得到的密文也是原密文的逐比特取补，即
如果 Y = DESK(X)，那么 Y’=DESK’(X’)
提示：对任意两个长度相等的比特串A和B，证明(A⊕B)’=A’⊕B。
证：
(i) 容易验证，在DES中所有的置换操作，包括初始置换IP、逆初始置换IP-1、选择扩展算法E、置换运算P以及置换选择PC1、置换选择PC2，都满足如下性质：
如果N=PO(M)，则N’=PO(M’)，其中PO是某种置换操作
即有 (PO(M))’= PO(M’)
(ii) 容易验证，密钥生成过程中的左循环移位LS满足如下性质：
如果N=LS (M)，那么N’=LS(M’)，
即有 (LS (M))’=LS(M’)
结合(1)可知，如果记子密钥为(K1,…,K16)，K为初始密钥，KG为密钥生成算法，则有如下性质：
如果 (K1,…,K16)=KG(K)，那么 (K1',…,K16')=KG(K’)
(iii)
对于任意两个比特a和b，有 (a⊕b)’= a⊕b⊕1=(a⊕1)⊕b=a’⊕b（= a⊕(b⊕1)=a⊕b’），因此对任意两个长度相等的比特串A和B，有(A⊕B)’=A’⊕B=A⊕B’成立。
(iv)
DES的轮变换为⎨⎧⎪Li=Ri−1，其中轮函数F可写为⎪⎩Ri=Li−1⊕F(Ri−1,Ki)F(R,K)=P(S(E(R)⊕K))。 因此有如下推理：
Y=DESK(X)⇒Y'=DESK'(X')⇔ Ri=Li−1⊕F(Ri−1,Ki) ⇒ Ri'=L'i−1⊕F(Ri'−1,Ki')
根据(i)(ii)⇔
(Li−1⊕F(Ri−1,Ki))' =(Li−1⊕F(Ri'−1,Ki')
)'
根据(iii)⇔ F(Ri−1,Ki) =F(Ri'−1,Ki')
⇔ P(S(E(Ri−1)⊕Ki))=P(S(E(Ri'−1)⊕Ki'))⇔ E(Ri−1)⊕Ki=E(Ri'−1)⊕Ki'根据(iii)可知
E(Ri−1)⊕Ki=(E(Ri−1)⊕Ki')'=(E(Ri−1))'⊕Ki⇔ (E(Ri−1))'⊕Ki=E(Ri'−1)⊕Ki'⇔ (E(Ri−1))'=E(Ri'−1) 由(i)知此式成立
(2) 对DES进行穷举搜索攻击时，需要在由256个密钥构成的密钥空间进行。能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。
解：(1) 根据取补的性质，密钥空间K可分成两部分K1/2和K’1/2，即K= K1/2∪K’1/2
对于任意一个k∈K1/2，它的取补k’∈K’1/2；对于任意一个k∈K’1/2，它的取补k’∈K1/2。即，K1/2和K’1/2是一一对应的；它们的空间大小都是
256/2=255。
其中x、y分别为明文和密文，E为DES加密算法，(2) 选择明文攻击时，假设有Ek0(x)=y，k0为真实的密钥。
第 3 页
NCUT 密码学 – 习题与答案 2010
穷举搜索密钥空间K1/2，对于某个k∈K1/2，假设
(i) Ek(x)=y1，如果 y1=y，则说明 k0=k 而且 k0∈K1/2。
(ii) Ek(x’)=y2，如果y2=y’，则说明k= k0’，即k0= k’ 而且 k0∈K’1/2。
综上可知：对于选定的明文密文对(x,y)，只需遍历K1/2中的所有密钥即可，此时密钥空间大小少为255。
2. 证明DES的解密变换是加密变换的逆。
证明：定义T是把64位数据左右两半交换位置的操作，即T(L,R)=(R,L)，则T2(L,R)=(L,R)，即T2=I，其中I为恒等变换。
定义DES中第i轮的主要运算为fi，即
fi(Li−1,Ri−1)=(Li−1⊕F(Ri−1,Ki),Ri−1)
则有，
fi2(Li−1,Ri−1)=(Li−1⊕F(Ri−1,Ki),Ri−1)=fi(Li−1⊕F(Ri−1,Ki),Ri−1)=((Li−1⊕F(Ri−1,Ki))⊕F(Ri−1,Ki),Ri−1)=(Li−1,Ri−1) 即
fi2=I。
DES的加密为：
c=DES(m)=IP−1⋅f16⋅(T⋅f15)⋅L⋅(T⋅f1)⋅IP(m) … (*)
解密为：DES−1(c)=IP−1⋅f1⋅(T⋅f2)⋅L⋅(T⋅f16)⋅IP(c)… (#)
把(*)式代入(#)式，可得
DES−1(DES(m))=m，由此可知DES的解密变换是加密变换的逆。
3. 在DES的ECB模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而在CBC模式中，将有错误传播。例如在图3-11中C1中的一个错误明显地将影响到P1和P2的结果。
(1) P2后的分组是否受到影响?
(2) 设加密前的明文分组P1中有1比特的错误，问这一错误将在多少个密文分组中传播?对接收者产生什么影响?
解： CBC的加密： C0=IV, Ci=DESK[Pi⊕Ci-1], i≥2
解密： Pi=DESK-1[Ci]⊕Ci-1 , i≥1
(1) 如果解密过程中C1有错误，由于P2=DESK-1[C2]⊕C1，所以P2将受到影响；但是当i≥3时，Pi=DESK-1[Ci]⊕Ci-1，与C1无关，因此Pi≥3不会受到影响。
则加密后C1也是错误的；(2) 加密前P1有错误，由于Ci=DESK[Pi⊕Ci-1], i≥2，因此Ci≥2也都是错误的，即P1中这一个比特的错误会在加密过程中传递到每一个密文分组。
由加密和解密的方式可知，如果密文Ci在从发送者到接收者的传递过程中没有改变（出错），那么密文解密后必然等于加密时输入的明文。因此对于接收者来说，由于加密前的明文分组P1中有l比特的错误，那第 4 页
CBC模式示意图
NCUT 密码学 – 习题与答案 2010
么解密后的P1跟加密前一样，同样有一个比特的错误，而对于Ci≥2能够解密得到无错误的明文。
4. 在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远。
解： 该错误将传播到后面的⎢⎣(64+8-1)/8⎥⎦= 8个单元， 共9个单元解密得到错误的明文。
CFB模式示意
第 5 页
NCUT 密码学 – 习题与答案 2010
四、公钥密码
1. 3. 用Fermat定理求3201 mod 11 。
解：对于模运算，有结论 (a×b) mod n = [ (a mod n)×(b mod n)] mod n
由Fermat定理，可知 310≡1 mod 11，因此有 (310)k
≡1 mod 11
所以 3201 mod 11= [(310)20×3] mod 11 = [( (310)20
mod 11)×(3 mod 11)] mod 11 = 3。
Fermat定理：若p是素数，a是正整数且gcd(a, p)=1，则ap-1≡1 mod p。
若gcd(a, p)=1，则aϕ≡1 mod p。
(p)
4. 用推广的Euclid算法求67 mod 119的逆元。
解：
q g u v
~ 119 1 0
~ 67 0 1
1 52 1 -1
1 15 -1 2
3 7 4 -7
2 1 -9
16
(
注： 1 = 119×(-9) + 67×16 )
所以 67-1 mod 119 = 16
5.
求gcd(4655, 12075)
。
解：12075 = 2×4655 + 2765
4655 = 1×2765 + 1890
2765 = 1×1890 + 875
1890 = 2×875 + 140
875 = 6×140 + 35
140 = 4×35+0
所以gcd(4655, 12075)=35。
⎧x≡2mod3⎪6. 求解下列同余方程组
⎨x≡1mod5。⎪x≡1mod7⎩
解：根据中国剩余定理求解该同余方程组，
记 a1=2, a2=1, a3=1, m1=3, m2=5, m3=7, M=m1×m2×m3=105,
M1=M/m1=35, M1-1 mod m1 = 35-1 mod 3 = 2,
M2=M/m2=21, M2-1 mod m2
= 21-1 mod 5 = 1,
M3=M/m3=15, M3-1 mod m3 = 15-1 mod 7 = 1
所以方程组的解为 x≡(M1M1-1a1 + M2M2-1a2 + M3M3-1a3) mod M
≡(35×2×2+21×1×1+15×1×1) mod 105
≡176 mod 105≡71 mod 105
10. 设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是C=10，求明文M
第 6 页
NCUT 密码学 – 习题与答案 2010
解： n=35 -> p=5, q=7
ϕ(n)=(p-1)(q-1)=24
d≡e-1 mod ϕ(n)≡5-1 mod 24≡5 mod 24 .... (因为 5×5≡1 mod 24)
所以，明文M ≡ Cd mod n ≡ 105 mod 35 ≡ 5
快速指数算法求模幂 105 mod 35：
5 = 4 + 1 = (101)2
bi=0, d <- d*d
d <- d*d*底
bi - 1 0 1 bi=0,
d 1 10 30 5
12. 设RSA加密体制的公开钥是(e,n)=(77, 221)。
(1) 用重复平方法加密明文160，得中间结果为：
k 2 4 8 16 32 64 72 76 77
160k mod 221 185 191 16 35 120 35 118 217 23
若敌手得到以上中间结果就很容易分解n，问敌手如何分解n？
(2) 求解密密钥d。
解：(1) 由16016 ≡16064 mod 221，可知 (16064 - 16016) mod 221 = 0
即 16016(16048 – 1) mod 221 = 0，从而有 16048 = 1 mod 221。
由Euler定理及定理4-7，猜测：
ordn(160) | 48 且 48 | ϕ(n)，即存在整数k满足ϕ(n)=48k
由 ϕ(n) 的定义可知， ϕ(n) 比 n 略小。
而当取k=4时，ϕ(n)=192为<221且与221最接近，因此猜测 ϕ(n)=192。
由ϕ(n)=(p-1)(q-1), n=pq，可知 p+q = n - ϕ(n) + 1 = 221 - 192 + 1 = 30
所以 p、q为一元二次方程 X2 - 30X + 221 = 0 的两个根，求得为13、17。
或： p-q = sqrt((p+q)2- 4n), 从而p = ((p+q) + (p-q) )/2, q =((p+q) - (p-q) )/2
所以，可得n的分解为： n = 221 = 13×17
(2) 解密密钥d为：d≡e-1 mod ϕ(n) = 77-1 mod 192 = 5
(∵ 77×5 - 192×2 = 1 )
13. 在ElGamal加密体制中，设素数p=71，本原根g=7，
(1)如果接收方B的公开钥是yB=3，发送方A选择的随机整数k=2，求明文M=30所对应的密文。
(2)如果A选择另一个随机整数k，使得明文M=30加密后的密文是C=(59, C2)，求C2。
解： (1) C1≡gk mod p = 72 mod 71 = 49， C2≡yBk M mod p = (32×30) mod 71= 57
所以密文为 C=(C1, C2)=(49, 57)。
(2)由 7k mod 71 = 59 ，穷举k可得k=3 。
所以 C2 = (3k×30) mod 71 = (33×30) mod 71 = 29。
18. 椭圆曲线E11(1,6)表示y≡x+x+6 mod 11，求其上的所有点。
第 7 页
23
NCUT 密码学 – 习题与答案 2010
解：
x
x3+x+6 mod 11
是否为mod 11的平方剩余
0 1 2 3 4 5 6 7 8 9 10
6 8 5 3 8 4 8 4 9 7 4
No No yes yes No yes No yes yes No yes
4, 7 5, 6 2, 9 2, 9 3, 8 2, 9
所以，E11(1, 6)上点为
{ O, (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7,2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9) }
y
x ≡ c mod p
要确定c是否是一个模p的平方剩余，可以用Euler准则来判断，即(p-1)/2≡1 mod p.
如果p是一个奇素数，则c是模p的平方剩余当且仅当c(p+1)/2
当p≡3 mod 4时，如果c是一个模p的平方剩余，则±c mod p，(p+1)/2(p+1)/2和p- c，就是c的两个模p的平方根。
即c
19. 已知点G=(2, 7) 在椭圆曲线E11(1,6)上，求2G和3G。
解： a=1, b=6, p=11, y2≡x3+x+6 mod 11
∵ 2G = G + G,
λ=(3×22+1)/(2×7)
mod 11=13/14 mod 11 = 2/3 mod 11 = 8
(∵ 3-1 mod 11 = 4)
x3=(82-2-2) mod 11=5, y3= [8(2-5)-7] mod 11=2
∴ 2G = (5, 2)
∵ 3G = 2G + G = (5, 2) + (2, 7),
λ=(7−2)/(2−5) mod 11=5/(-3) mod 11=5/8 mod 11=5*7 mod 11= 2
(∵
8*7=1 mod 11)
x3=(22-5-2) mod 11 = (-3) mod 11 = 8
y3=[2(5-8)-2] mod 11 = (-8) mod 11 = 3
∴ 3G = (8, 3)
2
20. 利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E11(1,6)，生成元G=(2,7)，接收方A的秘密钥nA=7。
(1) 求A的公开钥PA。
(2) 发送方B欲发送消息Pm=(10,9)，选择随机数k=3，求密文Cm。
(3) 显示接收方A从密文Cm恢复消息Pm的过程。
解： (1) A的公开钥 PA = nAG = 7G = (7, 2)
(2) C1=kG = 3G = (8, 3)
C2=Pm
+ kPA=(10,9) + 3(7, 2) = (10,9) + (3, 5) = (10, 2)
所以密文 Cm={C1, C2} = { (8,3), (10, 2) }
(3) 解密过程为
C2 - nAC1= (Pm
+ kPA) – nA
(kG) = (10, 2) – 7(8,3) = (10, 9) = Pm
第 8 页
NCUT 密码学 – 习题与答案 2010
五、消息认证与杂凑函数
1. 6.1.3节的数据认证算法是由CBC模式的DES定义的，其中初始向量取为0，试说明使用CFB模式也可获得相同结果。
（图1）
解：CFB模式中的加密部分的框图如下：
（图2）
如果要使 CFB模式输出结果和CBC模式的相同，那就要选择适当参数和输入。
假设消息为 M=D1D2…DN，则按如下思路考虑：
(1) CBC中DES加密算法输入输出都为64位，所以CFB中的参数j应取64。此时的CFB模式变为：
（图3）
(2)比较图1和图2中开始几个分组的处理，考虑DES加密的输入和输出，可知，
IV → D1, P1 → D2, ...
(3)CBC中最后一个DES加密的输出为消息认证符，即ON=EK(DN⊕ON-1)，因此在CFB中，，这样有CM=EK(CM-1)⊕Z64=EK(CM-1)。此时，应取 PM-1
=
应取PM为Z64（64比特都为0的分组）DN。
综上可知：对于消息 DN, 如果采用DES/CFB的数据认证算法，那么，当其参数取如下值时，
参数j=64, 参数IV=D1，输入消息M'=DNZ64
其输出与采用DES/CBC的数据认证算法的输出相同。
第 9 页
NCUT 密码学 – 习题与答案 2010
2. 有很多散列函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将消息M分成分组M1,M2,…,MN，H0=初值，迭代关系为Hi=EMi(Hi-1)⊕Hi-1
(i=1,2,…,N)，杂凑值取为HN，其中E是分组加密算法。
(1) 设E为DES，我们知道如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即如果Y=DESK(X)，那么Y’=DESK’(X’)。利用这一结论证明在上述散列函数中可对消息进行修改但却保持杂凑值不变。
(2) 若迭代关系改为Hi=EHi-1(Mi)⊕Mi，证明仍可对其进行上述攻击。解：(1) Hi=EMi(Hi-1)⊕Hi-1
Æ EMi(Hi-1)= Hi⊕Hi-1
Æ EMi’(H’i-1)= (Hi⊕Hi-1)' = Hi⊕H’i-1
即 Hi =EMi’(H’i-1)⊕H’i-1
则有H1 =EM1’(H’0)⊕H’0，
因此，构造消息M’1M2…Mn，同时初始向量取为原先的初始向量的补，则可得到相同的杂凑值。
(2) Hi=EHi-1(Mi)⊕Mi
Æ EHi-1(Mi)= Hi⊕Mi
Æ EH’i-1(M’i)= Hi⊕M’i
则有H1 =EH0’(M’1)⊕M’1
因此，构造消息M’1M2…Mn，同时初始向量取为原先的初始向量的补，则可得到相同的杂凑值。
3. 考虑用公钥加密算法构造散列函数，设算法是RSA，将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。设一消息被分成两个分组B1和B2，其杂凑值为H(B1,B2)=RSA(RSA(B1)⊕B2)。证明对任一分组C1可选C2，使得H(C1,C2)=H(B1,B2)。证明用这种攻击法，可攻击上述用公钥加密算法构造的散列函数。
证明： (1) 对任一分组C1，设RSA算法中加密公钥为e。
若取C2为
C2 = (C1e mod n)⊕(B1e mod n)⊕B2
则有
RSA(C1)⊕C2
= (C1e mod n)⊕[(C1e mod n)⊕(B1e mod n)⊕B2]
= (B1e mod n)⊕B2
= RSA(B1)⊕B2
从而有 H(C1,C2) = H(B1,B2) 成立。
(2) 对于消息M，设其分组为M1, M2, M3, ..., Mn，则 RSA-Hash(M) 为：
H = HRSA(M) = RSA(... (RSA(RSA(M1)⊕M2)⊕...)⊕Mn)
攻击过程如下：