Does the size of base, exponent, and modulus thwart the Giant-step/Baby-step algorithm in solving DLP using modular arithmetic or is it the use of a property of a particular prime as the modulus, or something else?


The Discrete Logarithm Problem for a fixed public prime modulus $p$ and generator $g$ of multiplicative order $q$ in $\Bbb Z_p^*$ (that is, $q$ is the smallest positive integer with $g^q\bmod p=1$ ) asks, given $y$ obtained as $y\gets g^x\bmod p$ for a random unknown $x$ in $[0,q)$, to find that $x$ (which is unique).

The Baby Step/Giant Step algorithm solves that problem with $\mathcal O(\sqrt q)$ multiplications modulo $p$, ignoring the cost of memory and memory accesses. The cost of one multiplication modulo $p$ grows slightly slower than $\mathcal O((\log(p))^2)$.

Thus what "prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic" is mostly choosing $p$ and $g$ such that the multiplicative order $q$ of $g$ is large enough: at least twice the desired security level. Say, 256-bit for 128-bit resistance.

Update per comment: The Pohlig-Hellman DLP algorithm essentially attacks each prime factor of $q$ separately. Guarding against it is obtained by insuring that at least one prime factor of the multiplicative order $q$ is at least twice the desired security level.

Further, due to yet other DLP algorithms (GNFS in particular), $p$ must be considerably larger than twice the desired security level (2048-bit $p$ should be a bare minimum nowadays).

The multiplicative order of any element in $\Bbb Z_p^*$ is always a divisor of $p-1$. Hence one way to ensure that $q$ is large and has a large prime factor is to choose prime $p$ as large as required per the above, and such that $(p-1)/2$ is also prime (that is, choose $p$ as a safe prime). It ensures $q$ is among $\{1,2,(p-1)/2,p-1\}$, and allows to choose $g$ leading to one of the two later options (both used in practice), giving a huge security margin w.r.t. Baby Step/Giant Step (or Pollard's Rho) and Pohlig-Hellman combined.

Another option is to first choose $q$ (usually as a prime at least twice as wide as the security level), and build $p$ as a large enough (thus much larger) prime such that $q$ divides $p-1$; then construct $g$ of multiplicative order $q$. That builds a so-called Schnorr group. It is used in Schnorr signature and similar, including DSA, with the advantage of shortening the signatures.

  • $\begingroup$ Since you mentioned GNFS, would you put Giant-step/Baby-step in the same category as GNFS or Pohlig-Hellman in terms of "what prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic is mostly choosing p and g such that the multiplicative order q of g is large enough"? $\endgroup$
    – JohnGalt
    Dec 19 '18 at 19:45

From the Wikipedia;

  • The baby-step giant-step algorithm is a generic algorithm. It works for every finite cyclic group.

Therefore, one has to consider the key size considering the time complexity of the algorithm; $\mathcal{O}(\sqrt(n))$

Note: Number Field Sieve has better complexity and the key length are calculated based on this.

  • $\begingroup$ Just to clarify, so choosing a "safe prime" for the modulus or the decision of which generator (a.k.a. base) to choose has nothing to do with undermining the baby-step giant-step algorithm? $\endgroup$
    – JohnGalt
    Dec 19 '18 at 0:12
  • $\begingroup$ Safe primes $\endgroup$
    – kelalaka
    Dec 19 '18 at 0:19
  • $\begingroup$ Thank you for the link which I'm currently trying to grok. It appears that the answer to my question regarding safe primes is in the affirmative. So is the answer to my original question a combination of large key sizes AND properties of certain primes (a.k.a. safe primes)? $\endgroup$
    – JohnGalt
    Dec 19 '18 at 0:34
  • 2
    $\begingroup$ @JohnGalt Rather than the size of the base or the size of the modulus, I think it's the size of the group generated by the base and the modulus that counts. For example, if $g^2 \equiv -1 \bmod P$, then there are only 4 elements in the subgroup generated by $g$. Obviously, if $P$ is small, then you'll have a similar problem, but $P$ just being large does not necessarily fix the problem, which is where the safe primes come in. $\endgroup$
    – Ella Rose
    Dec 19 '18 at 1:10

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.