Re: [Cfrg] Unknown order DH groups, e.g. as in RFC3526.

Hi Andrey,

It is true that RFC 3526 does not explicitly give out the group orders
-- these are safe primes. I recall when my late colleague at SSH, Mika
Kojo computed (or "found") them some 20 years ago -- they were
published posthumously and that's probably why such mathematical
details are missing. You can run a primality test of your choosing on
each (p-1)/2 to verify this if you like.

All of this, including Diffie-Hellman in a basically any group, is of
course of historical interest only.. but let me expand on this for
posteriority:

It is (or at least used to be) "common knowledge" that the MODP groups
(including RFC3526) were based on Sophie Germain primes, i.e. primes
of type p=2q+1 where q is also a prime. Therefore the group order of
any element x that is coprime with p can only be one of {1, 2, q,
2*q}. The latter two classes correspond to quadratic residues and
quadratic non-residues. There are O(log a log b) algorithms for
Legendre/Jacobi symbol so the group order of any element can be
efficiently evaluated if you accept that p is a "S.G." prime. In most
cases it is sufficient to check that x mod p is not one of { 0, 1, p-1
}, meaning that the group order is at least q -- the quadratic residue
check will only reveal the least significant bit of a secret exponent
-- if the generator happens to be a q.n.r.

Cheers,
- markku

Dr. Markku-Juhani O. Saarinen <mjos@iki.fi>

On Fri, Mar 8, 2019 at 11:17 PM Andrey Jivsov <crypto@brainhub.org> wrote:
>
> Sorry, a correction: https://tools.ietf.org/html/rfc7919 is the RFC that defines safe primes, and thus the group order is (p-1)/2 for each of them.
>
> What's the group order for random primes in https://tools.ietf.org/html/rfc3526 ? Do you mean the composite group order p-1 with potentially unpleasant many-small-factors factorization?
>
> On Fri, Mar 8, 2019 at 2:59 PM Scott Fluhrer (sfluhrer) <sfluhrer@cisco..com> wrote:
>>
>> I suspect you mistyped the RFC number you meant; instead of saying that the groups listed in RFC3526 didn’t specify an order (they do), you meant to talk about the groups in some other RFC…
>>
>>
>>
>> From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Andrey Jivsov
>> Sent: Friday, March 08, 2019 5:44 PM
>> To: cfrg@irtf.org
>> Subject: [Cfrg] Unknown order DH groups, e.g. as in RFC3526.
>>
>>
>>
>> Greetings.
>>
>>
>>
>> A quick question on DH primes.
>>
>>
>>
>> The IKE DH groups document didn't specify the group order https://tools.ietf.org/html/rfc3526 .
>>
>>
>>
>> This is in contrast to https://tools.ietf.org/html/rfc3526 that uses safe primes.
>>
>>
>>
>> Is my understanding correct that, as a general rule, these primes should not be used, e.g. where a contributory behaviour of DH is needed? The issue here is that a random element, received from a peer, can be in any subgroup, possibly in a subroup with lower security than 128 bits, and there is no way to verify this efficiently.
>>
>>
>>
>> Thank you.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg