On 2/27/06, Peter Gutmann <pgut001@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@ipdynamics.com> To: Bill Stewart <bill.stewart@pobox.com>, Adam Shostack <adam@homeport.org> Cc: cryptography@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---