0
$\begingroup$

I have been recently studying the Schnorr identification scheme. The book Cryptography: Theory and Practice by Stinson and Paterson states the following about the domain parameters in the Schnorr identification scheme:

The scheme requires a trusted authority, or TA, who chooses some common system parameters (domain parameters) for the scheme, as follows:

  1. $p$ is a large prime (i.e., $p\approx 2^{2048}$).

  2. $q$ is a large prime divisor of $p-1$ (i.e., $q\approx 2^{224}$).

  3. $\alpha \in \mathbb{Z}_p^*$ has order $q$

  4. $t$ is a security parameter such that $q>2^t$. (A security parameter is a parameter whose value can be chosen in order to provide a desired level of security in a given scheme. Here, the adversary's probability of deceiving Alice or Bob is $2^{-t}$, so $t=80$ will provide adequate security for most practical applications.)

My question is, how can we find such $p$, $q$, $\alpha$ and $t$? And why does it have to be $p\approx 2^{2048}$, $q\approx 2^{224}$ and $t=80$?

$\endgroup$
1
$\begingroup$

We will need an efficient primality test to produce $p$ and $q$. If you're happy with probable primes then the Miller-Rabin test will suffice for most practical purposes. Write IsPrime() for the test.

Firstly choose $t$ according to the security requirements of your scheme. There's a chance of $2^{-t}$ that a deceiver can subvert the scheme at random, so a choosing $t=80$ means that even if your attacker tried to spoof your system at random $2^{80}$ times they would on average only succeed once. Allowing an adversary $2^{80}$ attempts to spoof your system is unlikely to be a realistic proposition, so $t=80$ is considered fine in this regard.

We now find $q$, it should be large enough that an adversary cannot solve discrete logarithms in an arbitrary group of $q$ elements (e.g. using the baby-step-giant-step method) and also larger that $2^t$. If $q\approx 2^{224}$ then approximately $2^{112}$ group operations would be required by the method and so at least $2^{112}$ computational operations would be needed for BS-GS. To find 224-bit $q$ generate a random 223-bit number $n$ and let $q_0=2^{223}+n$. Compute IsPrime($q_0$) and if successful let $q=q_0$ otherwise increment $q_0$ by 1 and repeat until we are successful.

We now find $p$, it should be large enough that an adversary cannot solve discrete logarithms modulo $p$ (e.g. using the number field sieve). If $p\approx 2^{2048}$ NIST guidelines suggest that at least $2^{112}$ computational operations would be required. To find 2048-bit $p$, generate a random 1824-bit number $m$ and let $p_0=q(2^{1824}+m)$. Compute IsPrime($p_0$) and if successful let $p=p_0$ otherwise increment $p_0$ by $q$ and repeat until we are successful.

We now find $\alpha$. Let $r=(p-1)/q$ note that $r$ is an integer. Start with $g=2$. Compute $\alpha_0\equiv g^r\pmod p$, if $\alpha_0\not\equiv 1\pmod p$ take $\alpha=\alpha_0$, otherwise increment $g$ by 1 and repeat until successful.

The parameters are chosen to provide 112-bits of classical computational security, other parameters would provide different levels of security e.g. $q\approx 2^{160}$ and $p\approx 2^{1024}$ would provide about 80-bits of classical computational security and $q\approx 2^{256}$ and $p\approx 2^{3072}$ would provide about 128-bits of classical computational security.

$\endgroup$
1
  • 1
    $\begingroup$ $t$ is interesting from a theoretical standpoint, but in practice $t$ and $q>2^t$ does not matter, since (as indicated in the answer) we need $\sqrt q$ to be large enough to foil BSGS and variants using less memory such a Pollard's rho. $\endgroup$
    – fgrieu
    Sep 8 at 6:19

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.