University of Virginia, Department of Computer Science
CS588: Cryptography, Spring 2005


22 March 2005

Name:   Colleen M. Hacker      

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 = pq

    3. Choose e and d so: ed ≡ 1 mod (p - 1)(q - 1) or φ(n)
    4. Encryption function (public): E(M) = Me mod n.

    5. Decryption function (private): D(C) = Cd mod n

  2. What is the private key?

    (Note that p and q must be kept secret, but they are not part of the private key. They should be destroyed after e and d are choosen.)

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

    0 ≤ M < n
    Since the exponentiation is done mod n the value of M must be less than n.

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

    185 = 5 * 37
    For all primes p, φ(p) = p - 1.
    So, φ(185) = φ(37) * φ(5) = 36 * 4 = 144.

    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(n2) 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.
    All of the statements are true. Some people were tricked by (a). Recall that O establishes an upper bound. If an algorithm is O(n), it also must be O (n2) or any function that grows faster than n. All of the other statements follow directly from the paper.
    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?
    Read carefully what Gates wrote: "an easy way to factor large prime numbers". Depending on how you precisely define factoring, factoring a large prime number p is either trivial (p * 1) or impossible (it has no factors other than p and 1, that's what it means to be prime). With the first definition, the individual has no power at all; with the second definition, the individual would indeed be quite powerful! Of course, what Bill meant to say was "an easy way to factor large composite numbers" or "an easy way to find the prime factors of large composite numbers". Of course, most large composite numbers are easy to factor: half of them are even and have 2 as an obvious factor. The ones that are products of two large prime numbers are the ones that are hard to factor, and that is what RSA's security depends on.

CS 655 University of Virginia
Department of Computer Science
CS 588: Cryptology - Principles and Applications