Re: [TLS] I can has SHA-1 hashes for RFC 2409/3526 MODP groups?

[Henrick Hellström <[e-mail]>]

On 2014-02-28 22:22, Geoffrey Keating wrote:
> I'd encourage you to do the derivation again: compute
>
> 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
>
> and verify that it's prime.  I don't think any special security
> measures were taken during the creation of RFC 3526, you'd think by
> now someone would have noticed if the 'primes' weren't prime or didn't
> match the claimed polynomial, but if everyone thinks someone else has
> checked...

There is more.

1. The MODP primes are supposed to be safe primes (i.e. primes on the 
form p = 2q+1 where q is also prime). Furthermore, 2 will be a generator 
of the large sub group of order q, rather than of the entire 
multiplicative group of order 2q.

2. Pi might be calculated using the Bailey–Borwein–Plouffe formula. I 
calculated it for the first 2048 hexadecimal digits, which was a 
sufficiently good approximation for all of the MODP groups up to the 
8192 bit one.

3. All of the MODP primes are on the form p = 2^n - 2^(n-64) + 2^64( 
[2^(n-130)pi] + k). The value k is supposed to be the least positive 
integer, such that p is a safe prime. This check is important, to rule 
out that any candidates have been deliberately skipped, because they 
lack some (hidden) property.

I have generated the primes 1024, 2048, 3072, 4096, 6144 and 8192 from 
the formulae and verified that:
a: The numbers match the numbers in the RFCs.
b: The numbers are safe primes (using both Miller-Rabin tests and Lucas 
tests on q = (p-1)/2, and then the Pocklington Criterion on p).
c: The small constant k is indeed the least positive integer such that 
the number is a safe prime. (Well, to be honest I am still running this 
test for the largest group, just make sure once more.)