[3896] in cryptography@c2.net mail archive
Re: Large Primes
daemon@ATHENA.MIT.EDU (Wei Dai)
Sun Jan 3 20:28:22 1999
Date: Sun, 3 Jan 1999 16:17:13 -0800
From: Wei Dai <weidai@eskimo.com>
To: William Allen Simpson <wsimpson@greendragon.com>
Cc: Cryptography List <cryptography@c2.net>
In-Reply-To: <11727.wsimpson@greendragon.com>; from William Allen Simpson on Sun, Jan 03, 1999 at 07:48:11PM +0000
On Sun, Jan 03, 1999 at 07:48:11PM +0000, William Allen Simpson wrote:
> This generates "safe" primes, rather than "strong" primes.
>
> I meant to put this in a RFC someday, but it would be nice to know
> whether I'd done something wrong first.... Any problems/suggestions?
This code is kind of hard to understand. I couldn't figure out why you're
using three sieves (large, small, and tiny). Also, your sieve appears to
sieve candidates for p that are 3 mod 4, but you only need to sieve
integers that are 11 mod 12.
You might want to take a look at the safe prime generation code in
Crypto++ 3.0 (see the first constructor of PrimeAndGenerator in
nbtheory.cpp). The sieving code there is influenced by Colin Plumb's
bignum library.
// generate a safe prime with Crypto++
#include <iostream>
#include <rng.h>
#include <dh.h>
void main()
{
CryptoPP::LC_RNG rng(321);
CryptoPP::DH dh(rng, 1024);
std::cout << "p = " << dh.Prime() << std::endl;
std::cout << "g = " << dh.Generator() << std::endl;
}
