1
$\begingroup$

This is the Sage code that I use, and the results I get:

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

p=115792089237316195423570985008687907853269984665640564039457584007908834671663

sage: a=0
sage: b=7
sage: E = EllipticCurve(GF(p), [a, b])
sage: Q = E(36422191471907241029883925342251831624200921388586025344128047678873736520530,20277110887056303803699431755396003735040374760118964734768299847012543114150)
sage: P = E(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424 )

removed string because of error !!! - sage: assert(P.order() == p)
sage: n = SmartAttack(P, Q, p)
removed string because of error !!! - sage: assert(n*P == Q)
print n

First run  n = 1481170902213062751347549793598299888750197064064186460332519137791477653375047339953546448617086499045498251631750765637116741735445054401885264156639661
Second run n = 3063621772009781462544325995158413722808391605322359265303555353453780356669649154814686251048627622198935162903332336956331806043636843561839082016408566
Third  run n = 5973739259366183735200394522172110834640713917372582311655620227151618473645468913161330333367923422202295003748977124278519034520407547669075658208045142
etc…

I got code from - Why Smart's attack doesn't work on this ECDLP?

My 2 questions:

  1. Code always return different $n$. What I need to do to get normal stable?

  2. why $n$ so long ? How to modify code for getting adequate result? $n$ is 2 times bigger than normal private keys !!

$\endgroup$
  • $\begingroup$ I don't know why you do not get error. I use secp256k1 curve with base points, parameters and public key, and get error in "assert" functions. So I delete strings with "assert" $\endgroup$ – Donald Jul 25 at 14:18
  • $\begingroup$ yes this is secp256k1: ECData( p=2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1, a=0, b=7, Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8, n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 $\endgroup$ – Donald Jul 25 at 14:34
  • $\begingroup$ Welcome to crypto-SE. I made some clarifications, feel free to edit you question again. $\endgroup$ – fgrieu Jul 25 at 14:39
2
$\begingroup$

The question is referring to Nigel P. Smart's The Discrete Logarithm Problem on Elliptic Curves of Trace One, in Journal of Cryptology (1999) (earlier version). Quoting the intro:

(…) we describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice, the method described means that when choosing elliptic curves to use in cryptography one has to eliminate all curves whose group orders are equal to the order of the finite field.

Trace of an Elliptic Curve: For an elliptic curve $E$ defined over $F_q$ with $\#E(F_q) = q+1−t$. The $t$ is called the trace of $E$.

In the specification of secp256k1 it is apparent that $n$ (the curve's order¹,²) is not equal to $p$ (the order¹,³ of the base field). In other words, the trace $t=p-n+1$ is not $1$.

Thus Smart's attack can't apply to secp256k1.


Off-topic note: assertions are there to stop execution before code does a silly thing. Removing an assertion without other code change working around the asserted limitation is seldom a good idea.


¹ The order of a finite group or finite field is how many elements it has.

² That order is the number $\#E(F_q)$ of points on the elliptic curve including the neutral "point at infinity".

³ That order is $p=q$, the prime modulus. The finite field considered is integers modulo $p$, noted $(\Bbb Z_p,+,\cdot)$, equivalently $F_q$.

| improve this answer | |
$\endgroup$

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.