# error in elliptic curve scalar multiplication code

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

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])
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
start1 = time.time()
end1   = time.time()
print "\n Time Required to compute scalar multiplication: %s" % (end1 - start1)

edit retag close merge delete

Sort by » oldest newest most voted

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 )


delivers

sage: E = EllipticCurve( GF(37), [7, 25] )
....: P = E( 20, 32 )
....: Q = E(  1, 12 )
....:
(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
(20 : 32 : 1)
sage: point_add( E(0), P ) == P
True
(0 : 1 : 0)
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..."

more