密碼學(xué)第五部份課后答案

1、己知下面的密文由單表代換算法產(chǎn)生:53 計(jì)+305)6*;4826)舛.)什)：8()6*：4"鯽 6()85:8*;審'8+83 (88)5*欠46(;88*96*?;8產(chǎn)式;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;：!期?；請(qǐng)將它破譯。提示：1、正如你所知，英文中最多見(jiàn)的字母是e6因此，密文第一個(gè)或第二個(gè)(或許第三個(gè))顯現(xiàn)頻率最高的字符應(yīng)該代表e 6另外，e常常成對(duì)顯現(xiàn)(如m

2、eet, fleet, speed, seen, been, agree,等等)。找出代表e的字符,并第一將它譯出來(lái)。2、英文中最多見(jiàn)的單詞是“the”。利用那個(gè)事實(shí)猜出什么字母t和h。3、依照已經(jīng)取得的結(jié)果破譯其他部份，解：由題意分析：“8”顯現(xiàn)次數(shù)最多,對(duì)應(yīng)明文為48”代表的明文為“the”，“)”、 “*”、“5”顯現(xiàn)頻率都比較高,別離對(duì)應(yīng)“s”、"n”、“a”，由此破譯出密文對(duì)應(yīng)的明文為: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.在多羅的怪誕小說(shuō)中，有一個(gè)故事是如此的：地主彼得碰到了以下圖所示的消息，他找到 了密鑰，是一段整數(shù)：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.破譯這段消息。提示：最大的整數(shù)是什么？b.若是只明白算法而不明白密鑰，這種加密方案的平安性怎么樣？c.若是只明白密鑰而不明白算法，這種加密方案的平安性又怎么樣?解：R.依照提示，將密文排成每行8字母的矩陣，密鑰代表矩陣中每行應(yīng)取的字母，依次取相應(yīng) 字母即可得明文。明文為：He sitteth between the isles may be glad the rivers in the South.B.平安性專(zhuān)門(mén)好。假設(shè)密文的字母數(shù)為8n,那么共有8“種可能的密鑰，不易

7、攻破。C.平安性較差。將字母總數(shù)與密鑰總數(shù)相除，得每組8個(gè)字母，即可破譯。那個(gè)問(wèn)題給出了用一輪DES加密的具體數(shù)字的例子。假設(shè)明文和密鑰K有相同的位模式， 即：用十六進(jìn)制表示：0123456789ABCDEF用二進(jìn)制表示：0000 0001 0010 0011 0100 0101 0110 01111000 1001 1010 1011 1100 1101 1110 1111a.推導(dǎo)第一輪的子密鑰解：通過(guò)表（b） PC-1置換，得：co： 00DO： 00通過(guò)表（d）左移，得：cr ： ooDl' ： oo通過(guò)表（c）置換選擇，得：K1： 0000 1011 0000 0010 011

8、0 0111 1001 1011 0100 1001 1010 0101用十進(jìn)制表示為：0B02679B49A5b.推導(dǎo)L0, R0解：通過(guò)表（a）置換，得Lo ： 1100 1100 0000 0000 1100 1100 1111 1111Ro ： 1111 0000 1010 1010 1111 0000 1010 1010C.擴(kuò)展RO求E （RO）解：依照表（C）擴(kuò)充置換，得：E（R0）= OHIO 100001 010101 010101 011110 100001 010101 010101d.計(jì)算A=E （R0）KI解：依照a、c可得A = 011100 010001 01110

9、0 110010 111000 010101 110011 110000 e.把（d）的48位結(jié)果分成6位（數(shù)據(jù)）的集歸并求對(duì)應(yīng)S盒代換的值 解：依照表盒代換得T （1110） = . （14） =0 （10 進(jìn)制）=0000 （2 進(jìn)制）（1000）=瑪（8） =12 （10 進(jìn)制）=1100 （2 進(jìn)制）33 （1110） = '3 （14） =2 （10 進(jìn)制）=0010（2 進(jìn)制）24 （1001） = % =1（10 進(jìn)制）=0001 （2 進(jìn)制）"5 （1100） =（12） =6 （10 進(jìn)制）=0110 （2 進(jìn)制）（1010） = （io） =13 （10

