Elliptic Curve Multiplication Function

Question

I'm trying to make my own library for the elliptic curve. Some things work, but some others don't.

To calculate a public key from a private key, you should multiply the Generator Point with the private key, and you get another point: the public key Point (ECPoint = BigInteger * ECPoint).

Now, I have a private key, and I multiply it with the Generator Point of the Secp256k1 curve. I get a a key, but it is not the key I should get.

This is my JAVA code:

import java.math.BigInteger;

public class Point{

    public static final Point INFINITY = new Point();

    private final BigInteger x;
    private final BigInteger y;

    private Point(){
        this.x = null;
        this.y = null;
    }

    public Point(BigInteger x,BigInteger y){
        if(x==null || y==null){
            throw new NullPointerException("x or y is null");
        }
        this.x = x;
        this.y = y;
    }

    public BigInteger getX(){
        return this.x;
    }

    public BigInteger getY(){
        return this.y;
    }

    public boolean isInfinite(){
        return this.x==null || this.y==null;
    }

    public Point add(Curve ec,Point Q){
        Point P = this;

        if(P.isInfinite()){
            return Q;
        }
        if(Q.isInfinite()){
            return P;
        }
        if(P.getX().equals(Q.getX()) && P.getY().equals(Q.getY())){
            return this.twice(ec);
        }

        BigInteger lambda = Q.getY().subtract(P.getY()).divide(Q.getX().subtract(P.getX()));

        BigInteger xR = lambda.pow(2).subtract(P.getX()).subtract(Q.getX());
        BigInteger yR = lambda.multiply(P.getX().subtract(xR)).subtract(P.getY());

        Point R = new Point(xR,yR);

        return R;
    }

    public Point twice(Curve ec){
        if(this.isInfinite()){
            return this;
        }

        BigInteger lambda = BigInteger.valueOf(3).multiply(this.getX().pow(2)).add(ec.getA()).divide(BigInteger.valueOf(2).multiply(this.getY()));

        BigInteger xR = lambda.pow(2).subtract(this.getX()).subtract(this.getX());
        BigInteger yR = lambda.multiply(this.getX().subtract(xR)).subtract(this.getY());

        Point R = new Point(xR,yR);

        return R;
    }

    public Point multiply(Curve ec,BigInteger k){
        //Point P = this;
        //Point R = Point.INFINITY;

        if(this.isInfinite()){
            return this;
        }

        if(k.signum()==0){
            return Point.INFINITY;
        }

        BigInteger h = k.multiply(BigInteger.valueOf(3));
        Point neg = this.negate();
        Point R = this;

        for(int i=h.bitLength()-2;i>0;i--){
            R = R.twice(ec);

            boolean hBit = h.testBit(i);
            boolean eBit = k.testBit(i);

            if(hBit!=eBit){
                R = R.add(ec,(hBit?this:neg));
            }
        }

        return R;
    }

    public Point negate(){
        if(this.isInfinite()){
            return this;
        }

        return new Point(this.x,this.y.negate());
    }

}

Is there something with my code? Is there a specific multiplier algorithm for secp256k1?

Answer 1

Yes there is something wrong with your code; you are trying to divide in Z (using BigInteger) when you need to divide in Zp (aka Z/pZ) where p is the curve parameter defining the underlying field (for secp256k1 see SEC2). Modular division is implemented in Java by taking the modular inverse and modular-multiplying; see Scalar Multiplication of Point over elliptic Curve . Also you need to take at least the final results mod p, and it is usually more efficient to do the stepwise results as well.