现代密码学_清华大学_杨波着+习题答案
现代密码学_清华⼤学_杨波着+习题答案
设 A = ' ∞ ，广州2a大学
= =
≤ ? ≤ ∞ ' ? ≤ ? ≤ ∞ ' ? 可求得 A = '
⼀、古典密码（1,2,4）
11,23AGENCY ”加密，并使⽤解密变换 D 11,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= E 11,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] = YWPKXYHVKXONPTJCHYB
XLPKTB
∵ 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. 设多表代换密码 C i ≡ AM i + 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∞
a m +1 1a m + c 2a m 1 +L c m a 1 = c 2 j 1 = 0
a m + 2 1a m +1 2a m m a 2 = c 2 j = 1
= c 2 j 1 = 0
⼆、流密码（1,3,4）
1. 3 级线性反馈移位寄存器在 c 3=1 时可有 4 种线性反馈函数，设其初始状态为 (a 1,a 2,a 3)=(1,0,1)，求各线性反馈函数的输出序列及周期。解：设反馈函数为 f(a 1,a 2,a 3) = a 1⊕c 2a 2⊕c 1a 3
当 c1=0，c2=0 时，f(a 1,a 2,a 3) = a 1，输出序列为 101101…，周期为 3。
当 c1=0，c2=1 时，f(a 1,a 2,a 3) = a 1⊕a 2，输出序列如下 10111001011100…，周期为 7。当 c1=1，c2=0 时，f(a 1,a 2,a 3) = a 1⊕a 3，输出序列为 10100111010011…，周期为 7。当 c1=1，c2=1 时，f(a 1,a 2,a 3) = a 1⊕a 2⊕a 3，输出序列为10101010…，周期为 2。
3. 设 n=4，f(a 1,a 2,a 3,a 4)=a 1⊕a 4⊕1⊕a 2a 3，初始状态为(a 1,a 2,a 3,a 4)=(1,1,0,1)，求此⾮线性反馈移位寄存器的输出序列及周期。
解：列出该⾮线性反馈移位寄存器的状态列表和输出列表：
4. 密钥流由 m=2s 级的 LFSR 产⽣，前 m+2 个⽐特是(01)s+1，即 s+1 个 01，请问第 m+3 个⽐特有⽆可能是 1，为什么？解：根据题⽬条件，可知初始状态 s 0 为：
s 0 = (a 1, a 2 ,L, a m 1, a m ) = (0,1,..., 0,1)
设该 LFSR 的输出序列满⾜如下递推关系：
a m + k = c 1a m + k 1 + c 2a m 1 +L c m a k ,
则第 m+1, m+2 个⽐特为：
注：s 个01
k ε 1
s
= c j =1 s
= c + c +L c j =1
⽽第 m+3 ⽐特应为：
a m +3 = c 1a m +2 + c 2a m +1 + c 3a m + c 4a m 1 +L + c m 1a 4 + c m a 3
= c 1 ⊕1 + c 2 ⊕ 0 + c 3 ⊕1 + c 4 ⊕ 0 +LL + c m 1 ⊕1 + c m ⊕ 0
s
j =1 即第 m+3 ⽐特为 0，因此不可能为 1. M 的散列值相同。
R i i 1 F ( R i 1, K i ) (iv) DES 的轮变换为 ?
' ' ''
' '
根据(iii )可知 E (R i 1 ) K i = (E (R i 1 ) K i ) = (E (R i 1 ))' K i
' '
' '
' ' 三、分组密码（1,2,3,4）
1. (1) 设 M ’是 M 的逐⽐特取补，证明在 DES 中，如果对明⽂分组和密⽂分组都逐⽐特取补，
那么得到的密⽂也是原密⽂的逐⽐特取补，即
如果 Y = DES K (X)，那么 Y ’=DES K ’(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)可知，如果记⼦密钥为(K 1,…,K 16)，K 为初始密钥，KG 为密钥⽣成算法，则有如下性质：
如果 (K 1,…,K 16)=KG(K)，那么 (K 1',…,K 16')=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 ’成⽴。
L i = R i 1
= L ，其中轮函数 F 可写为 F ( R , K ) = P (S (E (R ) K )) 。因此有如下推理：
Y = DES K ( X ) ? Y ' = DES K ' ( X ')
R i = L i 1 F (R i 1, K i )  R i = L i 1 F (R i 1, K i )  ( L i 1 F (R i 1, K i )) ' = ( L 1 F (R 1, K ) ) '
根据(i)(ii) 根据(iii)
F (R i 1, K i ) = F (R i 1, K i )
P (S (E (R i 1 ) K i )) = P (S (E (R i ' 1 ) K i ' ))  E (R i 1) K i = E (R i 1 ) K i
' '
(E (R i 1 ))' K i = E (R i 1 ) K i
(E (R i 1 ))' = E (R i ' 1 )
由(i)知此式成⽴
(2) 对 DES 进⾏穷举搜索攻击时，需要在由 256 个密钥构成的密钥空间进⾏。能否根据(1)
的结论减少进⾏穷搜索攻击时所⽤的密钥空间。
解：(1) 根据取补的性质，密钥空间 K 可分成两部分 K 1/2 和 K ’1/2，即 K= K 1/2∪K ’1/2
对于任意⼀个 k ∈K 1/2，它的取补 k ’∈K ’1/2；对于任意⼀个 k ∈K ’1/2，它的取补 k ’∈ K 1/2。即，K 1/2 和 K ’1/2 是⼀⼀对应的；它们的空间⼤⼩都是 256/2=255。
(2) 选择明⽂攻击时，假设有 E k0(x)=y ，其中 x 、y 分别为明⽂和密⽂，E 为 DES 加密算法，
f i i 1, R i 1 ) = ( L i 1 F (R i 1, K i i 1 ) (L
), R 解密为： DES (c ) = IP ⊕ f 1 ⊕ (T ⊕ f 2 ) ⊕L ⊕ (T ⊕ f 16 ) ⊕ IP (c ) … (#) 穷举搜索密钥空间 K 1/2，对于某个 k ∈K 1/2，假设
(i) E k (x)=y 1，如果 y 1=y ，则说明 k 0=k ⽽且 k 0∈K 1/2。
(ii) E k (x ’)=y 2，如果 y 2=y ’，则说明 k= k 0’，即 k 0= k ’ ⽽且 k 0∈K ’1/2。
综上可知：对于选定的明⽂密⽂对(x,y)，只需遍历 K 1/2 中的所有密钥即可，此时密钥空间⼤⼩少为 255。
2. 证明 DES 的解密变换是加密变换的逆。
证明：定义 T 是把 64 位数据左右两半交换位置的操作，即 T(L,R)=(R,L)，则 T 2(L,R)=(L,R)，
即 T 2=I ，其中 I 为恒等变换。
定义 DES 中第 i 轮的主要运算为 f i ，即
f i (L i 1, R i 1 ) = ( L i 1 F (R i 1, K i ), R i 1 )
则有，
2 = f i (L i 1 F (R i 1, K i ), R i 1 ) = ( (L i 1 F (R i 1, K i )) F (R i 1, K i ), R i 1 ) = (L i 1, R i 1 )
即 f i 2 = I 。
DES 的加密为： c = DES (m ) = IP 1 ⊕ f 16 ⊕ (T ⊕ f 15 ) ⊕L ⊕ (T ⊕ f 1 ) ⊕ IP (m )
1 1
… (*)
把(*)式代⼊(#)式，可得 DES 1 (DES (m )) = m ，由此可知 DES 的解密变换是加密变换
的逆。
3. 在 DES 的 ECB 模式中，如果在密⽂分组中有⼀个错误，解密后仅相应的明⽂分组受到影响。
然⽽在 CBC 模式中，将有错误传播。例如在图 3-11 中 C 1 中的⼀个错误明显地将影响到 P 1 和 P 2 的结果。
(1) P 2 后的分组是否受到影响?
(2) 设加密前的明⽂分组 P 1 中有 1 ⽐特的错误，问这⼀错误将在多少个密⽂分组中传播? 对接收者产⽣什么影响?
解： CBC 的加密： C 0=IV, C i =DES K [P i ⊕C i-1], i ≥2
解密： P i =DES K-1[C i ]⊕C i-1 , i ≥1
(1) 如果解密过程中 C 1 有错误，由于
P 2=DES K-1[C 2]⊕C 1，所以 P 2 将受到影响；但是当 i ≥3 时，P i =DES K-1[C i ]⊕C i-1，与 C 1 ⽆关，因此 P i ≥3 不会受到影响。
(2) 加密前 P 1 有错误，则加密后 C 1 也是错误的；
由于 C i =DES K [P i ⊕C i-1], i ≥2，因此 C i ≥2 也都是错误的，即 P 1 中这⼀个⽐特的错误会在加密过程中传递到每⼀个密⽂分组。
由加密和解密的⽅式可知，如果密⽂ C i
在从发送者到接收者的传递过程中没有改变（出错），那么密⽂解密后必然等于加密时输⼊的明⽂。因此对于接收者来说，由于
么解密后的P1跟加密前⼀样，同样有⼀个⽐特的错误，⽽对于C i≥2能够解密得到⽆
错误的明⽂。
4.在8⽐特CFB模式中，如果在密⽂字符中出现1⽐特的错误，问该错误能传播多远。
解：该错误将传播到后⾯的 '≤(64+8-1)/8∞? = 8个单元，共9个单元解密得到错误的明⽂。
CFB 模式⽰意

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。