时间戳

首页 > 解决方案 > Python：点的顺序在 Hessian 曲线实现中不规则

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

问题描述

我已经用 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 是Pthen的顺序，[154800]P=0但不是

注意： c=1没有效果。它只有助于point_double何时c>1

标签： pythonelliptic-curve

解决方案

我已经弄清楚了问题所在，真正的解决方案并不容易。点的顺序(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

因此，它在点的第一次命中时返回，作为点的顺序。

真正的解决方案需要事先知道基点的阶数，或者更好地找到曲线的阶数，因为任何元素的阶数都会通过拉格朗日定理潜入曲线的阶数。找到后，我们就可以使用[ x mod k]P.doubleAndAdd

注意： Python中有现有的Schoof算法来计算点数，但是需要将Projective坐标更改为Affine坐标。Marc JoyeJean 和 Jacques Quisquater 在

推荐阅读