Re: public key crypto

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

  • Next message: Roger Schlafly: "Crypto Mini-FAQ" 
    Date: Mon, 05 Jul 2004 16:48:09 +0100

    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; 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. 

    -- 
Peter Fairbrother
  • Next message: Roger Schlafly: "Crypto Mini-FAQ"

    Relevant Pages

    • Re: How to telnet commands automatically ?
      ... Peter T. Breuer wrote: ... one of the fastest RSA ... not authentication. ... > administration in your life ... ...
      (comp.os.linux.misc)
    • Re: Major new online resource: "Medieval Lands"
      ... My memory is that Cawley did not wish to receive comments on the format, ... I understood that he is willing to receive corrections. ... The discussion of Peter Orseolo that Cawley singled out for mention in his ... We see today that John Brandon ...
      (soc.genealogy.medieval)
    • Re: Do Children Learn Languages at Different Rates?
      ... > You've obviously never talked with a 3-year-old Cantonese speaker in ... > Peter> form until it's ready to learn irregular verb forms. ... you cannot teach older children irregular verb forms. ... and they learn from the corrections. ...
      (sci.lang)
    • Re: Do Children Learn Languages at Different Rates?
      ... > Peter> The context was not the nature of language. ... > Peter> making corrections. ...
      (sci.lang)
    • Re: Susanna & Sarah, Interchangeable?
      ... That he never checked sources and couldn't ... credited Frederick Lewis Weis as author, "with additions and corrections by ... Walter Lee Sheppard, Jr. ... Peter Stewart ...
      (soc.genealogy.medieval)
    • Quantcast