[30643] in cryptography@c2.net mail archive
Re: Factorization polynomially reducible to discrete log - known
daemon@ATHENA.MIT.EDU (David Wagner)
Wed Jul 12 13:11:41 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: David Wagner <daw@cs.berkeley.edu>
To: goober@ksp.sk (Peter Kosinar)
Date: Wed, 12 Jul 2006 09:55:34 -0700 (PDT)
Cc: daw@cs.berkeley.edu (David Wagner), ondrej.mikle@gmail.com,
cryptography@metzdowd.com
In-Reply-To: <Pine.LNX.4.62.0607121553350.29350@element.ksp.sk> from "Peter Kosinar" at Jul 12, 2006 05:49:40 PM
> > The algorithm is very simple:
> > 1. Choose a big random value x from some very broad range
> > (say, {1,2,..,N^2}).
> > 2. Pick a random element g (mod N).
> > 3. Compute y = g^x (mod N).
> > 4. Ask for the discrete log of y to the base g, and get back some
> > answer x' such that y = g^x' (mod N).
> > 5. Compute x-x'. Note that x-x' is a multiple of phi(N), and
> > it is highly likely that x-x' is non-zero. It is well-known
> > that given a non-zero multiple of phi(N), you can factor N in
> > polynomial time.
>
> Not exactly. Consider N = 3*7 = 21, phi(N) = 12, g = 4, x = 2, x' = 5.
> You'll only get a multiple of phi(N) if g was a generator of the
> multiplicative group Z_N^*.
When N is a large RSA modulus, there is a non-trivial probability that g
will be a generator (or that g will be such that x-x' lets you factor N).
The above is good enough for a polytime reduction.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
