[30651] in cryptography@c2.net mail archive
Re: Factorization polynomially reducible to discrete log - known
daemon@ATHENA.MIT.EDU (Peter Kosinar)
Wed Jul 12 14:34:37 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 12 Jul 2006 19:43:11 +0200 (CEST)
From: Peter Kosinar <goober@ksp.sk>
To: David Wagner <daw@cs.berkeley.edu>
Cc: cryptography@metzdowd.com
In-Reply-To: <200607121655.k6CGtYbX025002@taverner.cs.berkeley.edu>
>> 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.
You're absolutely right, although the probability actually does not depend
on the size of the modulus (in fact, the provable lower bound on this
probability goes down with size of the modulus), as it depends only on the
factorization of phi(N) which, in turn, might depend on the process used
to choose the factors of the modulus (e.g. sometimes-suggested approach of
using Sophie-Germain primes creates abundance of generators; whereas some
primorial-like construction might decrease it).
Peter
--
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
