SOLUTIONS MANUAL FOR AN INTRODUCTION TO CRYPTOGRPHY WITH CODING

所需积分/C币:34 2016-04-24 06:07:24 781KB PDF

INTRODUCTION TO CRYPTOGRPHY WITH CODING (2nd Edition)的答案
Chapter 19- Exercises 51 Mathematica problems Chapter 2 52 Cha ap 63 Chapter 6 66 Chapter 7 72 Chapter 8 Chapter 9 75 Chapter 12 78 Chapter 16 79 Chapte pt er 18 81 aple problems Chapter 2 84 pter 98 Chapter 6 102 Chapter 7 1o9 Chapt 112 Chapter 9 113 Chapter 12 116 Chapter 16 118 Chapter 18 121 MATLAB problems Chapter 2 124 Chapter 3 147 Chapter 6 151 Chapter 7 161 Chapter 8 164 Chapter 165 Chapter 12 167 Chapter 16 l69 Chapter 18 174 Chapter 2-Exercises 1. Among the shifts of Evire, there are two words: arena and river. Therefore Anthony cannot determine where to meet Caesar of g mod 26 is 3 . =3(y-2)=3y-2(nod 26). Now sinply decrypt leter. 2. Th C, the decryption function etter as followS [=20 so decrypt. U by calculating 3* 20-6(mod 26)=2, and so on. The decrypted message is 'cat 3. Changing the plaintext to numbers yields 7, 14, 22, 0, 17.4, 24, 14, 20 Applying5x+7 to each yields5·7+7=42≡16(mod26),5·14+7=77≡25, etc. Changing back to letters yields QZNHOBXZD as the ciphertext 4. Let mc +n be the encryption function. Since h=7 and N=13, we have m. 7+n=13(mod 26). Using the second letters yields m.0+n= 14 Therefore n= 14. The first congruence now yields 7m=-l(mod 26 ). This yiclds m=ll. The cncryption function is thcrcforc 11 t 14 5. Let the decryption function be t =ay+b. The first letters tell us that 7=a 2+b(mod 26). The second letters tell us that=a. 17+b Subtracting ilds7≡a·(-15)≡1la. Since11-1=19(mod26), we have a≡19.7=3 (mod 26). The first congruence now tells us that 7=3 2+ b, so b=1. The decryption function is therefore a= 3y+1. Applying this to CRWWZ yields happy for the plaintext 6. Let m+n be one affine function and ac +b be another. applying the first then the second yields the function a(Tr +n)+b=(am +(an+b), which is an affine function. Therefore, successively encrypting with two affine functions is the same as encrypting with a single affine function. There is therefore no advantage of doing double encryption in this case. (Technical point: Since gcd(a, 26)=1 and gcd(m, 26)=1, it follows that gcd(am, 26)=1, so the affine function we obtained is still of the required form. 7. For an affine cipher m c + n(mod 27), we must have gcd (27, m) and we can always take 1 <Tr 27. So we Inust exclude all Multiples of 3 which leaves 18 possibilities for m. All 27 values of n are possible, so we have 18- 27=486 kcys. When we work mod 29, all valucs 1 <m< 28 arc allowed, so we have 28. 29=812 keys 8.(a. )In order for a to be va lid and lead to a decryption algorithm, we need ged(a, 30)=1. The possible values for a are 1, 7, 11,13, 17, 19 23, 29 (b We need to find two such that 10.c(mod 30) gives the same value There are many such possible answers. for example a= l and a =4 will work This corresponds to the letters’b’and'e’. 9.Ifx1=2+(26/d, then a1+6=am2++(a/d)26 since d= gcd(a, 26) divides a, the number a/26 is an integer. Therefore (a/d 26 is a multiple of 26, which means that ac1+B=a T2+3(mod 26). Therefore xI and 2 encrypt to the saine ciphertext, so unique decryption is impossible 10.(a) In order to find the most probable key length, we write the ciphertext down on two strips and shift the sccond strip by varying amounts. The shift with the most matches is the most likely key length. As an example, look at the shift by 1 BABA A BA B A This has a total of 2 matches. a shift by 2 has 6 matches, while a shift by 3 has 2 matches. Thus, the most likely key length is 2 (b) To decrypt, we use the fact that the key length is 2 and extract off every odd letter to get BBBAB, and then every even letter to get AAAAA. Using a frequency count on each of these yields that a shift of o is the most likely scenario for the first charactcr of the Vigcncrc key, whilc a shift of 1 is the most likely case for the second character of the key. Thus, the key is AB. Decrypting each subsequence yields BBBAB and BBBBB. Combining them gives the original plaintext bbbbbbabbb 11. If we look at shifts of 1.2. and 3 we have 2. 3. and 1 matches. This certainly rules out 3 as the key length, but the key length may be 1 or 2 In the ciphertext, there are 3 As, 5 Bs, and 2 Cs. If the key length were 1 his should approximate the frequencies. 7, 2,. 1 of the plaintext in some order which is not the case. So we rule out 1 as the key length Let's consider a key length of 2. The first, third, fifth,. letters are ACABA There are 3 As, 1 B, and 1C. These frequencies of 6,. 2,.2 is a close match to. 7, 2,. 1 shifted by 0 positions. The first element of the key is probably A The second, fourth,. letters of the ciphertext are BBBBC. There are 0 As, 4 Bs, and 1 C. These frequencies. 0. 8,. 2 and match. 7.2,I with a shift by 1 Therefore the second key element is probably B Since the results for length 2 match the frequencies most closely, we conclude that the key is probably AB 12. Sincc thc entries of Ai arc thc samc as thosc in Ao( shifted a fcw placcs the two vectors have thie saine lengthl. Therefore Ao. Ai=AollAi cos 0=Aol. cos 6 Note that when 6=0. but e wner the two vectors are equal. So we see that the largest value of the cosine is when Ao=Ai. Thcrcforc thc largest valuc of the dot product is when i=0 13. Change YIFZMA to pairs of numbers:(24, 8),(5, 25),(12,0). Invert the matrix to get N= 249 (mod 26). Calculate (24.8)N=(4,20).(5,25)N=(17,4),(12,0)N=(10.0). Change back to lett reke 14. Suppose the encryption matrix M is/ 6 Change the ciphertext to numbers:( 6, 4),(25, 23).(3, 18). Change the plaintext to numbers:(18, 14),(11,21),(4,3). We know(18,14)M≡(6,4),ete. We'll use(11,21)M (25, 23) and(4, 3)M=(3, 18) to get equations for a, b, c, d, which are most 1121 b 2523 easily put in matrix form 318 The inverse 43 C O71121 3/md26 43 2211 Multiply by this Matrix to obtain M= bd 15. Suppose the matrix has the form Then the encryption of a plaintext a =(b, a)=(1,0) yields(a, B). We know this corresponds to HC, alld hence (=7 and B=2. The second piece of information is that zz encrypts to gt. This corresponds to a plaintext of(25, 25) or equivalently(-1,-1). Using this yields -C-=6 and-6-8-=19. Thus, 13 and o=5 16.(a) The plaintext is(3, 14),(13, 19). The ciphertext is(4, 11),(13, 8) We have\1319/4≈/4 11 314 The inverse of 138 mod 26 1319 1912 133 Multiplying by this inverse yields M=\ 13 23 We have 314 M 411 1319 1310 Proceeding as in part(a),we 1019 find m 1319 17. Suppose the plaintext is of the form(, y), then the ciphertext is of the form (.+3y, 2 C +4y)(mod 26). There will be many possible plaintexts that will map to the same ciphertext. We will try to make plaintexts that yicld a ciphertext of the form(0, * To do so, we will havc the rclationship By(mod 26). Now we need to find two y values that produce the same 2(-3)+ y(mod 26). If we take y= 4 and 17 then we get, the same value for 2y (mod 26). Thus,(14, 4)and(1,17) are two plaintexts that ma ap to(0, 18) 18. We will need to use three different plaintexts. First, choose(a, y) (0,0). This will produce a ciphertext that is precisely (e, f). Next, try(r, y) (1,0). This will produce a ciphertext that is(a, b)+(e, f). We may subtract off (e, f) to find (a, b). Finally, use(a, y)=(0, 1) 1 to ge (c, d)+(e, f) as the ciphertext. We may subtract off(e, f) to get(c, d) 19. As is Section 2.11, set up the matrix equation 001 1 111 This yields co =1,C1=0, c2=1, so the recurrence is hm+3= kn +kin2. The next four terms of the sequence are 1,0,0, 1 20. The sequence is 1, 0, 1, 0, 1, 0, 1,.... The matrix equation is (3)(④) 1 0). This yields co=1, c1=0, so kin+2= kin 21. Set up the matrix equatior Using the values provided. we obtain C The inverse of the matrix can be found to be 1 01 12 (mod 3) Multiplying both sides of by the inverse matrix, yields co=2 and c1= 1 22. Use 1, I2 and 3 to solve for Cl by obtaining C1+2=1(mod 5 ). Thus 4. Next, use 2, 3 and 4 to solve for co. We get Co+C1+2(mod 5)=0, 4 23. The nunber of seconds in 120 years is 0×60×24×365×120≈38×10° Therefore you need to count 1000/ 3.8x10)N2.6x 0 numbers per second 24.(a) The ciphertext will consist of one letter repeated. However, there is no way of deducing what the key is (b) The ciphertext will consist of one letter repeated. However, there is no ay of deducing what the kcy is (c)The ciphertext will consist of a continuous stream of the letter A. This is easy to detect. However, there will be no way to tell what the key is 25.(a) The ciphertext will correspond to a shifted version of the key word that is repeated many times. The periodic nature of the resulting ciphertext will cauIse Fve to suspect the plaintext is a single letter, while the period of the repeating ciphertext will correspond to the key length (b) Using the fact that no English word of length six is the shift of another English word, simply treat the vigenere key as if it were the plaintext and the single character plaintext as if it were the shift in a shift cipher. Decrypting can be done by trying all possible shifts of the first six characters of the ciphertext One of these shifts will be a word that corresponds to the vigenere key (c) If we use the method of displacement, then shifting by six will have the llighlest nlumber of Latches. In fact, every place will Illatch up. This will be easy to detect. However, shifting the ciphertext by one place will just yield the amount of matches that occur when thc repeated kcy is shifted by onc placc In particular, the key word will most likely not have that many matches with itself when shifted over one place. Similarly for shifts of two, three, four, and five. As a result. other shifts will have a much smaller amount of matches Chapter 3- Exercises 1.(a) Apply the Euclidean algorithm to 17 and 101 101=5·17-16 17=1.16+1. Working back yields=17-16=17-(101-5·17)=(-1):101+6·17. (b)Since-101+6.17-1, we have 617=1(mod 101). Therefore 17-1=6 (mod 101) 2.(a)Apply the Euclidean algorithm to 7 and 30 30=4·7+2 7=3·2+1. Working back wards yields1=7-3.2=7-3.(30-4.7)=13·7+(-3)·30 Therefore 13.7=1 (mod 30), so d= 13 (b) Let c= m'(mod 31) be the ciphertext. Claim: c3= m(mod 31) (mod31) by Fermat. Then c23=15m≡m.Ifm≡0(m0d31), then c≡W Proof: c3=(m)13= m1=(m30)m. If m#0(mod 31)then m 30= 0, S0 C3=03=0=m. Therefore c3=m for all m. Therefore decryption is performed by raising the ciphertext to the 13th power mod 31 3. 3.(a) gcd(12, 236)=4, so divide both sides by 4 to obtain 3c=7 (mod 59). The inverse of 3 mod 59 is 20, so multiply both sides by 20 to obtain = 140=22(mod 59). This yields 22, 81, 140, 199(mod 236) (b)30 divisible by 4= gcd(12, 236), so there 30030 116·257+2 7 1·218+39 218 5·39+23 1.23+16 23 1.16+7 16 2·7+ 7 2·1+0

...展开详情
img
zxcvqwer3339

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