Ask Your Question
0

elliptic curve scalar multiplication

asked 2018-03-29 07:31:23 +0100

santoshi gravatar image

kindly provide me the code for left to right double and add scalar multiplication for following characteristics of elliptic curve for the following parameter. prime field P=37, A=7 B=25 G=(33,9) n=21

edit retag flag offensive close merge delete

Comments

In a dialog with the sage interpreter, by "coincidence", the following data ould be digested:

sage: E = EllipticCurve( GF(37), [7, 25] )
sage: G = E.point( [33, 9] )
sage: 21*G
(0 : 1 : 0)
sage: E.order().factor()
2 * 3 * 7

(I was trying to rather guess the framework.)

What is/are in this context the "left to right double and add scalar multiplication"?

(As seen, sage simply computes the multiplication 21*G.)

dan_fulea gravatar imagedan_fulea ( 2018-03-29 14:59:04 +0100 )edit

tx for your reply but i want the compution using above algorithm. also by defining function point_mul(k,p) where k is scalar and p is the point.

santoshi gravatar imagesantoshi ( 2018-03-29 17:06:09 +0100 )edit
1

Which algorithm should be used? (There is no description of an algorithm, no reference for a specific one.) Why not simply use the already implemented sage algorithm?

Note that 21*G is computed above by using the class method __mul__ for the class of the instance G.

For instance:

sage: G
(33 : 9 : 1)
sage: G.__class__
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: G.__mul__(7)
(1 : 25 : 1)
sage: 7*G
(1 : 25 : 1)
sage: G.__mul__(7) == 7*G
True
dan_fulea gravatar imagedan_fulea ( 2018-03-29 22:20:03 +0100 )edit

left to right double and add scalar multiplication algorithm for above parameter KP=k_0p+k_12p+K_24P+.........+K_l2^l-1*P I/P point P which is on elliptic curve , K=(k_l-1K_l-2.....K_0)_2 (that is binary representation of scalar) output KP uses P and Q

Q= infinity

for i=l-1 to 0 do Q=2Q if k_i=1 then Q=Q+P
return Q

santoshi gravatar imagesantoshi ( 2018-03-30 17:07:33 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-03-30 19:29:37 +0100

dan_fulea gravatar image

The following answer does not implement the two functions "add" and "double" on an elliptic curve, instead, it uses the already existing functionality of sage. (It would be too much to implement also these basic functions depending on the form of the elliptic curve and the base field characteristic.)

Code:

def left_to_right_double_and_add(n, G):
    """n is a positive integer number,
    G is a rational point of an elliptic curve E, 
    defined over some finite field F.
    This routine computes
    n*G
    in an ad-hoc manner.
    We use the standard add, and doubling on E,
    and do not implemented them here.
    """
    digits = ZZ(n).digits(base=2)
    E = G.curve()
    # F = E.base_field()
    P = G    # this corresponds to 1*G, init
    nG = E(0)    # and we add further contributions
    for digit in digits:
        if digit:
            nG = nG.__add__(P)    # or simply nG += P
        P = P.__mul__(2)          # or simply P  *= 2
        # print "\tdigit=%s P=%s nG=%s" % (digit, P, nG)
    return nG

# quick test on the given curve with the given poing:
E = EllipticCurve( GF(37), [7, 25] )
G = E.point( [33, 9] )

for n in [1..9]:
    nG = left_to_right_double_and_add(n, G)
    print ( "sage %s*G = %13s | ad-hoc %s*G = %13s | Are they equal? %s"
            % ( n, n*G, n, nG, n*G == nG ) )

This gives in the test:

sage 1*G =  (33 : 9 : 1) | ad-hoc 1*G =  (33 : 9 : 1) | Are they equal? True
sage 2*G =  (9 : 15 : 1) | ad-hoc 2*G =  (9 : 15 : 1) | Are they equal? True
sage 3*G =  (2 : 11 : 1) | ad-hoc 3*G =  (2 : 11 : 1) | Are they equal? True
sage 4*G = (35 : 15 : 1) | ad-hoc 4*G = (35 : 15 : 1) | Are they equal? True
sage 5*G =  (15 : 8 : 1) | ad-hoc 5*G =  (15 : 8 : 1) | Are they equal? True
sage 6*G = (30 : 22 : 1) | ad-hoc 6*G = (30 : 22 : 1) | Are they equal? True
sage 7*G =  (1 : 25 : 1) | ad-hoc 7*G =  (1 : 25 : 1) | Are they equal? True
sage 8*G = (31 : 27 : 1) | ad-hoc 8*G = (31 : 27 : 1) | Are they equal? True
sage 9*G = (17 : 32 : 1) | ad-hoc 9*G = (17 : 32 : 1) | Are they equal? True
edit flag offensive delete link more

Comments

in the above code how the addition and doubling is obtained.

santoshi gravatar imagesantoshi ( 2018-03-31 19:14:55 +0100 )edit

what are the standard add and doubling on E

santoshi gravatar imagesantoshi ( 2018-03-31 19:24:42 +0100 )edit

the above code gives me following error when run it on sagemath cloud Error in lines 13-16 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "<string>", line 4 salvus.execute_with_code_decorators(*_salvus_parsing.dec_args[Integer(3)]) ^ SyntaxError: invalid syntax

santoshi gravatar imagesantoshi ( 2018-03-31 19:29:50 +0100 )edit

Without the $[n \bmod order]G$ check this code will fail as see on Stackoverflow : order of a point is not regular in Hessian Curve implementation

klx gravatar imageklx ( 2020-08-19 21:09:43 +0100 )edit

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-03-29 07:31:23 +0100

Seen: 2,344 times

Last updated: Mar 30 '18