Join Log in
Score:2
Joe avatar Crypto

What is the purpose of "q" in Safe Prime definition during key pair generation?

in flag
Joe

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?

64
1 + 0
Score:1
fgrieu avatar Crypto
ng flag
fgrieu

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.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.