[30652] in cryptography@c2.net mail archive
Re: Factorization polynomially reducible to discrete log - known
daemon@ATHENA.MIT.EDU (Ondrej Mikle)
Wed Jul 12 14:34:58 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 12 Jul 2006 20:02:43 +0200
From: Ondrej Mikle <ondrej.mikle@gmail.com>
To: David Wagner <daw@cs.berkeley.edu>,
Peter Kosinar <goober@ksp.sk>, cryptography@metzdowd.com
In-Reply-To: <200607121655.k6CGtYbX025002@taverner.cs.berkeley.edu>
David Wagner wrote:
>>> 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.
>
Actually, you can never get a generator of Z_N^* unless p=q, because
when p != q, it is not a cyclic group (this error was in my proof, too).
Though with great probability you get an element of high order. It is
enough doing lcm() to get the phi(N) and it will run in polynomial time.
I noted the fact IFP(N) to DLOG in Z_N^* is really mentioned in Handbook
of Applied Crypto, but without proof or algorithm, just two lines (I
guess that's why I missed/didn't remember it).
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
