Describe, briefly, either the RSA or the Elgamal public key cipher. You should explain, without proof, why it is believed to be difficult to break the cipher you describe.

How can such a cipher be used to sign messages? You should explain how the intended recipient of the message can (a) know from whom it came; (b) know that the message has not been changed; and (c) demonstrate that the sender must have signed it.

Let $I_{0}, I_{1}, \ldots, I_{N}$ be friendly individuals each of whom has a public key cipher. $I_{0}$ wishes to send a message to $I_{N}$ by passing it first to $I_{1}$, then $I_{1}$ passes it to $I_{2}, I_{2}$ to $I_{3}$, until finally it is received by $I_{N}$. At each stage the message can be modified to show from whom it was received and to whom it is sent. Devise a way in which these modifications can be made so that $I_{N}$ can be confident both of the content of the original message and that the message has been passed through the intermediaries $I_{1}, I_{2}, \ldots, I_{N-1}$ in that order and has not been modified by an enemy agent. Assume that it takes a negligible time to transmit a message from $I_{k}$ to $I_{k+1}$ for each $k$, but the time needed to modify a message is not negligible.