(a)

(i) Bob has public RSA key (n = 77, e = 7).

Show that Bob's private key is (d = 43).

(ii) Alice wants to send the message m = 13 to Bob. She encrypts the message using Bob's public key. What is the value of the ciphertext that Alice sends to Bob?

(iii) David has also sent an encrypted message to Bob. The ciphertext value that Bob receives from David is 17. Showing all your working, use Bob's key to decrypt this ciphertext and recover the value of David's message.

(b)

Consider cryptographic hash functions.

(i) What is meant by collision resistance for a hash function?

(ii) What common usage do hash functions have in connection with digital signatures?

(iii) What is the difference between a hash function and a message authentication code (MAC)?

(iv) Why is it recommended to use a hash function with 2n bits of output when it is used as component in a system designed for n bits of security?