Ask Your Question
0

error in elliptic curve scalar multiplication code

asked 2018-04-23 01:58:43 -0600

santoshi gravatar image

updated 2018-04-24 11:47:41 -0600

slelievre gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-04-24 18:45:40 -0600

dan_fulea gravatar image

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 more

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-04-23 01:58:43 -0600

Seen: 38 times

Last updated: Apr 24