# Re: public key crypto

**From:** Peter Fairbrother (*zenadsl6186_at_zen.co.uk*)

**Date:** 07/05/04

**Next message:**Bill Unruh: "Re: Riemann Hypothesis and P vs NP"**Previous message:**Matthew Skala: "Re: Riemann Hypothesis and P vs NP"**In reply to:**Michael Amling: "Re: public key crypto"**Next in thread:**Peter Fairbrother: "Re: public key crypto"**Reply:**Peter Fairbrother: "Re: public key crypto"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Bill Unruh: "Re: Riemann Hypothesis and P vs NP"**Previous message:**Matthew Skala: "Re: Riemann Hypothesis and P vs NP"**In reply to:**Michael Amling: "Re: public key crypto"**Next in thread:**Peter Fairbrother: "Re: public key crypto"**Reply:**Peter Fairbrother: "Re: public key crypto"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]