1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'd guess these are safe primes, so $r=2$, for Schnorr groups we generally select a much smaller $q$, only twice the security level. $\endgroup$ – CodesInChaos Apr 25 '14 at 15:12
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks, this really helps me a lot... I thought it was a Schnorr group, but I couldn't understand how the generator could possibly be 2. $\endgroup$ – Cedric Martin Apr 25 '14 at 16:38
0
$\begingroup$

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}$.
$\endgroup$
  • 1
    $\begingroup$ In principle one could search for primes of the same shape, with the only difference being that one test for the criterion that $p$ has a 256-bit prime factor $q$ instead of a $\lfloor\lg p\rfloor$-bit prime factor $q$. Obviously, then there's little significance to $g = 2$, but one would get a Schnorr group with all the other consequences of the RFC 2412 criteria you described. $\endgroup$ – Squeamish Ossifrage Nov 29 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.