Блог

Я реализовал кривую мешанины с помощью 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 amp; 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

Я разобрался в проблеме, и реальное решение непросто. Порядок точек (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 существует алгоритм Шуфа, однако для этого необходимо изменить проективные координаты на аффинные координаты. Марк Джойеджан и Жак Кискватер предоставили формулы в

• Эллиптические кривые мешанины и атаки по побочным каналам