phi(n) = phi(p)*phi(q) = (p-1)*(q-1). If m is divisible by p, m = 0 (mod p), so m**phi(p) = 0 (mod p), so m**(k*phi(n) + 1) = 0 (mod p). Since 0 < m < n and (p,q)=1, m**phi(q) = 1 (mod q), so m**(k*phi(n)+1) = m (mod q) By Chinese remainder theorem, m**(k*phi(n)+1) = m (mod p*q). Of course, if you ever send such a message m, a simple gcd of the encrypted message with n will discover n's factorization, thereby breaking the code. RSA works because the probability of coming up with such a message is very small. --ms On Tuesday 13 April 2010 11:35:23 Guy Haworth 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?

Apologies as this is probably a noddy one, but thanks in advance.

Guy

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun