cryptographyelliptic-curvesmodular arithmetic
I am having hard time grasping the math behind the elliptic curve cryptography and have to solve the following problem. Some general explanation is welcome too. Thank you in advance, and the problem is the following:
Given is the elliptic curve:
$E:y^2 = x^3 + ax + b$, which is defined over $\mathbb{Z}_p$
How do you show that:
a) any point on $E$ with y-coordinate equal to zero has order $2$.
b) when $a = 0$ and $b\neq0$ , any point on $E$ with x-coordinate equal to zero has order $3$.
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..
There are a few possible explanations to your dilemma. Without a clearer statement of what exactly your problem is, it is impossible to be more precise.
Not all supersingular elliptic curves over $\mathbb{F}_{p^2}$ are isomorphic as abelian groups over $\mathbb{F}_{p^2}$. For example, taking $p=431$, the curve $E : y^2 = x^3 + x$ has group structure $E(\mathbb{F}_{p^2}) \cong (\mathbb{Z}/(p+1)\mathbb{Z})^2$ whereas its quadratic twist $E' : y^2 = x^3 + (2+i)x$ has group structure $E'(\mathbb{F}_{p^2}) \cong (\mathbb{Z}/(p-1)\mathbb{Z})^2$.
Even if two elliptic curves are isomorphic over $\mathbb{F}_{p^2}$ as abelian groups over $\mathbb{F}_{p^2}$, this does not mean they are isomorphic as elliptic curves. An elliptic curve has more structure than just merely that of an abelian group.
Even if you are only looking at abelian groups, isomorphic abelian groups may not be equivalent for the purposes of cryptography. For example the abelian groups $G_1 = (\mathbb{Z}/p\mathbb{Z})^*$ and $G_2 = \mathbb{Z}/(p-1)\mathbb{Z}$ are isomorphic as abelian groups, but the discrete logarithm problem is believed to be hard on $G_1$ whereas the same problem is known to be easy on $G_2$. In this case the issue is that the isomorphism, though it exists, is not efficiently computable in both directions, which makes a difference in cryptography.
Best Answer
Hints:
a) A point $P$ has order 2 if $P+P=\mathcal{O}$, and therefore $P=-P$. What is $-P$? Then equate the $y$-coordinates.
b) A point $Q$ has order 3 if $Q+Q+Q=\mathcal{O}$, and therefore $Q+Q=-Q$. Again write $-Q$ in terms of $Q$, and use the addition law to compute $Q+Q$. Then equate the $x$-coordinates of $Q+Q$ and $-Q$.