2
$\begingroup$

In the elliptic curve: $y^2 = x^3 + 20x + 13 \bmod{2111}$. Using the point $P=(3, 10)$

I am wondering how to multiply this point by the scalar $57$?

I realize I can write $57*P$ as $2^5*P + 2^4*P + 2^3*P + P = 2(2(2(2(2P)))) + 2(2(2(2P))) +2(2(2P)) + P$.

My question is what is the best way to calculate these doubles and additions?

Some pseudo code or real code would be greatly appreciated although even a tutorial on how to do this by hand would help a lot!

$\endgroup$
  • $\begingroup$ Are you familiar with how to add points on an Elliptic curve? $\endgroup$ – figlesquidge Nov 14 '13 at 16:05
2
$\begingroup$

Basically, you keep a separate variable, which is initially $P$ and then double it again and again. Initialize the sum with 0 and add the according values of the other variable. Basically this method is described as "square and multiply" for exponentiation (which works just the same way with squaring instead of doubling and multiplying instead of adding).

In your example:

  • Let's transform your number $57$ into a binary number $F$ and address its digits as $F[i]$.
  • $T:= P; S:= 0$
  • for all $i$:
    • if $F[i] == 1: S+= T$
    • T := 2T
  • return $S$
$\endgroup$
2
$\begingroup$

The typical way to do this is the double and add method.

You start with the binary expansion of the scalar $57_{10}=111001_2$

Then scanning right from left, for each bit you double and if the bit is set to $1$ you add.

With elliptic curves it would look like this:

$Q\gets\infty$ (or the point at infinity since it is the identity element)
$P_{tmp}\gets P$
$bin\gets [1,0,0,1,1,1]$ (i.e., the binary expansion of the scalar reversed)
for $i$ in $bin$:
$\ \ $if $i==1$:
$\ \ \ \ \ Q\mathrel{+}=P_{tmp}$
$\ \ P_{tmp}=P_{tmp}+P_{tmp}$
return $Q$

$\endgroup$
0
$\begingroup$

The exist answers have detailed the pseudo code, I will give the python implementation.

1. Given the Elliptic curve $E:y^2= x^3+20 x + 13 \pmod {2111} , \#E=2133$

We calculate the $57P$ with the double and add algorithm by a primitive point $P=(x_p,y_p)=(3,10)$ on the curve. We know that $57_{10}=111001_{2}$

2. The Python implementation:

# -*- coding:UTF-8

# Extended Euclidean algorithm
def extended_gcd(aa, bb):
   lastremainder, remainder = abs(aa), abs(bb)
   x, lastx, y, lasty = 0, 1, 1, 0
   while remainder:
       lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
       x, lastx = lastx - quotient*x, x
       y, lasty = lasty - quotient*y, y
   return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
# calculate `modular inverse`
def modinv(a, m):
   g, x, y = extended_gcd(a, m)
   if g != 1:
       raise ValueError
   return x % m

# double function
def ecc_double(x1, y1, p, a):
   s = ((3*(x1**2) + a) * modinv(2*y1, p))%p
   x3 = (s**2 - x1 - x1)%p
   y3 = (s*(x1-x3) - y1)%p
   return (x3, y3)
# add function
def ecc_add(x1, y1, x2, y2, p, a):
   s = 0
   if (x1==x2):
       s = ((3*(x1**2) + a) * modinv(2*y1, p))%p
   else:
       s = ((y2-y1) * modinv(x2-x1, p))%p
   x3 = (s**2 - x1 - x2)%p
   y3 = (s*(x1 - x3) - y1)%p
   return (x3, y3)
def double_and_add(multi, generator, p, a):
   (x3, y3)=(0, 0)
   (x1, y1) = generator
   (x_tmp, y_tmp) = generator
   init = 0
   for i in str(bin(multi)[2:]):
       if (i=='1') and (init==0):
          init = 1
       elif (i=='1') and (init==1):
          (x3,y3) = ecc_double(x_tmp, y_tmp, p, a)
          (x3,y3) = ecc_add(x1, y1, x3, y3, p, a)
          (x_tmp, y_tmp) = (x3, y3)
       else:
          (x3, y3) = ecc_double(x_tmp, y_tmp, p, a)
          (x_tmp, y_tmp) = (x3, y3)
   return (x3, y3)

# the curve:$E:y^2= x^3+20 x + 13 mod 2111 , #E=2133$
p = 2111
a = 20
b = 13
# the primitive point (3, 10)
generator=(3, 10)
# 57 = b(111001)
print "57P = ", double_and_add(57, generator, p, a)

3. Run this program, we can get the result:

57P =  (470, 1757)

4. the modinv function is taken from here.

https://gist.github.com/ssanin82/0b55a730ddbc7dafa94d

$\endgroup$
  • $\begingroup$ gist.github.com/ssanin82/0b55a730ddbc7dafa94d $\endgroup$ – kelalaka Sep 30 at 15:09
  • $\begingroup$ @kelalaka Yes I borrow the modinv function, Then I developed the main body of the algorithm. The main body of the program is also in my github. Any problem? $\endgroup$ – 孙海城 Sep 30 at 15:20
  • $\begingroup$ One should always give the reference even some parts are taken, right? $\endgroup$ – kelalaka Sep 30 at 15:21
  • $\begingroup$ @kelalaka OK, I wrote it long ago, so I forgot the details. $\endgroup$ – 孙海城 Sep 30 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.