Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition

Preview (16 of 181 Pages)

100%

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 1 preview image

Loading page ...

SOLUTIONS MANUALforINTRODUCTION TOCRYPTOGRAPHYwith Coding Theory, 2nd editionWade TrappeWireless Information Network Laboratoryand the Electrical and Computer Engineering DepartmentRutgers UniversityLawrence C. WashingtonDepartment of MathematicsUniversity of MarylandAugust 26, 2005

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 2 preview image

Loading page ...

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 3 preview image

Loading page ...

ContentsExercisesChapter 2 - Exercises1Chapter 3 - Exercises6Chapter 4 - Exercises14Chapter 5 - Exercises17Chapter 6 - Exercises19Chapter 7 - Exercises23Chapter 8 - Exercises25Chapter 9 - Exercises27Chapter 10 - Exercises28Chapter 11 - Exercises29Chapter 12 - Exercises31Chapter 13 - Exercises33Chapter 14 - Exercises34Chapter 15 - Exercises36Chapter 16 - Exercises40Chapter 17 - Exercises44Chapter 18 - Exercises46-2

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 4 preview image

Loading page ...

-1Chapter 19 - Exercises51Mathematica problemsChapter 252Chapter 363Chapter 666Chapter 772Chapter 874Chapter 975Chapter 1278Chapter 1679Chapter 1881Maple problemsChapter 284Chapter 398Chapter 6102Chapter 7109Chapter 8112Chapter 9113Chapter 12116Chapter 16118Chapter 18121

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 5 preview image

Loading page ...

0MATLAB problemsChapter 2124Chapter 3147Chapter 6151Chapter 7161Chapter 8164Chapter 9165Chapter 12167Chapter 16169Chapter 18174

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 6 preview image

Loading page ...

Chapter 2 - Exercises1.Among the shifts ofEVIRE, there are two words:arenaandriver. Therefore,Anthony cannot determine where to meet Caesar.2.The inverse of 9 mod 26 is 3.Therefore, the decryption function isx= 3(y−2) = 3y−2 (mod 26). Now simply decrypt letter by letter as follows.U= 20 so decryptUby calculating 3∗20−6 (mod 26) = 2, and so on. Thedecrypted message is ’cat’.3.Changing the plaintext to numbers yields 7, 14, 22, 0, 17, 4, 24, 14, 20.Applying 5x+ 7 to each yields 5·7 + 7 = 42≡16 (mod 26), 5·14 + 7 = 77≡25,etc. Changing back to letters yieldsQZNHOBXZDas the ciphertext.4.Letmx+nbe the encryption function.Sinceh= 7 andN= 13, wehavem·7 +n≡13 (mod 26). Using the second letters yieldsm·0 +n≡14.Thereforen= 14.The first congruence now yields 7m≡ −1 (mod 26).Thisyieldsm= 11. The encryption function is therefore 11x+ 14.5.Let the decryption function bex=ay+b. The first letters tell us that7≡a·2 +b(mod 26). The second letters tell us that 0≡a·17 +b.Subtractingyields 7≡a·(−15)≡11a. Since 11−1≡19 (mod 26), we havea≡19·7≡3(mod 26). The first congruence now tells us that 7≡3·2 +b, sob= 1. Thedecryption function is thereforex≡3y+ 1. Applying this toCRWWZyieldshappyfor the plaintext.6.Letmx+nbe one affine function andax+bbe another. Applying the firstthen the second yields the functiona(mx+n) +b= (am)x+ (an+b), which isan affine function. Therefore, successively encrypting with two affine functionsis the same as encrypting with a single affine function.There is therefore noadvantage of doing double encryption in this case.(Technical point:Sincegcd(a,26) = 1 and gcd(m,26) = 1, it follows that gcd(am,26) = 1, so the affinefunction we obtained is still of the required form.)7.For an affine ciphermx+n(mod 27), we must have gcd(27, m) = 1,and we can always take 1≤m≤27.So we must exclude all multiples of 3,which leaves 18 possibilities form. All 27 values ofnare possible, so we have18·27 = 486 keys. When we work mod 29, all values 1≤m≤28 are allowed,so we have 28·29 = 812 keys.8.(a) In order forαto be valid and lead to a decryption algorithm, we needgcd(α,30) = 1. The possible values forαare 1,7,11,13,17,19,23,29.(b) We need to find twoxsuch that 10x(mod 30) gives the same value.There are many such possible answers, for examplex= 1 andx= 4 will work.1

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 7 preview image

