Re: public key crypto

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 07/05/04 

Date: Sun, 04 Jul 2004 23:03:32 +0100

Michael Amling wrote:

> The weakest condition on d that I know is that
> d*e=1 mod LCM(p-1, q-1),
> from which it follows that that
> d*e=1 mod (p-1) and d*e=1 mod (q-1).
> When that's the case,
> m**(d*e)=m mod p and m**(d*e)=m mod q for all m,
> and from that you can establish
> m**(d*e)=m mod N
> from the Chinese Remainder Theorem. I suspect that d*e=1 mod LCM(p-1,
> q-1) is necessary and sufficient but I don't offhand have a proof.

You almost have a proof there. Think of RSA in CRT terms, and lets consider
it mod p first.

Let ed = r mod p-1, rewritten as ed = n.(p-1) + r where r and n are some
integers. Then:

A^de = A^(n(p-1)+r) mod p,

A^de = (A^r)(A^(n(p-1)) mod p,

A^de = (A^r)((A^(p-1)^n) mod p

* Fermat's theorem says A^(p-1) = 1 mod p.So:

A^de = (A^r)(1^n) mod p

A^de = A^r mod p.

Now RSA requires that A^de = A mod p, and this is only true iff r=1; ie, de
= 1 mod p-1. Both necessary and sufficient.

Similarly with mod q.

So mod pq, the necessary and sufficient conditions are that ed = 1 mod (p-1)
and mod (q-1), ie ed = 1 mod LCM(p-1,q-1).

*There is a bit about A and p being relatively prime which I missed out. If
1 < A < pq then an A cannot be relatively prime to both p and q
simultaneously. The rest is left for the reader - there is no trick, I'm
just too lazy to do it for free. 

-- 
Peter Fairbrother