密码学答案.pdf

中国科学 技 术大学 信 息安全专 业 密码 学导 论 1 / 11 第 1 组 作业 1 、 A good glass in the Bishops hostel in the Devils seattwenty-one degrees and thirteen minutesnortheast and by northmain branch seventh limb east sideshoot from the left eye of the deaths head a bee line from the tree through the shot fifty feet out. 2 、 pt boat one owe nine lost in action in blackett strait two miles sw meresu cove x crew of twelve x request any information 3 、 a) 25! 2 84 b) 25!/25=24! 因为五行的平移，或五列的平移不会影响加密结果。 4 、 K1=Diag(12) ，是 12 阶 对角阵；K2=(21,8,6,4,13,4,17,4,2,14,3,4) 。 5 、 注意到串“NOSMPUS ”出 现了两次。去掉一个串，统计字频，最高为 S （5 次） ，其次 是 U （4 次） ，双 字母 US 出现 3 次，USS 为结尾。由此猜测 US 为 es，解方 程组 18a+b=18 & 4a+b=20，得 a=11, b=2 ，即11m+2=C mod 26 。 解得 m=(C-2)*19 mod 26 Theres no business like show business. 6 、 3*5 分组交错 置乱为 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 输出为 0,5,10,1,6,11,2,7,12,3,8,13,4,9,14 ，其 循环分解为 (1,5,11,13,9,3)(2,10,8,12,4,6)(0)(7)(14) 中国科学 技 术大学 信 息安全专 业 密码 学导 论 2 / 11 第 2 组 作业 1 、 注意到轮密钥自成镜像。只需用加密 oracle 加 密密文 c ，即 可的明文 m 。 2 、 将左移改为右移。移动次数为： 轮数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 移动次数 0 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 3 、 a) 用真值表可以证明 ( ) AB A B = 。再结合 DES 结 构说明即可。 b) 对选择明文攻击，任选明文 X ，计算 Y1=E(K,X)和 Y2=E(K,X) 。注意到 Y2=E(K,X) 穷举攻击时 ，任选一个 密钥 T ，计算 Y=E(T,X)。若 Y=Y1 ，则 K=T ；若 T=Y2 ，则 K=T ；否则再尝试其他 T 。 由此，只需尝试 2 55 密钥 空间。 4 、 选择密文 1000,01000,00001，即密文 Ci 中 只有第 i 位为 1，其它为 0。取 得它们对应的明文 mi 。 若截获的密文可以表示为aiCi ，则 解密的明文为aimi 。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 3 / 11 第 3 组 作业 1 、 a.2 ；b.3 。 存在其它解。 2 、 a.34；b.35 。 3 、 a.3239；b. 不存在。 4 、 a.(x+1)(x2+x+1) ；b.不可 约 ；c.(x+1) 4 。 5 、 a.1 ；b.1 ；c.x+1 。 6 、 x 2 +1 7 、 Mode Encrypt Decrypt ECB C j = E(K, P j ) j = 1, , N P j = D(K, C j ) j = 1, , N CBC C 1 = E(K, P 1 IV) C j = E(K, P j C j1 ) j = 2, , N P 1 = D(K, C 1 ) IV P j = D(K, C j ) C j1 j = 2, , N CFB C 1 = P 1 S s (EK, IV) C j = P j S s (EK, C j1 ) P 1 = C 1 S s (EK, IV) P j = C j S s (EK, C j1 ) OFB C 1 = P 1 S s (EK, IV) C j = P j S s (E(K, C j1 P j1 ) P 1 = C 1 S s (EK, IV) P j = C j S s (E(K, C j1 P j1 ) CTR C j = P j EK, Counter + j 1 P j = C j EK, Counter + j 1 8 、 a.不影响；b. 会影响所有 密文分组，但对解密方仅影响相应的一位。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 4 / 11 第 4 组 作业 1 、 a.加密速率f bps ；解密 速率 f f bps ； 加密一位的时间为 1/f ， 解密一位的时间为 1/(f f) ，两者时 间差f/f(f f) 。 当累计时间差等于加密一位的时间时，将发生篡位错误。N f/f(ff)=1/f 这里 N 为累 计加密的位数，N=(ff)/ f f/f=1/P 因此，两次同步的时间间隔大约为 T=N/f=1/(fP)。 b.f=1MHz 时 ，加密速率 1Mbps ，解密 速率约 1Mbps，两次同步的时间间隔约 1000s ； f=100MHz 时，加密速率 100Mbps， 解密速率约 100Mbps，两 次同步的时间间隔约 10s 。 2 、 LFSR ： 联结多项式 1+D 2 +D 5 是生 成元 ，周期为 31 ，其输出为1000,0101,0111,0110,0011 3 、 sN d T(D) C(D) L m B(D) N - - - 1 0 -1 1 0 1 1 1 1+D 1 0 1 1 0 1 1+D 1 1 0 1 2 0 0 1 1 1 0 1 3 1 1 1 1+D 3 3 3 1 4 1 1 1+D 3 1+D+D 3 3 3 1 5 0 1 1+D+D 3 1+D+D 2 +D 3 3 3 1 6 1 1 1+D+D 2 +D 3 1+D+D 2 4 6 1+D+D 2 +D 3 7 0 1 1+D+D 2 1+D 3 +D 4 4 6 1+D+D 2 +D 3 8 0 1 1+D 3 +D 4 1+D 2 +D 5 5 8 1+D 3 +D 4 9 1 0 1+D 3 +D 4 1+D 2 +D 5 5 8 1+D 3 +D 4 10 1 1 1+D 2 +D 5 1+D 6 6 10 1+D 2 +D 5 11 0 0 1+D 2 +D 5 1+D 6 6 10 1+D 2 +D 5 12 1 0 1+D 2 +D 5 1+D 6 6 10 1+D 2 +D 5 13 a.线性复杂 度 6 ；b.LFSR ；c.初始状态 011001 ；d.00110 。 4 、 K0=K1=0,K2=255,K3=254,K255=2。 5 、 方法之一：将序列与 01010101串 相异或。 方法之二：将序列通过加密算法、哈希算法 中国科学 技 术大学 信 息安全专 业 密码 学导 论 5 / 11 6 、 n1 n n n1 ss 11 10 ss + = 2 11 01 10 1 1 = ， 3 1 1 10 10 0 1 = ， 4 1 1 11 1 0 10 = ， 5 1 1 01 1 0 11 = ， 6 1 1 10 1 0 01 = 因此 6 n6 n n5 n1 s s 11 10 ss + + = ，即密钥流的周期是 6 或6 的 因子。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 6 / 11 第 5 组 作业 1 、 3 10 1(mod 11) 。所以，3 201 = (3 10 ) 20 3 3 (mod 11) 。 2 、 x 28 1(mod29) ，x 84 1(mod29) 。x=6 。 3 、 x 24 1(mod35) ，x 72 1(mod35) ，x 12 1(mod35) ，x 84 1(mod35) 。x 6(mod35) 。 可验证，x=-6 不满足 x 12 -1(mod35) 。所以 x=6 。 4 、 a. (41 )=40 b. (27)=18 c. (231)=120 d. (440)=160 5 、 由 x=2 mod 6 可知 x=0 mod 2, x=2 mod 3；由 x=3 mod 4 可知 x=1 mod 2。 二者矛盾， 故无解。 6 、 由 x=2 mod 6 可知 x=0 mod 2, x=2 mod 3；与 x=0 mod 4 合并可 得 x=0 mod 4, x=2 mod 3 。 两个模数 3,4 互素，由中国剩余定理可解方程组。 7 、 x=1+2K 1 =2+3K 2 =3+4K 3 =4+K 4 =5+6K 5 =6+5K 6 =7K7 。x=371。 8 、 三个根：x=5+7t(t=0,1,2)=5,12,19。 9 、 z 4 mod p=p-x 1 , z 4 mod q=q-x 2 , z 1 mod p=x 1 , z 1 mod q=x 2 。z 1 +z 4 mod p=0, z 1 +z 4 mod q=0。 所以 z 1 +z 4 mod n=0。因为 z 1 和 z 4 都大 于 0 ，小于 n ，因此必有 z 1 +z 4 =n ，z 4 =n-z 1 。 同 理可证 z 3 =n-z 2 。 10、x 2 mod 7=4, x 2 mod 11=4 。x mod 7=2 或 5, x mod 11=2 或 9 。 所以 z 1 =2, z 2 =9, z 3 =68, z 4 =75 。 11、a. 若 r 是 n 模 p-1 的乘法 逆元，则 rn=1 mod p-1，有 y rn = 1 mod p 因此(y r ) n =1 mod p，即 y r mod p 是 y 的一个 n 次 根。 b. 3 模 4 的乘 法逆元是 3 ， 因此一个根是 x=4 3 mod 5=4。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 7 / 11 原方程等价于 x 3 -4 =0 mod 5，即(x-4)(x 2 +4x+1)=0 mod 5 另两个根为 4 12 4 2 22 = ，无整数解。因此只有一个解 4 。 c. (55)=40，3 模 40 的 乘法逆元是 27 ，因此一个 根是 x=4 27 mod 55=49 原方程等价于(x-49)(x 2 +49x+36)=0 mod 55 另两个根为 49 2257 49 2 22 = ，无整数解。因此只有一个解 49 。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 8 / 11 第 6 组 作业 1 、 n=35 ，a=9 。Alice 求解：x 2 mod 5=4, x 2 mod 7=2，x mod 5=2 或 3, x mod 7=3 或 4 ，解 得四个根为 3,17,18,32 。当 Alice 发送 17 或 18 时，Bob 可求 p,q 为 5,7 。 2 、 x 2 mod n=a, y 2 mod n=a 。 不妨设 xy ，(x+y)(x-y) mod n=0。因为 y x, y n-x ，x-y 0 ， x+y n ，所 以必有 x+y=p,x-y=q 或 x+y=q,x-y=p ，即 gcd(x+y,n)=p 或 q 。 3 、 n=403 ， ( n) =36 0 ，d=7 ，e=103 。m=3, c=3 103 =33 102 =39 51 =279 50 =2781 25 =17281 24 =172113 12 =172276 6 =1729 3 =3399 2 =33981=55 (mod 403) 。m=55 7 =5555 6 =55204 3 =339204 2 =339107=3 (mod 403) 。 4 、 5 。 5 、 有帮助。若明文与 n 有公因子，则密文也必与 n 有公因子。因此可以尝试求密文与 n 的最大公因子，若非 1 ， 则该最大公因子为 p 或 q 。 6 、 不安全。e 和 d 的泄漏有助于 n 的分解。x ed-1 1 mod N ，可以测试 gcd(x (ed-1)/2 -1,N) 。 7 、 不安全。攻击者可以计算 025 用公 钥加密的结果，将密文列表记录。之后可以对任意 密文用查表的方法破译。 8 、 a.(49,57) 。 b.C 2 =29 。 9 、 (4a 3 +27b 2 ) mod p = 4(10) 3 +27(5) 2 mod 17 = 4675 mod 17 = 0，不 能在 Z 17 上定 义一个群。 10、a.P B =7G=(7,2) 。 b.C m =3G,9G+37G=3G,4G=(8,3),(10,2) 。 c.P m =(10,2)7(8,3)=4G-73G=9G=(10,9) 。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 9 / 11 第 7 组 作业 1 、 可以用散列函数构造分组密码 Feistel 结构的轮函数 F ：F(RE i ,Ki) 2 、 取三个密钥 u,v,w ，使得 uvw=1 mod (n)。第一签名人私钥为 u ，第二签名人私钥为 v ， 公钥为 w 。显然，当文件用 u 签名 后，第二签名人可以根据 v 和 w 进行验证；而只有 u 和 v 都签名 后，公众才能用 w 验证。 3 、 a) g q mod p=1，则 g 的阶必 为 q 的因子 。q 是素数，因此确定 g 的阶为 q 。 b) g q mod p=h (p-1) mod p=1（ 费曼定理） 。 与 a 中一样 的理由，g 的阶为 q 。 c) 因为 q|(p-1) ，因此 Z p 中有 (q)=q-1 个元素的阶为 q 。则随机 选 择 g 的阶为 q 的概 率为(q-1)/(p-1) 。平均需要(p-1)/(q-1) 轮 循环，即 257.6 轮。 d) 不愿意。平均需要 2 864 轮循环 e) 算法 2 一轮失败的条件是 h (p-1)/q mod p =1。这意 味着 h 的阶是(p-1)/q 的因子。这样 的 h 一共有 (d) d|( p 1)/ q = (p 1)/q 个。因此，首轮找到生成元的概率为 1 (p 1)/q (p 1) 1 1/q ，约 0.994。 4 、 a) A 的私钥为 d A =3 ，B 的 私钥 d B =3 b) n A n B ，先加 密，后签名。C=(2 3 mod 15) 3 mod 33=(8 3 mod 33)=17 c) 先验证，后解密。m=(17 7 mod 33) 3 mod 15=8 3 mod 15=2 5 、 a) r=7 8 mod 13=3；3=(53+8s) mod 12, s=3 。密文是(3,3) b) r=7 5 mod 13=11 ；7=(511+5s) mod 12, s=0 。密文 是(11,0)。验 证： m mod p = 7 7 mod 13=6；Y A =7 5 mod 13=11，Y A r r s mod p = 11 11 11 0 mod 13=6 。这里 s=0，说 明 k 的选取不合适，应当重选。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 10 / 11 第 8 组 作业 1 、 a.Y A =51；b.Y B =4 ；c.K=30 2 、 a.t=4, K=2 b.k 1 =1, k 2 =4, k 3 =2, k 4 =3, k 5 =2 ； ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) x4x5x7 x2x5x7 14 141517 424547 h(x) mod7 x2x4x7 x2x4x5 32 525457 121415 x4x5x7 x2x5x7 14 56 mod 7 x2x4x7 x2x4x5 32 12 3 x4x5x7 3 x2x5x7 3 x2x4x7 + = + + = + + = + ( ) ( ) ( ) 3 mod 7 x2x4x5 3x 5x 2 =+ 所以 K=2 3 、 a.t=3, K=011 b.k 1 =111, k 2 =100, k 3 =111, k 4 =100 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) x 011 x 110 x 001 x 110 111 100 001 011 001 110 011 001 011 110 h(x) mod 1101 x 001 x 011 100 110 001 110 011 x 011 x 110 x 001 x 110 111 100 011 111 mod 1101 x 001 x 011 100 001 111 100 x 011 x 110 10 + = + + = + + = ( ) ( ) ( ) ( ) ( ) ( ) ( ) 22 2 2 0 101 x 001 x 110 mod 1101 100 x 001 x 011 110 x 101x 111 011 x 111x 110 mod 1101 100 x 010 x 011 001x 101x 011 + + = + =+ 所以 K=011 4 、 本题中的h(x)-K=-h(-x)-K，即 h(x)-K 为奇函数。显然会有 h(x)+h(p-x)=2K 。为避免 此类攻击，h(x) 中应当还有偶次项。 中国科学 技 术大学 信 息安全专 业 密码 学导 论 11 / 11 5 、 该男子 Z 可以采用重放攻击：在网上截获 E ka (R) 和 E R (M)后，发送A,Z, E ka (R)给服务 器；服务器将返回 E kz (R) ，则 z 可以 解密它获得 R ，并进而得到 M 。 6 、 漏洞 1 ，窃听者可以在截获两次的通信内容：R ka,Rka kb ，将两个结果异或，可得 B 的密钥； 漏洞 2 ，攻击 者可以冒充 A ，主动发送 R 给B ，B 返回 R kb ，则 可以获得 B 的密钥。