1
$\begingroup$

An adversary wants to find $a$ in

$$m \equiv g^a \bmod P$$

He knows prime $P = 2 \cdot c \cdot k +1$ with it's primes $c,k$, value $m$ and $g$. And he also knows that $g$ only has an order of $k$, so: $$g^k \equiv 1 \bmod P$$


Question:
If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$ only factor $c$ gets increased) does this decrease the security?

Why this? If $P \rightarrow \infty $ it would be the normal logarithm which is easy to compute compared to discrete version.

The smaller the better (for same $k$)? Any boundary for best security?


Discrete Log is hard because it is always reduced to a number from $0$ to $P-1$.
Is security bound to the number of multiplications of generator $g$ needed until over $P$ again? The less the better?

Question part 2:
Would be a higher value for $g$ increase security? (best would be $(P-1)/2$?)
Or to be more certain would a higher smallest group element $\not=1$ increase security?

$\endgroup$
  • $\begingroup$ @kelalaka This algorithm reduces the problem to the largest prime factor of the order size. But that is already the case. $g$ has order $k$ which is a prime factor of $P-1$. So you saying the security is independent of $P$ with constant order size $k$? $\endgroup$ – J. Doe Jan 16 at 0:27
  • $\begingroup$ @kelalaka $k$ has fixed size and is prime, so just factor $c$ gets increased. $\endgroup$ – J. Doe Jan 16 at 22:15
  • $\begingroup$ @kelalaka all should be primes $k,c,P$. So only selected primes values for $c$ are possible which result in a prime $P$ as well and $P=2ck+1$ is still true for the same $k$. $\endgroup$ – J. Doe Jan 16 at 22:49
2
$\begingroup$

If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$) does this decrease the security?

No, for random choice of $g$ among $g$ with large constant order $k$.

Why this? If $P \rightarrow \infty$ it would be the normal logarithm ..

When $P$ grows, $g$ also grows. So we never reach the threshold where $g^a<P$. Thus we can not use the normal logarithm.

The smaller the better (for same $k$)?

Uh, no, on the contrary! The above says that larger $P$ does not decrease security. Correspondingly, larger $P$ tends to increase security. However, very large $P$ does not much increase security, because the best known algorithms we have for the discrete logarithm for fixed $k$ and large $P$ perform a number of modular multiplications modulo $P$ that is a function¹ of $k$ only, and the time necessary for a multiplication modulo $P$ grows relatively slowly with $P$: in the order of $O(\log^2 P)$ for the simplest and common methods².

Any boundary for best security?

Only a lower boundary, and that's a nontrivial subject. The short answer might be: at least $2^{4095}$ (that is $P$ of $2^{12}$ bits) with $P$ not chosen close to the power of an integer.

The long answer includes that security against classical computers (not hypothetical quantum computers usable for cryptanalysis per e.g. Shor's algorithm) is believed to be limited by several possible attacks:

  • the Number Field Sieve, which efficiency is governed mostly by $P$, and which general form the General Number Field Sieve (the only form likely to be applicable to $P$ not chosen close to the power of an integer, a situation where the Special Number Field Sieve shines) is believed to require a $P$ in the order of at least $2^{11}$ to $2^{13}$ bits for security.
  • Pollard's rho, which efficiency is governed mostly by $k$, requiring a $k$ in the order of at least $2^8$ to $2^9$ bits for security.
  • Pohlig–Hellman (and possibly other algorithms) depending on the factorization of $k$, that do not work as well as Pollard's rho when $k$ is prime.

Would be a higher value for $g$ increase security?

Not much. The influence of $g$ on security is usually neglected for the aforementioned three algorithm. I doubt it can exceed $\mathcal O(\log g)$ (which can be approached in Baby-step/Giant-step). Also, I know no way to select a very small $g$ with order $k$ and $\log_2(k)\ll\log_2(P)$, much less for prime $k$, which is desirable for various reasons including blocking Pohlig–Hellman.

Or to be more certain would a higher smallest group element $\ne 1$ increase security?

Not that we know. Also I know no way to insure that for large parameters.


What we are discussing is a Schnorr group. There are well established methods to generate these, including from a public seed so as to tame suspicion of weak parameters. See FIPS 186-4, appendix A (which uses $p,q$ where the question and answer use $P,k$).


¹ That function is at most about $\alpha k^2$ for a constant $\alpha$ in the order of $2$ depending on a variety of details. But that's immaterial to the reasoning in the paragraph with this note.

² The cost can get down to $O(\log^{1.585\ldots}P)$ with Karatsuba which sometime is used; $O(\log P\;\log\log P\;\log\log\log P)$ with Schönhage-Strassen which could be of interest for insanely large $P$, and $O(\log P\;\log\log P)$ with Harvey-Hoeven (a bleeding edge result which seems unlikely to have practical application).

$\endgroup$
  • $\begingroup$ oh, dear forgot about the increasing $g$ if $P$ gets increased (with const $k$). Excellent answer. Ye, my questions was related to Schnorr group. $\endgroup$ – J. Doe Jan 16 at 11:09
  • $\begingroup$ about the lower boundary: It was meant to be a boundary for the ratio $P/k$ (or log ratio). With $P$ 4096 bits the order $k$ could still be a low prime if the other factor is high. E.g. order $k=7$ would be easy to solve, no matter how big $P$ is. As you written above the ratio is not that important. So the order $k$ should be a prime near $2^{4095}$? $\endgroup$ – J. Doe Jan 16 at 11:41
  • 1
    $\begingroup$ An upper bound of the security would be given by the generic group model: For a given order of a cyclic group, no encoding can be more difficult than ignoring the encoding and just looking at the group structure. $\endgroup$ – tylo Jan 16 at 11:53
  • $\begingroup$ @J.Doe: I have not introduced the ratio $P/k$ or $\log(P)/\log(k)$; you just did. The relation between reasonable $P$ and $k$ is one difficult to establish. The right ballpark around the values that I state might be that when we multiply the bit size of $k$ by $x$ with $1<x\le2$, we multiply the bit size of $P$ by $x^2$ to $x^3$. I stated that $k$ should be a prime of 256 to 512 bit (given as $2^8$ to $2^9$). Even with a large $P$ (say, 8192-bit) and $k$ prime, if $k<2^{128}$, then it is conceivable to compute the discrete logarithm with distributed Pollard's rho. $\endgroup$ – fgrieu Jan 16 at 12:33
  • $\begingroup$ @fgrieu: I meant my initial question was about the ratio. E.g. Let $k$ be fixed size of 512-bit. Does the security decrease if $P=2ck+1$ gets bigger? For $c=1$ the prime $P$ would have 513-bit. For $c$ a 512-bit prime $P$ would have 1025bit and so on. For a very large $c$ like a $2^{100}$-bit prime $P$ would be a $2^{110}$ bit prime. I thought that would involve many multiplications without mod. But as you wrote with higher $k$ also $g$ gets higher and no known way to find a small group element. It even increases security (a little) because multiplications need a little more computation power. $\endgroup$ – J. Doe Jan 16 at 22:45

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.