Re: [math-fun] Best proof that RSA Public-Key Cryptography works ?

On Tue, Apr 13, 2010 at 11:35 AM, Guy Haworth <g.haworth@reading.ac.uk>wrote:

I've had cause to revisit my notes on RSA Public Key Cryptography.

The proof that it works is trivial if the message 'm' is coprime to the 'n' = p*q which features in the Public Key.

I've seen no mentions of the case when m is divisible by p or q.

Is there a neat proof handy that it doesn't matter if 'm' is divisible by p or q?

Rich's answer is the right one, but from a practical point of view: If m is divisible by p or q, then you've just given out the factorization of your secret n, and the recipient of your message can deduce your private key. Don't do that! --Michael -- Forewarned is worth an octopus in the bush.