[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Proposal for new DH Groups 6, 7, and 8
There was much discussion at the recent bakeoff regarding DH prime
lengths. It was good to see that a number of people were implementing
Group 5, and all but one vendor that I found anyway (who actually changed
this during the bakeoff I believe) was doing at least Group 2.
However, as was raised at the Wednesday meeting, even Group 5 can be
considered too short -- especially as we forge ahead into 256 bit ciphers
wherein it is painfully inadequate.
I would like to propose three new DH Groups for IKE of 2048, 3072, and
4096 bits. This should adequately cover all foreseeable future needs. I
have included documentation on the generation of these primes which were
originally generated for PGPfone, and there is an interesting story about
how they were generated at the end of this message.
I know I should really write this up as a draft, but for now I just want
to float this here to get any feedback. The generator is 2 for all of
these primes.
Group ID: 6 (Note this is not officially assigned yet)
DH_2048bitPrime = {
0xF6, 0x42, 0x57, 0xB7, 0x08, 0x7F, 0x08, 0x17,
0x72, 0xA2, 0xBA, 0xD6, 0xA9, 0x42, 0xF3, 0x05,
0xE8, 0xF9, 0x53, 0x11, 0x39, 0x4F, 0xB6, 0xF1,
0x6E, 0xB9, 0x4B, 0x38, 0x20, 0xDA, 0x01, 0xA7,
0x56, 0xA3, 0x14, 0xE9, 0x8F, 0x40, 0x55, 0xF3,
0xD0, 0x07, 0xC6, 0xCB, 0x43, 0xA9, 0x94, 0xAD,
0xF7, 0x4C, 0x64, 0x86, 0x49, 0xF8, 0x0C, 0x83,
0xBD, 0x65, 0xE9, 0x17, 0xD4, 0xA1, 0xD3, 0x50,
0xF8, 0xF5, 0x59, 0x5F, 0xDC, 0x76, 0x52, 0x4F,
0x3D, 0x3D, 0x8D, 0xDB, 0xCE, 0x99, 0xE1, 0x57,
0x92, 0x59, 0xCD, 0xFD, 0xB8, 0xAE, 0x74, 0x4F,
0xC5, 0xFC, 0x76, 0xBC, 0x83, 0xC5, 0x47, 0x30,
0x61, 0xCE, 0x7C, 0xC9, 0x66, 0xFF, 0x15, 0xF9,
0xBB, 0xFD, 0x91, 0x5E, 0xC7, 0x01, 0xAA, 0xD3,
0x5B, 0x9E, 0x8D, 0xA0, 0xA5, 0x72, 0x3A, 0xD4,
0x1A, 0xF0, 0xBF, 0x46, 0x00, 0x58, 0x2B, 0xE5,
0xF4, 0x88, 0xFD, 0x58, 0x4E, 0x49, 0xDB, 0xCD,
0x20, 0xB4, 0x9D, 0xE4, 0x91, 0x07, 0x36, 0x6B,
0x33, 0x6C, 0x38, 0x0D, 0x45, 0x1D, 0x0F, 0x7C,
0x88, 0xB3, 0x1C, 0x7C, 0x5B, 0x2D, 0x8E, 0xF6,
0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x32, 0x0B, 0x3B
};
Group ID: 7 (Note this is not officially assigned yet)
DH_3072bitPrime = {
0xCC, 0x1D, 0x77, 0x57, 0x24, 0x38, 0x4A, 0xE2,
0xC4, 0xF0, 0xE8, 0x8E, 0x13, 0x67, 0x97, 0x4E,
0x92, 0x13, 0x61, 0xF6, 0xDB, 0xEB, 0x25, 0x0E,
0x17, 0xFD, 0xF6, 0x98, 0xF7, 0xC8, 0x7C, 0x79,
0xB0, 0x72, 0x1D, 0x38, 0x75, 0xFB, 0xF6, 0xC1,
0x73, 0xC4, 0x83, 0x11, 0x26, 0x2B, 0x43, 0x60,
0xC3, 0xE3, 0xE8, 0xD6, 0x0A, 0xFD, 0xA1, 0x28,
0x26, 0x0B, 0xAE, 0xA9, 0xAE, 0xB3, 0x65, 0x0F,
0xA2, 0x00, 0x53, 0x01, 0xA0, 0x7C, 0xD6, 0xAB,
0xA3, 0x12, 0x1E, 0xFA, 0x0F, 0x2A, 0xCE, 0x1F,
0x74, 0x84, 0x4F, 0xCA, 0xF3, 0x17, 0xF3, 0xA4,
0x40, 0xE9, 0xD7, 0xD2, 0x77, 0xB6, 0x42, 0x2D,
0x02, 0x36, 0xC1, 0x26, 0xCB, 0x68, 0x5E, 0x9D,
0x7C, 0x98, 0x09, 0x0A, 0x8D, 0x7E, 0x2D, 0xED,
0xE4, 0x5D, 0x79, 0xF5, 0xD4, 0x92, 0x4F, 0x9B,
0x18, 0x8E, 0xFC, 0x2A, 0xA7, 0x4B, 0x7C, 0x32,
0xF6, 0x42, 0x57, 0xB7, 0x08, 0x7F, 0x08, 0x17,
0x72, 0xA2, 0xBA, 0xD6, 0xA9, 0x42, 0xF3, 0x05,
0xE8, 0xF9, 0x53, 0x11, 0x39, 0x4F, 0xB6, 0xF1,
0x6E, 0xB9, 0x4B, 0x38, 0x20, 0xDA, 0x01, 0xA7,
0x56, 0xA3, 0x14, 0xE9, 0x8F, 0x40, 0x55, 0xF3,
0xD0, 0x07, 0xC6, 0xCB, 0x43, 0xA9, 0x94, 0xAD,
0xF7, 0x4C, 0x64, 0x86, 0x49, 0xF8, 0x0C, 0x83,
0xBD, 0x65, 0xE9, 0x17, 0xD4, 0xA1, 0xD3, 0x50,
0xF8, 0xF5, 0x59, 0x5F, 0xDC, 0x76, 0x52, 0x4F,
0x3D, 0x3D, 0x8D, 0xDB, 0xCE, 0x99, 0xE1, 0x57,
0x92, 0x59, 0xCD, 0xFD, 0xB8, 0xAE, 0x74, 0x4F,
0xC5, 0xFC, 0x76, 0xBC, 0x83, 0xC5, 0x47, 0x30,
0x61, 0xCE, 0x7C, 0xC9, 0x66, 0xFF, 0x15, 0xF9,
0xBB, 0xFD, 0x91, 0x5E, 0xC7, 0x01, 0xAA, 0xD3,
0x5B, 0x9E, 0x8D, 0xA0, 0xA5, 0x72, 0x3A, 0xD4,
0x1A, 0xF0, 0xBF, 0x46, 0x00, 0x58, 0x2B, 0xE5,
0xF4, 0x88, 0xFD, 0x58, 0x4E, 0x49, 0xDB, 0xCD,
0x20, 0xB4, 0x9D, 0xE4, 0x91, 0x07, 0x36, 0x6B,
0x33, 0x6C, 0x38, 0x0D, 0x45, 0x1D, 0x0F, 0x7C,
0x88, 0xB3, 0x1C, 0x7C, 0x5B, 0x2D, 0x8E, 0xF6,
0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
0xA2, 0x5E, 0xC3, 0x55, 0xE9, 0x4C, 0x32, 0x6F
};
Group ID: 8 (Note this is not officially assigned yet)
DH_4096bitPrime = {
0xF9, 0x18, 0xA0, 0x7E, 0x5A, 0x06, 0x61, 0x7A,
0x43, 0x90, 0x95, 0xDC, 0x05, 0x6C, 0x87, 0x86,
0xEC, 0x61, 0xEC, 0xCD, 0x45, 0x1F, 0x0E, 0xD8,
0xE0, 0xA3, 0x79, 0xC6, 0xC9, 0xDC, 0x7A, 0x0B,
0xAC, 0xE4, 0x3F, 0xE3, 0x46, 0x94, 0xB6, 0x30,
0x4A, 0x53, 0xD7, 0x7C, 0x02, 0x16, 0x48, 0x80,
0xB5, 0x15, 0xE5, 0x29, 0x99, 0xA9, 0x9F, 0x07,
0x74, 0xD3, 0xFF, 0xE3, 0xA1, 0xC5, 0x96, 0x20,
0x4E, 0x98, 0x65, 0xB8, 0xD8, 0x0D, 0xEE, 0x10,
0x5D, 0xAB, 0xB6, 0x17, 0x1C, 0x51, 0xD8, 0x50,
0xCA, 0x22, 0x57, 0x43, 0x29, 0xBE, 0x95, 0xE8,
0x56, 0x2B, 0x38, 0x78, 0x5C, 0x0B, 0xDB, 0xF8,
0x4C, 0x4D, 0xD5, 0xE3, 0xAA, 0x46, 0xCC, 0xFB,
0xCE, 0x17, 0xE8, 0x2A, 0x9D, 0x14, 0x61, 0xE3,
0x84, 0xA9, 0x4F, 0xD1, 0x83, 0x84, 0xA8, 0x79,
0xB6, 0xEF, 0x8F, 0xA7, 0x43, 0x46, 0x08, 0xC6,
0xCC, 0x1D, 0x77, 0x57, 0x24, 0x38, 0x4A, 0xE2,
0xC4, 0xF0, 0xE8, 0x8E, 0x13, 0x67, 0x97, 0x4E,
0x92, 0x13, 0x61, 0xF6, 0xDB, 0xEB, 0x25, 0x0E,
0x17, 0xFD, 0xF6, 0x98, 0xF7, 0xC8, 0x7C, 0x79,
0xB0, 0x72, 0x1D, 0x38, 0x75, 0xFB, 0xF6, 0xC1,
0x73, 0xC4, 0x83, 0x11, 0x26, 0x2B, 0x43, 0x60,
0xC3, 0xE3, 0xE8, 0xD6, 0x0A, 0xFD, 0xA1, 0x28,
0x26, 0x0B, 0xAE, 0xA9, 0xAE, 0xB3, 0x65, 0x0F,
0xA2, 0x00, 0x53, 0x01, 0xA0, 0x7C, 0xD6, 0xAB,
0xA3, 0x12, 0x1E, 0xFA, 0x0F, 0x2A, 0xCE, 0x1F,
0x74, 0x84, 0x4F, 0xCA, 0xF3, 0x17, 0xF3, 0xA4,
0x40, 0xE9, 0xD7, 0xD2, 0x77, 0xB6, 0x42, 0x2D,
0x02, 0x36, 0xC1, 0x26, 0xCB, 0x68, 0x5E, 0x9D,
0x7C, 0x98, 0x09, 0x0A, 0x8D, 0x7E, 0x2D, 0xED,
0xE4, 0x5D, 0x79, 0xF5, 0xD4, 0x92, 0x4F, 0x9B,
0x18, 0x8E, 0xFC, 0x2A, 0xA7, 0x4B, 0x7C, 0x32,
0xF6, 0x42, 0x57, 0xB7, 0x08, 0x7F, 0x08, 0x17,
0x72, 0xA2, 0xBA, 0xD6, 0xA9, 0x42, 0xF3, 0x05,
0xE8, 0xF9, 0x53, 0x11, 0x39, 0x4F, 0xB6, 0xF1,
0x6E, 0xB9, 0x4B, 0x38, 0x20, 0xDA, 0x01, 0xA7,
0x56, 0xA3, 0x14, 0xE9, 0x8F, 0x40, 0x55, 0xF3,
0xD0, 0x07, 0xC6, 0xCB, 0x43, 0xA9, 0x94, 0xAD,
0xF7, 0x4C, 0x64, 0x86, 0x49, 0xF8, 0x0C, 0x83,
0xBD, 0x65, 0xE9, 0x17, 0xD4, 0xA1, 0xD3, 0x50,
0xF8, 0xF5, 0x59, 0x5F, 0xDC, 0x76, 0x52, 0x4F,
0x3D, 0x3D, 0x8D, 0xDB, 0xCE, 0x99, 0xE1, 0x57,
0x92, 0x59, 0xCD, 0xFD, 0xB8, 0xAE, 0x74, 0x4F,
0xC5, 0xFC, 0x76, 0xBC, 0x83, 0xC5, 0x47, 0x30,
0x61, 0xCE, 0x7C, 0xC9, 0x66, 0xFF, 0x15, 0xF9,
0xBB, 0xFD, 0x91, 0x5E, 0xC7, 0x01, 0xAA, 0xD3,
0x5B, 0x9E, 0x8D, 0xA0, 0xA5, 0x72, 0x3A, 0xD4,
0x1A, 0xF0, 0xBF, 0x46, 0x00, 0x58, 0x2B, 0xE5,
0xF4, 0x88, 0xFD, 0x58, 0x4E, 0x49, 0xDB, 0xCD,
0x20, 0xB4, 0x9D, 0xE4, 0x91, 0x07, 0x36, 0x6B,
0x33, 0x6C, 0x38, 0x0D, 0x45, 0x1D, 0x0F, 0x7C,
0x88, 0xB3, 0x1C, 0x7C, 0x5B, 0x2D, 0x8E, 0xF6,
0xF3, 0xC9, 0x23, 0xC0, 0x43, 0xF0, 0xA5, 0x5B,
0x18, 0x8D, 0x8E, 0xBB, 0x55, 0x8C, 0xB8, 0x5D,
0x38, 0xD3, 0x34, 0xFD, 0x7C, 0x17, 0x57, 0x43,
0xA3, 0x1D, 0x18, 0x6C, 0xDE, 0x33, 0x21, 0x2C,
0xB5, 0x2A, 0xFF, 0x3C, 0xE1, 0xB1, 0x29, 0x40,
0x18, 0x11, 0x8D, 0x7C, 0x84, 0xA7, 0x0A, 0x72,
0xD6, 0x86, 0xC4, 0x03, 0x19, 0xC8, 0x07, 0x29,
0x7A, 0xCA, 0x95, 0x0C, 0xD9, 0x96, 0x9F, 0xAB,
0xD0, 0x0A, 0x50, 0x9B, 0x02, 0x46, 0xD3, 0x08,
0x3D, 0x66, 0xA4, 0x5D, 0x41, 0x9F, 0x9C, 0x7C,
0xBD, 0x89, 0x4B, 0x22, 0x19, 0x26, 0xBA, 0xAB,
0xA2, 0x5E, 0xC3, 0x55, 0xEB, 0x3D, 0xD6, 0x17
};
The following section could use some editing. These primes are being
proposed for IPsec, but I wanted to include documentation on the creation
of the primes at this time, and said documentation already existed in the
somewhat rough form below.
----------------------------
How PGPfone's DH Primes Were Derived
This section written by Colin Plumb.
PGPfone uses Diffie-Hellman key exchange to decide on a session key for
communication. Diffie-Hellman requires a prime modulus to work with.
(Note that this is unlike RSA, which uses a modulus which is the product
of two primes.) This note explains how these primes are computed.
"Kosherized" Primes
The security of the Diffie-Hellman exponential key agreement depends on
the difficulty of computing discrete logarithms. It has been suggested
that it may be possible to contrive a prime modulus such that it is easier
to compute discrete logs in that modulus’s field.
This is one reason why some have suggested that rather than trust a prime
generated by someone else, it is better to generate your own prime. This
approach can lead to a massive proliferation of primes in use in a
community of Diffie-Hellman users. But there are advantages in having
everyone use a small common set of well-known public primes. It makes key
management easier, and allows precomputation of the first phase of the
Diffie-Hellman exchange, which speeds things up.
The Diffie-Hellman primes used by PGPfone were derived in such a way that
anyone may independently verify that the primes were not contrived to make
it any easier to compute discrete logs. Thus, there is no reason why
everyone can’t trust the prime numbers selected for PGPfone. We will
describe here exactly how these primes were derived.
The prime generation is a variant of the technique for DSS prime
generation suggested by David Kravitz (of NSA, at that time) and
recommended by NIST. It is based on SHA and an arbitrary seed. Kravitz
calls this process "kosherizing the primes".
SHA is the NIST standard Secure Hash Algorithm with a 160-bit output. It
is widely believed in cryptographic circles that it is computationally
infeasible to choose an input value for SHA that will produce some chosen
output hash. We refer to the hash algorithm throughout this document as
SHA, even though it is actually the NIST-revised SHA, known as SHA-1.
Careful prime generation is significant to Diffie-Hellman because the
security of Diffie-Hellman key exchange rests on the difficulty of the
discrete log problem: given y, g and p, find x such that y = g^x mod p.
This is, in general, very difficult.
However, there are certain "cooked" primes p such that this is
comparatively easy to solve. These "cooked" primes are very rare - given
a random prime p, the chance that it is cooked is so small as to not be
worth worrying about. So to choose a prime and be convinced that it is
not cooked, it suffices to choose a prime from a given range in a manner
that prevents anyone from forcing the choice to one of the rare "cooked" values.
This is where SHA comes in. By using SHA to generate the primes, it is
possible to show the impossibility of steering the prime-selection process
to one of the rare "cooked" values, since it's not possible to steer the
output of SHA.
Since SHA generates 160-bit outputs, and we want larger primes (such as
2048 bits), we need to use SHA multiple times. The first invocation of
SHA generates the low 160 bits of the number. The next invocation
generates the next lowest 160 bits, and so on, until enough bits are
available. For example, a number of up to 1024 bits can be generated as follows:
( SHA(seed1) + 2^160 * SHA(seed2) + 2^320 * SHA(seed3) + 2^480 *
SHA(seed4) + 2^640 * SHA(seed6) + 2^800 * SHA(seed7) + 2^960 * SHA(seed8)
) mod 2^1024
The sum inside the parentheses generates a number 7*160 = 1120 bits long.
The modulo operation throws away the extra 96 bits that aren't needed.
The only thing needed here is 7 seed values. What the seed values are is
unimportant, as long as they are published so that anyone may verify the
fact that the number is generated by SHA.
(The 20-byte SHA output is treated as a big-endian number for the purpose
of these computations.)
For PGPfone, the seed1 value is an ASCII string of a recognizable phrase.
seed2 is created by incrementing the last byte of the phrase by 1. seed3
is created from seed2 by incrementing the byte again, et cetera.
PGPfone uses 5 user-selectable primes derived from the seed, of different
sizes: 512, 768, 1024, 1536, and 2048 bits. For the initial release of
PGPfone, the seed phrase is an ASCII string containing a quote from
Mahatma Gandhi: "Whatever you do will be insignificant, but it is very
important that you do it."
After the number is created, a few changes are made to it:
- The most significant bit is set, to ensure that the number is really
1024 bits long (or however many bits are desired).
- The second most significant bit is set to make the number larger. The
effort of performing Diffie-Hellman computations depends almost
exclusively on the number of significant bits in the number. There is no
real difference between high 1024-bit numbers close to 2^1024-1 and low
1024-bit numbers close to 2^1023. The effort of solving the discrete log
problem, however, depends more heavily on the value of the number, so
picking primes from the high half of the 1024-bit range provides slightly
better security at no cost.
Then this number is used as a starting value for a sequential prime
search. The first suitable prime greater than or equal to the starting
number is the generated prime.
"Suitable prime" is stronger than just "prime". For a prime p to be
suitable, (p-1)/2 must also be prime. If this is true, then the generator
g in the Diffie-Hellman computation can be chosen to be 2 without any loss
of security. This choice speeds up computation with the prime, so as
primes are generated rarely but used often, the extra effort taken to find
a "suitable" prime is amply repaid.
Comparison with Kravitz's technique
David Kravitz originally designed his technique for generation of primes
for the NIST Digital Signature Standard (DSS). DSS requires two primes,
so seed1 and seed2 were used to generate the small prime, and the large
prime was generated using seed3 and upwards. Since we only have one
prime, we start with seed1.
There was also a modular relationship required between the smaller and the
larger prime, which Kravitz' technique enforced by decreasing the large
prime to make the relationship hold. That does not apply to this
operation and is omitted.
The seed1, seed2, etc. generation using incrementing is exactly as in
Kravitz's original design.
Kravitz did not set the second highest bit. That is a simple modification
to make things slightly more difficult for an attacker.
The most significant difference is that Kravitz didn't generate a starting
value and do a sequential search for a prime; his technique kept using
more seed values to generate more random numbers, which were then tested
for primality.
His technique has some mathematical elegance advantages, in particular a
sequential search produces some primes (those with a long gap between them
and the previous suitable prime) more often than others (those which
closely follow the previous suitable prime), but the change is quite
minor, and definitely not significant for Diffie-Hellman primes.
(Diffie-Hellman primes aren't secret, so it isn't important to pick as
randomly as possible to make guessing difficult.) The advantage is that
sequential numbers can be tested for primality much faster than random
numbers. Prime generation is slow enough already; it doesn't need to be
made any slower.
Implementation details
This section describes the implementation of the search, for those who
wish to follow the supplied code and verify that it performs the
operations described above.
Generating the initial random number is straightforward enough. Searching
for suitable primes, however, is the subject of a great deal of
optimization. The prime search proceeds in two steps: sieving and testing.
First note that we are looking for a prime p such that q = (p-1)/2 is
prime. Thus, q must be odd and p must be congruent to 3 mod 4.
Further, neither q nor p = 2*q+1 may be congruent to 0 modulo 3. The
constraint on p means that q may not be congruent to 1 modulo 3, so q must
be congruent to 2 modulo 3. Combining this with the fact that q must be
odd implies that q must be congruent to 5 modulo 6. p must, therefore, be
congruent to 11 modulo 12.
The first step is to take the initial number s, find (s-1)/2, and round it
up until it is congruent to 5 modulo 6. This number is n1. Searching for
q proceeds in steps of 6 from this base. n2 = 2*n1+1 is the base for the
search for p, which proceeds in steps of 12.
To perform the sieving, a large bit array (65536 bits, or 8192 bytes) is
allocated. Bit i of the array will be cleared if either of n1+6*i or
n2+12*i have small divisors.
The small divisor test is performed by initially setting the array to all
ones, and then for each prime divisor d up to 65536 (since we are stepping
by 6 = 2*3, 2 and 3 are excluded), n1 modulo d is computed, and the
remainder used in a bit of computation to find the first index i such that
n1+6*i is divisible by d. Then every dth bit from that point onwards in
the array is cleared. Bits for which n2+12*i is divisible by d are
cleared similarly. n2 modulo d can be computed from n1 modulo d, by
doubling and adding 1, so the computation is very easy.
After that, the bit array is walked through looking for set bits, which
indicate possible primes q and p. At least, each candidate c1 has no
small prime factors, and c2 = 2*c1+1 has no small prime factors. For each
candidate pair, a Fermat test to the base 2 of c2 is performed. i.e. we
check if 2^(c2-1) == 1 (mod c2). If not, a dot is printed and the next
candidates are sought.
If we reach the end of the array, the starting number n1 is increased by
6*65536 and the process repeats. The search never gives up. A slash (/)
is printed when the bit array is exhausted like this.
The exponentiation 2^x (mod m) is handled in specially optimized code that
takes advantage of the simplifications allowed by using 2 as a base.
If the first Fermat test is passed, a "+" or "-" is printed, depending on
some slightly arcane mathematical property. (It's the sign of 2^c1 mod
c2, which is +1 or -1 if the test is passed.) Then a second Fermat test
is performed, this time on c1, to see if 2^(c1-1) == 1 (mod c1). If not,
a dot is printed and the search resumes.
If the second test is passed, we have found a suitable prime. An asterisk
(*) is printed to indicate success. But since the primality tests have a
(ridiculously low) chance of failing, some extra "confirmation" tests on
both c1 and c2 are performed. An asterisk is printed after each of these
is completed, too. Three confirmation tests are performed on each of c1
and c2, so a total of seven asterisks are printed.
(In the case that a confirmation test fails, a dot is printed and the
search is resumed, but this is not going to happen in your lifetime.)
At the end of this, c2 is the suitable prime p that is sought.
---------------------
The above section was written by Colin Plumb.
--
Will Price, Director of Engineering
PGP Security, Inc.
a division of Network Associates, Inc.
Direct (408)346-5906
Cell/VM (650)533-0399
Follow-Ups: