Exam (elaborations) TEST BANK FOR An Introduction to Mathematical Cryptography 2nd Edition By Jeffrey Hoffstein, Jill Pipher, Joseph H. Silvermana (Solution Manual)

Exam (elaborations) TEST BANK FOR An Introduction to Mathematical Cryptography 2nd Edition By Jeffrey Hoffstein, Jill Pipher, Joseph H. Silvermana (Solution Manual) An Introduction to Mathematical Cryptography Solution Manual Je®rey Ho®stein, Jill Pipher, Joseph H. Silverman °c 2008 by J. Ho®stein, J. Pipher, J.H. Silverman July 31, 2008 Chapter 1 An Introduction to Cryptography Exercises for Chapter 1 Section. Simple substitution ciphers 1.1. Build a cipher wheel as illustrated in Figure 1.1, but with an inner wheel that rotates, and use it to complete the following tasks. (For your convenience, there is a cipher wheel that you can print and cut out at . edu/~jhs/MathCrypto/CipherW.) (a) Encrypt the following plaintext using a rotation of 11 clockwise. A page of history is worth a volume of logic." (b) Decrypt the following message, which was encrypted with a rotation of 7 clockwise. AOLYLHYLUVZLJYLAZILAALYAOHUAOLZLJYLALZAOHALCLYFIVKFNBLZZLZ (c) Decrypt the following message, which was encrypted by rotating 1 clock- wise for the ¯rst letter, then 2 clockwise for the second letter, etc. XJHRFTNZHMZGAHIUETXZJNBWNUTRHEPOMDNBJMAUGORFAOIZOCC Solution to Exercise 1.1. (a) apageofhistoryisworthavolumeoflogic LALRPZQSTDEZCJTDHZCESLGZWFXPZQWZRTN This quote is in a court decision of Oliver Wendell Holmes, Jr. (1921). (b) therearenosecretsbetterthanthesecretsthateverybodyguesses AOLYLHYLUVZLJYLAZILAALYAOHUAOLZLJYLAZAOHALCLYFIVKFNBLZZLZ There are no secrets better than the secrets that everybody guesses. This quote is due to George Bernard Shaw, Mrs. Warren's Profession (1893) 1 2 Exercises for Chapter 1 (c) whenangrycounttenbeforeyouspeakifveryangryanhundred XJHRFTNZHMZGAHIUETXZJNBWNUTRHEPOMDNBJMAUGORFAOIZOCC When angry, count ten before you speak; if very angry, an hundred. This quote is due to Thomas Je®erson, A Decalogue of Canons. . . (1825). 1.2. Decrypt each of the following Caesar encryptions by trying the various possible shifts until you obtain readable text. (a) LWKLQNWKDWLVKDOOQHYHUVHHDELOOERDUGORYHOBDVDWUHH (b) UXENRBWXCUXENFQRLQJUCNABFQNWRCJUCNAJCRXWORWMB (c) BGUTBMBGZTFHNLXMKTIPBMAVAXXLXTEPTRLEXTOXKHHFYHKMAXFHNLX Solution to Exercise 1.2. (a) ithinkthatishallneverseeabillboardlovelyasatree LWKLQNWKDWLVKDOOQHYHUVHHDELOOERDUGORYHOBDVDWUHH I think that I shall never see, a billboard lovely as a tree. This quote is due to Ogden Nash, Many Long Years Ago (1945), Song of the Open Road. (b) loveisnotlovewhichalterswhenitalterationfinds UXENRBWXCUXENFQRLQJUCNABFQNWRCJUCNAJCRXWORWMB Love is not love which alters when it alteration ¯nds. This quote is due to William Shakespeare, Sonnet 116. (c) inbaitingamousetrapwithcheesealwaysleaveroomforthemouse BGUTBMBGZTFHNLXMKTIPBMAVAXXLXTEPTRLEXTOXKHHFYHKMAXFHNLX In baiting a mousetrap with cheese, always leave room for the mouse. This quote is due to H.H. Munro (Saki), The Square Egg (1924). 1.3. For this exercise, use the simple substitution table given in Table 1.11. (a) Encrypt the plaintext message The gold is hidden in the garden. (b) Make a decryption table, that is, make a table in which the ciphertext alphabet is in order from A to Z and the plaintext alphabet is mixed up. (c) Use your decryption table from (b) to decrypt the following message. IBXLX JVXIZ SLLDE VAQLL DEVAU QLB Solution to Exercise 1.3. (a) Exercises for Chapter 1 3 a b c d e f g h i j k l m n o p q r s t u v w x y z S C J A X U F B Q K T P R W E Z H V L I G Y D N M O Table 1.1: Simple substitution encryption table for exercise 1.3 t h e g o l d i s h i d d e n i n t h e g a r d e n I B X F E P A Q L B Q A A X W Q W I B X F S V A X W Breaking it into ¯ve letter blocks gives the ciphertext IBXFE PAQLB QAAXW QWIBX FSVAX W (b) d h b w o g u q t c j s y x z l i m a k f r n e v p A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (c) t h e s e c r e t p a s s w o r d i s s w o r d f i s h I B X L X J V X I Z S L L D E V A Q L L D E V A U Q L B Putting in word breaks gives the plaintext The secret password is swordfish. 1.4. Each of the following messages has been encrypted using a simple sub- stitution cipher. Decrypt them. For your convenience, we have given you a frequency table and a list of the most common bigrams that appear in the ciphertext. (If you do not want to recopy the ciphertexts by hand, they can be downloaded or printed from the web site listed in the preface.) (a) A Piratical Treasure" JNRZR BNIGI BJRGZ IZLQR OTDNJ GRIHT USDKR ZZWLG OIBTM NRGJN IJTZJ LZISJ NRSBL QVRSI ORIQT QDEKJ JNRQW GLOFN IJTZX QLFQL WBIMJ ITQXT HHTBL KUHQL JZKMM LZRNT OBIMI EURLW BLQZJ GKBJT QDIQS LWJNR OLGRI EZJGK ZRBGS MJLDG IMNZT OIHRK MOSOT QHIJL QBRJN IJJNT ZFIZL WIZTO MURZM RBTRZ ZKBNN LFRVR GIZFL KUHIM MRIGJ LJNRB GKHRT QJRUU RBJLW JNRZI TULGI EZLUK JRUST QZLUK EURFT JNLKJ JNRXR S The ciphertext contains 316 letters. Here is a frequency table: R J I L Z T N Q B G K U M O S H W F E D X V Freq 8 7 6 5 5 3 2 4 Exercises for Chapter 1 The most frequent bigrams are: JN (11 times), NR (8 times), TQ (6 times), and LW, RB, RZ, and JL (5 times each). (b) A Botanical Code" KZRNK GJKIP ZBOOB XLCRG BXFAU GJBNG RIXRU XAFGJ BXRME MNKNG BURIX KJRXR SBUER ISATB UIBNN RTBUM NBIGK EBIGR OCUBR GLUBN JBGRL SJGLN GJBOR ISLRS BAFFO AZBUN RFAUS AGGBI NGLXM IAZRX RMNVL GEANG CJRUE KISRM BOOAZ GLOKW FAUKI NGRIC BEBRI NJAWB OBNNO ATBZJ KOBRC JKIRR NGBUE BRINK XKBAF QBROA LNMRG MALUF BBG The ciphertext contains 253 letters. Here is a frequency table: B R G N A I U K O J L X M F S E Z C T W P V Q Freq 10 10 8 8 7 7 6 5 3 2 1 1 1 The most frequent bigrams are: NG and RI (7 times each), BU (6 times), and BR (5 times). (c) In order to make this one a bit more challenging, we have removed all occurrences of the word the" from the plaintext. A Brilliant Detective" GSZES GNUBE SZGUG SNKGX CSUUE QNZOQ EOVJN VXKNG XGAHS AWSZZ BOVUE SIXCQ NQESX NGEUG AHZQA QHNSP CIPQA OIDLV JXGAK CGJCG SASUB FVQAV CIAWN VWOVP SNSXV JGPCV NODIX GJQAE VOOXC SXXCG OGOVA XGNVU BAVKX QZVQD LVJXQ EXCQO VKCQG AMVAX VWXCG OOBOX VZCSO SPPSN VAXUB DVVAX QJQAJ VSUXC SXXCV OVJCS NSJXV NOJQA MVBSZ VOOSH VSAWX QHGMV GWVSX CSXXC VBSNV ZVNVN SAWQZ ORVXJ CVOQE JCGUW NVA The ciphertext contains 313 letters. Here is a frequency table: V S X G A O Q C N J U Z E W B P I H K D M L R F Freq 6 5 5 5 4 3 2 1 1 The most frequent bigrams are: XC (10 times), NV (7 times), and CS, OV, QA, and SX (6 times each). Solution to Exercise 1.4. (a) The message was encrypted using the table: a b c d e f g h i j k l m n o p q r s t u v w x y z I E B H R W D N T P X U O Q L M A G Z J K V F C S Y The plaintext reads: These characters, as one might readily guess, form a cipher|that is to say, they convey a meaning; but then, from what is known of Captain Kidd, I could not suppose him capable of constructing any of the more abstruse cryptographs. I made up my mind, at once, that this was of a simple species| such, however, as would appear, to the crude intellect of the sailor, absolutely insoluble without the key." (The Gold-Bug, 1843, Edgar Allan Poe) (b) The message was encrypted using the table: Exercises for Chapter 1 5 a b c d e f g h i j k l m n o p q r s t u v w x y z R V C X B F S J K Q P O E I A W D U N G L T Z Y M H The plaintext reads: I was, I think, well educated for the standard of the day. My sister and I had a German governess. A very sentimental creature. She taught us the language of °owers|a forgotten study nowadays, but most charming. A yellow tulip, for instance, means Hopeless Love, while a China Aster means I die of Jealousy at your feet." (The Four Suspects, 1933, Agatha Christie) (c) The message was encrypted using the table: a b c d e f g h i j k l m n o p q r s t u v w x y z S D J W V E H C G L R U Z A Q P T N O X I M K Y B F The plaintext reads (all occurrences of the word the" were omitted from the text before encryption): I am fairly familiar with all forms of secret writing, and am myself (the) author of a tri°ing monograph upon (the) subject, in which I analyze one hundred separate ciphers, but I confess that this is entirely new to me. (The) object of those who invented this system has apparently been to conceal that these characters convey a message, and to give (the) idea that they are (the) mere random sketches of children. (The Adventure of the Dancing Men, 1903, Sir Arthur Conan Doyle) 1.5. Suppose that you have an alphabet of 26 letters. (a) How many possible simple substitution ciphers are there? (b) A letter in the alphabet is said to be ¯xed if the encryption of the letter is the letter itself. How many simple substitution ciphers are there that leave: (i) no letters ¯xed? (ii) at least one letter ¯xed? (iii) exactly one letter ¯xed? (iv) at least two letters ¯xed? (Part (b) is quite challenging! You might try doing the problem ¯rst with an alphabet of four or ¯ve letters to get an idea of what is going on.) Solution to Exercise 1.5. (a) We can assign A to any of 26 letters, then B to any of the remaining 25 letters, etc. So there are 26! = di®erent simple substitution ciphers. (b) Let S(n; k) denote the number of permutations of n elements that ¯x at least k elements. You might guess that since there are ¡n k ¢ ways to choose k elements to ¯x and (n ¡ k)! permutations of the remaining n ¡ k elements, S(n; k) = µ n k ¶ (n ¡ k)! á Incorrect Formula: (1.1) 6 Exercises for Chapter 1 But this overcounts because any permutation ¯xing more than n ¡ k ele- ments will be counted multiple times. We can, however, get a useful formula out of this mistake by modifying it somewhat. If we let R(n; k) denote the number of permutations of n elements that ¯x exactly k elements, and !(n¡k) (the subfactorial of (n ¡ k)) denote the number of permutations of n ¡ k ele- ments that ¯x no elements (such permutations are called derangements), then the following equation holds: R(n; k) = µ n k ¶ !(n ¡ k): (1.2) How can we compute !n? One way would be to consider cycle decompo- sitions of permutations of n elements, since any derangement of n elements decomposes into a disjoint union of cycles, with the size of the cycles summing to n. This, however, is only feasible for relatively small n. It would also be possible to formulate a recurrence relation, but a method following that tack would take several steps. We'll instead use the following fact: !n = n! ¡ #fpermutations that ¯x at least 1 elementg: (1.3) Now if we notice that #fpermutations that ¯x at least 1 elementg = #fpermutations that ¯x element 1g [fpermutations that ¯x element 2g [ ¢ ¢ ¢ [ fpermutations that ¯x element ng (1.4) and use an analogue of the following formula in probability (often called the inclusion{exclusion principle): P(E1 [ E2 [ ¢ ¢ ¢ [ En) = Xn i=1 P(Ei) + X i1i2 P(Ei1 Ei2 ) + : : : +(¡1)r+1 X i1i2¢¢¢ir P(Ei1 Ei2 Eir ) + : : : +(¡1)n+1P(E1 E2 ¢ ¢ ¢ En) (1.5) we see that !n = Xn i=1 #fpermutations that ¯x element ig ¡ Xn i1i2 #fpermutations that ¯x elements i1 and i2g + : : : +(¡1)r+1 X i1i2¢¢¢ir #fpermutations that ¯x elements i1, i2, . . . irg + : : : +(¡1)n+1#fpermutations that ¯x everythingg: (1.6) Exercises for Chapter 1 7 Given k elements, the number of permutations ¯xing them is (n ¡ k)! regardless of which k elements you ¯x, and there are ¡n k ¢ ways to choose k elements to ¯x. So the above equation becomes !n = µ n 1 ¶ (n ¡ 1)! ¡ µ n 2 ¶ (n ¡ 2)! + : : : +(¡1)k+1 µ n k ¶ (n ¡ k)! + ¢ ¢ ¢ + (¡1)n+1(n ¡ n)!: (1.7) Now noticing that µ n k ¶ (n ¡ k)! = n! (n ¡ k)!k! (n ¡ k)! = n! k! ; (1.8) the formula (??) becomes !n = n! Xn k=0 (¡1)k k! : (1.9) This sum is somewhat cumbersome to compute when n is large, but notice that it resembles the series for e¡1. Thus Xn k=0 (¡1)k k! = e¡1 ¡ 1X k=n+1 (¡1)k k! : Since the series is alternating and the terms are decreasing in magnitude, each term is larger than the sum of the remaining terms (alternating series test). So ¯¯¯ Xn k=0 (¡1)k k! ¡ e¡1 ¯¯¯ 1 (n + 1)! : Multiplying by n! and using (??) yields ¯¯¯ !n ¡ n! e ¯¯¯ 1 n + 1: Hence !n is the closest integer to n!=e. Now that we're able to compute !n, we can compute R(n; k) = µ n k ¶ !(n ¡ k) = µ n k ¶¹ (n ¡ k)! e ¼ ; and then we can compute S(n; k) using S(n; k) = Xn j=k R(n; j) = n! ¡ kX¡1 j=0 R(n; j): (1.10) 8 Exercises for Chapter 1 (b-i) No letters ¯xed is R(n; 0) =!n is the nth derangement number. For n = 26 we get R(26; 0) =!26 = b26!=ee = b:964e = : (b-ii) At least one letter ¯xed is n! minus no letters ¯xed, so S(n; 1) = n! ¡ R(n; 0) = n!¡!n = n! ¡ bn!=ee: Hence S(26; 1) = 26! ¡ b26!=ee = : (b-iii) Exactly 1 letter ¯xed is R(n; 1) = n¢!(n ¡ 1) = n ¹ (n ¡ 1)! e ¼ ; so R(26; 1) = 26 ¹ 25! e ¼ = : (b-iv) At least two letters ¯xed is n! minus zero or one letters ¯xed, so S(n; 1) = n! ¡ R(n; 0) ¡ R(1; 0) = n!¡!n ¡ n¢!(n ¡ 1) = n! ¡ bn!=ee ¡ nb(n ¡ 1)!=ee: Hence S(26; 1) = 26! ¡ b26!=ee ¡ 26 ¢ b25!=ee = : Section. Divisibility and greatest common divisors 1.6. Let a; b; c 2 Z. Use the de¯nition of divisibility to directly prove the following properties of divisibility. (This is Proposition 1.4.) (a) If a j b and b j c, then a j c. (b) If a j b and b j a, then a = §b. (c) If a j b and a j c, then a j (b + c) and a j (b ¡ c). Solution to Exercise 1.6. (a) By de¯nition we have b = aA and c = bB for some integers A and B. Multiplying gives bc = aAbB, and dividing by b yields c = aAB. (Note that b is nonzero, since zero is not allowed to divide anything.) Hence c is an integer multiple of a, so a j c. (b) By de¯nition we have b = aA and a = bB for some integers A and B. Multiplying gives ab = aAbB, and dividing by ab yields 1 = AB. (Note that a Exercises for Chapter 1 9 and b are nonzero, since zero is not allowed to divide anything.) But the only way for two integers to have product 1 is for A = B = §1. (c) By de¯nition we have b = au and c = av for some integers u and v. Then b § c = au § av = a(u § v); so both b + c and b ¡ c are integer multiples of a. Hence both are divisible by a. 1.7. Use a calculator and the method described in Remark 1.9 to compute the following quotients and remainders. (a) 34787 divided by 353. (b) divided by 7843. (c) 3 divided by . (d) 7 divided by 76348. Solution to Exercise 1.7. (a) a = 34787, b = 353, a=b = 98:, q = 98, r = a ¡ b ¢ q = 193. (b) a = , b = 7843, a=b = 30:, q = 30, r = a ¡ b ¢ q = 3502. (c) a = 3, b = , a=b = 11253:, q = 11253, r = a ¡ b ¢ q = 60788. (d) a = 7, b = 76348, a=b = 19625:, q = 19625, r = a ¡ b ¢ q = 57987. 1.8. Use a calculator and the method described in Remark 1.9 to compute the following remainders, without bothering to compute the associated quo- tients. (a) The remainder of 78745 divided by 127. (b) The remainder of divided by 4387. (c) The remainder of 3 divided by 18754. (d) The remainder of 3 divided by . Solution to Exercise 1.8. (a) a = 78745, b = 127, a=b = 620:. r ¼ 127 ¢ 0: ¼ 4:; so r = 5. (b) a = , b = 4387, a=b = 646:. r ¼ 4387 ¢ 0: ¼ 3644:; so r = 3645. (c) a = 3, b = 18754, a=b = :. r ¼ 18754 ¢ 0: ¼ 17232:; so r = 17233. (d) a = 3, b = , a=b = 463:. r ¼ ¢ 0: ¼ :; so r = . 10 Exercises for Chapter 1 1.9. Use the Euclidean algorithm to compute the following greatest common divisors. (a) gcd(291; 252). (b) gcd(16261; 85652). (c) gcd(; ). (d) gcd(44; 7). Solution to Exercise 1.9. (a) gcd(291; 252) = 3. (b) gcd(16261; 85652) = 161. (c) gcd(; ) = 1. (d) gcd(44; 7) = 43. 1.10. For each of the gcd(a; b) values in Exercise 1.9, use the extended Euclidean algorithm (Theorem 1.11) to ¯nd integers u and v such that au + bv = gcd(a; b). Solution to Exercise 1.10. (a) 291 ¢ 13 ¡ 252 ¢ 15 = 3 (b) 16261 ¢ 85573 ¡ 85652 ¢ 16246 = 161 (c) ¢ ¡ ¢ = 1 (d) 44 ¢ ¡ 7 ¢ = 43 1.11. Let a and b be positive integers. (a) Suppose that there are integers u and v satisfying au + bv = 1. Prove that gcd(a; b) = 1. (b) Suppose that there are integers u and v satisfying au + bv = 6. Is it nec- essarily true that gcd(a; b) = 6? If not, give a speci¯c counterexample, and describe in general all of the possible values of gcd(a; b)? (c) Suppose that (u1; v1) and (u2; v2) are two solutions in integers to the equa- tion au + bv = 1. Prove that a divides v2 ¡ v1 and that b divides u2 ¡ u1. (d) More generally, let g = gcd(a; b) and let (u0; v0) be a solution in integers to au + bv = g. Prove that every other solution has the form u = u0 + kb=g and v = v0 ¡ ka=g for some integer k. (This is the second part of Theorem 1.11.) Solution to Exercise 1.11. (a) Let g = gcd(a; b). Then a = gA and b = gB for some integers A and B. Substituting into the given equation au + bv = 1 yields 1 = au + bv = gAu + gBv = g(Au + Bv): Thus g divides 1, so we must have g = 1. (c) No, au+bv = 6 does not imply gcd(a; b) = 6. For example, if gcd(a; b) = 1, then we can solve aU + bV = 1, and multiplying this equation by 6 gives a(6U)+b(6V ) = 6. For a speci¯c counterexample, take a = 3 and b = 2. Then Exercises for Chapter 1 11 a ¢ 6 + b ¢ (¡6) = 6; but gcd(a; b) = 1. In general, if au +