现代密码学-清华大学-杨波着+习题答案.doc

NCUT


密码学 – 习题与答案


2010

（ 声 明：非 标 准 答 案，仅 供 参 考 ）

一、古典密码 （1,2,4）

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
(说明：求模逆可采用第4章的“4.1.6欧几里得算法”，或者直接穷举1~25)

∴ 解密变换为 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

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 ⎤
⎣ c d ⎦

则有：

⎡ 4 ⎤ ⎡a b ⎤ ⎡ 3 ⎤ ⎡13⎤ ⎡a b ⎤ ⎡13⎤
⎢11⎥ ⎢ c d ⎦⎣14⎥ (mod 26) ， ⎢ 8 ⎥ ⎢ c d ⎦⎣19⎥ (mod 26)

⎡10 13⎤
⎣ 9 23⎥
第 1 页字母
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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

设 A = ⎢
⎥ ，
=
=
⎣ ⎦ ⎣ ⎥ ⎢ ⎦ ⎣ ⎦ ⎣ ⎥ ⎢ ⎦
可求得 A = ⎢
⎦

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)，求此非线性
反馈移位寄存器的输出序列及周期。
解：列出该非线性反馈移位寄存器的状态列表和输出列表：

因此，输出序列为 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)
设该 LFSR 的输出序列满足如下递推关系：
am+ k = c1am+ k −1 + c2am−1 +L cmak ,
则第 m+1, m+2 个比特为：
注：s个01

k ≥ 1

s
= c
j =1
s
= c + c +Lc
j =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
s

j =1

即第 m+3 比特为 0，因此不可能为 1. M 的散列值相同。

第 2 页状态(a1,a2,a3,a4)
f(a1,a2,a3,a4)
输出
(1,1,0,1)
1
1
(1,0,1,1)
1
1
(0,1,1,1)
1
0
(1,1,1,1)
0
1
(1,1,1,0)
1
1
(1,1,0,1)
1
1
…
…
…

am+1 1am + c2am−1 +Lcma1 = ∑ c2 j −1 = 0
am+ 2 1am+1 2am ma2 = ∑ c2 j = 1
= ∑ c2 j −1 = 0

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’成立。

⎧⎪Li = Ri −1
= L

，其中轮函数 F 可写为

F ( R, K ) = P(S (E(R) ⊕ K )) 。 因此有如下推理：

Y = DESK ( X ) ⇒ Y ' = DES K ' ( X ')

⇔ 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 ) ) '
根据(i)(ii)
根据(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
' '

⇔ (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 页⎪⎩Ri i −1 ⊕ F ( Ri −1, Ki )
(iv) DES 的轮变换为 ⎨
' ' ''
' '
根据(iii)可知 E(Ri −1 ) ⊕ Ki = (E(Ri −1 ) ⊕ Ki ) = (E(Ri −1 ))' ⊕ Ki
' '
' '
' '

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 )

则有，

2

= 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)
−1 −1


… (*)

把(*)式代入(#)式，可得 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 不会受到影响。
(2) 加密前 P1 有错误，则加密后 C1 也是错误的；
由于 Ci=DESK[Pi⊕Ci-1], i≥2，因此 Ci≥2 也都
是错误的，即 P1 中这一个比特的错误会在加
密过程中传递到每一个密文分组。
由加密和解密的方式可知，如果密文 Ci
在从发送者到接收者的传递过程中没有改
变（出错），那么密文解密后必然等于加密

时输入的明文。因此对于接收者来说，由于
加密前的明文分组 P1 中有 l 比特的错误，那
第 4 页

CBC 模式示意图

fi i −1, Ri −1 ) = ( Li −1 ⊕ F (Ri−1, Ki i−1 )
(L
), R
解密为： DES (c) = IP ⋅ f1 ⋅ (T ⋅ f 2 ) ⋅L⋅ (T ⋅ f16 ) ⋅ IP(c) … (#)

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，则 a
ϕ(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

p-1

≡1 mod p。

2 1 -9
16
( 注： 1 = 119×(-9) + 67×16 )

所以
-1

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 ≡ 2 mod 3
⎪
⎪ x ≡ 1mod 7

解：根据中国剩余定理求解该同余方程组，
记 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 页若 gcd(a, p)=1，则 a
≡1 mod p。
67 mod 119 = 16
6. 求解下列同余方程组 ⎨ x ≡ 1mod 5 。
⎩

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

bi
- 1 0 1 bi=0, d <- d*d*底

d 1 10 30 5

12. 设 RSA 加密体制的公开钥是(e,n)=(77, 221)。
(1) 用重复平方法加密明文 160，得中间结果为：

若敌手得到以上中间结果就很容易分解 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。

2 3

第 7 页

k
2
4
8
16
32
64
72
76
77
k
160 mod 221
185
191
16
35
120
35
118
217
23

18. 椭圆曲线 E11(1,6)表示 y ≡x +x+6 mod 11，求其上的所有点。

NCUT


密码学 – 习题与答案


2010

解：

所以，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

要确定c是否是一个模p的平方剩余，可以用Euler准则来判断，即

如果p是一个奇素数，则c是模p的平方剩余当且仅当c
(p-1)/2
≡1modp.

当p≡3mod4时，如果c是一个模p的平方剩余，则±c
(p+1)/2
modp，

即c
(p+1)/2
和p-c
(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,

ë=(3×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),
ë=(7−2)/(2−5) mod 11=5/(-3) mod 11=5/8 mod 11=5*7 mod 11= 2
(∵ 3-1 mod 11 = 4)

(∵ 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)

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 页

x
0
1
2
3
4
5
6
7
8
9
10
3
x +x+6 mod 11
6
8
5
3
8
4
8
4
9
7
4
是否为 mod 11 的
平方剩余
No
No
yes
yes
No
yes
No
yes
yes
No
yes
y

4, 7
5, 6

2, 9

2, 9
3, 8

2, 9

x≡cmodp
，就是c的两个模p的平方根。

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 中，
应取 PM 为 Z64（64 比特都为 0 的分组），这样有 CM=EK(CM-1)⊕Z64=EK(CM-1)。此时，应取 PM-1 =
DN。

综上可知：对于消息 M=D1D2...DN, 如果采用 DES/CFB 的数据认证算法，那么，当其参数
取如下值时，
参数 j=64, 参数 IV=D1，输入消息 M'=D2D3...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)
攻击过程如下：
a)任取一分组C1
b)计算C2=RSA(C1)⊕RSA(M1)⊕M2
c)构造另一消息M'=C1C2M3...Mn
d)计算M'的散列值HRSA(M')
由(1)结论可知：
上述过程得到的 M'的散列值与消息 M 的散列值相同，
即HRSA(M')= HRSA(M)

第 10 页