COMP4109 - Applied Cryptography Practice Questions – Midterm 2 1. What is the Diffie-Hellman key exchange protocol? 2. Suppose Alice and Bob want to use DH key exchange to share a secret x. If they use Z∗11 with the generator g = 2, what is the secret if Alice send g5 and Bob sends g3? Show (picture) how they each compute this shared secret. 3. Describe the man-in-the-middle attack on the Diffie-Hellman scheme. 4. Suppose we use Z∗p for some large prime p (4000 bits). Given a generator for this group g and some other element gx, for some randomly chosen 1 < x < p− 1, can we find x efficiently? 5. What is the (textbook) RSA cryptosystem? 6. What is semantic security for a public key encryption scheme? How does it differ from semantic security of a secret key encryption scheme? 7. What do IND-CPA, IND-CCA1 and IND-CCA2 mean for public-key cryptosystems? 8. Define the following problems: • (DL) discrete logarithm problem • (CDH) computational Diffie-Hellman problem • (DDH) decisional Diffie-Hellman problem 9. Show that if you can solve the discrete log problem then you an solve the com- putational Diffie-Hellman problem. 10. Is textbook RSA semantically secure? (why or why not?) 11. In textbook RSA, what is the danger in using public exponent e = 3? How do protect against this in a real implementation of RSA with e = 3? 12. Suppose you have RSA with two 1024-bit primes. • What is the bitlength of the modulus N? • If you choose a random number in {1, 2, ...N}, what is the expected bitlength of this number (roughly)? • Using schoolbook multiplication (which has cost O(n2) to multiply two n-bit numbers), what is the cost of computing an RSA encryption with e = 3? What is the cost if e is chosen randomly in the range {3, 5, 7, ..., φ(N)− 1}? 13. Given an RSA public key (e,N) = (3, 33), what is the ciphertext of the plaintext message m = 8? 14. What is the size of the plaintext space of RSA when the primes p = 17 and q = 3 are used for the modulus? 1 15. Give a brute-force method to compute an inverse of a modulo n. (I.e., the method should have runtime O(nM(log n), where M(x) is the cost of multiplying two x-bit integers). 16. The Elliptic Curve Method (ECM) for factoring has a heuristic expected runtime of eo(1)(2 log p log log p) 1/2 Number Field Sieve (NFS) for factoring has a heuristic expected runtime of e(1.92+o(1))(logN) 1/3(log logN)2/3 Both methods are sub-exponential. When do we expect ECM to factor a number N more efficiently than NFS? 17. How do digital signatures schemes, MACs and hash functions compare to each other? That is, what cryptographic goals do each achieve (or not achieve)? 18. Briefly explain what each of the following mean w.r.t. digital signature schemes. • existential forgery • selective forgery • universal forgery 19. Briefly explain each of the following (wrt digital signature schemes) • key-only attack • known-message attack • chosen-message attack 20. What does it mean for a digital signature scheme to be secure? 21. How does the RSA-FDH signature scheme work? (Explain all 3 algorithms) 22. Suppose Alice used an RSA signature scheme (with hash function H(x) = x) with public (verifying) key (e,N) = (3, 33). Is (m,σ) = (5, 14) a valid message-signature pair. 23. In the RSA-FDH signature scheme, explain how to create a forgery if any of the three cryptographic properties of the hash function used are not met. 24. In the DSA (or ElGamal), explain why each signature must have a unique k value? 25. Consider the following hash function for a message x = x1||x2|| · · · ||x2n: h(x) = AES0 ( AES0(x1 ⊕ x2n)||AES0(x2 ⊕ x2n−1)|| · · · ||AES0(xn ⊕ xn+1) ) where the key used in AES is k = 0. What is wrong with this hash function? 26. What is the inverse of 9 in Z∗11? 27. What is the inverse of 4 in Z∗8? 28. What is φ(N) for N = 7, 23, 28? 29. Let N = 11. What is 22652557887263 mod N? 30. Answer all the questions to the practice midterm for the last midterm. 2 The multiplication table for Z11. × 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 4 6 8 10 1 3 5 7 9 3 3 6 9 1 4 7 10 2 5 8 4 4 8 1 5 9 2 6 10 3 7 5 5 10 4 9 3 8 2 7 1 6 6 6 1 7 2 8 3 9 4 10 5 7 7 3 10 6 2 9 5 1 8 4 8 8 5 2 10 7 4 1 9 6 3 9 9 7 5 3 1 10 8 6 4 2 10 10 9 8 7 6 5 4 3 2 1 (Z∗11,×) the group of units of Z11 under multiplication Z∗11 Exp 0 1 2 3 4 5 6 7 8 9 10 g g0 g1 g2 g3 g4 g5 g6 g7 g8 g9 g10 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 4 8 5 10 9 7 3 6 1 3 1 3 9 5 4 1 3 9 5 4 1 4 1 4 5 9 3 1 4 5 9 3 1 5 1 5 3 4 9 1 5 3 4 9 1 6 1 6 3 7 9 10 5 8 4 2 1 7 1 7 5 2 3 10 4 6 9 8 1 ... 10 1 10 1 10 1 10 1 10 1 10 1 3
欢迎咨询51作业君
