Python：Hessian 曲线实现中点的顺序不规则

Question

我已经用 Python

实现了 Hessian 曲线

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)

当我运行这段代码时，结果是

[ 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)

通常，如果点 P 有阶 k，则 [k]P=O 其中 O 是无穷远点。如果你继续把 P 加到它自己上，就会得到 [2k]P=O，更一般的是 [ x mod k]P

因此，如果 77400 是 P 的顺序，则 [154800]P=0 但它不是

这里缺少什么结果与预期值不一致？

注意： c=1没有效果。它仅在 c>1

时对 point_double 有贡献

Answer 1

问题我想通了，真正解决起来也不容易。 (4,2,6)点的顺序是77400.

问题依赖于doubleAndAdd算法的实现。考虑 G 的起点。变量 addend 和 result 在点 G 的开始和第二次访问期间不相同，因为 addend 已更新。

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

相反，我更新了 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

所以，它returns在无穷大点的第一个命中作为点的顺序。

真正的解法需要事先得到基点的顺序，或者最好找到order of the curve since the order of any element dives the order of the curve by Lagrange Theorem。一旦找到，我们就可以在doubleAndAdd.

中使用公式[ x mod k]P

注意：现有Schoof's Algorithm in Python可以统计点数，但是需要将Projective坐标改成Affine坐标。 Marc JoyeJean 和 Jacques Quisquater 提供了

中的公式

Hessian Elliptic Curves and Side-Channel Attacks

Python：Hessian 曲线实现中点的顺序不规则

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

python

elliptic-curve