CS588: Cryptography, Spring 2005

Quiz
22 March 2005
Name: ___________________________________________
Work alone. No notes. No books. No other materials. Answer all questions (both sides).
RSA Paper
 Here is the RSA algorithm, with some pieces missing. Fill in the blanks:
 Pick 2 large secret primes, p and q.
 Let n = _______________ [blank 1]
 Choose e and d so: ed ≡ 1 mod _____________ [blank 2]
 Encryption function (public): E(M) = M^{e} mod n.
 Decryption function (private): D(C) = ___________________ [blank 3]
 What is the private key?
 What is the range of M that can be reliably transmitted using RSA?
 What is φ(185)? (Hint: divide by 5)
Continues on back side Practical Techniques for Searches on Encrypted Data
 Check all of the below statements that are true about the paper:
 ___ It describes techniques for searching encrypted data that can search a document of length n in O(n^{2}) stream cipher and block cipher operations.
 ___ It describes techniques for searching encrypted data that can search a document of length n in O(n) stream cipher and block cipher operations.
 ___ It mentions the birthday paradox.
 ___ It presents techniques that are provably secure.
 ___ For the final scheme, when Alice sends a search query to Bob, Bob can learn something about which documents contain Alice's query term.
Security of RSA  [Bonus] In The Road Ahead, Bill Gates wrote
Because both the system's privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. Any person or organization possessing this power could counterfeit money, penetrate any personal, corporate, or government file, and possibly even undermine the security of nations.How powerful would someone who developed an easy way to factor large prime numbers be?
University of Virginia Department of Computer Science CS 588: Cryptology  Principles and Applications 
cs588–staff@cs.virginia.edu 