Loading page ...

2This corresponds to the letters ’b’ and ’e’.9.Ifx1=x2+(26/d), thenαx1+β=αx2+β+(α/d)26. Sinced= gcd(α,26)dividesα, the numberα/26 is an integer. Therefore (α/d)26 is a multiple of 26,which means thatαx1+β≡αx2+β(mod 26). Thereforex1andx2encryptto the same ciphertext, so unique decryption is impossible.10.(a) In order to find the most probable key length, we write the ciphertextdown on two strips and shift the second strip by varying amounts.The shiftwith the most matches is the most likely key length.As an example, look atthe shift by 1:BABABAAABABABABAAABA**This has a total of 2 matches. A shift by 2 has 6 matches, while a shift by3 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 everyodd letter to get BBBAB, and then every even letter to get AAAAA. Using afrequency count on each of these yields that a shift of 0 is the most likely scenariofor the first character of the Vigenere key, while a shift of 1 is the most likelycase for the second character of the key. Thus, the key isAB. Decrypting eachsubsequence yields BBBAB and BBBBB. Combining them gives the originalplaintext BBBBBBABBB.11.If we look at shifts of 1, 2, and 3 we have 2, 3, and 1 matches.Thiscertainly rules out 3 as the key length, but the key length may be 1 or 2.In the ciphertext, there are 3A’s, 5B’s, and 2C’s. If the key length were 1,this 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 areACABA.There are 3A’s, 1B, and 1C. These frequencies of .6, .2, .2 is a close matchto .7, .2, .1 shifted by 0 positions. The first element of the key is probablyA.The second, fourth, ... letters of the ciphertext areBBBBC. There are 0A’s, 4B’s, and 1C. These frequencies .0, .8, .2 and match .7, .2, .1 with a shift by 1.Therefore the second key element is probablyB.Since the results for length 2 match the frequencies most closely, we concludethat the key is probablyAB.12.Since the entries ofAiare the same as those inA0( shifted a few places)the two vectors have the same length. ThereforeA0·Ai=|A0||Ai|cosθ=|A0|2cosθ.Note that cosθ≤1, and equals 1 exactly whenθ= 0. Butθ= 0 exactly whenthe two vectors are equal. So we see that the largest value of the cosine is whenA0=Ai. Therefore the largest value of the dot product is wheni= 0.13.ChangeYIFZMAto pairs of numbers: (24, 8), (5, 25), (12, 0). Invertthe matrix to getN=(3−13−29)≡(313249)(mod 26).Calculate(24,8)N= (4,20), (5,25)N= (17,4), (12,0)N= (10,0).Change back toletters:eureka.

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 8 preview image

Loading page ...

