Python : order of a point is not regular in Hessian Curve implementation

user_1820553 0
Viewed 108

I've implemented Hessian Curve with Python

def checkPoint(P,p,c,d):
  
    #X^3 + Y^3 + cZ^3 = dXYZ over GF(p)
  
    if ( P[0]**3 + P[1]**3 + c * P[2]**3) % p == ( d * P[0] * P[1] * P[2] ) % p :
        return True
    
    return False
    
def bits(n):

    while n:
        yield n & 1
        n >>= 1
        
def point_add( P, Q , p) : 

    if P is None or Q is None: # check for the zero point
        return P or Q
     
    #12M + 3add, consistent with the "12 multiplications" stated in 1986 Chudnovsky/Chudnovsky: 
    X3 = Q[0] * Q[2] * P[1]**2 - P[0] * P[2] * Q[1]**2
    Y3 = Q[1] * Q[2] * P[0]**2 - P[1] * P[2] * Q[0]**2
    Z3 = Q[0] * Q[1] * P[2]**2 - P[0] * P[1] * Q[2]**2

    return ( X3 % p, Y3 % p, Z3 % p)

def point_double(P, p, c): #6M + 3S + 3add, consistent with the "9 multiplications" stated in 1986 Chudnovsky/Chudnovsky:
    
    if P is None:
        return None 
    
    X3 = P[1] * ( P[2]**3 - P[0]**3 )
    Y3 = P[0] * ( P[1]**3 - P[2]**3 )
    Z3 = P[2] * ( P[0]**3 - P[1]**3 )  

    return ( X3 % p, Y3 % p, Z3 % p)

def doubleAndAdd( G, k , p ,c):

    addend = G
    result = None
    
    for b in bits(k) :
        if b:
            result = point_add(result, addend, p)
        addend = point_double(addend, p, c)
    return result

def findOrder(P, POI, p,c):
    
    for i in range(2,1104601): # 1104601 upper range on the number of points 
        res = doubleAndAdd(P,i,p,c)
        if res == POI:
            print( "[",i,"]", P, "= ", res )
            

p = 1051
c = 1
d = 6
G = (4,2,6)  #base point

Pinfinity = (1,1050,0) #(1,-1,0) inverse of O itself, inverse of (U,V,W) is (V,U,W)

print ( "d^3 == 27c? False expected : ", (d**3) % p == (27 *c) % p)

print("is point on the curve?", checkPoint(G,p,c,d))

findOrder(G, Pinfinity, p,c)

When I run this code, the result is

[ 77400 ] (4, 2, 6) =  (1, 1050, 0)
[ 103500 ] (4, 2, 6) =  (1, 1050, 0)
[ 153540 ] (4, 2, 6) =  (1, 1050, 0)
[ 164340 ] (4, 2, 6) =  (1, 1050, 0)
[ 169290 ] (4, 2, 6) =  (1, 1050, 0)
[ 233640 ] (4, 2, 6) =  (1, 1050, 0)

Normaly, if a point P has an order k then [k]P=O where O is the point at the infinity. And if you continue adding P to itself, one will get [2k]P=O, more generally it is [ x mod k]P

So if 77400 is order of P then [154800]P=0 but it is not

  • what is missing here so that result is not consistent with the expected values?

note : c=1 has no effect. It only contributes to point_double when c>1

elliptic-curve python
1 Answers

I've figured out the problem, and the real solution is not easy. The order of the point (4,2,6) is 77400.

The problem relies on the implementation of the doubleAndAdd algorithm. Consider the starting point with G. The variables addend and result during the start and during the second visit for the point G are not the same since the addend was updated.

def doubleAndAdd( G, k , p ,c):

    addend = G
    result = None
    
    for b in bits(k) :
        if b:
            result = point_add(result, addend, p)
        addend = point_double(addend, p, c)
    return result

Instead, I've updated the findOrder

def findOrder(P, POI, p,c):
    
    #for i in range(2,1104601): # 1104601 upper range on the number of points 
    for i in range(1104601):
        Gprime = doubleAndAdd(G,i,p,c)
        if Gprime == POI:
            print(i, " ", Gprime)
            return i

So, it returns in the first hit of the Point at the Infinity as the order of the point.

The real solution requires the order of the base point beforehand, or better find the order of the curve since the order of any element dives the order of the curve by Lagrange Theorem. Once it is found, we can use the formula [ x mod k]P in the doubleAndAdd.

Note: there are existing Schoof's Algorithm in Python to count the number of points, however, one needs to change the Projective coordinates the Affine coordinates. Marc JoyeJean and Jacques Quisquater provided the formulas in

user_18205530
Related