error in elliptic curve scalar multiplication code

asked 2018-04-23 08:58:43 +0100

santoshi
131 ●17 ●22 ●37

updated 2018-04-24 18:47:41 +0100

slelievre
17684 ●22 ●160 ●349 http://carva.org/samue...

The following code i have written for scalar multiplication over elliptic curve for prime field 37 but it gives me error for some of the scalar. the method is LSB first.

import time
import sys
from sage.all import *

# elliptic curve domain parameters, prime192v1

# domain parameters

p = 37
A = 7
B = 25
G = 1
n = 21

print "\n p =", p
print "\n A =", A
print "\n B =", B
F = GF(p)

E = EllipticCurve(F, [A,B])
print "\n Elliptic curve equation:", E

def point_add(P, Q):

    x1 = P[0]
    y1 = P[1]
    x2 = Q[0]
    y2 = Q[1]

    # check P == O
    if P == [0, 0]:
        return Q

    # check Q == O
    if Q == [0, 0]:
        return P

    # check Q == -P
    if x1 == x2 and y1 + y2 == 0:
        return [0, 0]

    # check P == Q
    if P == Q:
        return point_double(P)
    slope = F((y2 - y1)/(x2 - x1))
    x3 = F(slope**2 - x1 - x2)
    y3 = F(slope * (x1 - x3) - y1)

    return[x3, y3]

def point_double(P):

    # if P == [0, 0]:
    #     return [0, 0]

    x1 = P[0]
    y1 = P[1]

    slope = F((3 * x1**2 + A)/(2 * y1))
    x3 = F(slope**2 - 2 * x1)
    y3 = F(slope * (x1 - x3) - y1)
    return [x3, y3]

def scalar_mult(K,P):
    print('hi')
    b_k = ZZ(K).bits(); print(b_k) # ; K.digits(2)
    l = len(b_k); l
    sum1 = 0*P; sum1
    print(b_k[0])
    if b_k[0] == 1:
        sum1 = P; sum1
    else:
        sum1 = 0
    Q = P; print(Q)
    for i in range(1, l):
        Q = point_double(Q); print(Q)
        if b_k[i] == 1: 
            print (b_k[i])
            # sum = point_add(sum, Q)
            sum1 = point_add(sum1, Q)
            print(sum1)
            # Q = point_double(Q)
    return sum1

P = E(20,32); P  #; P.random_point(); P
f1 = P.order(); f1
K = randint(1,f1); K
answer1 = K*P; answer1
start1 = time.time()
answer = scalar_mult(K,P); answer
end1   = time.time()
print "\n Time Required to compute scalar multiplication: %s" % (end1 - start1)
answer2 = E(answer); answer2

answered 2018-04-25 01:45:40 +0100

dan_fulea
5537 ●5 ●43 ●95

This was started as a comment, but it ran out of space. So it became an answer.

Please fix the representation of the "zero" on the curve. The comment

# check P == O
if P == [0, 0]:
    return Q

shows where things may go wrong. Explicitly:

Please use (for the own safety) different notations for different objects (of different classes). For instance, P should not stay for both an "elliptic curve point" like P = E(20,32) and a vector like in the return [0,0] of the functions used.
How is E(0), the point at infinity, represented as a vector?

A possible way to avoid all problems is to use always "true points on the elliptic curve", since they come with the whole structural functionality. For instance:

def point_add(P, Q):
    """P, Q are points on the same elliptic curve, not vectors
    """
    # check P == O
    if P.is_zero():
        return Q

    # check Q == O
    if Q.is_zero():
        return P

    x1, y1 = P.xy()
    x2, y2 = Q.xy()

    # check Q == -P
    if x1 == x2 and y1 + y2 == 0:
        return P.curve()(0)

    # check P == Q
    if P == Q:
        return point_double(P)

    slope = F( (y2 - y1)/(x2 - x1) )
    x3 = F( slope**2 - x1 - x2 )
    y3 = F( slope * (x1 - x3) - y1 )

    return P.curve()( x3, y3 )

It is a good idea to write a function, then test it immediately. (Some IDE's ~ integrated development environments like eclipse and pycharm give a good, supported debug framework.) In this case:

Then

E = EllipticCurve( GF(37), [7, 25] )
P = E( 20, 32 )
Q = E(  1, 12 )
point_add( P, Q )

delivers

sage: E = EllipticCurve( GF(37), [7, 25] )
....: P = E( 20, 32 )
....: Q = E(  1, 12 )
....: point_add( P, Q )
....: 
(25 : 27 : 1)

One should also add in a test suite the particular cases, for instance:

sage: point_add( P, E(0) )
(20 : 32 : 1)
sage: point_add( P, E(0) ) == P
True
sage: point_add( E(0), P )
(20 : 32 : 1)
sage: point_add( E(0), P ) == P
True
sage: point_add( P, -P )
(0 : 1 : 0)
sage: point_add( P, -P ).is_zero()
True

To the posted question, the simple answer would have been: "(0,0) is not a point on the curve, but some functions return it..."

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

error in elliptic curve scalar multiplication code

1 Answer

Your Answer

Question Tools

Stats

error in elliptic curve scalar multiplication code edit

1 Answer

Your Answer

Question Tools

Stats

error in elliptic curve scalar multiplication code