314. Suppose the encryption matrixMis(abcd). Change the ciphertextto 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), etc.We’ll use (11,21)M≡(25,23) and (4,3)M≡(3,18) to get equations fora, b, c, d, which are mosteasily put in matrix form:(112143) (abcd)≡(2523318). The inverseof(112143)mod 26 is(352211).Multiply by this matrix to obtainM=(abcd)≡(123112).15.Suppose the matrix has the formM=(αβγδ)Then the encryption of a plaintextx= (b, a) = (1,0) yields (α, β).We knowthis corresponds to HC, and henceα= 7 andβ= 2.The second piece ofinformation is that zz encrypts to GT. This corresponds to a plaintext of (25,25)or equivalently (−1,−1). Using this yields−α−γ= 6 and−β−δ= 19. Thus,γ= 13 andδ= 5.16.(a) The plaintext is (3,14), (13, 19). The ciphertext is (4,11), (13, 8).We have(3141319)M≡(411138). The inverse of(3141319)mod 26is(1912133). Multiplying by this inverse yieldsM≡(1091323).(b) We have(3141319)M≡(4111310). Proceeding as in part (a), wefindM≡(10191319).17.Suppose the plaintext is of the form (x, y), then the ciphertext is ofthe form (x+ 3y,2x+ 4y) (mod 26).There will be many possible plaintextsthat will map to the same ciphertext.We will try to make plaintexts thatyield a ciphertext of the form (0,∗).To do so, we will have the relationshipx=−3y(mod 26). Now we need to find twoyvalues that produce the same2(−3y) + 4y=−2y(mod 26).If we takey= 4 andy= 17 then we get thesame value for−2y(mod 26). Thus, (14,4) and (1,17) are two plaintexts thatmap to (0,18).18.We will need to use three different plaintexts.First, choose (x, y) =(0,0). This will produce a ciphertext that is precisely (e, f). Next, try (x, y) =(1,0).This will produce a ciphertext that is (a, b) + (e, f).We may subtractoff (e, f) to find (a, b).Finally, use (x, y) = (0,1) to get (c, d) + (e, f) as theciphertext. We may subtract off (e, f) to get (c, d).

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 9 preview image

Loading page ...

419.As is Section 2.11, set up the matrix equation001011111c0c1c2≡110.This yieldsc0= 1, c1= 0, c2= 1, so the recurrence iskn+3≡kn+kn+2. Thenext 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(1001) (c0c1)≡(10). This yieldsc0= 1, c1= 0, sokn+2≡kn.21.Set up the matrix equation(xnxn+1xn+1xn+2) (c0c1)=(xn+2xn+3).Using the values provided, we obtain(1110) (c0c1)=(02).The inverse of the matrix can be found to be−(0−1−11)=(0112)(mod 3)Multiplying both sides of by the inverse matrix, yieldsc0= 2 andc1= 1.22.Usex1,x2andx3to solve forc1by obtainingc1+ 2≡1 (mod 5). Thus,c1= 4. Next, usex2,x3andx4to solve forc0. We getc0+c1+ 2 (mod 5)≡0,and hencec0= 4.23.The number of seconds in 120 years is60×60×24×365×120≈3.8×109.Therefore you need to count 10100/(3.8×109)≈2.6×1090 numbers per second!24.(a) The ciphertext will consist of one letter repeated. However, there isno way of deducing what the key is.(b) The ciphertext will consist of one letter repeated. However, there is noway of deducing what the key is.(c) The ciphertext will consist of a continuous stream of the letterA. Thisis 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 wordthat is repeated many times.The periodic nature of the resulting ciphertextwill cause Eve to suspect the plaintext is a single letter, while the period of therepeating ciphertext will correspond to the key length.(b) Using the fact that no English word of length six is the shift of anotherEnglish word, simply treat the Vigenere key as if it were the plaintext and the

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 10 preview image

Loading page ...

5single character plaintext as if it were the shift in a shift cipher. Decrypting canbe 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 thehighest number of matches.In fact, every place will match up.This will beeasy to detect. However, shifting the ciphertext by one place will just yield theamount of matches that occur when the repeated key is shifted by one place.In particular, the key word will most likely not have that many matches withitself when shifted over one place. Similarly for shifts of two, three, four, andfive. As a result, other shifts will have a much smaller amount of matches.

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 11 preview image

Loading page ...

