Mallory can easily intercept C, and decrypt it using the public key [e,n] (which everyone knows because it has been published). But with this interception, all Mallory can do is determine M, the same thing Bob can do. Alice makes no secret of the fact she created M, in fact she is trying to prove she did so. Suppose Mallory also substitutes a phony C' before forwarding C' to Bob, to try to pass it off as Alice's message. Bob might well be fooled upon initial receipt, but once he tries decrypting it, Bob will find it implausible that C' originated with Alice.

The problem for Mallory is that she has no way of creating a cipher text C' that decrypts to a plausible false message. She can easily create an arbitrary, random C', but this will generally decrypt into gibberish (for widely-used key lengths, the chances of getting non-gibberish with a random C' are minuscule). And Mallory wants to substitute a specific false message (e.g., Mallory wants to replace Alice's message "I agree to the contract" with the false message, "I refuse to sign the contract"). Without having d, Mallory has no way to create a C' that will decrypt to the desired false message, nor even to any non-gibberish message at all. Once Bob decrypts the note that (purportedly) comes from Alice into something meaningful (and even topical), he can be assured it comes from Alice (or at least from someone who knows d; this alone cannot ensure that Mallory has not managed to steal d by some other means).

At its heart, what Alice has done is "digitally sign" her message. Real protocols provide additional features and improve efficiency. But RSA-in-reverse is identical in concept to all digital signature procedures.