Ask Your Question

# 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

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

edit retag close merge delete

## 1 Answer

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 )
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..."

more

## Your Answer

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

Add Answer

## Stats

Asked: 2018-04-23 08:58:43 +0200

Seen: 234 times

Last updated: Apr 25 '18