Transforming Elliptic Curve to Hessian Form

cryptographyelliptic-curves

In the The Hessian Form of an Elliptic Curve, (NP Smart – ‎2001), they began with the elliptic curve

$$E': y^2 +xy = x^3 + x^2 + b$$ defined over the $\operatorname{GF}(2^{192})$ with the polynomial basis in $t$ over $\operatorname{GF}(2)$, where $$t^{191} + t^9 + 1 = 0.$$
with

$$b = \texttt{0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48}$$

The curve group order

$$ 6 \cdot q = 3138550867693340381917894711648254768837315541933943803842$$ with prime $q$. A point of order 3 on $E'$ is given by the point $(x_3,y_3)$;

$$x_3 = \texttt{0x4763CFBC4340674B749E57887850E92C9B6BEDF58EEDC3BF}$$
$$y_3 = \texttt{0x14A96A1E53DCC3E73CFB22B80E8658CE0D6D8E82ED2AEC7D}$$

Then proposed a change of variable

$$ X = x + x_3 \quad Y =y+sx+x^2$$ where $$s = \frac{x_3^2+y_3}{x_3},$$

then the elliptic form is obtained.

$$E:Y^2 + XY + x_3 Y = X^3$$

Then using the above the Hessian Form is obtained;

$$ x^3 + y^3 + z^3 = Dxyz$$ where

$$D = \texttt{ 0x16A4C7C2030FAD1380ABF8C2D47DC3E0C20AF62F6EDD06A7}$$

  1. How does one find a point with order 3?
  2. What is the intuition behind the change of variables?
  3. How the Hessian form is obtained in the last step?

Best Answer

Since the situation in the OP is related to a special example, i will use this example to illustrate the steps. Computations are done in sage. Some ingredients in the OP differ from the one in the reference [Smart N.P., The Hessian form of an Elliptic Curve], these are marked in red. (Colors are also used to mark matching pieces in longer computations.) All computational details are given, if the computer support feels annoying for a community reader, please skip it, the remained part is still giving the frame of the structure.

We consider the field $$ F=\Bbb F_q=\Bbb F_2[T]/(T^{\color{red}{191}}+T^9+1) $$ with $q=2^{191}$ elements (migrated letter for the usual reason). Let $t$ be $T$ modulo the quotient ideal.

We associate the curve $E'$, given by the affine equation: $$ E': \ y^2 +xy = x^3 + x^2 + b\ . $$ The order of the curve is $6N$, with a big prime $N$. Let us initialize the curve in sage, and check the order.

R.<T> = PolynomialRing(GF(2))
F.<t> = GF(2^191, modulus=T^191 + T^9 + 1)

b = F.fetch_int(0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48)
x3 = F.fetch_int(0x4763CFBC4340674B749E57887850E92C9B6BEDF58EEDC3BF)
y3 = F.fetch_int(0x14A96A1E53DCC3E73CFB22B80E8658CE0D6D8E82ED2AEC7D)

E = EllipticCurve(F, [1, 1, 0, 0, b])
N = ZZ(3138550867693340381917894711648254768837315541933943803842 / 6)

Q = E( (x3, y3) )    # this is the given point. Is it a 3-torsion point?
print("For the given point Q do we have 3.Q = O? {}\n"
      .format(3*Q == E(0)))

# we check that multiplication with 6N maps a random point P to O.
P = E.random_point()
print("For some random point P, do we have 6N.P = O? {}\n"
      .format(6*N*P == E(0)))

We obtain so far:

For the given point Q do we have 3.Q = O? False

For some random point P, do we have 6N.P = O? True

So $Q$ is not a $3$-torsion point, it is rather a point of (prime) order $N$, useful for the usual cryptographic reasons.

sage: N*Q
(0 : 1 : 0)
sage: N * Q == E(0)
True

We will forget this point $Q$ in the following, thus also using the notations / the variables x3 and y3 for other purposes.

In order to construct a $3$-torsion point, we consider the $3$-torsion (or division) polynomial, which is $$ x^4+x^3+b\ . $$ Formally one can see this as follows. Let $(x{_0},y{_0})$ be a point on the curve. The formal differential of the given curve equation, computed in this point, is $2y_0\; dy+x_0\; dy+y_0\; dx+3x_0^2\; dx+2x_0^2\; dx=0$, i.e. $(x_0^2+y_0)\; dx +x_0\; dy=0$. We formally replace $dx$, $dy$ by $(x-x_0)$, $(y-y_0)$ getting the tangent/line equation $(x_0^2+y_0)(x-x_0)+x_0(y-y_0)=0$. Its slope is a function $s$ of/in $(x_0,y_0)$, formally obtained as $$s=s(x_0,y_0)=\frac1{x_0}(x_0^2+y_0)\ .$$ Now we would like to obtain an equation for the first component in the identity $-2T_3=T_3$ of a $3$-torsion point $T_3$. It is $s^2+s+1=x$. This leads to $x^4+x^3+b=0$.

