现代密码学_清华大学_杨波著习题答案.pdf-资料库

NCUT 密码学 – 习题与答案 2010 （声明：非标准答案，仅供参考）一、古典密码（1,2,4）字母 A B C D E F G H I J K L 数字 0 1 2 3 4 5 6 7 8 9 10 11 M 12 N 13 O 14 P 15 Q 16 R 17 S 18 V W U T X 19 20 21 22 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 (说明：求模逆可采用第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 a b c d ⎡ = ⎢ ⎣ ⎤ ⎥ ⎦ ，则有： 4 ⎡ ⎤ ⎢ ⎥ 11 ⎣ ⎦ = a b c d ⎡ ⎢ ⎣ 3 14 ⎤ ⎡ ⎥ ⎢ ⎦ ⎣ ⎤ ⎥ ⎦ (mod 26) ， 13 ⎡ ⎤ ⎢ ⎥ 8 ⎣ ⎦ = a b c d ⎡ ⎢ ⎣ 13 19 ⎤ ⎡ ⎥ ⎢ ⎦ ⎣ ⎤ ⎥ ⎦ (mod 26) 可求得 10 13 A ⎡ ⎤ = ⎢ ⎥ 23 9 ⎣ ⎦ 第 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,0,1) (1,0,1,1) (0,1,1,1) (1,1,1,1) (1,1,1,0) (1,1,0,1) … 1 1 1 0 1 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 为： a− , m 1 (0,1,...,0,1) 注：个01 a a , 1 s 0 = a s ) ( , , = 设该 LFSR 的输出序列满足如下递推关系： + c a 1 则第 m+1, m+2 个比特为： c a 2 L 1 + − m k + m k = + a 1 − m m 2 c a m k L , k ≥ 1 a m 1 + = c a m 1 + c a m 2 1 − + c a m 1 = L a m + 2 = c a m 1 1 + + c a m 2 + c a m 2 = L s ∑ j 1 = s ∑ j 1 = c 2 j 1 − = 0 c 2 j = 1 而第 m+3 比特应为： a m + 3 = c a 1 m + 2 + c a 2 m 1 + + c a 3 m + c a 4 m 1 − + = c 1 1 ⋅ + c 2 0 ⋅ + c 3 1 ⋅ + c 4 0 ⋅ + LL 1 = 即第 m+3 比特为 0，因此不可能为 1. M 的散列值相同。 j + L c m + c m a 1 4 − + c a m 3 1 ⋅ + c m 1 − ⋅ 0 = s =∑ c 2 1 − j 第 2 页 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’成立。 (iv) DES 的轮变换为 L =⎧⎪ i ⎨ R = ⎪⎩ i R i L i 1 − 1 − ⊕ F R K 1, − i ( ，其中轮函数 F 可写为 ) i F R K , ( ) = P S E R ( ( ( ) ⊕ 。因此有如下推理： K )) ' ( 1 − 1 − 1 − ' i 1 − ' i ) ⊕ , Y DES X Y DES X ) ' ( ( ') = ⇒ = K K L R F R K L R ) ( ( , ' ' ⇔ = ⇒ = ⊕ i i i i i i 1 1 − − ( ( ) L L F R K F R K ( ) ' ( , ' ⊕ ⇔ = ⊕ i i i i i 1 − F R K F R K , ( ) ( ) , ' ' ⇔ = i i i i 1 1 − − P S E R P S E R K ( ( ) ( ) ) ( ( ' = ⇔ ⊕ i i i 1 − K E R K E R ) ) ( ( ' ' ⇔ ⊕ = ⊕ i i i i 1 − E R K E R iii ( ( ) ( ( ) ⊕ = 根据可知 i i 1 − K E R K E R ( ( ) ' ' ⊕ = ⇔ ⊕ i i i i 1 − E R E R ( (i) ) ( ' ' ⇔ = 由知此式成立 i i )) )) ( ( ⊕ ⊕ K K )) ' ) ' i ) 1 − ) 1 − = i 1 − 1 − 1 − 1 − ' F R K ' i , ) 1 − ' ) 根据根据 (i)(ii) (iii) ' i ( E R ( i 1 − ' )) ⊕ K 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 密码学 – 习题与答案 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，即 ( L i f L R ( i i = ) 1 − 1 − , i ⊕ 1 − F R K R i ), ( 1 − , i i ) 1 − 则有，即 2 if I= 。 ( , , ), = ( L F R K R f L R ) ( ( 2 ⊕ i i i i i i 1 1 1 1 − − − − F R K R f L ) , ), ( ⊕ = i i i i 1 1 − − ( F R K R F R K L ( ( )) ( = ⊕ ⊕ i i L R ) ( = i i 1 − , 1 − , ), 1 − 1 − 1 − 1 − 1 − , i i i i i ) ) 1 − i DES 的加密为： 1 − 解密为： DES 1 − f 16 = = c DES m IP = ( T f c ( ) ⋅ 1( − ( T f ( ⋅ ⋅ 15 ( T f f ⋅ ⋅ ⋅ L 16 1 m DES DES m )) ( = ，由此可知 DES 的解密变换是加密变换 ( T f ⋅ ⋅ L 1 IP c ( ) … (#) … (*) IP m ⋅ ) IP ) ⋅ ) ) ⋅ ⋅ ) 1 − ( ) ⋅ ⋅ 2 把(*)式代入(#)式，可得的逆。 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 有错误，由于 -1[C2]⊕C1，所以 P2 将受到影响；但 -1[Ci]⊕Ci-1，与 C1 无 P2=DESK 是当 i≥3 时，Pi=DESK 关，因此 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 比特的错误，问该错误能传播多远。解：该错误将传播到后面的 (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ϕ(p)≡1 mod 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。 6. 求解下列同余方程组 x ≡⎧ ⎪ ≡⎨ x ⎪ ≡⎩ x 2mod3 1mod 5 1mod 7 。解：根据中国剩余定理求解该同余方程组，记 a1=2, a2=1, a3=1, m1=3, m2=5, m3=7, M=m1×m2×m3=105, M1=M/m1=35, M1 M2=M/m2=21, M2 M3=M/m3=15, M3 -1 mod m1 = 35-1 mod 3 = 2, -1 mod m2 = 21-1 mod 5 = 1, -1 mod m3 = 15-1 mod 7 = 1 -1a2 + M3M3 -1a1 + M2M2 -1a3) mod M 所以方程组的解为 x≡(M1M1 ≡(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 bi - 1 0 1 bi=0, d <- d*d*底 d 1 10 30 5 12. 设 RSA 加密体制的公开钥是(e,n)=(77, 221)。 (1) 用重复平方法加密明文 160，得中间结果为： k 160k mod 221 2 185 4 191 8 16 16 35 32 120 64 35 72 118 76 217 77 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≡yB 所以密文为 C=(C1, C2)=(49, 57)。 (2)由 7k mod 71 = 59 ，穷举 k 可得 k=3 。所以 C2 = (3k×30) mod 71 = (33×30) mod 71 = 29。 k M mod p = (32×30) mod 71= 57 18. 椭圆曲线 E11(1,6)表示 y2≡x3+x+6 mod 11，求其上的所有点。第 7 页

NCUT 密码学 – 习题与答案 2010 解： x x3+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 7 4 8 9 9 7 No yes yes No 10 4 yes 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) } x2 ≡ c mod p 要确定 c 是否是一个模 p 的平方剩余，可以用 Euler 准则来判断，即如果 p 是一个奇素数，则 c 是模 p 的平方剩余当且仅当 c(p-1)/2≡1 mod p. 当 p≡3 mod 4 时，如果 c 是一个模 p 的平方剩余，则±c(p+1)/2 mod p，即 c(p+1)/2 和 p- c(p+1)/2，就是 c 的两个模 p 的平方根。 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) 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 页

资料库

现代密码学_清华大学_杨波著习题答案.pdf

相关推荐

课程资源

热门标签

最新资料