Double and Add Method

Computing a new point on an elliptic curve Q = kP for given k and P could be performed by combination of point addition and point doubling. Thus, computation is performed by less than k steps. This approach is called as addition chains. Finding the optimum addition chain is NP-Complete problem.

In this post, we’ll mention the double and add method (a.k.a. binary method) and implement the concept in Java.

---

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

---

Vlog

Implementation

public static int multiplyScalarPoint(int k){

String kAsBinary = Integer.toBinaryString(k);

int step = 0;

//decimal to binary conversion
System.out.println("k = ("+k+")10 = ("+kAsBinary+")2\n");

int q = 1, p = 1;
int a = 0, b = 0;

//header
System.out.println("i\tki\t|\ta\t\tb\n--\t--\t|\t--\t\t--");

for(int i=1;i<kAsBinary.length();i++){

System.out.print(i+"\t");

int currentBit = Integer.parseInt(kAsBinary.substring(i, i+1));
System.out.print(currentBit+"\t|\t");

System.out.print(q+"P+"+q+"P=");

q = q+q;
a = q;
step++;

System.out.print(a+"P\t");

if(currentBit == 1){

System.out.print(q+"P+"+p+"P=");

q = q + p;
b = q;
step++;

System.out.print(b+"P\t");

}

b = 0;

System.out.println("");

}

System.out.println("\nQ=kP is calculated in "+step+"th step");

return step;

}

What We Have Gained

Suppose that k = 1017. Then, going to Q = 1017P is implemented rapidly by 16 steps as shown above. However, brute force attack has to be applied to calculate k for given points Q and P. This means k = 1017 steps required to implement the brute force attack for the worst case scenario. (a.k.a. Discrete Logarithm Problem for Elliptic Curves)

Let’s monitor the change of k over required steps for computing kP.

The figure illustrates the easiness of computing Q = kP for given k and P with binary method. Also, it shows the difficulty of computing k for given P and Q=kP with brute force method. Step(kP) remains stable while k increased dramatically. That is the power of the elliptic curve cryptography.

Python

Each elliptic curve form has its own method for constructing addition formulas. In the Weierstrass and Koblitz forms, addition involves drawing a line that intersects two points, and the reflection of the third intersection point across the x-axis gives the sum. Doubling a point requires drawing a tangent line at that point. The Edwards form, however, does not have a graphical representation for addition; instead, it relies solely on a mathematical formula that can be proven.

LightECC is a lightweight elliptic curve cryptography library for Python that simplifies ECC arithmetic. It abstracts the complexities of different curve forms, allowing users to define an elliptic curve and perform addition, subtraction, multiplication, and division of points using standard operators without needing to understand the underlying principles.

from lightecc import LightECC

# build an elliptic curve
ec = LightECC(
    form_name = "weierstrass", # or edwards, koblitz.
    curve_name = "secp256k1", # bitcoin's curve
)

# get the base point
G = ec.G

# addition
_2G = G + G
_3G = _2G + G
_5G = _3G + _2G
_10G = _5G + _5G

# subtraction
_9G = _10G - G

# multiplication
_20G = 20 * G
_50G = 50 * G

# division
_25G = _50G / G

 

---

---

---

Support this blog if you do like!

    

---