10、進(jìn)制）=1101 （2 進(jìn)制）（1001）=的=5 （10 進(jìn)制）=0101 （2 進(jìn)制）年（1000）=迦（8） =0 （10 進(jìn)制）=0000 （2 進(jìn)制）f.利用（e）的結(jié)論來(lái)求32位的結(jié)果B解：B = 0000 1100 0010 0001 0110 1101 0101 0000g.利用置換求P(B)解：依照表(d),得P(B) = 1001 0010 0001 1100 0010 0000 1001 1100 h.計(jì)算R1=PL0解：R1二 0101 1110 0001 1100 1110 1100 0110 0011i.寫(xiě)出密文解：L1=RO,連接L-、R1可得密文為：MEYE82

11、16個(gè)密鑰（K 一、K2K16）在DSE解密進(jìn)程中是逆序利用的。因此，圖的右半部份再也 不正確。請(qǐng)仿照表（d）為解密進(jìn)程設(shè)計(jì)一個(gè)適合的密鑰移位擴(kuò)展方案。解：選代輪數(shù)12345678910111213141516移位次數(shù)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算法所進(jìn)行的除法運(yùn)算比較復(fù)雜，而Stein算法只 需完成除以二、相等、求差或取最小值的簡(jiǎn)單運(yùn)算，減小了運(yùn)算復(fù)雜度。a. 9xq + 7x + 7b. 5x3 + 7x£ + 2x + 6a. 1b. 1c. x + 1d. x + 78因?yàn)閄n+l = (aXn ) mod 24,易知假設(shè)a為偶數(shù)，

18、那么通過(guò)n輪以后Xn+1必恒等于0, 故a必為奇數(shù)。且水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必為奇數(shù)同理，種子必需為奇數(shù)。兩個(gè)發(fā)生器產(chǎn)生的偽隨機(jī)數(shù)別離為：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,從中能夠看出，第二個(gè)發(fā)生器產(chǎn)生的偽隨機(jī)數(shù)存在一部份Xn+1=2Xn的現(xiàn)象，因此第 一個(gè)偽隨機(jī)數(shù)發(fā)生器的隨機(jī)性更好一些。a = 9794 mod 73=12而0<a<72, 73為素?cái)?shù)，故取a=12因?yàn)?<1> (35)=24, x* 4)(35)=lmod35因此 x 85mod35= (x*24mo

20、d35)* 3) * (x* 12mod35) * (xmod35)mod35=(x*12mod35)*(xmod35)mod35又因?yàn)?x'24mod35=l因此 x" 12mod35=l 或T因此 x*85mod35=xmod35 或-xmod35=6故x=6或x=29,代入驗(yàn)證得x=6因?yàn)閚=35因此 (55)=24因?yàn)?ed=l mod (35) ; e=5 因此 d=5因此 M= Cd mod n=5不平安因?yàn)樵谝阎猲的情形下易知 5),依照密鑰產(chǎn)生原那么：(1)選擇e使其與 儲(chǔ))互 素且小于 山)(2)確信d使得de=l(mod (儲(chǔ)且水 ()能夠得出e、d的 可

21、能值，再通過(guò)進(jìn)一步觀看即可求出e和d,專(zhuān)門(mén)是在n很小的情形下，只需通過(guò)簡(jiǎn)單 的計(jì)算就能夠夠破解密鑰。離散對(duì)數(shù)表如以下圖所示:a1231567891011121311Log2, 29 ( a)248163112241991871428a1516171819202122232425262728Log2, 29 ( a)27252113262317510201122156B.因?yàn)?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 因?yàn)?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.因?yàn)?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