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

没有效果。它仅在

point_double

 时对 

c>1

有贡献

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

因此，它会在 Infinity 处的点的第一次命中中作为该点的顺序返回。

真正的解决方案需要预先确定基点的阶数，或者更好地找到曲线的阶数，因为任何元素的阶数都会通过拉格朗日定理淹没曲线的阶数。一旦找到，我们就可以在

[ x mod k]P

中使用公式

doubleAndAdd

。

注意：Python 中已有Schoof 算法来计算点数，但是需要将投影坐标更改为仿射坐标。 Marc JoyeJean 和 Jacques Quisquater 提供了

中的公式

• Hessian 椭圆曲线和侧信道攻击

Answer 2

我认为问题在于大小的选择，当模数大小与标量乘数大小不同时。