Public$-$key cryptography can solve the authentication problem. The host keeps a file of every

user's public key; all users keep their own private keys. Write a protocol for Authentication using

public key cryptography $(5$ Marks$)$

Question: The interlock protocol, invented by Ron Rivest and Adi Shamir has a good chance of

foiling the man$-$in$-$the$-$middle attack.

$(1)$ Alice sends Bob her public key.

$(2)$ Bob sends Alice his public key.

$(3)$ Alice encrypts her message using Bob's public key. She sends half of the encrypted message to

Bob.

$(4)$ Bob encrypts his message using Alice's public key. He sends half of the encrypted message to

Alice.

$(5)$ Alice sends the other half of her encrypted message to Bob.

$(6)$ Bob puts the two halves of Alice's message together and decrypts it with his private key. Bob

sends the other half of his encrypted message to Alice.

$(7)$ Alice puts the two halves of Bob's message together and decrypts with her private key.

The important point is that half of the message is useless without the other half; it can't be decrypted.

Bob cannot read any part of Alice's message until step $(6)$; Alice cannot read any part of Bob's

message until step $(7).$

Analyze the Security of the protocol $(5$ Marks$)$