Math/CS 332 Exam #2 Practice
NAME:
YOU can do it!
1 Topics
• RSA
• Diffie-Hellman Key Exchange and El Gamal Public Key Cryptosystem
• Shank’s Baby Step-Giant Step Algorithm
• Chinese Remainder Theorem
• Pohlig-Hellman Algorithm
• Elliptic Curve Key Exchange
• Elliptic Curve Method for Factoring
• Koblitz’ Method for Assignment
• Polynomial Threshold Scheme
2 Problems
2.1 Conceptual
1. What is/are the main difference(s) between symmetric/private key encryption systems (such as affine
ciphers, Vigenere ciphers, Enigma ciphers, DES, AES, . . . ) and asymmetric/public key encryption
systems (such as RSA, Diffie-Hellman Key Exchange, El Gamal, . . . )? How is each type of system
used in our modern devices?
2. What is the mathematical problem underlying each family of public key cryptosystems?
3. Which public key cryptosystem is fastest, when security level is fixed?
4. Order the public key cryptosystem families in terms of increasing vulnerability to quantum algo-
rithms.
5. What are some ways that the “stripped down” descriptions of the public key cryptosystems described
in class are vulnerable to attack?
6. What are some additions to the “stripped down” (or “schoolbook”) descriptions that are needed in
order to make the public key cryptosystems we’ve studied applicable and practical?
7. You have discovered a long-lost oracle, one that can solve the Diffie-Hellman Problem (computing
the value of gab modulo a prime p from the known values of ga (mod p) and gb (mod p), without
explicitly knowing the values of a or b). Explain how this oracle will help you decrypt messages that
have been encrypted using the ElGamal public key cryptosystem.
1
2.2 Computational
7. Let E be the elliptic curve defined by the equation Y 2 = X3 + 1. For each prime p ≥ 5, let Np be
the cardinality of the group of points on E modulo p. Here is the initial start of the sequence (Np)
as p tends towards infinity: N5 = 6, N7 = 12, N11 = 12, N13 = 12, N17 = 18, N19 = 12, N23 = 24,
N29 = 30, . . . For the set of primes satisfying p ≡ 2 modulo 3, can you see a pattern for the values
of Np? Make a general conjecture for the value of Np when p ≡ 2 modulo 3. (For good luck: Prove
your conjecture!)
8. A dumb friend told you that d = 543546506135745129 in an RSA cryptosystem community where
the friend’s public address is (718548065973745507, 3449). Factor n to show your dumb friend what
an idiot they are being by sharing d.
9. You witness Alice and Bob agree on a secret key using the Diffie-Hellman key exchange. Alice and
Bob chose p = 97 and g = 5. Alice send Bob the number 3 and Bob sent Alice the number 7. Brute
force crack their code: What is the secret key that Alice and Bob agreed upon? What were their
secret keys?
10. Use the Pohlig-Hellman Algorithm to solve 2x ≡ 14 modulo 19.
11. Use the Pohlig-Hellman Algorithm to solve the discrete log problem 10x ≡ 243278 modulo 746497.
12. Solve x ≡ 17 modulo 101, x ≡ 18 modulo 201, and x ≡ 19 modulo 301.
13. Let E be the elliptic curve E : Y 2 = X3 + 3X + 2 over Z/7Z.
(a) Make a list of the points on E.
(b) Make an addition table for the points on E.
14. Let E be the elliptic curve E : Y 2 = X3 + X + 1 and let P = (4, 2) and Q = (0, 1).
(a) Check that P and Q are on the curve E.
(b) Compute P Q, P P , and Q Q.
(c) Compute 3P and 3Q.
(d) Find x such that Q = xP .
15. Alice and Bob agree to use elliptic curve Diffie-Hellman key exchange with the prime p = 2671,
elliptic curve E : Y 2 = X3 + 171X + 853, and the point P = (1980, 431).
(a) Alice sends Bob the point QZ = (2110, 543). Bob uses b = 1943. What should Bob send to
Alice? (You should use Sage!)
(b) What is the secret shared value?
16. The Menezes-Vanstone variant of the elliptic ElGamal public key cryptosystem improves message
expansion while avoiding the difficulty of directly attaching plaintexts to points on an elliptic curve.
The MV-ElGamal cryptosystem is described in Figure 1.
(a) The last line of the table claims that m′1 = m1 and m′2 = m2. Explain why this is true (and
thus why the decryption process does work).
(b) Alice and Bob agree to use MV-ElGamal with p = 1201, E : Y 2 = X3 + 19X + 17, and
P = (278, 285). Alice’s secret value nA = 595. What is her public key?
(c) Under the same assumptions, Bob sends Alice the encrypted message ((1147, 640), 279, 1189).
What is the plaintext?
2
Figure 1
17. Use the elliptic curve factorization algorithm to factor N = 589 using the elliptic curve E where
A = 4 and point P = (2, 5).
18. Consider the following DES-like encryption method. Start with a message of 2n bits. Divide it into
two blocks of length n, to get M0M1. The key K consists of k bits for some k ∈ N and there is a
function f(x, y) that takes in an input x with k bits and an input y with n bits, producing an output
of n bits. One round of encryption starts with a pair MiMi+1 and produces the pair Mi+1Mi+2
where Mi+2 = Mi XOR f(K,Mi+1). This is done for r rounds so that the ciphertext is MrMr+1.
(a) If you have a machine that does the r-round encryption just described, how would you use the
same machine to decrypt the ciphertext MrMr+1 (using the same key K)? Explain why your
descryption method works.
(b) Suppose that k = n and r = 2, with f(x, y) = x XOR y. If you know only a ciphertext, can you
deduce the plaintext and the key? If you know a ciphertext and the corresponding plaintext,
can you deduce the key? Explain your answers.
(c) Suppose instead that k = n and r = 3, with f(x, y) = x XOR y. Why is this encryption system
no more secure than when r = 2?
19. Let P be a point on an elliptic curve E modulo n.
(a) Show that E has only finitely many points, so P has only finitely many distinct multiples.
(b) Show that there are integers i, j with i > j such that iP = jP . Then, determine (i− j)P .
(c) Let x be a positive integer. Show that the following procedure computes xP .
i. Start with a = x, B = O, and C = P .
ii. If a is even, let a = a2 , and let B = B, C = 2C.
3
iii. If a is odd, let a = a− 1, and let B = B + C, C = C.
iv. If a 6= 0, go to Step 2.
v. Output B.
20. Factor 35 using each elliptic curve and point as specified.
(a) y2 = x3 + 26 and P = (10, 9)
(b) y2 = x3 + 5x + 8 and P = (1, 28)
4

欢迎咨询51作业君