第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
现代密码学-清华大学-杨波+习题答案.doc
NCUT
密码学 – 习题与答案
（ 声 明：非 标 准 答 案，仅 供 参 考 ）
2010
一、古典密码 （1,2,4）
字母
数字
A
0
B
1
C
2
D
3
E
4
F
5
G
6
H
7
I
8
J
9
K
10
L
11
M
12
N
13
O
14
P
15
Q
16
R
17
S
18
T
19
U
20
V
21
W
22
X
23
Y
24
Z
25
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
∵ 11*19 ≡ 1 mod 26
∴ 解密变换为 D(c)≡19*(c-23)≡19c+5 (mod 26)
对密文 C 进行解密：
(说明：求模逆可采用第4章的“4.1.6欧几里得算法”，或者直接穷举1~25)
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
4. 设多表代换密码 Ci ≡ AMi + B (mod 26) 中，A 是 2×2 矩阵，B 是 0 矩阵，又知明文“dont”
被加密为“elni”，求矩阵 A。
解： dont = (3,14,13,19)
elni = (4,11,13,8)
=>
⎡ a b⎤
设 A⎢
⎣
c d⎦
则有：
⎥ ，
⎡ 4⎤
⎢ 11⎥
⎣
⎦
⎣
⎡ 10 13⎤
⎣ 9 23⎥
⎦
可求得 A⎢
⎡ a b⎤
⎢
c d⎦
⎥
⎢
⎡ 3⎤
⎣ 14⎥
⎦
⎣
⎡ a b⎤
⎡ 13⎤
(mod 26) ，⎢ 8⎥
⎢
⎢
⎥
⎦
⎦
⎣
⎡ 13⎤
c d⎦
⎣ 19⎥
(mod 26)
第 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，输出序列如下 10111001011100…，周期为 7。
当 c1=1，c2=0 时，f(a1,a2,a3) = a1⊕a3，输出序列为 10100111010011…，周期为 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
1
1
0
1
1
…
因此，输出序列为 11011 11011 …，周期为 5。
(1,1,0,1)
(1,0,1,1)
(0,1,1,1)
(1,1,1,1)
(1,1,1,0)
(1,1,0,1)
…
1
1
0
1
1
1
…
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)
设该 LFSR 的输出序列满足如下递推关系：
则第 m+1, m+2 个比特为：
am k c1am k−1 c2am−1L cmak ,
注：s个01
k≥ 1
am1
1am c2am−1Lcma1∑ c2 j−1 0
c
s
j1
s
j1
am 2
c cLc
1am1
2am
而第 m+3 比特应为：
ma2∑ c2 j 1
am3 c1am2 c2am1 c3am c4am−1L cm−1a4 cma3
c1⋅ 1 c2⋅ 0 c3⋅ 1 c4⋅ 0LL cm−1⋅ 1
∑ c2 j−1 0
s
j1
cm⋅ 0
即第 m+3 比特为 0，因此不可能为 1. M 的散列值相同。
第 2 页
NCUT
密码学 – 习题与答案
2010
三、分组密码 （1,2,3,4）
1. (1) 设 M’是 M 的逐比特取补，证明在 DES 中，如果对明文分组和密文分组都逐比特取补，
那么得到的密文也是原密文的逐比特取补，即
提示：对任意两个长度相等的比特串 A 和 B，证明(A⊕B)’=A’⊕B。
如果 Y = DESK(X)，那么 Y’=DESK’(X’)
证：
(i) 容易验证，在 DES 中所有的置换操作，包括初始置换 IP、逆初始置换 IP-1、选择扩展算
法 E、置换运算 P 以及置换选择 PC1、置换选择 PC2，都满足如下性质：
如果 N=PO(M)，则 N’=PO(M’)，其中 PO 是某种置换操作
(ii) 容易验证，密钥生成过程中的左循环移位 LS 满足如下性质：
即有 (PO(M))’= PO(M’)
如果 N=LS (M)，那么 N’=LS(M’)，
即有 (LS (M))’=LS(M’)
结合(1)可知，如果记子密钥为(K1,…,K16)，K 为初始密钥，KG 为密钥生成算法，则有
如下性质：
(iii) 对于任意两个比特 a 和 b，有 (a⊕b)’= a⊕b⊕1=(a⊕1)⊕b=a’⊕b（= a⊕(b⊕1)=a⊕b’），
如果 (K1,…,K16)=KG(K)，那么 (K1',…,K16')=KG(K’)
因此对任意两个长度相等的比特串 A 和 B，有(A⊕B)’=A’⊕B=A⊕B’成立。
⎧
(iv) DES 的轮变换为⎨
⎪
⎪ Li Ri−1
⎩ Ri
L
i−1⊕ F Ri−1, Ki
F R, K P(S (E(R)⊕ K )) 。 因此有如下推理：
，其中轮函数 F 可写为
Y DESK ( X )⇒ Y ' DES K ' ( X ')
根据(i)(ii)
根据(iii)
'
'
'
''
'
'
'
⇔ Ri Li−1⊕ F (Ri−1, Ki )⇒ Ri Li−1⊕ F (Ri−1, Ki )
⇔ Li−1⊕ F (Ri−1, Ki ) ' Li−1⊕ F (Ri−1, Ki ) '
⇔ 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。
(2) 选择明文攻击时，假设有 Ek0(x)=y，其中 x、y 分别为明文和密文，E 为 DES 加密算法，
k0 为真实的密钥。
第 3 页
NCUT
密码学 – 习题与答案
穷举搜索密钥空间 K1/2，对于某个 k∈K1/2，假设
2010
(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
则有，
), R
i−1
2
i−1, Ri−1 ) Li−1⊕ F (Ri−1, Ki
(L
fi
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 )
即 fi 2 I 。
DES 的加密为： c DES (m) IP−1⋅ f16⋅ T⋅ f15⋅ L⋅ T⋅ f1⋅ IP(m)
解密为： DES (c) IP⋅ f1⋅ T⋅ f 2⋅ L⋅ T⋅ f16⋅ IP(c) … (#)
把(*)式代入(#)式，可得 DES−1 (DES (m)) m ，由此可知 DES 的解密变换是加密变换
的逆。
… (*)
−1−1
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 不会受到影响。
(2) 加密前 P1 有错误，则加密后 C1 也是错误的；
由于 Ci=DESK[Pi⊕Ci-1], i≥2，因此 Ci≥2 也都
是错误的，即 P1 中这一个比特的错误会在加
密过程中传递到每一个密文分组。
由加密和解密的方式可知，如果密文 Ci
在从发送者到接收者的传递过程中没有改
变（出错），那么密文解密后必然等于加密
时输入的明文。因此对于接收者来说，由于
加密前的明文分组 P1 中有 l 比特的错误，那
第 4 页
CBC 模式示意图
NCUT
密码学 – 习题与答案
2010
么解密后的 P1 跟加密前一样，同样有一个比特的错误，而对于 Ci≥2 能够解密得到无
错误的明文。
4. 在 8 比特 CFB 模式中，如果在密文字符中出现 1 比特的错误，问该错误能传播多远。
解： 该错误将传播到后面的⎢
⎦ = 8 个单元， 共 9 个单元解密得到错误的明文。
⎣
(64+8-1)/8⎥
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，则 a
若 gcd(a, p)=1，则 a
≡1 mod p。
ϕ(p)
≡1 mod p。
p
-
1
4. 用推广的 Euclid 算法求 67 mod 119 的逆元。
解：
q
~
~
1
1
3
2
所以
g
119
67
52
15
7
1
-1
u
1
0
1
-1
4
-9
v
0
1
-1
2
-7
16
( 注： 1 = 119×(-9) + 67×16 )
67 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。
6. 求解下列同余方程组⎨
⎧
x≡ 2 mod 3
⎪
x≡ 1mod 5 。
⎪
x≡ 1mod 7
⎩
解：根据中国剩余定理求解该同余方程组，
记 a1=2, a2=1, a3=1, m1=3, m2=5, m3=7,
M=m1×m2×m3=105,
M1=M/m1=35,
M2=M/m2=21,
M3=M/m3=15,
M1-1 mod m1 = 35-1 mod 3 = 2,
M2-1 mod m2 = 21-1 mod 5 = 1,
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
解： n=35 -> p=5, q=7
密码学 – 习题与答案
2010
ϕ(n)=(p-1)(q-1)=24
d≡e-1 modϕ(n)≡5-1 mod 24≡5 mod 24
所以，明文 M ≡ Cd mod n ≡ 105 mod 35 ≡ 5
.... (因为 5×5≡1 mod 24)
快速指数算法求模幂 105 mod 35：
5 = 4 + 1 = (101)2
1
bi
d
0
10 30 5
1
1
-
bi=0, d <- d*d
bi=0, d <- d*d*底
12. 设 RSA 加密体制的公开钥是(e,n)=(77, 221)。
(1) 用重复平方法加密明文 160，得中间结果为：
k
k
64
35
160 mod 221
若敌手得到以上中间结果就很容易分解 n，问敌手如何分解 n？
2
185
32
120
4
191
8
16
16
35
72
118
76
217
77
23
(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 且ϕ(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，求其上的所有点。
2
3
第 7 页
NCUT
解：
x
3x +x+6 mod 11
是否为 mod 11
的
平方剩余
y
密码学 – 习题与答案
0
6
1
8
No
No
2
5
yes
4, 7
3
3
yes
5, 6
4
8
No
5
4
yes
2, 9
6
8
No
7
4
yes
2, 9
8
9
yes
3, 8
9
7
No
2010
10
4
yes
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) }
2
x≡cmodp
要确定c是否是一个模p的平方剩余，可以用Euler准则来判断，即
如果p是一个奇素数，则c是模p的平方剩余当且仅当c
(p-1)/2 ≡1modp.
(p+1)/2 modp，
当p≡3mod4时，如果c是一个模p的平方剩余，则±c
即c (p+1)/2 和p-c
，就是c的两个模p的平方根。
(p+1)/2
19. 已知点 G=(2, 7) 在椭圆曲线 E11(1,6)上，求 2G 和 3G。
解： a=1, b=6, p=11, y2≡x3+x+6 mod 11
∵ 2G = G + G,
×22+1)/(2×7) mod 11=13/14 mod 11 = 2/3 mod 11 = 8
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),
−− mod 11=5/(-3) mod 11=5/8 mod 11=5*7 mod 11= 2
x3=(22-5-2) mod 11 = (-3) mod 11 = 8
y3=[2(5-8)-2] mod 11 = (-8) mod 11 = 3
∴ 3G = (8, 3)
(∵ 3-1 mod 11 = 4)
(∵ 8*7=1 mod 11)
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 页
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
