2
$\begingroup$

First, sorry for my english which is not my natural language and secondly, I hope I am posting on the right section.

So let's explain my problem.

I am trying to implement the Pohlig-Hellman algorithm based on elliptic curves with the Baby-Steps-Giant-Steps for each iteration.

My Python implementation use a curve on finite field with a smooth prime modulus $N = 2*853*3593*4339$.

With the curve : $y^2 = x^3 + 521x + 1331$ on $\mathbb{F}_{26596586063}$

And the generator $G = (20197258757, 24233149744)$

In theory, and if I understand correctly, the worst complexity in the Baby-Steps-Giant-Steps phase will be $\sqrt{4339}$, right ?

My implementation seems to work (I have the right solution) but I don't have the right complexity : the Polhig-Hellman problem reduction seems useless because I have the same complexity with the Baby-Steps-Giant-Steps running alone.

When I try to solve the discrete logarithm : $H = xG$, my implementation run with a complexity of : $O(\sqrt{x})$ approximatly.

I don't understand my mistake and I am very confuse...

Thanks for your answer.

Here is my implementation (in Python):

def baby_step_giant_step(curve, G, H, order):

    m = int(math.ceil(gmpy2.sqrt(order)))
    L = {}


    # Baby steps
    for j in range(0, m):
        P_tmp = curve.mul(j, G)
        L[str(P_tmp)] = j

    mG = curve.mul(m, G)

    # Giant steps
    for i in range(0, m):
        P_tmp = curve.mul(i, mG)
        if not P_tmp.isInf():
            P_tmp = ecc.Point(P_tmp.x, (-P_tmp.y) % curve.p)

        P = curve.add(H, P_tmp)

        index = str(P)

        if index in L:
            return (L[index] + i*m) % curve.p

    return None

# Solve the equation : G^x = H (mod curve.p)
def pohlig_hellman(curve, G, H):
    N = curve.p-1
    factors = decompose_order(N)
    x = 0


    for i in range(len(factors)):
        ni = factors[i][0]**(factors[i][1])
        tmp = N//ni
        G_prime = curve.mul(tmp, G)
        H_prime = curve.mul(tmp, H)

        # Now, use the Baby Step Giant Step algorithm to solve :
        # H_prime = x_prime*G_prime
        x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)
        while x_prime == None:
            order *= 2
            x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)

        # Use the CRT to solve the equation x_prime = x (mod ni)
        (gcd, x0, x1) = xgcd(ni, tmp)

        x += x_prime*x1*tmp

    return x % N

# (A, B, N)
curve = ecc.Curve(521, 1331, 26596586063)
G = ecc.Point(20197258757,24233149744)

H = curve.mul(523151, G)

x = pohlig_hellman(curve, G, H)
print("x = %s" % x)

PS : don't be afraid by the WHILE loop, it was only for debuging purpose.

$\endgroup$
  • $\begingroup$ Programming language specific highlighting is disabled as this is not a programming forum. It's pretty specific to crypto, I must admit though. $\endgroup$ – Maarten - reinstate Monica Nov 3 '16 at 20:16
  • $\begingroup$ With such small parameters, the difference between various algorithms will be very small. Try with larger ones. $\endgroup$ – fkraiem Nov 4 '16 at 8:16
3
$\begingroup$

Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment.

You are indeed right that the complexity of Pohlig-Hellman is lower than the complexity of BSGS (for a curve of smooth order). However, your parameters are relatively small. Looking at the definition of the big-$O$ notation, we see that this line of reasoning will ignore some constants. That is, roughly, the complexity $O(\sqrt{x})$ means that there is some constant $c$ such that for large parameters the complexity will be $\leq c\sqrt{x}$. This is however only a statement about large parameter values, and does not have much meaning for specifically chosen (small) parameters. For example a situation where an algorithm with complexity $O(t)$ is slower than an algorithm with complexity $O(t^2)$ for a specific instance is easily possible. Note that the definitions of small and large here depend very much on context.

Having said that, I am not sure whether that is actually the problem here. Iirc Pohlig-Hellman does not behave very poorly for small parameters, nor does BSGS. Perhaps you should be careful how you are measuring your complexity. Is it running time, number of curve operations, number of field multiplications, etc.? It could be that there is some overhead unrelated to the algorithm which affects the complexity.

Edit: Okay, there are some confusing parts in your question. Let's get the details straight. We are assuming a curve $E:y^2=x^3+521x+1331$ over the field $\mathbb{F}_{26596586063}$. As you say, the points on this curve form a group of order $N=2*853*3593*4339$, with some generator $G$. Suppose there is some $H\in E$ such that $H=\ell G$ for $\ell\in[1,..,N]$. I deliberately name the scalar $\ell$ as opposed to $x$ to avoid confusion with the curve variable $x$. Let's compare the two ways in which we can solve this DLP (with a bit of abuse of notation):

  1. BSGS: Doing BSGS on a group of order $N$ has complexity $O(\sqrt{N})$ and will give us $\ell\pmod{N}$.
  2. Pohlig-Hellman: Doing PH will cut the DLP up into four parts. We solve four smaller DLP's with respective complexities $O(\sqrt{2})$, $O(\sqrt{853})$, $O(\sqrt{3593})$ and $O(\sqrt{4339})$ (these are your $ni$'s), to get $\ell\pmod{2}$, $\ell\pmod{853}$, $\ell\pmod{3593}$ and $\ell\pmod{4339}$. We then use the CRT to recover $\ell\pmod{N}$. Hence we have complexity $O(\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339})$ for the small DLP's. Note that we are forgetting about the cost to actually reduce to these small-order DLP's.

What we conclude is that for BSGS we have a complexity of around $\sqrt{N}\approx 163085$ while for Pohlig-Hellman we only have a complexity of around $\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339}\approx 156$.

$\endgroup$
  • $\begingroup$ Thanks you for your answer. To be exact, I tried on larger parameters (with a modulus of ~250 bits), and I had the same results. I didn't give the whole code, that's why you was not able to run it. I can give everything, but it is quite long... With my current implementation it appears to be impossible to resolve the discrete logarithm when the $x$ in the $H = xG$ equation become larger, with a smooth prime modulus... $\endgroup$ – Tosh Nov 4 '16 at 14:57
  • $\begingroup$ Could you elaborate on what you mean by "I had the same results"? Did you simply measure the running times of the algorithms and compare them? This is generally not the best metric, as it will rely on the speed of the underlying functions. Perhaps it is worthwhile to count the number of elliptic curve operations (additions and doublings) for both algorithms, and compare those (just add some counters in the algorithm). $\endgroup$ – CurveEnthusiast Nov 4 '16 at 17:06
  • $\begingroup$ I rely on the $order$ parameter of the baby_step_giant_step function. To get a solution, it must always be approximatly $x$...And the baby_step_giant_step run with a complexity of $O(\sqrt{order})$. If I understand correctly the Polhig-Hellman algorithm, the 'order' parameter should be approximatly the $ni$ of each iteration. $\endgroup$ – Tosh Nov 5 '16 at 8:40
  • $\begingroup$ That is correct. Therefore if the $ni$ are much smaller than $N$, Pohlig-Hellman will do much better than BSGS. See the edit. $\endgroup$ – CurveEnthusiast Nov 5 '16 at 10:03
  • $\begingroup$ So I understood correctly the two algorithms. But do you understand why my current Polhig-Hellman implementation runs with a complexity of $O(\sqrt{N})$ ? $\endgroup$ – Tosh Nov 5 '16 at 10:20

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.