Tutorial #17

1. One of the biggest problems with secret (single) key encryption is that two people who have never met cannot ever communicate privately/securely. This is solved with public key encryption. Explain how.

2. In the RSA example given in the lecture, what aspect of the system makes it difficult to discover Ks (the decryption, or private key) given that you know Kp, the public encryption key?

3. One of the major disadvantages of a public key cryptosystem based on RSA is its seriously slow speed of encryption and decryption. Explain briefly why the RSA algorithm is slow compared to a single-key encryption system such as DES. How can public key and single key encryption be combined to give a secure, but fast, encryption system?

4. What is the difference between a digital signature and a message digest? What are the advantages and disadvantages of each? How are these two technologies combined in modern "message signing"?

5. In the public-key authentication protocol given in the lecture notes, why is the random number "R" (or nonce) needed? Why can't Alice either encrypt the original "I am Alice" message with her private key, or alternatively "sign" this message using a digital signature? Note: the answer is not obvious.

6. One key characteristic of message digest algorithms is that every bit in the original message affects every bit in the digest at some point in the process. What is the intended result of this?

7. In the lecture notes, it was claimed that no one can generate two messages that have the same message digest. How can the system designer ensure this?

8. The public-key authentication protocol given in the lecture notes is susceptible to a well known security vulnerability called a man-in-the-middle attack. In this attack, a third party (Trudy?) intercepts all message traffic between Bob and Alice, including Bob's original request to Alice for a copy of her public key. Trudy is able to read, in plaintext, all of Bob and Alice's communications, in such a way that both Alice and Bob are unaware that it is happening. Explain how this is done, and describe how Bob and Alice can protect themselves against it.

9. The Unix system uses a scheme with some similarities to a message digest for storage of user passwords. In what ways are these similar? NB: if you don't use Unix, or use it infrequently, you may be excused from this question.

10. (Requires basic mathematical skill. This will not be on the exam!) Using the RSA cryptosystem with p = 7 and q = 11,
    1. Write down the values of n and X.
    2. Find a suitable value for E. What is the public key Kp corresponding to these values?
    3. Discover a legal value for D. What is the private key Ks corresponding to these values?

11. (Very advanced -- maths majors only. This will definitely not be on the exam!) In the lecture, a demonstration was given of a RSA-like public key encryption system, albeit one using very small primes. The numerical results were given without justification. Attempt to verify the correctness of the calculations presented there.

12. (Very advanced -- maths majors only. This will definitely not be on the exam!) Again using an RSA cryptosystem, this time with p = 13, q = 31 and D = 7, find E.

13. (Very advanced -- maths majors only. This will definitely not be on the exam!) Using the results of the previous question for p, q, D and E,
    1. Ascertain the largest message size (in bits) which can be encrypted using these values, and
    2. Demonstrate the encryption and decryption of a message.