2
$\begingroup$

Consider the following case, given x(private key) and y(public key), how to determine whether this key pair is generated by a pre-defined Safe Prime Group(Say FFDHE, RFC 7919)?

In context of SP800 56Ar3 Section 5.6.1.1.4, my understanding is we need to check 2 conditions,

i. y = g^x mod p
ii. 1 < x < min(2^N, q-1)

where N is the max bit size of private key can generate

(i) makes sense because if I change p and g, x and y will fail the key verification.

However, in (ii), if I completely ignore q(makes 1 < x < 2^N), or change value q(makes q != (p-1)/2), I still can pass this key verification method. q seems is only used to bound the range of x to [1, min(2^N, q-1)]. Is there any more meaning for this q in key generation phase?

My understanding of Safe Prime key pair generation are following, please correct me if I am wrong, thanks.

Phase 1: Generate DH parameters p, q, g. Here requires q to hold properties of

1. g^q = 1 mod p, 
2. q = (p-1)/2
3. q is a prime

Since RFC defines the exact p, q, g to use, so we don't consider this phase.

Phase 2: Use p, q, g to generate Key Pair x and y. In this phase, SP800 56A bounds the range of x to [1, min(2^N, q-1)], what if I generate a larger x that, q < x < 2^N ? Is this just FIPS document wants it or there are some underlie mathematical meaning behind it?

$\endgroup$

1 Answer 1

1
$\begingroup$

The key generation/validation procedure considered supports the two kinds of parameters explained in Section 5.5.1.1 FFC Domain Parameter Selection/Generation:

a class of “safe” domain parameters (…)
and a class of “FIPS 186-type” domain parameters (…)

In the former case, $2q+1=p$, and typical parameters could be $2^{2047}<p<2^{2048}$, $N=256$. In that case $2^N<q$ and $q$ plays no role in the key generation/validation procedure, as noted in the question. Notice that if we used $N=2048$ (also possible, though not believed to much increase security), $q$ would come into play.

In the later case, better known a Schnorr group, $r\,q+1=p$ for some large $r$. Typical parameters could be $2^{2047}<p<2^{2048}$, $2^{255}<q<2^{256}$, $N=256$. In that case $2^N>q$ and $N$ plays no role in the key generation/validation procedure. Notice that if we used $N=224$ (also possible, and not believed to much lower security), $N$ would come into play.

What if I generate a larger $x$ that, $q < x < 2^N$ ?

Mathematically that's fine as long as $x\bmod q$ is not too poorly distributed. When used as exponent (modulo $p$), $x$ will produce the same result as $x'=x\bmod q$, thus no compatibility issue is to fear, except if the private key gets transmitted to another device: conforming implementations will reject $x\ge q$ when importing a key.

When it comes to performance, shorter $x$ tend to be better.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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