Review Questions
1. What are the principal elements of a public-key cryptosystem?
There are six basic elements:
- Plaintext
- Encryption algorithm
- Public and private key.
- Ciphertext
- Decryption algorithm.
2. What are the roles of the public and private key?
- Public Key: Used to encrypt messages to the private key holder
- Private Key: Used to decrypt messages recieved that have been encrypted using the public key, and to create a digital signature that authenticates the sender to the reciever.
3. What are three broad categories of applications of public-key cryptosystems?
- Encryption/Decryption
- Digital Signature
Secret key or session key exchange
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
- determine the private key given the public key.
- Decrypt the ciphertext knowing the public key (when encrypted by the private key).
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.
Pick an odd integer n at random (e.g., using a pseudorandom number generator).
Pick an integer $$a<n$$ at random.
Perform the probabilistic primality test, such as Miller-Rabin. If n fails the test, reject the value of n and go to (1).
If n has passed a sufficent number of tests, accept n; otherwise, go to (2)