Quiz

22 March 2005

Name: ___________________________________________

Work alone. No notes. No books. No other materials. Answer all questions (both sides).

RSA Paper

1. Here is the RSA algorithm, with some pieces missing. Fill in the blanks:
   1. Pick 2 large secret primes, p and q.

      
      

   2. Let n = _______________ [blank 1]

      
      

   3. Choose e and d so: ed ≡ 1 mod _____________ [blank 2]
   4. Encryption function (public): E(M) = M^e mod n.

      
      

   5. Decryption function (private): D(C) = ___________________ [blank 3]

   
   

2. What is the private key?

   
   

   
   

   
   

3. What is the range of M that can be reliably transmitted using RSA?

   
   

   
   

   
   

   
   

4. What is φ(185)? (Hint: divide by 5)

   
   

   
   

   
   

   
   

   
   

   Continues on back side
   Practical Techniques for Searches on Encrypted Data

5. Check all of the below statements that are true about the paper:
   1. ___ It describes techniques for searching encrypted data that can search a document of length n in O(n²) stream cipher and block cipher operations.
   2. ___ It describes techniques for searching encrypted data that can search a document of length n in O(n) stream cipher and block cipher operations.
   3. ___ It mentions the birthday paradox.
   4. ___ It presents techniques that are provably secure.
   5. ___ 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
6. [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