L. Smithline – Math 135 Practice Exam Questions – Spring 2004 11. Suppose you have a magic box which has an input slot and an outputslot. The box works as follows: If you write a prime number P , a base B,and an integer R on a strip of paper, feed the strip into the input slot, andwait one second, the machine will return a different strip through the outputslot with a number X. This number X solvesBX≡ R mod P.If no such X exists, then the machine returns a short blank paper strip.You eavesdrop on two people, Gene and Hilary, using Diffie-Helman KeyExchange, withP = 47, B = 3.You overhear the public part of the exchange:3G≡ 8 mod 47, 3H≡ 18 mod 47.Using the magic box, you discover35≡ 8 mod 47, 319≡ 18 mod 47,that is,G = 5, H = 19.a. Compute the shared secret. Explain what you are calculating and themethod you use.b. Explain why Diffie-Helman Key Exchange seems to be secure, in real life,and why this magic box compromises the security of this cryptosystem.Note. On the exam, the particular P , B, G, and H may be different, butthey will be of a similar size to the ones here.L. Smithline – Math 135 Practice Exam Questions – Spring 2004 22. Suppose you have a magic box which has an input slot and an outputslot. The box works as follows: if you write a natural number N on a strip ofpaper, feed the strip into the input slot, and wait one second, the machine willreturn a different strip through the output slot, with a list of numbers. Thesenumbers will be all the solutions X between 1 and N − 1 to the equationX2≡ 1 mod N.For example, if you give the machine the number 779, the reply is1, 286, 493, 778,because12≡ 1, 2862≡ 1, 4932≡ 1, 7782≡ 1 mod 779,and those are all the solutions to X2≡ 1 mod 779 for X between 1 and 778.a. Given N which is the product of two distinct prime factors, explain howto use the box to find these factors.b. Demonstrate the method you propose to factor N = 779. Do not simplywrite the factors. Show how you get them from the information given.c. Explain whether this magic box impacts the security of the RSA cryp-tosystem.Note. On the exam, the particular N , and, of course, the resulting solutionsto X2≡ 1 mod N may be different, but they will be of a similar size to theones here.L. Smithline – Math 135 Practice Exam Questions – Spring 2004 33. Let H(n) be the number of pips in a hexagonal grid with n pips on aside. Shown below are the grids with 1, 2, 3, and 4 pips on a side... .. . .. .. . .. . . .. . . . .. . . .. . .. . . .. . . . .. . . . . .. . . . . . .. . . . . .. . . . .. . . .TTTTTTTTTTa. Compute the differences H(3) − H(2), H(4) − H(3), and H(5) − H(4).b. Use an induction argument to show that for natural numbers n,H(n) = 3n(n − 1) + 1.(The lines drawn on the last hex grid suggest a way to cut the hexagon intomore manageable triangle pieces.)L. Smithline – Math 135 Practice Exam Questions – Spring 2004 44. Communication over a certain channel requires a message to be in a spe-cial form: a message is a string of binary bits, always beginning with thebit 1, and has no consecutive 1 bits. (This was true for some real hardwarewhich could not distinguish between two 1’s in a row and a single 1 stretchedout by inaccurate system timing.)There is one valid message of length one: 1.There is one valid message of length two: 10.The message 010101 is invalid; it begins with 0.The message 101101 is invalid; it has two consecutive 1 bits.The message 101010 is valid.a. Write out all the valid three bit, four bit, and five bit messages. Howmany are there of each?b. Let V (x) be the number of valid messages which are x bits long. SoV (1) = 1, V (2) = 1, and you computed V (3), V (4), and V (5) above. Use aninduction argument to show for natural numbers x > 2,V (x) = V (x − 1) + V (x − 2).L. Smithline – Math 135 Practice Exam Questions – Spring 2004 55. Described below is a two phase cipher. First, there is a substitution.Second, there is a transposition.This substitution cipher uses multiple symbols for certain letters. Theletters Q and X are deleted from the plaintext alphabet, so that there canbe two possible substitutions for E and T. The enciphering cryptoclerk usesthe lowercase e and t to indicate that the alternative substitution is to beused. The deciphering cryptoclerk does not care. If Q or X appears in theplaintext, the letters K, KW, KS, or Z are used phonetically.Here is the substitution:plain A B C D E F G H I J K L M N O P e R S T U V W t Y Zcipher V O D K A T H U M B S C R E W I N G L Y Z X Q P J Fa. Encipher “THeAtER” using the substitution above, and the alternativesubstitutions where indicated.b. The second phase of this cipher system is a transposition. The result ofthe substitution cipher is written in five rows of equal length and copied incolumns. You receive the following message:TPWPQ GUJAK ANAGA NGCMK KMCET WHYVM RUUDG MPNGN LYVWFWhat is the first word in the plaintext?Hint: the word theater appears in the message, using the same choices foralternative substitutions as the first part, but not as the first word.Note. On the exam, the particular word in the first part and message in thesecond part might be different.L. Smithline – Math 135 Practice Exam Questions – Spring 2004 66. The World War I era ADFGVX cipher is a two step method. The first stepis a substitution using two letters among ADFGVX to stand for each plaintextletter or digit. The second step is a keyword columnar transposition. Belowthe key word, the result of the first step is written out, using one column foreach letter of the key word. The result is copied in columns, in alphabeticalorder of the letters of the key word.Here is the substitution table:A D F G V XA F L 1 A O 2D J D W 3 G UF C I Y B 4 PG R 5 Q 8 V EV 6 K 7 Z M XX S N H ∅ T 9Each letter or digits is substituted with the pair using first the letter at theleft end of the row and second the letter at the top of the column. So Lenciphers as AD.a. Encipher AND using the substitution table.b. The following message was enciphered first by applying the ADFGVX substi-tution and second, using keyword columnar transposition with the key wordM O R I A:GDFDXXGG XVAXGGVX XXADDDXX AAAGDDDG FGGXADXAWhat is the first word of the message?Hint: the word AND appears in the message, but not as the first word.Note. On the …