MATH  187A                                  Introduction  to  Cryptography              Lecture  A,  Fall  2021

PRACTICE PROBLEMS FOR THE FINAL EXAM

Instructions. Recall that the final will count as much as three quizzes and it cannot be dropped. The final will take place 3-6pm on Friday December 10, location TBA. Please note that by signing up for this course, you are agreeing to sitfor the final examination at this date and time.

You do not need a bluebook, but you do need your student ID.

Rules for the final.  For the final, all computations have to be done by hand or by an offline basic calculator. No graphing calculators will be allowed. You will also not be allowed to use your phones. You can use an offline calculator to do simple calculations, but nothing more complicated than simple multiplication/squaring (as integers or modulo n) or square roots.

Allowed material:

● basic calculators

● class slides printed out and slightly annotated or your own notes from the lectures

● class website

● anything on the Canvas page for this class

● computers/tablets/etc as long as they are used only to access the items above

Not allowed: Anything that is not in the category of allowed material above. In particular, the following items are not allowed:

● solutions to sample quizzes

● solutions to this set of problems

● solutions to exams, quizzes or sample problems from previous years

● notes from discussions

● any written material except material posted on the class website or the Canvas page for this class (e.g. the class slides) or your own notes you took in lecture

● anything online except the class website or the class page in Canvas

● communication with anyone whatsoever except the instructor and the TAs; in par- ticular no talking, email, texting, chatting, twitter, instagram, tiktok, snapchat, sign language, etc; in short, no communication of any sort with any people except the in- structor and the TAs.

1. Use the formula for cyclotomic polynomials to compute the polynomial C10(x). Show the intermediate steps.

2. Using the appropriate cyclotomic polynomial, find which of 5 and/or 7 is a primitive root mod 37.

3. Show that 2 is a primitive root mod 61 and compute log2 (29) mod 61.

4. To communicate in secret, Alice and Bob agree to use the Diffie-Hellman key exchange protocol with modulus p = 29 and primitive root a = 3.

Alice picks the secret key x = 7, and Bob’s public key is B = 28.

(a) What is Alice’s public key A?

(b) What is their shared secret key?

(c) What is Bob’s secret key?

5.   (a) Bob wants to send the message m = 15 to Alice using the ElGamal cryptosystem based on the same pair p = 29, and primitive root r = 3. Alice uses the secret key a = 8. Bob chooses the session key k = 5 and sends to Alice two numbers (U, V). What are these two numbers?

(b) Alice receives the message (21, 17) from Eve. Decipher it and find the plaintext m.

6. When Alice wanted to convince Bob that she knows the square root s of y she sent Bob two numbers x1 and x2. How were these two numbers constructed?

7.   (a) Give a complete list of quadratic residues mod 37. (b) Find all the solutions to the quadratic equation

x2 + 12x + 3 三 0  (mod 37).

Hint: complete the square.

8. Does the equation x2  三 11(mod 31) have a solution? Explain.

9. Compute the following quantities by hand showing every step of the computation:

(a) gcd(24, 601) using Berlekamp;

(b) J(24, 601);

(c) 24300 (mod 601) using repeated squaring modulo n.

What does this tell you about the primality of 601?

10. Find all primitive roots modulo 19.

11. Which of the following equations defines an elliptic curve? Justify your answer. (a) y2  = x8 · x + 1

(b) y2  = x3 · x + 1

(c) y2  = x3 · 3x + 2

12. Consider the elliptic curve E : y2  = x3 · 15x + 18.

(a) Check that it is a valid elliptic curve.

(b) Check that the point P = (1, 2) is on the curve.

(c) Compute ·P and 2P.

(d) Let P/ = (1, ·2). Compute P + P/ .

(e) Check that the point Q = (7, 16) is on the curve.

(f) Compute P + Q and · Q.

13. Consider the elliptic curve E29  : y2  = x3 + 16x + 14 modulo the prime p = 29. (a) Check that it is a valid elliptic curve.

(b) Check that the points P = (5, 25) and Q = (12, 7) are on the curve and compute P + Q.

(c) Now P = (7, 11). Check that the point is on the curve and compute 2P.

14. In order to communicate securely, Alice and Bob use the ElGamal cryptosystem with the elliptic curve E29  : y2  = x3 + 16x + 14 mod the prime p = 29 and point P = (7, 11). (You checked in Problem 2 that P is a point on E29.)

(a) Alice chooses the secret key a = 4. Compute her public key A = aP.

(b) Bob wants to send the message M = (12, 7). (Btw, you also checked in Problem 3 that M is a point on E29.) to Alice using Alice’s public key A and the (secret) ephemeral key k = 3. Compute the pair C1 and C2 of points that Bob sends to Alice.

(c) Eve also wants to communicate with Alice. She uses the public key A to encode her message and sends Alice the points C1  = (8, 25) and C2  = (8, 4). Decrypt Eve’s mes- sage.