[math-fun] Best proof that RSA Public-Key Cryptography works ?
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
This problem was discussed in the original RSA paper, with the suggestion that messages divisible by P or Q be avoided, and pointing out that they are sparse. I reviewed the paper, and pointed out the trick below to Rivest. The trick is to look at mod P and mod Q separately. The encryption exponent E (and the decryption exponent D) are selected to be coprime to phi(M) = (P-1)(Q-1), and so that E*D = 1 (mod phi(M)). This implies E*D = 1 (mod P-1), so any message m will satisfy m^(ED) = m (mod P). This includes m=0 (mod P), i.e. the P|m case. The same idea works for Q of course, and since the equation m^(ED) = m is true mod P and mod Q, it's true mod PQ. This proof unifies the not-divisible and the divisible cases. It also shows that RSA still works when the modulus is the product of three (different) primes P,Q,R (etc.), and it shows the case that fails: When the modulus has a square factor P^2, then the m^(ED) map is no longer 1-1: Here, if P|m but P^2 ~| m, then m^(ED) will have a factor of P^2, but m does not. So the m^(ED) formula will fail in this case, because information is lost when m is raised to a power. A simple intuition is to think of modulus 100: m^21 = m (mod 100) when m is prime to 10, but m^2 loses information when m is even or a multiple of 5: t0^2 = 0 (mod 100). Rich -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Guy Haworth Sent: Tuesday, April 13, 2010 9:35 AM To: math-fun@mailman.xmission.com Subject: [math-fun] Best proof that RSA Public-Key Cryptography works ? 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
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.
participants (3)
-
Guy Haworth -
Michael Kleber -
Schroeppel, Richard