0
$\begingroup$

I have some code, which can crack a discrete logarithm problem in ~ O(0.5n) time. However, this only works if, in the following, N is less than P:

G^N (mod P). To be clear, my program can figure out the value of N based on G and P as long as N is in between 1 and P (inclusive and exclusive respectively).

This would be helpful for cracking something like Diffie-Hellman, but I have one question: In most discrete logarithm problems like this one, is it common practice to only choose values of N between 1 and P?

Also, I'm not sure if this is the right forum for this kind of thing, please inform me if it is not.

$\endgroup$
3
  • 1
    $\begingroup$ If a solution exists, there must exist another solution satisfying your constraints, because $G^N \equiv G^{ N \mod{P-1}} \pmod{P}$ (I am assuming $P$ is prime here). In other words, adding or subtracting $P-1$ in the exponent does not change anything. $\endgroup$
    – Fractalice
    Nov 21 at 18:53
  • $\begingroup$ How $n$ is related to $N$? $\endgroup$
    – Fractalice
    Nov 21 at 18:53
  • $\begingroup$ n is just P - 1, because in my algorithm, the number of steps it takes to complete increases relative to the size of P - 1. $\endgroup$ Nov 21 at 20:25
1
$\begingroup$

The problem of solving for $N$ the equation $G^N\equiv A\pmod P$ for given integers $P$, $G$, $A$ is generally stated for integer $N$ with $0<N\le Q$ for some $Q<P$.

The function $N\mapsto G^N\bmod P$ is periodic. Hence if $N$ is a solution, the set of all solutions is obtained by adding a multiple of the period¹ of that function to that $N$. Thus it's pointless to consider $N$ larger than the period if we can find it, in which case we choose the upper limit for $P$ equal to that period, and name it $Q$. In any case, since $G^N\bmod P$ (when not $0$) belongs to the integers in $[1,P-1]$, which has $P-1$ elements, the period cant exceed $P-1$, hence $Q<P$.

That period $Q$ is the order of $G$ modulo $P$, that is the smallest integer $Q$ with $G^Q\equiv1\pmod P$. It depends on $G$. It is a divisor of $\lambda(P)$, where $\lambda$ is Carmichael's function. $\lambda(P)$ is $P-1$ when $P$ is prime, lower otherwise.

When the factorization of $P$ is known (including prime $P$), $\lambda(P)$ is easy to compute, and the order of $G$, being a divisor of $\lambda(P)$, also is easy to compute.

Standard practice in cryptography are $P$ a large prime (e.g. at least 1024-bit, that is 309 decimal digits), and $Q$ the order of $G$ modulo $P$, thus $Q$ a divisor of $P-1$. Depending on cryptosystem that can be $Q=P-1$, or prime $Q=(P-1)/2$, or a mildly large prime $Q$ (e.g. at least 160-bit, that is 49 decimal digits) dividing $P-1$. The former two are common in Diffie-Hellman, the later in Schnorr signature and DSA.

Depending on the magnitude of $P$ and $Q$, the best algorithms we know to find $N$ are either

  • Pollard's rho, which cost is $\mathcal O(\sqrt Q)$ modular multiplications modulo $P$.
  • index calculus, which cost grows sizably slower when $\log (Q)\lesssim\log(P)$.

¹ We define the period as the lowest strictly positive period.

$\endgroup$
1
  • $\begingroup$ Thank you. This helped a lot. $\endgroup$ Nov 21 at 20:27

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.