Suppose two parties A and B agree to communicate through the internet where messages are publicly readable, and anyone can try to pretend to be anyone else. A and B agree (beforehand) on a large prime p (which is made public, and so not a secret), and two secret numbers a and b ∈ Zp (both a, b are known only to A and B). This defines a hash function x → h (x) = ax +b mod p.

When A wishes to send a message to B (and we assume it can be coded via ASCII code as an integer 1 <p), A sends the message x and an authentication v = ax+b mod p. B convinces herself that this message x was sent by A by verifying that h(x) = v.

• Now suppose some nefarious entity C wants to pretend to be A and sends B a message (x', v') (where x' ≠ x ). Suppose C has seen a legitimate message (x, v) from A to B. If C does not know the secret a and b that define the hash function (even knowing the form of the hash function and the prime p), prove that C cannot fool B into believing that this message (x', v') was sent from A. (You prove that the probability that C can send the correct v' is 1/p.)

• Now suppose C has intercepted two messages from A to B, in the form of (x,v) and (y, w). Show that C now can pretend to be A and convinces B of any message x' by appending the proper v' pretending that it was sent from A.

• Suggest a way to change the communication scheme that A and B agree beforehand that can tolerate some adversary C from intercepting up to two messages.

How about up to k intercepted messages?