Chapter 3 - Exercises1.(a) Apply the Euclidean algorithm to 17 and 101:101 = 5·17 + 1617 = 1·16 + 1.Working back yields 1 = 17−16 = 17−(101−5·17) = (−1)·101 + 6·17.(b) Since−101+6·17 = 1, we have 6·17≡1 (mod 101). Therefore 17−1≡6(mod 101).2.(a) Apply the Euclidean algorithm to 7 and 30:30 = 4·7 + 27 = 3·2 + 1.Working backwards yields 1 = 7−3·2 = 7−3·(30−4·7) = 13·7 + (−3)·30.Therefore 13·7≡1 (mod 30), sod= 13.(b) Letc≡m7(mod 31) be the ciphertext.Claim:c13≡m(mod 31).Proof:c13≡(m7)13≡m91≡(m30)3m.Ifm6≡0 (mod 31) thenm30≡1(mod 31) by Fermat. Thenc13≡13m≡m. Ifm≡0 (mod 31), thenc≡m7≡0, soc13≡013≡0≡m. Thereforec13≡mfor allm. Therefore decryption isperformed 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 3x≡7(mod 59). The inverse of 3 mod 59 is 20, so multiply both sides by 20 to obtainx≡140≡22 (mod 59). This yieldsx≡22,81,140,199 (mod 236).(b) 30 is not divisible by 4 = gcd(12,236), so there are no solutions.4.(a)30030=116·257 + 218257=1·218 + 39218=5·39 + 2339=1·23 + 1623=1·16 + 716=2·7 + 27=3·2 + 12=2·1 + 0.6

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 12 preview image

Loading page ...

7Therefore, gcd(30030,257) = 1.(b) If 257 is composite, it is divisible by a primep≤ √257 = 16.03. . ..Theprimes satisfying this are exactly the prime factors of 30030. Since the gcd is 1,none of them divide 257, so 257 is prime.5.(a)4883=1·4369 + 5144369=8 ˙514 + 257514=2·257 + 0.Therefore, the gcd is 257.(b) We know that both numbers have 257 as a factor. This yields 4883 = 257·19and 4369 = 257·17.6.(a) The first two steps of the Euclidean algorithm areFn=1·Fn−1+Fn−2Fn−1=1·Fn−2+Fn−3.It continues in this way until2=2·1 + 11=1·1 + 0.Therefore, the gcd is 1.(b)11111111=1000·11111 + 11111111=100·111 + 11111=10·11 + 111 = 11·1 + 0.Therefore, the gcd is 1.(c) The first step of the Euclidean algorithm isa= 10Fn−2·b+c,wherecconsists ofFn−2repeated 1’s. Continuing in this way, in each step wedivideFj−1repeated 1’s intoFjrepeated 1’s and get a remainder consisting ofFj−2repeated 1’s.Eventually, we get down to the computations of part (b),and then obtain that the gcd is 1.7.(a) Ifab≡0 (modp), thenp|ab. By the Corollary on page 64, sincepisprime, eitherp|aorp|b. Therefore, eithera≡0 (modp) orb≡0 (modp).(b) We follow the proof of the Corollary on page 64.Since gcd(a, n) = 1,there are integersx, ysuch thatax+ny= 1. Multiply bybto obtainabx+bny=b. Sincen|ab, both terms on the left are multiples ofn. Thereforen|b.8.(x+1)(x−1)≡0 (modp) implies, by 3(a), that eitherx+1≡0 (modp)orx−1≡0 (modp). Thereforex≡ ±1 (modp).

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 13 preview image

Loading page ...

