密码学第五版部分课后答案.doc

2.4 已知下面的密文由单表代换算法产生： 请将它破译。提示：1、 正如你所知，英文中最常见的字母是e。因此，密文第一个或第二个（或许第三个）出现频率最高的字符应该代表e。此外，e经常成对出现（如meet,fleet,speed,seen,been,agree,等等）。找出代表e的字符，并首先将它译出来。2、 英文中最常见的单词是“the”。利用这个事实猜出什么字母t和h。3、 根据已经得到的结果破译其他部分。解：由题意分析：“8”出现次数最多，对应明文为“e”，“；48”代表的明文为“the”，“）”、“*”、“5”出现频率都比较高，分别对应“s”、“n”、“a”，由此破译出密文对应的明文为： a good glass in the bishops hostel in the devils seat-twenty-one degrees and thirteen minutes-northeast and by north-main branch seventh limb east side-shoot from the left eye of the deaths head-a bee line from the tree through the shot fifty feet out.2.20 在多罗的怪诞小说中，有一个故事是这样的：地主彼得遇到了下图所示的消息，他找到了密钥，是一段整数： 7876565434321123434565678788787656543432112343456567878878765654343211234a.破译这段消息。提示：最大的整数是什么？b.如果只知道算法而不知道密钥，这种加密方案的安全性怎么样？c.如果只知道密钥而不知道算法，这种加密方案的安全性又怎么样？解：a. 根据提示，将密文排成每行8字母的矩阵，密钥代表矩阵中每行应取的字母，依次取相应字母即可得明文。明文为：he sitteth between the cherubims.the isles may be glad thereof.as the rivers in the south.b.安全性很好。若密文的字母数为8n，则共有种可能的密钥，不易攻破。c.安全性较差。将字母总数与密钥总数相除，得每组8个字母，即可破译。3.8 这个问题给出了用一轮des加密的具体数字的例子。假设明文和密钥k有相同的位模式，即： 用十六进制表示：0 1 2 3 4 5 6 7 8 9 a b c d e f 用二进制表示： 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111a.推导第一轮的子密钥解：经过表3.4（b）pc-1置换，得：c0：1111000011001100101010100000d0：1010101011001100111100000000经过表3.4（d）左移，得：c1：1010000110011001010101000001d1：0101010110011001111000000001经过表3.4（c）置换选择，得：k1：0000 1011 0000 0010 0110 0111 1001 1011 0100 1001 1010 0101用十进制表示为：0 b 0 2 6 7 9 b 4 9 a 5b.推导l0，r0解：经过表3.2（a）置换，得l0 ：1100 1100 0000 0000 1100 1100 1111 1111r0 ：1111 0000 1010 1010 1111 0000 1010 1010c.扩展r0求e（r0）解：根据表3.2（c）扩充置换，得：e(r0) = 01110 100001 010101 010101 011110 100001 010101 010101d.计算a=e(r0)k1解：根据a、c可得a = 011100 010001 011100 110010 111000 010101 110011 110000e.把（d）的48位结果分成6位（数据）的集合并求对应s盒代换的值解：根据表3.3s盒代换得(1110) = (14) =0 (10进制)=0000 (2进制)(1000) = (8) =12 (10进制)=1100 (2进制)(1110) = (14) =2 (10进制)=0010(2进制)(1001) = (9) = 1(10进制)=0001(2进制)(1100) = (12) =6 (10进制)=0110 (2进制)(1010) = (10) =13 (10进制)=1101(2进制)(1001) = (9) =5 (10进制)=0101 (2进制)(1000) = (8) =0 (10进制)=0000 (2进制)f.利用（e）的结论来求32位的结果b解：b = 0000 1100 0010 0001 0110 1101 0101 0000g.利用置换求p(b)解：根据表3.2（d），得p(b) = 1001 0010 0001 1100 0010 0000 1001 1100h.计算r1=p(b)l0解：r1 = 0101 1110 0001 1100 1110 1100 0110 0011i.写出密文解：l1=r0，连接l1、r1可得密文为：meye823.12 16个密钥（k1、k2k16）在dse解密过程中是逆序使用的。因此，图3.5的右半部分不再正确。请模仿表3.4（d）为解密过程设计一个合适的密钥移位扩展方案。解：选代轮数12345678910111213141516移位次数01222222122222213.10 （a） 解：t16(l15 | r15) = l16 | r16t17(l16 | r16) = r16 | l16ip ip1 (r16 | l16) = r16 | l16td1(r16 | l16) = l16 | r16 f(l16, k16)=r15 | l15 f(r15, k16) f(r15, k16)= r15 |l15 （b）解：t16(l15 | r15) = l16 | r16ip ip1 (l16 | r16) = l16 | r16td1(r16 | l16) = r16 | l16 f(r16, k16)= l15 f(r15, k16)| r15 f(r16, k16)l15 | r153.15for 1 i 128, take ci 0, 1128 to be the string containing a 1 in position i and then zeros elsewhere. obtain the decryption of these 128 ciphertexts. let m1, m2, . . . , m128 be the corresponding plaintexts. now, given any ciphertext c which does not consist of all zeros, there is a unique nonempty subset of the cis which we can xor together to obtain c. let i(c) 1, 2, . . . , 128 denote this subset. observethus, we obtain the plaintext of c by computing . let 0 be the all-zero string. note that 0 = 0 0. from this we obtain e(0) = e(0 0) = e(0) e(0) = 0. thus, the plaintext of c = 0 is m = 0. hence we can decrypt every c 0, 1128. 4.15a.gcd(24140, 16762) = gcd(16762, 7378) = gcd(7378, 2006) = gcd(2006, 1360) = gcd(1360, 646) = gcd (646, 68) = gcd(68, 34) = gcd(34, 0) = 34b.gcd(4655, 12075) = gcd(12075, 4655) = gcd(4655, 2765) = gcd(2765, 1890) = gcd(1890, 875) = gcd (875, 140) = gcd(140, 35) = gcd(35, 0) =354.17 a. euclid: gcd(2152, 764) = gcd(764, 624) = gcd(624, 140) = gcd(140, 64) = gcd(64, 12) = gcd(12, 4) = gcd(4, 0) = 4stein: a1 = 2152, b1 = 764, c1 = 1; a2 = 1076, b2 = 382, c2 = 2; a3 = 538, b3 = 191, c3 = 4; a4 = 269, b4 = 191, c4 = 4; a5 = 78, b5 = 191, c5 = 4; a6 = 39, b6= 191,c6 = 4; a7 = 152, b7 = 39, c7 = 4; a8 = 76, b8 = 39, c8 = 4; a9 = 38, b9 = 39, c9 = 4; a10 = 19, b10 = 39, c10 = 4; a11 = 20, b11 = 19, c11 = 4; a12 = 10, b12 = 19, c12 = 4; a13 = 5, b13 = 19, c13 = 4; a14 = 14, b14 = 5, c14 = 4; a15 = 7, b15 = 5, c15 = 4; a16 = 2, b16 = 5, c16 = 4;a17 = 1, b17 = 5, c17 = 4; a18 = 4, b18 = 1, c18 = 4; a19 = 2, b19 = 1, c19 = 4; a20 = 1, b20 = 1, c20 = 4; 故gcd(2152, 764) = 1 4 = 4 b. 在每一步算法中，euclid算法所进行的除法运算比较复杂，而stein算法只需完成除以2、相等、求差或取最小值的简单运算，减小了运算复杂度。4.23a.9x2 + 7x + 7b.5x3 + 7x2 + 2x + 64.25a.1b.1c.x + 1 d.x + 787.2 因为xn+1 = (axn ) mod 24，易知若a为偶数，则经过n轮之后xn+1必恒等于0，故a必为奇数。且a16,分别取a=3,5,7,9,11,13,15，得： a=3,则xn=1,3,9,11,1,3， 或xn=5,15,13,7,5,15， a=5,则xn=1,5,9,13,1,5， 或xn=3,15,11,7,3,15， a=7,则xn=1,7,1 舍去 a=9,则xn=1,9,1 舍去 a=11,则xn=1,11,9,3,1,11， 或xn=5,7,13,15,5,7， a=13,则xn=1,13,9,5,1,13， 或xn=3,7,11,15,3,7， 故：（a） 最大周期为4（b） a=3或5或11或13（c） 与a必为奇数同理，种子必须为奇数。7.4 两个发生器产生的伪随机数分别为： 1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, . . .1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, . . . 从中可以看出，第二个发生器产生的伪随机数存在一部分xn+1 = 2xn的现象，所以第一个伪随机数发生器的随机性更好一些。8.5a = 9794 mod 73=12而0a72, 73为素数，故取a=128.8因为(35)=24，x(35)=1mod35所以x85mod35=(x24mod35)3)*(x12mod35)*(xmod35)mod35=(x12mod35)*(xmod35)mod35又因为x24mod35=1所以x12mod35=1或-1所以x85mod35=xmod35或-xmod35=6故x=6或x=29,代入验证得x=69.3 因为 n=35 所以f(35) =24 因为 ed=1 mod f(35) ; e=5 所以 d=5 所以 m= cd mod n=59.5 不安全 因为在已知n的情况下易知f(n)，根据密钥产生原则：（1）选择e使其与f(n)互素且小于f(n) （2）确定d使得de=1(mod f(n)且d f(n) 可以得出e、d的可能值，再通过进一步观察即可求出e和d，特别是在n很小的情况下，只需通过简单的计算就可以破解密钥。8.21离散对数表如下图所示：a1234567891011121314log2,29(a)248163112241991871428a1516171819202122232425262728log2,29(a)27252113262317510201122156b. 因为17x2 =10（mod29）所以dlog2,29(17)+2dlog2,29(x)(mod28)=2321+2log2,29(x)(mod28)=23所以21+2log2,29(x)=23或 21+2log2,29(x)=51所以x=2或x=27c. 因为x2-4x-16=(0mod29)所以(x-2)2=(20mod29)易知x!=1所以2dlog2,29(x-2)(mod28)=24所以dlog2,29(x-2)=12或 dlog2,29(x-2)=26所以x=9或x=21d. 因为x7=17（mod29）所以7log2,29(x)=21所以7log2,29(x)=21或49或77或105或133或161或189所以x=8或10或12或15或18或26或279.14this algorithm is discussed in the cesg report mentioned in chapter 6 elli99, and is known as cocks algorithm.a.cocks makes use of the chinese remainder theorem (see section 8.4 and problem 8.10), which says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli. in particular for relatively prime p and q, any integer m in the range 0 m n can be the pair of numbers m mod p and m mod q, and that it is possible to recover m given m mod p and m mod q. the security lies in the difficulty of finding the prime factors of n.b.in rsa, a user forms a pair of integers, d and e, such thatde 1 mod (p 1)(q 1), and then publishes e and n as the public key. cocks is a special case in which e = n.c.the rsa algorithm has the merit that it is symmetrical; the same process is used both for encryption and decryption, which simplifies the software needed. also, e can be chosen arbitrarily so that a particularly simple version can be used for encryption with the public key. in this way, the complex process would be needed only for the recipient.d.the private key k is the pair p and q; the public key x is n; the plaintext p is m; and the ciphertext z is c. m1 is formed by multiplying the two parts of k, p and q, together. m2 consists of raising m to the power n (mod n). m3 is the process described in the problem statement.10.6a.(49, 57)b.c2 = 2911.1a.yes. the xor function is simply a vertical parity check. if there is an odd number of errors, then there must be at least one column that contains an odd number of errors, and the parity bit for that column will detect the error. note that the rxor function also catches all errors caused by an odd number of error bits. each rxor bit is a function of a unique spiral of bits in the block of data. if there is an odd number of errors, then there must be at least one spiral that contains an odd number of errors, and the parity bit for that spiral will detect the error. b.no. the checksum will fail to detect an even number of errors when both the xor and rxor functions fail. in order for