Are the RFC3526 MODP groups Schnorr groups?

Question

I was wondering if a group like the 1536-bit MODP Group from RFC 3526 was a Schnorr group?

A Schnorr group must apparently have:

• $p$ and $q$ being primes
• $p = q\cdot r+1$
• $1 < h < p$
• $h^r\not\equiv 1\pmod p$

And then $g = h^r\bmod p$ is the generator.

In RFC3526's 1536-bit MODP, there's a prime: $$2^{1536}-2^{1472}-1+2^{64}\cdot\lfloor2^{1406}\cdot\text{pi}+741804\rfloor$$ ^{(not too sure what $\text{pi}$ is here)}
and the generator is $g=2$.

My question is if such a group is a Schnorr group or not?

If it's a Schnorr group, what are the values or $p$, $q$, $r$ and $h$?

References:
RFC3526 MODP Diffie-Hellman groups for IKE
en.wikipedia.org/wiki/Schnorr_group

Answer 1

Yes, it meets the formal definition of a Schnorr group; however it was constructed somewhat differently. Normally, when we generate a Schnorr group, we pick a prime $q$, and then search for an $r$ so that $qr+1$ is also prime; with the RFC3526 group, they picked $p$ and $q$ simultaneously. In addition, when it came to selecting the generator, they did not select the value $h$ and compute $g$ from that. Instead, they selected $p$ such that $g=2$ generated a prime subgroup.

As for the values you asked about:

$$p = 2^{1536} - 2^{1472} - 1 + 2^{64} * \lfloor 2^{1406} \pi + 741804 \rfloor$$

(and yes, $pi = \pi$ is everyone's favorite transcendental number)

$$q = (p-1)/2$$

$$r = 2$$

$$h = 2^{(p+1)/4} \bmod p$$

We have this rather odd looking $h$ because that makes $h^r \equiv 2$. Since Schnorr groups had no restriction on what $h$ is (other than $h^r \not\equiv 1$), this satisfies the definition.

Answer 2

While MODP groups such as the question's one meet the definition of Schnorr groups (as explained in the other answer), we'd normally not call them Schnorr groups. By analogy, we'd normally not call $42$ a complex number.

MODP groups belong to a very special subclass of Schnorr groups: they use $p=2q+1$ with $q$ prime, maximizing the order of $h$ (with that restricted to be prime). Use of $p$ with this special form (called safe primes) predate the notion of Schnorr group. These are named after the publication of Claus-Peter Schnorr, Efficient Identification and Signatures for Smart Cards, in proceedings of Crypto 1989. He exposed groups devised so that the prime order $q$ of generator $h$ is much shorter than $p$, allowing shorter signatures. That's what we'd normally expect from a Schnorr group, and that's not met by a MODP group.

Further, the MODP groups of RFC 2409 and RFC 3526 use $p$ of the special form $$p=2^{64k}-2^{64k-64}-1+2^{64}\bigl\lfloor 2^{64k-130}\pi+s_k\bigr\rfloor$$ for some integer $k$, and $s_k$ the smallest integer such that $q=(p-1)/2$ is prime and $2^q\bmod p\ne1$. This insures that

• $h=2$ can be used as a generator of prime order (that's the prescribed generator).
• The number of consecutive high-order bits set in $p$ is $66$, which simplifies estimation of quotient digits in Euclidean division with base $2^{64}$ (or smaller powers of two) while not overly simplifying Discrete Logarithm computation with SNFS.
• The low-order $64$ bits are set, which simplifies Montgomery arithmetic in base $2^{64}$.