LAB: Digital Signatures

Suppose you have:

a cryptographic hash function H (let's say for today that it's SHA-256)
your own public/secret RSA key pair P = (n,e) and S = (n,d)
the public-key encryption function E defined by E(P,M) = E((n,e),M) = M^e mod n and similarly, E(S,M) = E((n,d),M) = M^d mod n

You have a document (i.e., a sequence of bytes) named D and you want to send it to Alice with your stamp of approval. So you compute the following:

Sig = E(S,H(D))

and then send D || Sig to Alice. Assume Alice already knows to expect a signed message from you, and that you are using E and H to compute your signature.

Your Carleton user name, lower case:

Alice receives a message M, ostensibly from you, and wants to convince herself that you actually signed it. What does she do to separate the document from the signature?

Once Alice has separated M into pieces she provisionally calls the "document" X and the "signature" Y, what computation does she perform to make sure that Y is really a signature computed by you of the document X?

Suppose Mal intercepts M before Alice gets it, and he wants to change the document D part of the message to D2. If he just sends D2 || Sig along to Alice, can she tell that the document has been changed? (Hint: Yes. But how?)

Same situation. Can Mal compute Sig2 in some way and send D2 || Sig2 to Alice in a way that she won't notice? How, or why not?