Re: Secure generation of primes

Subject: Re: Secure generation of primes
From: Peter Gutmann (pgut001cs.auckland.ac.nz)
Date: Tue Dec 07 1999 - 08:35:09 CST

• Next message: Ge' Weijers: "Re: Lucre fixed?"
• Previous message: Jeremey Barrett: "Re: ICQ security"
• Maybe in reply to: Jack Lloyd: "Secure generation of primes"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

lcs Mixmaster Remailer <mixanon.lcs.mit.edu> wrote:

>Ben Laurie:
>>BTW, it occurred to me that if you are going to generate safe primes
>>(i.e. primes p s.t. (p-1)/2 is prime) then you can sieve on p and
>>(p-1)/2 at the same time, which must be quite a win, but I haven't tried
>>it yet.

>Yes, this is absolutely the way to do it, and this method is used for
>example in the MPI library by Colin Plumb, used in PGP and cryptlib.
>The term used there is Sophie Germain primes, which actually refers to
>the smaller prime of the pair. Java used Colin's library but may not
>have exposed this functionality.

PGP 5, GPG, cryptlib, and probably various others now use the Lim-Lee algorithm
which generates primes of the form

  p = 2 * q * ( prime[1] * ... prime[n] ) + 1

This is much faster than generating Sophie Germain primes, and avoids various
attacks on DH (or actually on DLP-based PKC's in general). The X9.42 DH
will-eventually-become-a-standard-at-some-point recommends use of the DSA
kosheriser for DH keygen which IMHO is [2 pages of ranting deleted] but you can
make Lim-Lee keys look the same as kosheriser-generated keys since they produce
the same output values so it could be worse.

The Lim-Lee algorithm is described in "A key recovery attack on discrete
log-based schemes using a prime order subgroup", C.H. Lim and P.J. Lee, Crypto
'97, LNCS #1295. More considerations about things to watch out for in DH are
given in draft-ietf-smime-small-subgroup-03.txt, "Methods for Avoiding the
'Small-Subgroup' Attacks on the Diffie-Hellman Key Agreement Method for S/MIME"
(the name is a bit misleading, it's for DH in general but happens to be
published under the ietf-smime umbrella).

Peter.

• Next message: Ge' Weijers: "Re: Lucre fixed?"
• Previous message: Jeremey Barrett: "Re: ICQ security"
• Maybe in reply to: Jack Lloyd: "Secure generation of primes"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

This archive was generated by hypermail 2b27 : Mon Dec 06 1999 - 17:02:32 CST