Re: are RFC 3526 primes "safe"? (Re: [Ietf-krb-wg] RFC 4556 DH parameter oddities)

On Tue, Mar 13, 2012 at 10:04 PM, Jon Callas <jon <at> callas.org> wrote:
> On Mar 13, 2012, at 7:09 PM, Tom Yu wrote:
>> Also, could someone with better number theory and/or cryptography
>> experience than me please confirm whether the RFC 3526 primes are
>> indeed safe primes?
>
> What would make them non-safe primes?
>
> I'm not being dismissive, I want to know what the concern is.
>
> Is this related to the weak RSA key brou-ha-ha? Or is it just a matter of making sure that they've been
properly vetted not to have number-theoretic issues?

These are DH groups though, so this is not about the RSA common primes problem.

DH MODP groups generally need to have safe primes, or so I understand.  E.g.,

http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

which says

"The order of G should be prime or have a large prime factor to
prevent use of the Pohlig–Hellman algorithm to obtain a or b. For this
reason, a Sophie Germain prime q is sometimes used to calculate
p=2q+1, called a safe prime, since the order of G is then only
divisible by 2 and q. g is then sometimes chosen to generate the order
q subgroup of G, rather than G, so that the Legendre symbol of ga
never reveals the low order bit of a."

I believe Tom is asking whether the primes in RFC3526 are safe in this sense:

http://en.wikipedia.org/wiki/Safe_prime

I suppose the answer is: subtract 1, div 2, confirm that the result is
Sophie Germain prime.

I thought of checking the form of the primes myself, but I don't know
what " { [2^1406 pi] + 741804 }" means in this (from RFC3526):

"
   The prime is: 2^1536 - 2^1472 - 1 + 2^64 * { [2^1406 pi] + 741804 }
"

Nico
--

-- 

Nico
--
_______________________________________________
saag mailing list
saag <at> ietf.org
https://www.ietf.org/mailman/listinfo/saag