L. Smithline – Math 135 Final Exam – Solutions 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-Hellman KeyExchange, withP = 53, B = 3.You overhear the public part of the exchange:3G≡ 31 mod 53, 3H≡ 21 mod 53.Using the magic box, you discover G = 5, H = 11., that is,35≡ 31 mod 53, 311≡ 21 mod 53.a. (10 pt) Compute the shared secret (also called the agreed key). Explainwhat you are calculating and the method you use.The shared secret is (3G)H≡ (3H)G≡ 3GH.One way to compute is by repeated squaring to find 215.Another way is to use Fermat’s little Theorem: 355≡ 35233≡ 1 · 33≡ 27.b. (20 pt) Explain why Diffie-Hellman Key Exchange seems to be secure, inreal life, and why this magic box compromises the security of this cryptosys-tem.The security of Diffie-Hellman rests in the apparent difficulty of the dis-crete log problem. There is no known polynomial time (relative to the numberof digits of the input) algorithm to solve discrete logs.The magic box solves the discrete log problem in constant time plushowever long it takes to write the problem and the answer. This makessolving the discrete log easy.L. Smithline – Math 135 Final Exam – Solutions 22. Let H(n) be the number of dots in a hexagonal grid with n dots on aside. Shown below are the grids with 1, 2, 3, and 4 dots on a side... .. . .. .. . .. . . .. . . . .. . . .. . .. . . .. . . . .. . . . . .. . . . . . .. . . . . .. . . . .. . . .TTTTTTTTTTa. (10 pt) Compute the differences H(3)−H(2), H(4)−H(3), and H(5)−H(4).H(3) − H(2) = 12, H(4) − H(3) = 18, H(5) − H(4) = 24, by counting thedots.b. (20 pt) Use an induction argument to show that for natural numbers n,H(n) = 3n(n − 1) + 1.The dots of the hexagon with n dots on a side are covered by one dot inthe center plus six triangles with n−1 dots on a side. Let T (n−1) be the num-ber of dots in a triangle with n−1 dots on a side. We see H(n) = 6T(n−1)+1.Claim: T(n − 1) = n(n − 1)/2.Proof, by induction. Base case is T (0) = 0. If there are no dots, there areno dots. Inductive hypothesis: suppose for a given k > 0, that T (k − 1) =k(k − 1)/2. Inductive step: I will show that T (k) = (k + 1)k/2, the nextcase. T(k) is the number of dots in a triangle with k dots on a side. This isjust one more row than the triangle with k − 1 dots on a side, and that lastrow has k dots. Thus, T (k) = T (k − 1) + k. Using the inductive hypothesis,T (k) = k(k − 1)/2 + k = (k(k − 1) + 2k)/2. Using the distributive andcommutative laws of multiplication, the result T (k) = (k + 1)k/2 follows.By the principle of mathematical induction, T (n − 1) = n(n − 1)/2 for allnatural numbers n.H(n) = 6n(n − 1)/2 + 1 = 3n(n − 1) + 1.L. Smithline – Math 135 Final Exam – Solutions 33. 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 substitutedwith the pair using first the letterat the left end of the row and secondthe letter at the top of the column.So L enciphers as AD.a. (10 pt) Encipher THE using the substitution table.XV XF GXb. (20 pt) The following message was enciphered first by applying the ADFGVXsubstitution and second, using keyword columnar transposition with the keyword P A R I S:DAVFAADX VXFGVXVX FFXXXVFX XGXGXAVA DAGXAVGGWhat is the first word of the message?P A R I S3 1 4 2 5F D X V DF A G X AX V X F GX F G G XX A X V AV A A X VF D V V GX X A X GPlain text: ITWASTHEBESTOFTIMES∅First word: ITL. Smithline – Math 135 Final Exam – Solutions 44. Farmer Magog comes home from the Neolithic Revolution. Magog haslearned about the latest inventions: planting crops, and also writing numbersin base ten (using fashionable Arabic numerals).a. (5 pt) Farmer Magog has a square field measuring 200 cubits on a side. IfFarmer Magog harvests150bushels of grain per square cubit, to the nearestwhole bushel, how much does Magog harvest?(200 cubits)(200 cubits)(150bushels / square cubit) = 800 bushels.b. (5 pt) Farmer Magog scratches this number in base ten on a stone tablet,taking 1 minute per digit. How long does it take Farmer Magog to recordthe harvest?blog10800c + 1 = 3, so 3 minutes (or just count the digits).Magog is prosperous, and periodically acquires larger lands. Suppose Magoghas a square field measuring C cubits on a side. Crop yield is the same150bushels per square cubit.c. (10 pt) Let h(C) be the amount of Magog’s harvest, in bushels. Whichcomplexity class, from the list below, is the smallest containing h(C), andwhich word best describes this class?As suggested above, h(C) = C2·150bushelscubit2.Thus, h(C) is in O(C2), which is type I and polynomial order.d. (10 pt) Magog still records the harvest on a stone tablet. It takes timer(C) to write the number in base ten. Which complexity class, from the listbelow, is the smallest containing r(C), and which word best describes thisclass?The time to record h(C) is r(C) = (blog10h(C)c + 1) minutes. Using theresult for h(C) above, we see r(C) = (b2 log10C − log1050c + 1) minutes. Forlarge C, r(C)/ log C is about 2, so r(C) is type III, which is logarithmic.Complexity classes:I. O(CK), K > 0 for example: O(C1), O(C2), O(C10),II. O(KC), K > 1 for example: O(2C), O(eC), O(10C),III. O(log C),IV. O(1). In cases I and II, K is a some constant indep endent of C.Descriptions: constant, exponential, logarithmic, polynomial.L. Smithline – Math 135 Final Exam – Solutions 55. A eight bit linear feedback shift register generates a key for a binarystream cipher. If the register has …