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?

Serene

What is your input, expected output and the current output? – Samora

Input = 059E2BF5E2C7A4098C164B29A91CF70508D2FD1A256A60656FD2593BDB980FAA / Expected ouput = 04 + (DA43096D079CED007CDF810ECB27030FFBDBCCAB0400A5A040D282EF8049805B,A4F8D0BE0BDABE528524245B5BBD5A125835A302F61156CE6BE48530B8F53C66) – Ruble

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.

Tommietommy

It works, but the are this functions only for secp256k1 or only for Prime Curves? Where van I find a full documentation for Elliptic Curve (Prime, F2M, etc.)? – Ruble

@BenvanHartingsveldt: Those formulas are for curves over a prime field in Weierstrass format, which includes the commonly used ones. I don't think there's full doc any one place because this is a new and still-changing field, but for the curves it covers I like the SECG docs at www.secg.org -- they include most of what I (and maybe you) need without huge amounts of digression and fluff. And of course Stack is always good, especially crypto.SX and security.SX :-) – Tommietommy