Code computing this polynomial and using it:

pol = E.division_polynomial(3)
# or pol = E.torsion_polynomial(3)

roots = pol.roots(ring=F, multiplicities=False) 
print(f"The given polynomial has {len(roots)} roots over F")

# and we try to lift the roots one by one
three_torsion_points = []

print("\n...lifting found roots...")
for r in roots:
    try:
        U = E.lift_x(r)
        three_torsion_points.extend([U, -U])
        print(f"... OK: LIFTED ROOT {hex(r.integer_representation())}")

    except:
        print(f"... could *NOT* lift the root {hex(r.integer_representation())}")

print()
for U in three_torsion_points:
    Ux, Uy = U.xy()
    hexu = hex(Ux.integer_representation())
    hexv = hex(Uy.integer_representation())
    print(f"Computed 3-torsion point with components:\nx3 = {hexu}\ny3 = {hexv}")

This gives:

The given polynomial has 2 roots over F
...lifting found roots...
... OK: LIFTED ROOT 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
... could *NOT* lift the root 0x66b8ff1e96ee97559108d9e34fd7c48a372313924b5e81ea

Computed 3-torsion point (u, v) with:
u = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
v = 0x38a4365e3388fc1094ba6755e471788805c9961f52054d79
Computed 3-torsion point (u, v) with:
u = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
v = 0x5ef9e8160d614a08a1c9429db217b97121d48fcb0c73959a

