Factorization polynomially reducible to discrete log - known

[Ondrej Mikle]

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 at metzdowd.com