Review Questions

1. What are the principal elements of a public-key cryptosystem?

There are six basic elements:

  1. Plaintext
  2. Encryption algorithm
  3. Public and private key.
  4. Ciphertext
  5. Decryption algorithm.

2. What are the roles of the public and private key?

3. What are three broad categories of applications of public-key cryptosystems?

4. What requirements must a public-key cryptosystem fulfill to be a secure algorithm?

There are really only two parts. Obiously valid parties must be able to encrypt and decrypt things easily. To be secure it must be hard to

5. What is a one-way function?

A one-way function is easy to perform, but very difficult to reverse.

6. What is a trap-door one-way function?

A trap-door one-way function is easy to calculate in one direction and infeasible to calculate in the other direction unless certain additional infromation is known.

7. Describe in general terms an efficient procedure for picking a prime number.

Pick a random odd number and test it for primality. If it fails try another one until you do find one.

  1. Pick an odd integer n at random (e.g., using a pseudorandom number generator).

  2. Pick an integer latex2($a<n$) at random.

  3. Perform the probabilistic primality test, such as Miller-Rabin. If n fails the test, reject the value of n and go to (1).

  4. If n has passed a sufficent number of tests, accept n; otherwise, go to (2)