To find all points of order three, we asked for the corresponding division polynomial, then for its roots in $F$, which correspond to the $x$-components of the $3$-torsion points. Then we tried to lift. Lifting needs the existence of a square root for the remained equation in $y$ (from $E'$), after plugging in the found $x$ value. We could lift one root of the $3$-torsion polynomial.

So the given point $Q$ is not a $3$-torsion point. But we have a good one. (There are two points sharing the same $x$-component, denoted above by u.)

Let us check that pol is in fact $x^4+x^3+b$:

sage: S = pol.parent()
sage: x, = S.gens()
sage: pol == x^4 + x^3 + b
True

This concludes (1).

Let $T_3(x_3,y_3)$ be the first $3$-torsion point from above. (The other one is $-T_3$.)

The second question. We are using a transformation of coordinates, which maps $T_3$ to the point $(0,0)$ of an other elliptic curve with equation in $X,Y$, obtained by passing from $(x,y)$ to $(X,Y)$ via $$ \begin{aligned} &\left\{ \begin{aligned} x &= X-x_3=X+x_3\ ,\\ y &= Y-sx-x^2_{\color{red}3}=Y+sx+x^2_{\color{red}3}\ , \end{aligned} \right. \\ &\qquad \qquad \text{ with }t=\frac{y_3}{x_3}\ ,\ s=x_3+t=x_3+\frac{y_3}{x_3} \\ &\left\{ \begin{aligned} X &= x+x_3\ ,\\ Y &=y+sx+x^2_{\color{red}3}\ , \end{aligned} \right. \\ &\qquad \qquad \text{ so that }T_3(x_3,y_3) \\ &\qquad \qquad \text{ goes to } (X_3,Y_3)=(x_3+x_3,y_3+sx_3+x_3^2)=(0,0)\ . \end{aligned} $$ We plug in $(x,y)$ from above in the equation $y^2 +xy = x^3 + x^2 + b$ of the given curve $E'$ and obtain (recalling that in our case $2=0$, so that for instance squaring is compatible with addition) an equation in $(X,Y)$: $$ \begin{aligned} y^2 &= (Y-sx-x^2_3)^2=(Y+sx+x^2_3)^2=Y^2+s^2x^2+x^4_3\\ &=Y^2+(x_3^2+t^2)(X^2+x_3^2) + x_3^4\ ,\\ &=Y^2+x_3^2X^2+t^2X^2+y_3^2\ ,\\ &=Y^2+s^2X^2+y_3^2\ , \\[2mm] xy &=(X+x_3)(Y+s(X+x_3)+x^2_3)\\ &=XY+x_3Y + (x_3+t)(X^2+x_3^2)+x_3^2X +x_3^3\ ,\\ &=XY+x_3Y + x_3X^2+tX^2+x_3^3+x_3y_3 +x_3^2X +x_3^3\\ &=XY+x_3Y + x_3X^2+tX^2+x_3y_3 +x_3^2X \ , \\[2mm] x^3+x^2+b &=(X^3+x_3X^2+x_3^2X+x_3^3)+(X^2+x_3^2)+b\ ,\\[2mm] &\text{ which implies}\\[2mm] 0 &=(y^2+xy)\pm(x^3+x^2+b)\\ &=Y^2 + \color{red}{s^2X^2} +\color{blue}{y_3^2}\\ &\qquad + XY + x_3Y + \color{red}{sX^2} + \color{blue}{x_3y_3} +x_3^2X \\ &\qquad\qquad + (X^3 + \color{red}{x_3X^2} + x_3^2X + \color{blue}{x_3^3}) + (\color{red}{X^2} + \color{blue}{x_3^2})+\color{blue}{b} \\ &=Y^2 + XY + x_3Y+X^3\\ &\qquad+ \color{red}{\underbrace{(s^2+s+x_3+1)}_{=0}}X^2 + \color{blue}{0} \\ &=Y^2 + XY + x_3Y+X^3\ . \end{aligned} $$ Note that the red term $s^2+s+x_3+1$ vanishes, since $x_3$ is a root of the $3$--torsion polynomial $x^4+x^3+b$: $$ \begin{aligned} x_3^2(s^2+s+x_3+1) &=x_3^2\left( x_3^2+\frac{y_3^2}{x_3^2} + x_3+\frac{y_3}{x_3} + x_3+1 \right) \\ &=x_3^4+\color{blue}{y_3^2+x_3y_3}+x_3^2\\ &=x_3^4+\color{blue}{x_3^3+x_3^2+b}+x_3^2\\ &=x_3^4+\color{blue}{x_3^3+b}\\ &=0\ . \end{aligned} $$ The sage code checking this vanishing is:

for U in three_torsion_points:
    x3, y3 = U.xy()
    s = x3 + y3/x3
    if s^2 + s + x3 + 1 != 0:
        continue
    hexu = hex(x3.integer_representation())
    hexv = hex(y3.integer_representation())
    print(f"ss + s + x3 + 1 = 0 for the values:\nx3 = {hexu}\ny3 = {hexv}")

It gives:

ss + s + x3 + 1 = 0 for the values:
x3 = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
y3 = 0x38a4365e3388fc1094ba6755e471788805c9961f52054d79
ss + s + x3 + 1 = 0 for the values:
x3 = 0x665dde483ee9b618357325c85666c1f9241d19d45e76d8e3
y3 = 0x5ef9e8160d614a08a1c9429db217b97121d48fcb0c73959a

Note that the procedure of moving the torsion point $T_3(x_3,y_3)$ to the point $(0,0)$ of an other elliptic curve in long Weierstraß form in $X,Y$, while also moving the tangent in $(0,0)$ to $Y=0$ is a standard procedure. See e.g.

https://en.wikipedia.org/wiki/Hessian_form_of_an_elliptic_curve#Definition

in the proposition [ Conversely... ].
This answers the second question (structurally and programmatically).

To obtain the hessian form from the equation: $$ E''\ :\ Y^2 + XY + x_3Y = X^3\ , $$ we proceed as in loc. cit., page 120, [§3. The Hessian Form of an Elliptic Curve]. The values for $a_1$, $a_3$ are in our case explicitly $1$ and $x_3$, so for instance $\Delta =x_3^3(1-27x_3)=x_3^3(1+x_3)=b$, and $\delta = 1+x_3$. We compute a root of the polynomial in $T$ $$ T^3-\delta T^2+\frac 13 \delta^2T+x_3\delta^2 $$ and build $$ D=3\frac{\mu-\delta}\mu =1+\frac{\delta}\mu \ . $$ The hex value for this number is...

PF.<T> = PolynomialRing(F)
delta = x3 + 1
mu = (T^3 - delta*T^2 + delta^2*T + x3*delta^2).roots(multiplicities=False)[0]
D = 1 + delta/mu
print(f"D is {hex(D.integer_representation())}")

which gives:

D is 0x16a4c7c2030fad1380abf8c2d47dc3e0c20af62f6edd06a7

which is the same value as in loc. cit..

Related Question