Add initial implementation of curve25519 (in Weierstrass form!)

4 files changed, 653 insertions, 1 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519.java b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519.java
new file mode 100644
index 00000000..87802847
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519.java
@@ -0,0 +1,105 @@
+package org.bouncycastle.math.ec.custom.djb;
+
+import java.math.BigInteger;
+
+import org.bouncycastle.math.ec.ECCurve;
+import org.bouncycastle.math.ec.ECFieldElement;
+import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.custom.sec.Nat256;
+import org.bouncycastle.math.field.FiniteFields;
+import org.bouncycastle.util.encoders.Hex;
+
+public class Curve25519 extends ECCurve
+{
+    public static final BigInteger q = Nat256.toBigInteger(Curve25519Field.P);
+
+    private static final int Curve25519_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED;
+
+    protected Curve25519Point infinity;
+
+    public Curve25519()
+    {
+        super(FiniteFields.getPrimeField(q));
+
+        this.infinity = new Curve25519Point(this, null, null);
+
+        this.a = fromBigInteger(new BigInteger(1,
+            Hex.decode("2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA984914A144")));
+        this.b = fromBigInteger(new BigInteger(1,
+            Hex.decode("7B425ED097B425ED097B425ED097B425ED097B425ED097B4260B5E9C7710C864")));
+        this.order = new BigInteger(1, Hex.decode("1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED"));
+        this.cofactor = BigInteger.valueOf(8);
+
+        this.coord = Curve25519_DEFAULT_COORDS;
+    }
+
+    protected ECCurve cloneCurve()
+    {
+        return new Curve25519();
+    }
+
+    public boolean supportsCoordinateSystem(int coord)
+    {
+        switch (coord)
+        {
+        case COORD_JACOBIAN_MODIFIED:
+            return true;
+        default:
+            return false;
+        }
+    }
+
+    public BigInteger getQ()
+    {
+        return q;
+    }
+
+    public int getFieldSize()
+    {
+        return q.bitLength();
+    }
+
+    public ECFieldElement fromBigInteger(BigInteger x)
+    {
+        return new Curve25519FieldElement(x);
+    }
+
+    protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression)
+    {
+        return new Curve25519Point(this, x, y, withCompression);
+    }
+
+    protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression)
+    {
+        return new Curve25519Point(this, x, y, zs, withCompression);
+    }
+
+    protected ECPoint decompressPoint(int yTilde, BigInteger X1)
+    {
+        ECFieldElement x = fromBigInteger(X1);
+        ECFieldElement alpha = x.square().add(getA()).multiply(x).add(getB());
+        ECFieldElement beta = alpha.sqrt();
+
+        //
+        // if we can't find a sqrt we haven't got a point on the
+        // curve - run!
+        //
+        if (beta == null)
+        {
+            throw new RuntimeException("Invalid point compression");
+        }
+
+        if (beta.testBitZero() != (yTilde == 1))
+        {
+            // Use the other root
+            beta = beta.negate();
+        }
+
+        return new Curve25519Point(this, x, beta, true);
+    }
+
+    public ECPoint getInfinity()
+    {
+        return infinity;
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Curve25519Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Field.java
index 05691931..663e2fb3 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Curve25519Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Field.java
@@ -1,8 +1,9 @@
-package org.bouncycastle.math.ec.custom.sec;
+package org.bouncycastle.math.ec.custom.djb;
 
 import java.math.BigInteger;
 
 import org.bouncycastle.math.ec.Nat;
+import org.bouncycastle.math.ec.custom.sec.Nat256;
 
 public class Curve25519Field
 {
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519FieldElement.java
new file mode 100644
index 00000000..470b92c8
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519FieldElement.java
@@ -0,0 +1,234 @@
+package org.bouncycastle.math.ec.custom.djb;
+
+import java.math.BigInteger;
+
+import org.bouncycastle.math.ec.ECFieldElement;
+import org.bouncycastle.math.ec.Mod;
+import org.bouncycastle.math.ec.custom.sec.Nat256;
+import org.bouncycastle.util.Arrays;
+
+public class Curve25519FieldElement extends ECFieldElement
+{
+    public static final BigInteger Q = Curve25519.q;
+
+    // Calculated as ECConstants.TWO.modPow(Q.shiftRight(2), Q)
+    private static final int[] PRECOMP_POW2 = new int[]{ 0x4a0ea0b0, 0xc4ee1b27, 0xad2fe478, 0x2f431806,
+        0x3dfbd7a7, 0x2b4d0099, 0x4fc1df0b, 0x2b832480 };
+
+    protected int[] x;
+
+    public Curve25519FieldElement(BigInteger x)
+    {
+        if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0)
+        {
+            throw new IllegalArgumentException("x value invalid for Curve25519FieldElement");
+        }
+
+        this.x = Curve25519Field.fromBigInteger(x);
+    }
+
+    public Curve25519FieldElement()
+    {
+        this.x = Nat256.create();
+    }
+
+    protected Curve25519FieldElement(int[] x)
+    {
+        this.x = x;
+    }
+
+    public boolean isZero()
+    {
+        return Nat256.isZero(x);
+    }
+
+    public boolean isOne()
+    {
+        return Nat256.isOne(x);
+    }
+
+    public boolean testBitZero()
+    {
+        return Nat256.getBit(x, 0) == 1;
+    }
+
+    public BigInteger toBigInteger()
+    {
+        return Nat256.toBigInteger(x);
+    }
+
+    public String getFieldName()
+    {
+        return "Curve25519Field";
+    }
+
+    public int getFieldSize()
+    {
+        return Q.bitLength();
+    }
+
+    public ECFieldElement add(ECFieldElement b)
+    {
+        int[] z = Nat256.create();
+        Curve25519Field.add(x, ((Curve25519FieldElement)b).x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement addOne()
+    {
+        int[] z = Nat256.create();
+        Curve25519Field.addOne(x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement subtract(ECFieldElement b)
+    {
+        int[] z = Nat256.create();
+        Curve25519Field.subtract(x, ((Curve25519FieldElement)b).x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement multiply(ECFieldElement b)
+    {
+        int[] z = Nat256.create();
+        Curve25519Field.multiply(x, ((Curve25519FieldElement)b).x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement divide(ECFieldElement b)
+    {
+//        return multiply(b.invert());
+        int[] z = Nat256.create();
+        Mod.invert(Curve25519Field.P, ((Curve25519FieldElement)b).x, z);
+        Curve25519Field.multiply(z, x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement negate()
+    {
+        int[] z = Nat256.create();
+        Curve25519Field.negate(x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement square()
+    {
+        int[] z = Nat256.create();
+        Curve25519Field.square(x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    public ECFieldElement invert()
+    {
+//        return new Curve25519FieldElement(toBigInteger().modInverse(Q));
+        int[] z = Nat256.create();
+        Mod.invert(Curve25519Field.P, x, z);
+        return new Curve25519FieldElement(z);
+    }
+
+    /**
+     * return a sqrt root - the routine verifies that the calculation returns the right value - if
+     * none exists it returns null.
+     */
+    public ECFieldElement sqrt()
+    {
+        /*
+         * Q == 8m + 5, so we use Pocklington's method for this case.
+         *
+         * First, raise this element to the exponent 2^252 - 2^1 (i.e. m + 1)
+         * 
+         * Breaking up the exponent's binary representation into "repunits", we get:
+         * { 251 1s } { 1 0s }
+         * 
+         * Therefore we need an addition chain containing 251 (the lengths of the repunits)
+         * We use: 1, 2, 3, 4, 7, 11, 15, 30, 60, 120, 131, 251
+         */
+
+        int[] x1 = this.x;
+        if (Nat256.isZero(x1) || Nat256.isOne(x1))
+        {
+            return this;
+        }
+
+        int[] x2 = Nat256.create();
+        Curve25519Field.square(x1, x2);
+        Curve25519Field.multiply(x2, x1, x2);
+        int[] x3 = x2;
+        Curve25519Field.square(x2, x3);
+        Curve25519Field.multiply(x3, x1, x3);
+        int[] x4 = Nat256.create();
+        Curve25519Field.square(x3, x4);
+        Curve25519Field.multiply(x4, x1, x4);
+        int[] x7 = Nat256.create();
+        Curve25519Field.squareN(x4, 3, x7);
+        Curve25519Field.multiply(x7, x3, x7);
+        int[] x11 = x3;
+        Curve25519Field.squareN(x7, 4, x11);
+        Curve25519Field.multiply(x11, x4, x11);
+        int[] x15 = x7;
+        Curve25519Field.squareN(x11, 4, x15);
+        Curve25519Field.multiply(x15, x4, x15);
+        int[] x30 = x4;
+        Curve25519Field.squareN(x15, 15, x30);
+        Curve25519Field.multiply(x30, x15, x30);
+        int[] x60 = x15;
+        Curve25519Field.squareN(x30, 30, x60);
+        Curve25519Field.multiply(x60, x30, x60);
+        int[] x120 = x30;
+        Curve25519Field.squareN(x60, 60, x120);
+        Curve25519Field.multiply(x120, x60, x120);
+        int[] x131 = x60;
+        Curve25519Field.squareN(x120, 11, x131);
+        Curve25519Field.multiply(x131, x11, x131);
+        int[] x251 = x11;
+        Curve25519Field.squareN(x131, 120, x251);
+        Curve25519Field.multiply(x251, x120, x251);
+
+        int[] t1 = x251;
+        Curve25519Field.square(t1, t1);
+
+        int[] t2 = x120;
+        Curve25519Field.square(t1, t2);
+
+        if (Nat256.eq(x1, t2))
+        {
+            return new Curve25519FieldElement(t1);
+        }
+
+        /*
+         * If the first guess is incorrect, we multiply by a precomputed power of 2 to get the second guess,
+         * which is ((4x)^(m + 1))/2 mod Q
+         */
+        Curve25519Field.multiply(t1, PRECOMP_POW2, t1);
+
+        Curve25519Field.square(t1, t2);
+
+        if (Nat256.eq(x1, t2))
+        {
+            return new Curve25519FieldElement(t1);
+        }
+
+        return null;
+    }
+
+    public boolean equals(Object other)
+    {
+        if (other == this)
+        {
+            return true;
+        }
+
+        if (!(other instanceof Curve25519FieldElement))
+        {
+            return false;
+        }
+
+        Curve25519FieldElement o = (Curve25519FieldElement)other;
+        return Nat256.eq(x, o.x);
+    }
+
+    public int hashCode()
+    {
+        return Q.hashCode() ^ Arrays.hashCode(x, 0, 8);
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Point.java
new file mode 100644
index 00000000..f2341314
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Point.java
@@ -0,0 +1,312 @@
+package org.bouncycastle.math.ec.custom.djb;
+
+import org.bouncycastle.math.ec.ECCurve;
+import org.bouncycastle.math.ec.ECFieldElement;
+import org.bouncycastle.math.ec.ECPoint;
+
+public class Curve25519Point extends ECPoint
+{
+    /**
+     * Create a point which encodes with point compression.
+     * 
+     * @param curve the curve to use
+     * @param x affine x co-ordinate
+     * @param y affine y co-ordinate
+     * 
+     * @deprecated Use ECCurve.createPoint to construct points
+     */
+    public Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y)
+    {
+        this(curve, x, y, false);
+    }
+
+    /**
+     * Create a point that encodes with or without point compresion.
+     * 
+     * @param curve the curve to use
+     * @param x affine x co-ordinate
+     * @param y affine y co-ordinate
+     * @param withCompression if true encode with point compression
+     * 
+     * @deprecated per-point compression property will be removed, refer {@link #getEncoded(boolean)}
+     */
+    public Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression)
+    {
+        super(curve, x, y);
+
+        if ((x == null) != (y == null))
+        {
+            throw new IllegalArgumentException("Exactly one of the field elements is null");
+        }
+
+        this.withCompression = withCompression;
+    }
+
+    Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression)
+    {
+        super(curve, x, y, zs);
+
+        this.withCompression = withCompression;
+    }
+
+    protected ECPoint detach()
+    {
+        return new Curve25519Point(null, getAffineXCoord(), getAffineYCoord());
+    }
+
+    protected boolean getCompressionYTilde()
+    {
+        return this.getAffineYCoord().testBitZero();
+    }
+
+    public ECFieldElement getZCoord(int index)
+    {
+        if (index == 1)
+        {
+            return getJacobianModifiedW();
+        }
+
+        return super.getZCoord(index);
+    }
+
+    // B.3 pg 62
+    public ECPoint add(ECPoint b)
+    {
+        if (this.isInfinity())
+        {
+            return b;
+        }
+        if (b.isInfinity())
+        {
+            return this;
+        }
+        if (this == b)
+        {
+            return twice();
+        }
+
+        ECCurve curve = this.getCurve();
+
+        ECFieldElement X1 = this.x, Y1 = this.y;
+        ECFieldElement X2 = b.getXCoord(), Y2 = b.getYCoord();
+
+        ECFieldElement Z1 = this.zs[0];
+        ECFieldElement Z2 = b.getZCoord(0);
+
+        boolean Z1IsOne = Z1.isOne();
+
+        ECFieldElement Z1Squared, U2, S2;
+        if (Z1IsOne)
+        {
+            Z1Squared = Z1; U2 = X2; S2 = Y2;
+        }
+        else
+        {
+            Z1Squared = Z1.square();
+            U2 = Z1Squared.multiply(X2);
+            ECFieldElement Z1Cubed = Z1Squared.multiply(Z1);
+            S2 = Z1Cubed.multiply(Y2);
+        }
+
+        boolean Z2IsOne = Z2.isOne();
+        ECFieldElement Z2Squared, U1, S1;
+        if (Z2IsOne)
+        {
+            Z2Squared = Z2; U1 = X1; S1 = Y1;
+        }
+        else
+        {
+            Z2Squared = Z2.square();
+            U1 = Z2Squared.multiply(X1); 
+            ECFieldElement Z2Cubed = Z2Squared.multiply(Z2);
+            S1 = Z2Cubed.multiply(Y1);
+        }
+
+        ECFieldElement H = U1.subtract(U2);
+        ECFieldElement R = S1.subtract(S2);
+
+        // Check if b == this or b == -this
+        if (H.isZero())
+        {
+            if (R.isZero())
+            {
+                // this == b, i.e. this must be doubled
+                return this.twice();
+            }
+
+            // this == -b, i.e. the result is the point at infinity
+            return curve.getInfinity();
+        }
+
+        ECFieldElement HSquared = H.square();
+        ECFieldElement G = HSquared.multiply(H);
+        ECFieldElement V = HSquared.multiply(U1);
+
+        ECFieldElement X3 = R.square().add(G).subtract(two(V));
+        ECFieldElement Y3 = V.subtract(X3).multiplyMinusProduct(R, G, S1);
+
+        ECFieldElement Z3 = H;
+        if (!Z1IsOne)
+        {
+            Z3 = Z3.multiply(Z1);
+        }
+        if (!Z2IsOne)
+        {
+            Z3 = Z3.multiply(Z2);
+        }
+
+        ECFieldElement Z3Squared = (Z3 == H) ? HSquared : null;
+
+        // TODO If the result will only be used in a subsequent addition, we don't need W3
+        ECFieldElement W3 = calculateJacobianModifiedW(Z3, Z3Squared);
+
+        ECFieldElement[] zs = new ECFieldElement[]{ Z3, W3 };
+
+        return new Curve25519Point(curve, X3, Y3, zs, this.withCompression);
+    }
+
+    // B.3 pg 62
+    public ECPoint twice()
+    {
+        if (this.isInfinity())
+        {
+            return this;
+        }
+
+        ECCurve curve = this.getCurve();
+
+        ECFieldElement Y1 = this.y;
+        if (Y1.isZero()) 
+        {
+            return curve.getInfinity();
+        }
+
+        return twiceJacobianModified(true);
+    }
+
+    public ECPoint twicePlus(ECPoint b)
+    {
+        if (this == b)
+        {
+            return threeTimes();
+        }
+        if (this.isInfinity())
+        {
+            return b;
+        }
+        if (b.isInfinity())
+        {
+            return twice();
+        }
+
+        ECFieldElement Y1 = this.y;
+        if (Y1.isZero()) 
+        {
+            return b;
+        }
+
+        return twiceJacobianModified(false).add(b);
+    }
+
+    public ECPoint threeTimes()
+    {
+        if (this.isInfinity())
+        {
+            return this;
+        }
+
+        ECFieldElement Y1 = this.y;
+        if (Y1.isZero())
+        {
+            return this;
+        }
+
+        return twiceJacobianModified(false).add(this);
+    }
+
+    protected ECFieldElement two(ECFieldElement x)
+    {
+        return x.add(x);
+    }
+
+    protected ECFieldElement three(ECFieldElement x)
+    {
+        return two(x).add(x);
+    }
+
+    // D.3.2 pg 102 (see Note:)
+    public ECPoint subtract(ECPoint b)
+    {
+        if (b.isInfinity())
+        {
+            return this;
+        }
+
+        // Add -b
+        return add(b.negate());
+    }
+
+    public ECPoint negate()
+    {
+        if (this.isInfinity())
+        {
+            return this;
+        }
+
+        ECCurve curve = this.getCurve();
+        int coord = curve.getCoordinateSystem();
+
+        if (ECCurve.COORD_AFFINE != coord)
+        {
+            return new Curve25519Point(curve, this.x, this.y.negate(), this.zs, this.withCompression);
+        }
+
+        return new Curve25519Point(curve, this.x, this.y.negate(), this.withCompression);
+    }
+
+    protected ECFieldElement calculateJacobianModifiedW(ECFieldElement Z, ECFieldElement ZSquared)
+    {
+        ECFieldElement a4 = this.getCurve().getA();
+        if (Z.isOne())
+        {
+            return a4;
+        }
+
+        if (ZSquared == null)
+        {
+            ZSquared = Z.square();
+        }
+
+        return ZSquared.square().multiply(a4);
+    }
+
+    protected ECFieldElement getJacobianModifiedW()
+    {
+        ECFieldElement W = this.zs[1];
+        if (W == null)
+        {
+            // NOTE: Rarely, twicePlus will result in the need for a lazy W1 calculation here
+            this.zs[1] = W = calculateJacobianModifiedW(this.zs[0], null);
+        }
+        return W;
+    }
+
+    protected Curve25519Point twiceJacobianModified(boolean calculateW)
+    {
+        ECFieldElement X1 = this.x, Y1 = this.y, Z1 = this.zs[0], W1 = getJacobianModifiedW();
+
+        ECFieldElement X1Squared = X1.square();
+        ECFieldElement M = three(X1Squared).add(W1);
+        ECFieldElement _2Y1 = two(Y1);
+        ECFieldElement _2Y1Squared = _2Y1.multiply(Y1);
+        ECFieldElement S = two(X1.multiply(_2Y1Squared));
+        ECFieldElement X3 = M.square().subtract(two(S));
+        ECFieldElement _4T = _2Y1Squared.square();
+        ECFieldElement _8T = two(_4T);
+        ECFieldElement Y3 = M.multiply(S.subtract(X3)).subtract(_8T);
+        ECFieldElement W3 = calculateW ? two(_8T.multiply(W1)) : null;
+        ECFieldElement Z3 = Z1.isOne() ? _2Y1 : _2Y1.multiply(Z1);
+
+        return new Curve25519Point(this.getCurve(), X3, Y3, new ECFieldElement[]{ Z3, W3 }, this.withCompression);
+    }
+}