密码学第五部份课后答案

1、己知下面的密文由单表代换算法产生:53 计+305)6*;4826)舛.)什)：8()6*：4"鲫 6()85:8*;审'8+83 (88)5*欠46(;88*96*?;8产式;485);5*十2:舁(；495625*-4)88 ;4069285);)6t8)4tddagger;l (19;48081 ;8:8$ 1 ;48t85:4)485t528806 8 住 9;48;(88;4 件?34;48)舛;161;：!期?；请将它破译。提示：1、正如你所知，英文中最多见的字母是e6因此，密文第一个或第二个(或许第三个)显现频率最高的字符应该代表e 6另外，e常常成对显现(如m

2、eet, fleet, speed, seen, been, agree,等等)。找出代表e的字符,并第一将它译出来。2、英文中最多见的单词是“the”。利用那个事实猜出什么字母t和h。3、依照已经取得的结果破译其他部份，解：由题意分析：“8”显现次数最多,对应明文为48”代表的明文为“the”，“)”、 “*”、“5”显现频率都比较高,别离对应“s”、"n”、“a”，由此破译出密文对应的明文为:A good glass in the Bishop, s hostel in the Devil? s seat-twenty-one degrees and thirteen minut

3、es-northeast and by north-main branch seventh limb east side-shoot from the left eye of the death* s head-a bee line from the tree through the shot fifty feet out.在多罗的怪诞小说中，有一个故事是如此的：地主彼得碰到了以下图所示的消息，他找到 了密钥，是一段整数：I 卅ougM +o see 坤e fairies jn 扑e b" I aw only +Ae ev" e("hao+$ wi卅 iheir

4、btaek back- Woe! how 讣H "gh+ awed Me!7he eNes danced 呼 around and about while I heard voice， casing c(ear(v AA! how I +ried +。.£uetAfgw off 十he ugly c(oud，6u+ no bnd eve of a woriaj w”。引什ed +。Y Aem So then came winstreis? having，o(d +raMeH, bar” aod drum一 These slaved very (oud(v beside Me

5、, breaking 十八"$oe" So the "eaM vani仆ej, whereat I -hanked Weaven. I 仆ed Many fean before +he fhin moon rose aP,a* and fain- as a sickle of rfraw- Mow “uugh +he EncAan+er gnash hh vai"v, ve+ s6a<( 6e return as fhe Sarin，reborn£ Oh? wrefcAed Mao! Heit 夕aE£, Erebus now

6、(*eT G»en The mg«，A9 of Oeah wa(f on +Av eod3211234a.破译这段消息。提示：最大的整数是什么？b.若是只明白算法而不明白密钥，这种加密方案的平安性怎么样？c.若是只明白密钥而不明白算法，这种加密方案的平安性又怎么样?解：R.依照提示，将密文排成每行8字母的矩阵，密钥代表矩阵中每行应取的字母，依次取相应 字母即可得明文。明文为：He sitteth between the isles may be glad the rivers in the South.B.平安性专门好。假设密文的字母数为8n,那么共有8“种可能的密钥，不易

7、攻破。C.平安性较差。将字母总数与密钥总数相除，得每组8个字母，即可破译。那个问题给出了用一轮DES加密的具体数字的例子。假设明文和密钥K有相同的位模式， 即：用十六进制表示：0123456789ABCDEF用二进制表示：0000 0001 0010 0011 0100 0101 0110 01111000 1001 1010 1011 1100 1101 1110 1111a.推导第一轮的子密钥解：通过表（b） PC-1置换，得：co： 00DO： 00通过表（d）左移，得：cr ： ooDl' ： oo通过表（c）置换选择，得：K1： 0000 1011 0000 0010 011

8、0 0111 1001 1011 0100 1001 1010 0101用十进制表示为：0B02679B49A5b.推导L0, R0解：通过表（a）置换，得Lo ： 1100 1100 0000 0000 1100 1100 1111 1111Ro ： 1111 0000 1010 1010 1111 0000 1010 1010C.扩展RO求E （RO）解：依照表（C）扩充置换，得：E（R0）= OHIO 100001 010101 010101 011110 100001 010101 010101d.计算A=E （R0）KI解：依照a、c可得A = 011100 010001 01110

9、0 110010 111000 010101 110011 110000 e.把（d）的48位结果分成6位（数据）的集归并求对应S盒代换的值 解：依照表盒代换得T （1110） = . （14） =0 （10 进制）=0000 （2 进制）（1000）=玛（8） =12 （10 进制）=1100 （2 进制）33 （1110） = '3 （14） =2 （10 进制）=0010（2 进制）24 （1001） = % =1（10 进制）=0001 （2 进制）"5 （1100） =（12） =6 （10 进制）=0110 （2 进制）（1010） = （io） =13 （10

10、进制）=1101 （2 进制）（1001）=的=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)解：依照表(d),得P(B) = 1001 0010 0001 1100 0010 0000 1001 1100 h.计算R1=PL0解：R1二 0101 1110 0001 1100 1110 1100 0110 0011i.写出密文解：L1=RO,连接L-、R1可得密文为：MEYE82

11、16个密钥（K 一、K2K16）在DSE解密进程中是逆序利用的。因此，图的右半部份再也 不正确。请仿照表（d）为解密进程设计一个适合的密钥移位扩展方案。解：选代轮数12345678910111213141516移位次数0122222212222221(a)解：T16(L15R15)= L16R16T17(L16R16) = R16L16ip ip-1 (r16l16) = r16l16td1(r16L6)= L6R16f(h6，K16)=R15L15f (R15» K16)f(R】5， K16)= R15L15(b)解：T16(L15R15)= L16R16IP LIP_1 (l16

12、r16) = l16r16TD1 尔16 HP = R16 L16 f(R16, W=L15 f(R15> K16) R15f(R】6，K16)L15R15For 1 W i W 128, take q e 0, 1128 to be the string containing a 1 in position i and then zeros elsewhere. Obtain the decryption of these 128 ciphertexts. Let mp m?,mpg be the corresponding plaintexts. Now, given any cip

13、hertext c which does not consist of all zeros, there is a unique nonempty subset of the cj s which we can XOR together to obtain c. Let I (c) c 1, 2, . . . , 128 denote this subset. ObserveA g= A E(mJ =di(c)Thus, we obtain the plaintext of c by computing HL. Let 0 be the all-zero ii /(C)string. Note

14、 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 everyC 0. I128.a. gcd(24140, 16762) = gcd(16762, 7378) = gcd(7378, 2006) = gcd(2006t 1360) = gcd(1360, 646) = gcd (646, 68) = gcd(68, 34) = gcd(34, 0) = 34 b. gcd (4655, 12075

15、) = gcd (12075, 4655) = gcd (4655, 2765) = gcd (2765, 1890) =gcd (1890, 875) = gcd (875, 140) = gcd (140, 35) = gcd (35, 0) =35a. Euclid: gcd(2152, 764) = gcd(764, 624) = gcd(624, 140) = gcd(140, 64)= gcd(64, 12) = gcd(12, 4)= gcd(4, 0) = 4Stein: A】=2152,=764, q = 1;A2 = 1076, Bg = 382, C2= 2;A3 = 5

16、38, B3 = 191, C3 = 4;A4 - 269, B4 - 191, C4 = 4;A5 = 78, B5 = 191, c5 = 4;Ag = 39, B6= 191, C6 = 4;A7 = 152, By = 39, Cy = 4;Ag = 76, Bg = 39, Cg - 4;Ag = 38, Bg = 39, Cg = 4;A|q = 19, B0 = 39, C0 = 4;A= 20, B= 19, C= 4;a13 = 5，b13 = 19, C13 = 4;A14 二 14, B4 = 5, C" = 4;A15 = 7, B15 = 5, C15 =

17、4;a16 - 2, B16 = 5, C16 = 4;A7 = 1，B17 = 5, C7= 4;a18 = 4，b18 = 1，C8 二 4;a20 = 1，B20 = 1，C20 = 4;故 gcd(2152, 764) = 1 ' 4 = 4b.在每一步算法中，Euclid算法所进行的除法运算比较复杂，而Stein算法只 需完成除以二、相等、求差或取最小值的简单运算，减小了运算复杂度。a. 9xq + 7x + 7b. 5x3 + 7x£ + 2x + 6a. 1b. 1c. x + 1d. x + 78因为Xn+l = (aXn ) mod 24,易知假设a为偶数，

18、那么通过n轮以后Xn+1必恒等于0, 故a必为奇数。且水16,别离取a=3, 5, 7, 9, 11,13, 15,得：a=3,那么 Xn=l,3,9,11,1,3, 或 Xn=5,15,13, 7, 5,15, a=5,那么 Xn=l,5,9,13,1,5, 或Xn=3,15,11, 7, 3,15, a=7,那么Xn=l, 7,1舍去a=9,那么Xn=l, 9,1舍去a=ll,那么 Xn=l, 11,9,3, 1,11,或 Xn=5, 7,13,15, 5, 7,a=13,那么 Xn=l, 13,9,5,1,13, 或 Xn=3, 7,11,15,3, 7, 故：(a)最大周期为4(b)

19、a=3 或 5 或 11 或 13(C) 与a必为奇数同理，种子必需为奇数。两个发生器产生的伪随机数别离为：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的现象，因此第 一个伪随机数发生器的随机性更好一些。a = 9794 mod 73=12而0<a<72, 73为素数，故取a=12因为 <1> (35)=24, x* 4)(35)=lmod35因此 x 85mod35= (x*24mo

20、d35)* 3) * (x* 12mod35) * (xmod35)mod35=(x*12mod35)*(xmod35)mod35又因为 x'24mod35=l因此 x" 12mod35=l 或T因此 x*85mod35=xmod35 或-xmod35=6故x=6或x=29,代入验证得x=6因为n=35因此 (55)=24因为 ed=l mod (35) ; e=5 因此 d=5因此 M= Cd mod n=5不平安因为在已知n的情形下易知 5),依照密钥产生原那么：(1)选择e使其与 储)互 素且小于 山)(2)确信d使得de=l(mod (储且水 ()能够得出e、d的 可

21、能值，再通过进一步观看即可求出e和d,专门是在n很小的情形下，只需通过简单 的计算就能够够破解密钥。离散对数表如以下图所示:a1231567891011121311Log2, 29 ( a)248163112241991871428a1516171819202122232425262728Log2, 29 ( a)27252113262317510201122156B.因为 17x2 =10 (mod29 )因此dlog2, 29(17)+2dlog2, 29 (x) (mod28)=2321+21og2, 29(x)(mod28)=23因此 21+21og2, 29(x)=23或 21+21

22、og2,29(x)=51因此x=2或x=27C 因为 x,-4x-16=(0niod29)因此(x-2)2=(20niod29)易知x!二l因此2dlog2, 29 (x-2) (mod28) =24因此 dlog2, 29 (x-2) =12或 dlog2,29(x-2)=26因此x=9或x=21D.因为 X7=17 (mod29)因此71og2, 29(x)=21因此 71og2, 29(x)=21 或 49 或 77 或 105 或 133 或 161 或 189因此x=8或10或12或15或18或26或27This algorithm is discussed in the CESG

23、report mentioned in Chapter 6 ELLI99, and is known as Cocks algorithm.a. Cocks makes use of the Chinese remainder theorem (see Section and Problem , which says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli. In particula

24、r for relatively prime P and Q, any integer M in the range 0 W 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

25、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

26、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. Ml is for

27、med 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.a. (49, 57)b. C, 29a. Yes. The XOR function is simply a vertical parity check. If there is an odd number of errors, then there must be at le

28、ast 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