6. Cryptography: hash functions and MACs

Question 1

What is a one way function?

Answer 1

A function f is one-way if for all y there is no efficient algorithm to compute x such that f(x) = y

Question 2

What is a collision resistant function?

Answer 2

A function f is collision resistant if there is no efficient algorithm that can find m1, m2 such that f(m1) = f(m2)

Question 3

What is the Merkle–Damgård construction?

Answer 3

Builds a collision-resistant cryptographic hash functions from collision-resistant one-way compression functions Split the message (padded with its length) into fixed blocks, feed each block combined with the output of the previous round into the function (use initialisation vector for first)

Question 4

How do you encrypt with RSA?

Answer 4

m^e mod n where m is the message, and (e, n) is the encryption key

Question 5

How do you decrypt with RSA?

Answer 5

c^d mod n where c is the ciphertext, and (d, n) is the decryption key

Question 6

Show RSA is consistent

Answer 6