89.One solution is to look at the numbers congruent to 3 (mod 10) untilwe find one that is 2 (mod 7): 3, 13≡6, 23≡2 (mod 7).Thereforex≡23(mod 70).10.Suppose there arexpeople. Thenx≡1 (mod 3), x≡2 (mod 4), x≡3(mod 5).The last two congruences combine tox≡18 (mod 20).List thenumbers that are 18 (mod 20) until you find one that is 1 (mod 3). The answerisx≡58 (mod 60).11.Ifa6≡0 (modp), then Fermat says thatap−1≡1 (modp). Multiplybyato getap≡a(modp). Ifa≡0 (modp), thenap≡0p≡0≡a(mod ).Thereforeap≡a(modp) for alla.12.By Fermat’s theorem, 2100≡1 (mod 101). Therefore, 210203≡(2100)10223≡110223≡8. Therefore, the remainder is 8.13.“Last two digits” means we work mod 100. Sinceφ(100) = 40, Euler’stheorem says that 12340≡1 (mod 100). Therefore, 123562≡(12340)141232≡1232≡232≡529≡29. The last two digits are 29.14.(a) 77≡(−1)7≡ −1≡3 (mod 4).(b) 77= 3 + 4kfor somek. By Euler’s theorem, 74≡1 (mod 10). Therefore,777= 73(74)k≡73·1k≡343≡3(mod 10).The last digit is 3.15.(a)φ(1) = 1, φ(2) = 1, φ(5) = 4, φ(10) = 4. The sum is 10.(b)φ(1) = 1, φ(2) = 1, φ(3)2, φ(4) = 2, φ(6) = 2, φ(12) = 4. The sum is 12.(c) The sum ofφ(d), for all of the divisorsdofn, equalsn.16.(a) Sincep∤a, Fermat says thatap−1≡1 (modp). Forp= 7, we havea6≡1 (mod 7), soa1728≡(a6)288≡1288≡1 (mod 7). Since 1728 = 12·144and 1728 = 18·96, a similar argument works forp= 13 and forp= 19.(b) Ifp∤a, then multiply the result of (a) byato geta1729≡a(modp). Ifp|a, thena1729andaare both 0 (modp), soa1729≡ain this case, too.(c) Fix a numbera. The Chinese Remainder Theorem says thatx≡a1729(mod 7), x≡a1729 (mod 13), x≡a1729(mod 19) has a unique solutionx(mod 1729), since 1729 = 7·13·19.We know two such solutions:x=a(from part (b) andx=a1729 (trivially). Sincexis unique mod 1729, we musthavea≡a1729(mod 1729).17.(a) The powers of 2 mod 11 are 2,4,8,5,10,9,7,3,6,1.This gives allnonzero congruence classes mod 11, so 2 is a primitive root mod 11.(b) The inverse of 3 (mod 10) is 7. We obtain87≡(23)7≡221≡(210·21≡1·2≡2(mod 11).Therefore,x= 7.(c) This can be done directly, but here is another way. Ifc6≡0 (mod 11), thenc≡2jfor somej. Therefore,c≡(87)j≡87j(mod 11), socis a power of 8.(d) Writexy= 1 + (p−1)k. Thenhx≡(gy)x≡g·(gp−1)k≡g·1k≡g(modp).

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 14 preview image

Loading page ...

9(e) Letcbe nonzero modp. Thenc≡gj(modp) for somej, soc≡(hx)j≡hxj(modp). Since every nonzero congruence class is a power ofh, we have thathis a primitive root modp.18.(a) The determinant is 1·1−1·6 =−5≡21 (mod 26). The inverse ofthe determinant is 5 (mod 26). The inverse of the matrix is therefore121(1−1−61)≡5(1−1−61)≡(521225).(b) The determinant is 1−b.The matrix is invertible mod 26 exactly whengcd(1−b,26) = 1.This happens when 1−bis odd and not 0 mod 13, sob≡0,2,4,6,8,10,12,16,18,20,22,24 (mod 26).19.The determinant is 9−35 =−26. This is divisible by 2 and by 13, sothese are the two primes for which the matrix is not invertible modp.20.(a) We knowaφ(n)≡1 (modn), by Euler. Sinceris smallest,r≤φ(n).(b) Sincear≡1, we haveam≡(ar)k≡1k≡1 (modn).(c) By (b),aqr≡1. Therefore, 1≡(by assumption)at≡aqras≡1·as≡as.(d) Sinceas≡1 andris the smallest positive integer withar≡1, we musthaves= 0. Thereforet=qr, sor|t.(e) By Euler,aφ(n)≡1 (modn). From part (d) witht=φ(n), we obtainordn(a)|φ(n).21.(a) Ifrdivides 600, thenr= 2a·3b·5cwitha≤3, b≤1, c≤2.Ifr <600, then we cannot havea= 3, b= 1, c= 2. Ifa≤2, thenr|22·3·52= 300.Ifb= 0 thenr|23·52= 200. Ifc≤1 thenr|23·3·5 = 120.(b) From 9(e), we know that ord601(7)|600.If ord601(7)<600, then itdivides 300, 200, or 120, by (a).(c) Suppose ord601(7)|300.By 9(b), we must have 7300≡1 (mod 601),which is not the case. Therefore, ord601(7)∤300. Similarly, ord601(7)∤200 andord601(7)∤120.(d) From (b) and (c), we cannot have ord601(7)<600. Since ord601(7)≤600from 9(a), we must have ord601(7) = 600. Therefore the numbers 7j(mod 601),forj= 0,1, . . . ,599 are distinct, so there are 600 of them. This implies that 7is a primitive root mod 601.(e) Calculateg(p−1)/qi(modp) fori= 1,2, . . . , s.If each of these is6≡1(modp), thengis a primitive root modp. (Of course, perhaps we should checkfirst thatp∤g.)22.(a) We have 316k≡2k6≡1 (mod 65537) and 332k≡232≡1 (mod 65537).Therefore 65536∤16kand 65536|32k. Write 32k= 65536ℓfor someℓ. Divideby 32 to obtaink= 2048ℓ, so 211= 2048|k.If 212= 4096|k, then 16kis amultiple of 16·4096 = 65536, which we showed doesn’t happen. Thereforekisa multiple of 2048, but is not a multiple of 4096.(b) From (a), we see thatkis an odd multiple of 2048. We also know that0≤k <65536, since every nonzero number mod 65537 can be written as a powerof 3 with exponent in this range. There are 65536/2048=32 multiples of 2048 inthis range. Of these, 16 are multiples of 4096. The remaining 16 are possibilitiesfork. We now calculate 32048m(mod 65537) form= 1,3,5,· · ·. We find (withthe help of a computer) thatm= 27 works. Sok= 2048∗27 = 55296.

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 15 preview image

Loading page ...

1023.(a) We claim that after thekth step 2, we haverk≡yb1b2···bk(modn).This is easily seen to be the case fork= 1. Assume it is true fork−1. We’llshow it’s true fork.We havesk≡r2k−1≡y2·b1b2···bk−1.Thenrk≡skybk≡r2kybk≡y2·b1...bk−1+bk≡yb1···bk−1bk. Therefore, whenk=wwe haverw≡yx,as desired.(b) Writex=b1. . . bwin binary as in (a). We assumeb1= 1. The algorithmis easily seen to work whenx= 0, so we may assumew≥1.We claim thatafter step 2,a=b1. . . bw−k,b≡ybw−k+1...bwandc≡y2kfor some value ofk.When we start, we havek= 0.Suppose we arrive at step 2 witha=b1. . . bw−k,b≡ybw−k+1...bw, andc≡y2k.Ifais odd, then the output of step 2 is the same as the input,hence of the desired form.Ifais even, thenbw−k= 0.We obtain the newa=b1. . . bw−k−1,b≡ybw−kbw−k+1...bw(we may include the extra bit at thebeginning since it is 0), andc≡y2k+1. Therefore the output hasa, b, cin thedesired form withk+ 1 in place ofk.Now let’s look at what happens in step 3.The output of step 2 is of theforma=b1. . . bw−j,b≡ybw−j+1...bwandc≡y2jfor some value ofj.Ifaiseven, step 3 does nothing, so the output still has the desired form. Ifais odd,then the last bitbw−jofais 1. The newaisa=b1. . . bw−j−10. Also, the newbisybw−jbw−j+1...bw·y2j≡y1bw−jbw−j+1...bw≡ybw−jbw−j+1...bw. The newcis stilly2j.If the newa= 0, thenj=w−1, sob≡yx. Therefore step 5 outputsyx, asdesired. Otherwise, step 4 sends us to step 2, which outputsa=b1. . . bw−j−1,b≡ybw−jbw−j+1...bw, andc≡y2j+1. This is of the desired form withk=j+ 1.Therefore, the output of step 2 always has the desired form, as claimed.Sinceagets smaller at each application of steps 2 and 3, eventuallya= 0and the algorithm stops. As pointed out above, the output of step 5 is thenyx(modn).24.Sincezj≡0 (modmi) whenj6=i, we havex≡aiyizi≡aiz−1izi≡ai(modmi).25.(a) Solvex2≡133 (mod 11) to obtainx≡ ±1 (mod 11).Now solvex2≡133 (mod 13) to obtainx≡ ±4 (mod 13). There are four ways to combinethese via the Chinese Remainder Theorem:x≡43,56,87,100 (mod 143).(b) This reduces tox2≡77 (mod 11) andx2≡77 (mod 13). The solutionssatisfyx≡0 (mod 11) andx≡ ±5 (mod 13).These combine to yieldx≡44,99 (mod 143).26.Supposex2≡ −1 (modp). Raise both sides to the (p−1)/2 power toobtainxp−1≡(−1)(p−1)/2(modp). By Fermat,xp−1≡1. Sincep≡3]pmod4,the exponent (p−1)/2 is odd. Therefore (−1)(p−1)/2=−1. This yields 1≡ −1(modp), which is a contradiction. Thereforexcannot exist.27.(a) There are at most 4 square roots ofx(modn). Therefore, severalrandom selections of these square roots should include the meaningful messagem.(b) Being able to find square roots modnis computationally equivalent tofactoringn, which is presumed to be hard.

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition - Page 16 preview image

Loading page ...

11(c) Eve chooses a random numbermand computesx≡m2(modn). Shegivesxto the machine, which outputs a square rootm′ofx. If gcd(m, n) = 1,there are four possiblem′, namelym,−m, and two others. After a few tries,Eve should obtainm′withm′6≡ ±m(modn). Sincem2≡x≡m′2 (modn),a nontrivial factor ofnis given by gcd(m−m′, n).28.(a) Sincer1=a−bq1andd|a, b, we haved|r1. Sincer2=b−q2r1andd|b, r1, we haved|r2.(b) Supposed|r1, . . . , rj.Sincerj+1=rj−1−qj+1rjandd|rj−1, rj, wehaved|rj+1. By induction, we haved|rifor alli.(c) Sincerk−1=qk+1rk, we haverk|rk−1. Assumerk|rk−ifori= 1,2, . . . , j.Sincerk−j−1=qk−j+1rk−j+rk−j+1andrk|rk−j, rk−j+1by assumption, wehaverk|rk−j−1. By induction,rk|rifor alli.(d) Sinceb=q2r1+r2andrk|r1, r2, we haverk|b. Sincea=q1b+r1andrk|a, r1, we haver|a.(e) Sinced|rkfor each common divisord, we haverk≥dfor all commondivisorsd. Sincerkis a common divisor, it is the largest.29.(a)(123401)=(401123)=(32123)=(2123)5=−1.Therefore, there is no solution.(b)(43179)=−(17943)=−(743)=(437)=(143)= 1.Therefore, there is a solution.(c)(109365537)=(655371093)=(21093) (5251093)=−(43525)=−(943)=−1.Therefore, there is no solution.30.(a) Ifa≡b2(modn), then(an)=(bn)2= (±1)2= 1.Therefore, if(an)=−1, thenacannot be a square modn.(b)(335)=−(353)=−(23)= 1.(c) Since 3 is not a square mod 5, it cannot be a square mod 35.31.(215)= 1, but 27≡8 (mod 15).32.(a)(365537)=(655373)=(23)=−1.

Preview Mode

This document has 181 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

Solution Manual for Introduction to Cryptography with Coding Theory, 3rd Edition

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Company

Explore

Study Tools