2
$\begingroup$

I want to calculate a base point on the twist of secp192k1 with maximal order.

'secp192k1': _ECData(
    p=2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1, 
    a=0, b=3,
    Gx=0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D, 
   Gy=0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D,


 n=0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D
$\endgroup$
4
$\begingroup$

Let $\beta$ a non-square element in $\mathbf{F}_p$, then the elliptic curve defined by $\beta y^2 = x^3 + 3$ is a quadratic twist of secp192k1 whose equation is $y^2 = x^3 + 3$.

It means that if $x_0^3 + 3$ is a square, there exists $y_0 \in \mathbf{F}_p$ that is a square root of $x_0^3 + 3$, so $(x_0, y_0)$ belongs to secp192k1, and on the other hand if $x_0^3 + 3$ is not a square, there exists $y_0$ such that $\beta y_0^2 = x_0^3 + 3$, so $(x_0, y_0)$ lies on the quadratic twist instead. Here, we can take $\beta = -1$ since it is not a square in the finite field $\mathbf{F}_p$.

There is a relation between the cardinality (number of points) with the quadratic twist. The cardinality of secp192k1 is a prime number $n$, that can be rewritten as $$ n = p + 1 - t, $$ where the value $t$ is called the trace of Frobenius. Then it is easy to compute the cardinality $n'$ of the quadratic twist: $$ \begin{align} n' & = p + 1 + t, \\ & = 3 \cdot 373 \cdot 56383 \cdot 619124299 \cdot 160695254510139039862526647837522958722153. \end{align} $$ Write $n'= h\cdot q$ where $q$ is the largest prime in the decomposition. The goal is to find a point of order $q$ on the twist. Let's use SageMath for the computation, but unfortunately it does not handle elliptic curves with an equation of the form $-y^2 = x^3 + 3$. That's not a problem, a simple change of variable will do the trick: let $x'=-x$, and the equation becomes $-y^2 = -x'^3 + 3$, and by multiplying each side by $-1$ we get $y^2 = x'^3 - 3$.

We can make some check that all is good:

p = 2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1
E = EllipticCurve(GF(p), [0, 3])
n = E.cardinality()
print(n.is_prime())
t = p + 1 - n
Et = EllipticCurve(GF(p), [0, -3])
nn = Et.cardinality()
print(nn == p + 1 + t)
print(Et.is_quadratic_twist(E))

The last command returns a nonzero value if the two curves are indeed a quadratic twist of each other.

To find a point whose order is the largest prime $q$, we can run something similar as in this post.

  1. Generate a random point on the twist;
  2. Compute $Q = [h]P$;
  3. If $Q \neq \mathcal{O}$, then $Q$ is a point of order $q$.
h = 39062147507228523
q = 160695254510139039862526647837522958722153
while True:
    P = Et.random_element()
    Q = h*P
    if Q != Et(0):
        break
print(Q)
print(Q.order() == q)
| improve this answer | |
$\endgroup$
  • $\begingroup$ The relation of the cardinality of of a Curve and it's quadratic twist over a finite field can be better explained as either the $y$ is a quadratic residue or a non-quadratic residue. So the curve and the twist contains exactly two points $(x,y_i)$ for $x\in F_p$. So in total, it makes $2q+2$ with the point of infinity counted twice. Now we can use the trace of the Frobenius. $\endgroup$ – kelalaka Jul 31 at 10:53

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.