Baby-step giant-step


In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group due to Daniel Shanks. The discrete log problem is of fundamental importance to the area of public key cryptography.
Many of the most commonly used cryptography systems are based on the assumption that the discrete log is extremely difficult to compute; the more difficult it is, the more security it provides a data transfer. One way to increase the difficulty of the discrete log problem is to base the cryptosystem on a larger group.

Theory

The algorithm is based on a space–time tradeoff. It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.
Given a cyclic group of order, a generator of the group and a group element, the problem is to find an integer such that
The baby-step giant-step algorithm is based on rewriting :
Therefore, we have:
The algorithm precomputes for several values of. Then it fixes an and tries values of in the right-hand side of the congruence above, in the manner of trial multiplication. It tests to see if the congruence is satisfied for any value of, using the precomputed values of.

The algorithm

Input: A cyclic group G of order n, having a generator α and an element β.
Output: A value x satisfying.
  1. m ← Ceiling
  2. For all j where 0 ≤ j < m:
  3. # Compute αj and store the pair in a table.
  4. Compute α−m.
  5. γ ← β.
  6. For all i where 0 ≤ i < m:
  7. # Check to see if γ is the second component of any pair in the table.
  8. # If so, return im + j.
  9. # If not, γ ← γ • α−m.

    C++ algorithm (C++17)


  1. include
  2. include
  3. include
std::uint32_t pow_m
/// Computes x such that g^x % mod h
std::optional babystep_giantstep

In practice

The best way to speed up the baby-step giant-step algorithm is to use an efficient table lookup scheme. The best in this case is a hash table. The hashing is done on the second component, and to perform the check in step 1 of the main loop, γ is hashed and the resulting memory address checked. Since hash tables can retrieve and add elements in Big O notation| time, this does not slow down the overall baby-step giant-step algorithm.
The running time of the algorithm and the space complexity is Big O notation|, much better than the Big O notation| running time of the naive brute force calculation.
The Baby-step giant-step algorithm is often used to solve for the shared key in the Diffie Hellman key exchange, when the modulus is a prime number. If the modulus is not prime, the Pohlig–Hellman algorithm has a smaller algorithmic complexity, and solves the same problem.