Re: public key crypto

From: Michael Amling (nospam_at_nospam.com)
Date: 07/05/04 

Date: Mon, 05 Jul 2004 19:10:09 GMT

Peter Fairbrother wrote:
> I'm reposting this, with a few corrections. It should be correct now, I
> hope!
>
> Peter
>
> 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 for all A, 1 < A < pq:
>
> 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;

   The "if" part of this "iff" is obvious. Do you have a proof of the
"only if"? (Also, it would be better to explicitly state that 1<=r<=p-1).

> ie, de
> = 1 mod p-1 is a both necessary and sufficient condition for RSA to work mod
> p.
>
> Doing the same mod q, we get the condition ed = 1 mod q-1.
>
> So mod pq, the necessary and sufficient conditions are that ed = 1 mod (p-1)
> and ed = 1 mod (q-1), ie ed = 1 mod LCM(p-1,q-1). QED.
>
>
>
> *A and p should be relatively prime for this to be true. If A is a multiple
> of p then A^de mod p = p. Such an A must be relatively prime to q, so A^de
> mod pq = p((A^de) mod q) = p(A^r mod q) = A mod pq iff r=1, the condition is
> necessary and sufficient for all A < pq, and again RSA works. Similarly if A
> is a multiple of q.
> 

-- 
--Mike Amling