密码学答案.pdf

中国科学技术大学 信息安全专业 密码学导论 1 / 11 第第 1 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 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) 用真值表可以证明()ABAB =。再结合 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 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 Cj = E(K, Pj) j = 1, , N Pj = D(K, Cj) j = 1, , N CBC C1 = E(K, P1 IV) Cj = E(K, Pj Cj1) j = 2, , N P1 = D(K, C1) IV Pj = D(K, Cj) Cj1 j = 2, , N CFB C1 = P1 Ss(EK, IV) Cj = Pj Ss(EK, Cj1) P1 = C1 Ss(EK, IV) Pj = Cj Ss(EK, Cj1) OFB C1 = P1 Ss(EK, IV) Cj = Pj Ss(E(K, Cj1 Pj1) P1 = C1 Ss(EK, IV) Pj = Cj Ss(E(K, Cj1 Pj1) CTR Cj = Pj EK, Counter + j 1 Pj = Cj EK, Counter + j 1 8、 a.不影响；b.会影响所有密文分组，但对解密方仅影响相应的一位。 中国科学技术大学 信息安全专业 密码学导论 4 / 11 第第 4 4 组组作业作业 1、 a.加密速率 f bps；解密速率 ff bps； 加密一位的时间为 1/f，解密一位的时间为 1/(ff)，两者时间差f/f(ff)。 当累计时间差等于加密一位的时间时，将发生篡位错误。Nf/f(ff)=1/f 这里 N 为累计加密的位数，N=(ff)/ff/f=1/P 因此，两次同步的时间间隔大约为 T=N/f=1/(fP)。 b.f=1MHz 时，加密速率 1Mbps，解密速率约 1Mbps，两次同步的时间间隔约 1000s； f=100MHz 时，加密速率 100Mbps，解密速率约 100Mbps，两次同步的时间间隔约 10s。 2、 LFSR： 联结多项式 1+D 2+D5是生成元，周期为 31，其输出为 1000,0101,0111,0110,0011 3、 s sN N d d T(D)T(D) C(D)C(D) L L m m B(D)B(D) N 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+D3 3 3 1 6 1 1 1+D+D 2+D3 1+D+D 2 4 6 1+D+D 2+D3 7 0 1 1+D+D 2 1+D 3+D4 4 6 1+D+D 2+D3 8 0 1 1+D 3+D4 1+D 2+D5 5 8 1+D 3+D4 9 1 0 1+D 3+D4 1+D 2+D5 5 8 1+D 3+D4 10 1 1 1+D 2+D5 1+D 6 6 10 1+D 2+D5 11 0 0 1+D 2+D5 1+D 6 6 10 1+D 2+D5 12 1 0 1+D 2+D5 1+D 6 6 10 1+D 2+D5 13 a.线性复杂度 6；b.LFSR；c.初始状态 011001；d.00110。 4、 K0=K1=0,K2=255,K3=254,K255=2。 5、 方法之一：将序列与 01010101串相异或。 方法之二：将序列通过加密算法、哈希算法 中国科学技术大学 信息安全专业 密码学导论 5 / 11 6、 n 1n nn 1 ss11 10ss + = 2 1101 1011 = ， 3 1110 1001 = ， 4 1111 1010 = ， 5 1101 101 1 = ， 6 1110 1001 = 因此 6 n 6n n 5n 1 ss11 10ss + + = ，即密钥流的周期是 6 或 6 的因子。 中国科学技术大学 信息安全专业 密码学导论 6 / 11 第第 5 5 组组作业作业 1、 3101(mod 11)。所以，3201 = (310)2033 (mod 11)。 2、 x281(mod29)，x841(mod29)。x=6。 3、 x241(mod35)，x721(mod35)，x121(mod35)，x841(mod35)。x6(mod35)。 可验证，x=-6 不满足 x12-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+2K1=2+3K2=3+4K3=4+K4=5+6K5=6+5K6=7K7。x=371。 8、 三个根：x=5+7t(t=0,1,2)=5,12,19。 9、 z4 mod p=p-x1, z4 mod q=q-x2, z1 mod p=x1, z1 mod q=x2。z1+z4 mod p=0, z1+z4 mod q=0。 所以 z1+z4 mod n=0。因为 z1和 z4都大于 0，小于 n，因此必有 z1+z4 =n，z4=n-z1。同 理可证 z3=n-z2。 10、x2 mod 7=4, x2 mod 11=4。x mod 7=2 或 5, x mod 11=2 或 9。所以 z1=2, z2=9, z3=68, z4=75。 11、a. 若 r是 n模 p-1 的乘法逆元，则 rn=1 mod p-1，有 yrn = 1 mod p 因此(yr)n =1 mod p，即 yr mod p 是 y的一个 n 次根。 b. 3模 4 的乘法逆元是 3，因此一个根是 x=43 mod 5=4。 中国科学技术大学 信息安全专业 密码学导论 7 / 11 原方程等价于 x3-4 =0 mod 5，即(x-4)(x2+4x+1)=0 mod 5 另两个根为 41242 22 =，无整数解。因此只有一个解 4。 c. (55)=40，3 模 40 的乘法逆元是 27，因此一个根是 x=427 mod 55=49 原方程等价于(x-49)(x2+49x+36)=0 mod 55 另两个根为 492257492 22 =，无整数解。因此只有一个解 49。 中国科学技术大学 信息安全专业 密码学导论 8 / 11 第第 6 6 组组作业作业 1、 n=35，a=9。Alice 求解：x2 mod 5=4, x2 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、 x2 mod n=a, y2 mod n=a。不妨设 xy，(x+y)(x-y) mod n=0。因为 yx, yn-x，x-y0， x+yn，所以必有 x+y=p,x-y=q 或 x+y=q,x-y=p，即 gcd(x+y,n)=p 或 q。 3、 n=403，(n)=360，d=7，e=103。m=3, c=3103=33102=3951=27950=278125=1728124 =17211312=1722766=17293=33992=33981=55 (mod 403)。m=557=55556=552043 =3392042=339107=3 (mod 403)。 4、 5。 5、 有帮助。若明文与 n 有公因子，则密文也必与 n 有公因子。因此可以尝试求密文与 n 的最大公因子，若非 1，则该最大公因子为 p 或 q。 6、 不安全。e 和 d 的泄漏有助于 n 的分解。xed-11 mod N，可以测试 gcd(x(ed-1)/2-1,N)。 7、 不安全。攻击者可以计算 025 用公钥加密的结果，将密文列表记录。之后可以对任意 密文用查表的方法破译。 8、 a.(49,57)。 b.C2=29。 9、 (4a3+27b2) mod p = 4(10)3+27(5)2 mod 17 = 4675 mod 17 = 0，不能在 Z17上定义一个群。 10、a.PB=7G=(7,2)。 b.Cm=3G,9G+37G=3G,4G=(8,3),(10,2)。 c.Pm=(10,2)7(8,3)=4G-73G=9G=(10,9)。 中国科学技术大学 信息安全专业 密码学导论 9 / 11 第第 7 7 组组作业作业 1、 可以用散列函数构造分组密码 Feistel 结构的轮函数 F：F(REi,Ki) 2、 取三个密钥 u,v,w，使得 uvw=1 mod (n)。第一签名人私钥为 u，第二签名人私钥为 v， 公钥为 w。显然，当文件用 u 签名后，第二签名人可以根据 v 和 w 进行验证；而只有 u 和 v 都签名后，公众才能用 w验证。 3、 a) gq mod p=1，则 g 的阶必为 q 的因子。q 是素数，因此确定 g的阶为 q。 b) gq mod p=h(p-1) mod p=1（费曼定理） 。与 a 中一样的理由，g 的阶为 q。 c) 因为 q|(p-1)，因此 Zp中有 (q)=q-1 个元素的阶为 q。则随机选择 g 的阶为 q 的概 率为(q-1)/(p-1)。平均需要(p-1)/(q-1)轮循环，即 257.6 轮。 d) 不愿意。平均需要 2864轮循环 e) 算法 2 一轮失败的条件是 h(p-1)/q mod p =1。这意味着 h 的阶是(p-1)/q 的因子。这样 的 h 一共有 (d) d|(p1)/q = (p 1)/q 个。因此，首轮找到生成元的概率为 1 (p 1)/q (p 1)1 1/q，约 0.994。 4、 a) A的私钥为 dA=3，B 的私钥 dB=3 b) nAnB，先加密，后签名。C=(23 mod 15)3 mod 33=(83 mod 33)=17 c) 先验证，后解密。m=(177 mod 33)3 mod 15=83 mod 15=2 5、 a) r=78 mod 13=3；3=(53+8s) mod 12, s=3。密文是(3,3) b) r=75 mod 13=11；7=(511+5s) mod 12, s=0。密文是(11,0)。验证：m mod p = 77 mod 13=6；YA=75 mod 13=11，YArrs mod p = 1111110 mod 13=6。这里 s=0，说明 k 的选取不合适，应当重选。 中国科学技术大学 信息安全专业 密码学导论 10 / 11 第第 8 8 组组作业作业 1、 a.YA=51；b.YB=4；c.K=30 2、 a.t=4, K=2 b.k1=1, k2=4, k3=2, k4=3, k5=2； ()()() ()()() ()()() ()()() ()()() ()()() ()()() ()()() ()()()()()() ()()()()()() ()()()()()() ()()() x4x5x7x2x5x7 14 14 1 5 1 7424547 h(x)mod7 x2x4x7x2x4x5 32 52545712 14 1 5 x4x5x7x2x5x7 14 56 mod7 x2x4x7x2x4x5 32 12 3 x4x5x73 x2x5x7 3 x2x4x7 + = + + = + + = +()()() 3 mod7 x2x4x5 3x5x2 =+ 所以 K=2 3、 a.t=3, K=011