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.

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;
}

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.

## 1 Comment