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.

 

---

Support this blog if you do like!

    

---