Elliptic curve point addition using bouncycastle

Question

My problem is very straightforward: I need to add two points over Fp using Java. As soon as java api lacks some ecc utils I'm using bouncycastle.

Here is the formulas used:

P + Q = -R
α = (yq - yp)/(xq-xp)
уr = -yp + α(xp - xr)
xr = α^2 - xp - xq

And quick implementation of above formulas in java:

String newline = System.lineSeparator();
BigInteger yp = new BigInteger("4018974056539037503335449422937059775635739389905545080690979365213431566280");
BigInteger yq = new BigInteger("17614944419213781543809391949654080031942662045363639260709847859438286763994");
BigInteger xp = new BigInteger("2");
BigInteger xq = new BigInteger("57520216126176808443631405023338071176630104906313632182896741342206604859403");
BigInteger p = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564821041");
BigInteger a_ = new BigInteger("7");
BigInteger b_ = new BigInteger("43308876546767276905765904595650931995942111794451039583252968842033849580414");
ECFieldElement x1 = new ECFieldElement.Fp(p, xp);
ECFieldElement y1 = new ECFieldElement.Fp(p, yp);

ECFieldElement x2 = new ECFieldElement.Fp(p, xq);
ECFieldElement y2 = new ECFieldElement.Fp(p, yq);


ECFieldElement a = new ECFieldElement.Fp(p, a_);
System.out.print("A = " + a.toBigInteger() + newline);
ECFieldElement b = new ECFieldElement.Fp(p, b_);
System.out.print("B = " + b.toBigInteger() + newline);

BigInteger alpha = (yq.subtract(yp)).divide((xq.subtract(xp)));
ECFieldElement alpha_ = new ECFieldElement.Fp(p, alpha);

ECFieldElement xr = new ECFieldElement.Fp(p,alpha.pow(2).subtract(x1.toBigInteger()).subtract(x2.toBigInteger()));
ECFieldElement yr = new ECFieldElement.Fp(p,y1.negate().add(x1.multiply(alpha_)).subtract(xr.multiply(alpha_)).toBigInteger());
System.out.print("P + Q x coordinate:" + xr.toBigInteger() + newline);
System.out.print("P + Q y coordinate:" + yr.toBigInteger() + newline);

The output as follows:

A = 7
B = 43308876546767276905765904595650931995942111794451039583252968842033849580414
P + Q x coordinate:-57520216126176808443631405023338071176630104906313632182896741342206604859405
P + Q y coordinate:53877070562119060208450043081406894150999252942914736939037812638743133254761

These results are incorrect, because following Sage script and this service have same result and it's different from mine.

p = 57896044618658097711785492504343953926634992332820282019728792003956564821041;
A = 7;
B = 43308876546767276905765904595650931995942111794451039583252968842033849580414;
xp = 2;
yp = 4018974056539037503335449422937059775635739389905545080690979365213431566280;
xq = 57520216126176808443631405023338071176630104906313632182896741342206604859403;
yq = 17614944419213781543809391949654080031942662045363639260709847859438286763994;
F = GF(p)
C = EllipticCurve(F, [ A, B ])
P = C(xp, yp)
Q = C(xq, yq)
P + Q
(51107436475926671824327183547145585639291252685317542895128927043108270260044 : 8275382333273532770266263241039288966808027917805772529614893800343160424015 : 1)

Can someone please point me out what I'd fix to get the right result?

Answer 1

Here's a code example showing both an explicit calculation and also how you would just use the built-in library functionality for this. The output agrees with the Sage output in both cases.

package org.bc.sample;

import java.math.BigInteger;

import org.bouncycastle.math.ec.ECCurve;
import org.bouncycastle.math.ec.ECFieldElement;
import org.bouncycastle.math.ec.ECPoint;

public class ECPointAddition
{
    public static void main(String[] args)
    {
        BigInteger prime = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564821041");
        BigInteger A = new BigInteger("7");
        BigInteger B = new BigInteger("43308876546767276905765904595650931995942111794451039583252968842033849580414");

        ECCurve curve = new ECCurve.Fp(prime, A, B);

        BigInteger Px = new BigInteger("2");
        BigInteger Py = new BigInteger("4018974056539037503335449422937059775635739389905545080690979365213431566280");
        BigInteger Qx = new BigInteger("57520216126176808443631405023338071176630104906313632182896741342206604859403");
        BigInteger Qy = new BigInteger("17614944419213781543809391949654080031942662045363639260709847859438286763994");

        // Explicit affine addition
        ECFieldElement xp = curve.fromBigInteger(Px), yp = curve.fromBigInteger(Py);
        ECFieldElement xq = curve.fromBigInteger(Qx), yq = curve.fromBigInteger(Qy);
        ECFieldElement alpha = yq.subtract(yp).divide(xq.subtract(xp));
        ECFieldElement xr = alpha.square().subtract(xp).subtract(xq);
        ECFieldElement yr = xp.subtract(xr).multiply(alpha).subtract(yp);

        System.out.println("EXPLICIT");
        System.out.println(xr.toBigInteger().toString(10));
        System.out.println(yr.toBigInteger().toString(10));

        // Point addition using built-in formulae
        ECPoint P = curve.createPoint(Px, Py);
        ECPoint Q = curve.createPoint(Qx, Qy);
        ECPoint R = P.add(Q).normalize();

        System.out.println("BUILT-IN");
        System.out.println(R.getAffineXCoord().toBigInteger().toString(10));
        System.out.println(R.getAffineYCoord().toBigInteger().toString(10));
    }
}

When you see formulae involving the coordinates of elliptic curve points, it should be understood that those calculations need to be done in the finite field the coordinates belong to, whereas you are calculating e.g. alpha just using BigInteger math. The divide in particular goes wrong as a result.

Note also that the explicit formula here won't work if the two input points have the same x-coordinate. The built-in library method handles this sort of edge case correctly, so I would recommend you use that.

---

Runnable version of code can be found here.