A New Class of Unsafe Primes

[coderman]

On 2/27/06, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:
> The IACR ePrint archive contains a paper from 2002 titled "A New Class of
> Unsafe Primes", http://eprint.iacr.org/2002/109, which proposes a fast way to
> find a prime factor p of an integer n when 4p - 1 has the form db^2, where d =
> { 3, 11, 19, 43, 67, 163 }.  I haven't been able to find any references to
> this anywhere, is this something like the p +/- 1 factoring methods where the
> values they're effective against are so unlikely that they can be safely
> ignored, or is it just that no-one's ever noticed this paper?

i'd be interested to know what you find out.

----

[[[
totally unrelated commentary:
i dreamed recently i was an old man with a failing liver
(E_TOO_MUCH_DEFCON)  performing one last bemused retrospective on life
before my session expired.  i chuckled over the use of public key
encryption in a world with common large qubit quantum computers: the
relative key strengths now in use were measured in killowatts of
computation sustained over a minimum time period for key pair
generation on dedicated hardware with open ended storage (meaning
whatever you could generate within a lifetime of key pair computation
could be stored reasonably on a common storage medium)

i recall a very strong key pair started at 64 kilowatts over 100 days
but was at least conjectured to require a coherent state (raw qubit
brute force) larger than anything possible to build in our solar
system.

nonces, digests, symmetric secrets and one time pads for key exchange
were all still measured in bytes though... *grin*
]]



something else of potential relevance:

---cut---

Date: Thu, 2 Jan 2003 11:23:21 -0800

From: Zully Ramzan <zramzan at ipdynamics.com>

To: Bill Stewart <bill.stewart at pobox.com>, Adam Shostack <adam at homeport.org>

Cc: cryptography at wasabisystems.com

Subject: RE: Implementation guides for DH?

Hi Bill --

> Stiglic's paper goes into a lot of explanation about
> some issues of safe parameters, particularly recommendations
> for sufficiently safe primes.  Much of the discussion on the net
> about prime safety for DH has been about whether safe primes
> are necessary or not worth the bother, and at least with the
> current methods for factoring, it's believed they aren't needed.
> (One catch, of course, is that the best factoring method
> 10 or 50 years from now may be affected by safe vs. unsafe primes.)
> At least in the initial Photuris versions, there were some
> standard choices of primes that everybody used,
> so it made sense to pick Sophie-Germain primes anyway.

I know there has been some discussion on whether _strong_ primes are
needed for _RSA_.  The definition of a strong prime is a little more
involved; c.f. the paper by Rivest and Silverman
[http://eprint.iacr.org/2001/007/  and also available on Ron Rivest's
web page].  I was unaware, though, that there is a debate regarding the
use of safe primes for Diffie-Hellman.  My impression is that the use of
safe primes is generally accepted to be an important practice that
thwarts various attempts to compute a discrete log (e.g.
Pohlig-Hellman); also enough safe primes and generators are published --
one may utilize them in a protocol (assuming the people who published
the list are trusted not to have deliberately chosen prime groups for
which computing a discrete log is easier :)).
I'm also not sure how the choice of primes for Diffie-Hellman relates to
the complexity of factoring as you mentioned in your post.  As far as I
know, no one (in the open community at least) has discovered a
meaningful reduction in a standard model between the Diffie-Hellman
problem over a prime group and Factoring (nor has anyone proven that
such reductions cannot exist).  The closest thing I can think of is
trying to come up with the factorization of p-1 as you might want to do
in the Pohlig-Hellman algorithm -- but in that case, the complexity
would be prohibitive if p-1 had any large prime factors...
Are you referring to performing Diffie-Hellman over some other group?
Or is there a connection that you know of and can elaborate on?
Best Regards,
Zully

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Zulfikar Ramzan
IP Dynamics, Inc.   http://www.ipdynamics.com
Secure, Scalable Virtual Community Networks
---------------------------------------------------------------------
---end cut---