1
$\begingroup$

I tried implementing the Hessian form of an Elliptic curve over the prime field Fp where, p I have taken as 1051. The curve equation I took is $X^3 + Y^3 + cZ^3 = dXYZ$ with c = 1 and d = 6. Selected (4,2,6) as the base point.

Followed the equation (5) and (6) of https://www.iacr.org/archive/pkc2010/60560246/60560246.pdf for point addition and point doubling respectively.

However, when multiplying (4,2,6) with 42, I am getting (0,0,0) after the 30 steps. For ease of understanding, I am providing the formulae for addition and doubling.

Addition

$X3 = X2*Z2*Y1^2 - X1*Z1*Y2^2$

$Y3 = Y2*Z2*X1^2 - Y1*Z1*X2^2$

$Z3 = X2*Y2*Z1^2 -X1*Y1*Z2^2$

Doubling

$X3 = Y1*(c*Z1^3 - X1^3)$

$Y3 = X1*(Y1^3 -c*Z1^3)$

$Z3 = Z1*(X1^3 - Y1^3)$

All the points have been computed with respect to modulo p.

$\endgroup$
  • $\begingroup$ I tried calculating the order of the generator in a way, where the X coordinate of the point becomes 0. In doing that with respect to 1051, I got an answer of 59. $\endgroup$ – DEBASMITA DEY Aug 15 at 15:29
  • $\begingroup$ I intended on using projective coordinates. I can not provide a link to the whole code, as it is part of my research. It will also be helpful if somebody points out any gap in my understanding. $\endgroup$ – DEBASMITA DEY Aug 15 at 17:40
  • $\begingroup$ No, it is not the point of infinity. If I do [59]P I am getting only the X coordinate 0. I intended on using this method of finding the order instead of using any other. Should Schoof's algorithm help me? $\endgroup$ – DEBASMITA DEY Aug 15 at 17:45
  • $\begingroup$ If I am doing [59]P I am getting (0,657,154). Whereas, 60[P] is giving me (920, 743, 548). But it should give me back the point (4,2,6), if it would have been the order right? And, (0,1,0) is the point at infinity for Weierstrass form of curve. But in Hessian, it is claimed to be of (0, -1, 1). But for base point, we can take any point that satisfies the equation? $\endgroup$ – DEBASMITA DEY Aug 15 at 17:58
  • $\begingroup$ I've written some codes ( fallow the SO link) and updated the result. Hope those provide you some experience, too. $\endgroup$ – kelalaka Aug 18 at 20:26
1
$\begingroup$

The user94293's answer is correct, If you look at the equation you will see that the result will be zero if you add the number itself. It is designed for the points $P$ and $Q$ such that $P\neq Q$. If you want to calculate the $P+P$ that is called point doubling and it is written as $[2]P$. There are always special formulas for doubling since it adds the point itself.

The addition formula is optimized and cannot be used for $2[p]$. From your questions and comments, I understand that you are trying to find the scalar multiplication by just adding;

Scalar Multiplication

The scalar multiplication $[k]P$ this actually means adding $P$, $k$-time itself. More formally;

let $k \in \mathbb{N}\backslash\{ 0\}$

\begin{align} [k]:& E \to E\\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}

Double-and-Add

To use these formulas correctly, you need the double-and-add algorithm

#Returns [k]G, where p is modulus 
#and c is the constant of the Generalized Hessian Curve
doubleAndAdd(G, k , p ,c)
  N = P
  Q = 0
  for i in bits(k)
     if i = 1 then
         Q = point_add(Q, N)
     N = point_double(N)
  return Q

Where the bits convert the $k$ into binary form and started from LSB.


Updates on implementation

I've found a problem during the calculation of the order an element, later figured out the cause. One can reach the codes and explanations on the Q/A from the StackOverflow

The order of $(4,2,6)$ is $77400$ i.e. $[77400](4,2,6) = \mathcal{O}$ and the order factors into $2,2,2,3,3,5,5,43$. Not a good curve.

To run better, the order of the curve must be calculated before and so that one can use $[k]P = [k \bmod order]P$ equality.

Smart's Sample Curve

N.Smart wrote an article titled The Hessian Form of an Elliptic Curve. In this work first, a curve over $\operatorname{GF}(2^{191})$ on the form $$E': y^2 +xy = x^3 + x^2 + b$$ $$b = \texttt{0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48}$$ is given, and that then transferred to a Hessian form.

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

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

A point of order $q$ on $C$ is also given by $(x, y, z)$, where

$$x = \texttt{0x52FD0CE78D0651B4F66D2F4E12E170CA3E429F6A06433B22}$$ $$y = \texttt{0x1BECA50368403F3D13173968082B035397C77830A9D90E5D}$$ $$z = \texttt{0x2B08F7C0CCAC86151AA6FECABDD2D052BD60924F28A6A78E}$$

That is not generalized, however, your $c=1$ make is in this case. You can benefit from this curve.

| improve this answer | |
$\endgroup$
0
$\begingroup$

The addition formula (5) cannot be used to double a point. If you do so, you end up with the invalid point (0:0:0).

| 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.