Port of latest Curve25519 stuff from Java build

5 files changed, 604 insertions, 5 deletions

diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs
index cd6811dfa..0430a6110 100644
--- a/crypto/src/math/ec/ECPoint.cs
+++ b/crypto/src/math/ec/ECPoint.cs
@@ -1191,13 +1191,13 @@ namespace Org.BouncyCastle.Math.EC
             ECFieldElement W = ZZ[1];
             if (W == null)
             {
-                // NOTE: Rarely, twicePlus will result in the need for a lazy W1 calculation here
+                // NOTE: Rarely, TwicePlus will result in the need for a lazy W1 calculation here
                 ZZ[1] = W = CalculateJacobianModifiedW(ZZ[0], null);
             }
             return W;
         }
 
-        protected FpPoint TwiceJacobianModified(bool calculateW)
+        protected virtual FpPoint TwiceJacobianModified(bool calculateW)
         {
             ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord, Z1 = this.RawZCoords[0], W1 = GetJacobianModifiedW();
 
diff --git a/crypto/src/math/ec/custom/djb/Curve25519.cs b/crypto/src/math/ec/custom/djb/Curve25519.cs
new file mode 100644
index 000000000..3dbdac051
--- /dev/null
+++ b/crypto/src/math/ec/custom/djb/Curve25519.cs
@@ -0,0 +1,100 @@
+using System;
+
+using Org.BouncyCastle.Math.EC.Custom.Sec;
+using Org.BouncyCastle.Math.Field;
+using Org.BouncyCastle.Utilities.Encoders;
+
+namespace Org.BouncyCastle.Math.EC.Custom.Djb
+{
+    internal class Curve25519
+        :   ECCurve
+    {
+        public static readonly BigInteger q = Nat256.ToBigInteger(Curve25519Field.P);
+
+        private const int Curve25519_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED;
+
+        protected readonly Curve25519Point m_infinity;
+
+        public Curve25519()
+            :   base(FiniteFields.GetPrimeField(q))
+        {
+            this.m_infinity = new Curve25519Point(this, null, null);
+
+            this.m_a = FromBigInteger(new BigInteger(1,
+                Hex.Decode("2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA984914A144")));
+            this.m_b = FromBigInteger(new BigInteger(1,
+                Hex.Decode("7B425ED097B425ED097B425ED097B425ED097B425ED097B4260B5E9C7710C864")));
+            this.m_order = new BigInteger(1, Hex.Decode("1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED"));
+            this.m_cofactor = BigInteger.ValueOf(8);
+            this.m_coord = Curve25519_DEFAULT_COORDS;
+        }
+
+        protected override ECCurve CloneCurve()
+        {
+            return new Curve25519();
+        }
+
+        public override bool SupportsCoordinateSystem(int coord)
+        {
+            switch (coord)
+            {
+            case COORD_JACOBIAN_MODIFIED:
+                return true;
+            default:
+                return false;
+            }
+        }
+
+        public virtual BigInteger Q
+        {
+            get { return q; }
+        }
+
+        public override ECPoint Infinity
+        {
+            get { return m_infinity; }
+        }
+
+        public override int FieldSize
+        {
+            get { return q.BitLength; }
+        }
+
+        public override ECFieldElement FromBigInteger(BigInteger x)
+        {
+            return new Curve25519FieldElement(x);
+        }
+
+        protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression)
+        {
+            return new Curve25519Point(this, x, y, withCompression);
+        }
+
+        protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression)
+        {
+            return new Curve25519Point(this, x, y, zs, withCompression);
+        }
+
+        protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
+        {
+            ECFieldElement x = FromBigInteger(X1);
+            ECFieldElement alpha = x.Square().Add(A).Multiply(x).Add(B);
+            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 ArithmeticException("Invalid point compression");
+
+            if (beta.TestBitZero() != (yTilde == 1))
+            {
+                // Use the other root
+                beta = beta.Negate();
+            }
+
+            return new Curve25519Point(this, x, beta, true);
+        }
+    }
+}
diff --git a/crypto/src/math/ec/custom/sec/Curve25519Field.cs b/crypto/src/math/ec/custom/djb/Curve25519Field.cs
index ee0f88311..084ca96af 100644
--- a/crypto/src/math/ec/custom/sec/Curve25519Field.cs
+++ b/crypto/src/math/ec/custom/djb/Curve25519Field.cs
@@ -1,7 +1,9 @@
 using System;
 using System.Diagnostics;
 
-namespace Org.BouncyCastle.Math.EC.Custom.Sec
+using Org.BouncyCastle.Math.EC.Custom.Sec;
+
+namespace Org.BouncyCastle.Math.EC.Custom.Djb
 {
     internal class Curve25519Field
     {
@@ -190,7 +192,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             c >>= 32;
             if (c != 0)
             {
-                Nat.IncAt(7, z, 1);
+                Nat.IncAt(8, z, 1);
             }
             z[7] &= P7;
         }
@@ -202,7 +204,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             c >>= 32;
             if (c != 0)
             {
-                Nat.DecAt(7, z, 1);
+                Nat.DecAt(8, z, 1);
             }
             z[7] &= P7;
         }
diff --git a/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs b/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs
new file mode 100644
index 000000000..8d5a80326
--- /dev/null
+++ b/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs
@@ -0,0 +1,233 @@
+using System;
+
+using Org.BouncyCastle.Math.EC.Custom.Sec;
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math.EC.Custom.Djb
+{
+    internal class Curve25519FieldElement
+        :   ECFieldElement
+    {
+        public static readonly BigInteger Q = Curve25519.q;
+
+        // Calculated as ECConstants.TWO.modPow(Q.shiftRight(2), Q)
+        private static readonly uint[] PRECOMP_POW2 = new uint[]{ 0x4a0ea0b0, 0xc4ee1b27, 0xad2fe478, 0x2f431806,
+            0x3dfbd7a7, 0x2b4d0099, 0x4fc1df0b, 0x2b832480 };
+
+        protected internal readonly uint[] x;
+
+        public Curve25519FieldElement(BigInteger x)
+        {
+            if (x == null || x.SignValue < 0 || x.CompareTo(Q) >= 0)
+                throw new ArgumentException("value invalid for Curve25519FieldElement", "x");
+
+            this.x = Curve25519Field.FromBigInteger(x);
+        }
+
+        public Curve25519FieldElement()
+        {
+            this.x = Nat256.Create();
+        }
+
+        protected internal Curve25519FieldElement(uint[] x)
+        {
+            this.x = x;
+        }
+
+        public override bool IsZero
+        {
+            get { return Nat256.IsZero(x); }
+        }
+
+        public override bool IsOne
+        {
+            get { return Nat256.IsOne(x); }
+        }
+
+        public override bool TestBitZero()
+        {
+            return Nat256.GetBit(x, 0) == 1;
+        }
+
+        public override BigInteger ToBigInteger()
+        {
+            return Nat256.ToBigInteger(x);
+        }
+
+        public override string FieldName
+        {
+            get { return "Curve25519Field"; }
+        }
+
+        public override int FieldSize
+        {
+            get { return Q.BitLength; }
+        }
+
+        public override ECFieldElement Add(ECFieldElement b)
+        {
+            uint[] z = Nat256.Create();
+            Curve25519Field.Add(x, ((Curve25519FieldElement)b).x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement AddOne()
+        {
+            uint[] z = Nat256.Create();
+            Curve25519Field.AddOne(x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement Subtract(ECFieldElement b)
+        {
+            uint[] z = Nat256.Create();
+            Curve25519Field.Subtract(x, ((Curve25519FieldElement)b).x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement Multiply(ECFieldElement b)
+        {
+            uint[] z = Nat256.Create();
+            Curve25519Field.Multiply(x, ((Curve25519FieldElement)b).x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement Divide(ECFieldElement b)
+        {
+            //return Multiply(b.Invert());
+            uint[] z = Nat256.Create();
+            Mod.Invert(Curve25519Field.P, ((Curve25519FieldElement)b).x, z);
+            Curve25519Field.Multiply(z, x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement Negate()
+        {
+            uint[] z = Nat256.Create();
+            Curve25519Field.Negate(x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement Square()
+        {
+            uint[] z = Nat256.Create();
+            Curve25519Field.Square(x, z);
+            return new Curve25519FieldElement(z);
+        }
+
+        public override ECFieldElement Invert()
+        {
+            //return new Curve25519FieldElement(ToBigInteger().ModInverse(Q));
+            uint[] 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 override 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]
+             */
+
+            uint[] x1 = this.x;
+            if (Nat256.IsZero(x1) || Nat256.IsOne(x1))
+                return this;
+
+            uint[] x2 = Nat256.Create();
+            Curve25519Field.Square(x1, x2);
+            Curve25519Field.Multiply(x2, x1, x2);
+            uint[] x3 = x2;
+            Curve25519Field.Square(x2, x3);
+            Curve25519Field.Multiply(x3, x1, x3);
+            uint[] x4 = Nat256.Create();
+            Curve25519Field.Square(x3, x4);
+            Curve25519Field.Multiply(x4, x1, x4);
+            uint[] x7 = Nat256.Create();
+            Curve25519Field.SquareN(x4, 3, x7);
+            Curve25519Field.Multiply(x7, x3, x7);
+            uint[] x11 = x3;
+            Curve25519Field.SquareN(x7, 4, x11);
+            Curve25519Field.Multiply(x11, x4, x11);
+            uint[] x15 = x7;
+            Curve25519Field.SquareN(x11, 4, x15);
+            Curve25519Field.Multiply(x15, x4, x15);
+            uint[] x30 = x4;
+            Curve25519Field.SquareN(x15, 15, x30);
+            Curve25519Field.Multiply(x30, x15, x30);
+            uint[] x60 = x15;
+            Curve25519Field.SquareN(x30, 30, x60);
+            Curve25519Field.Multiply(x60, x30, x60);
+            uint[] x120 = x30;
+            Curve25519Field.SquareN(x60, 60, x120);
+            Curve25519Field.Multiply(x120, x60, x120);
+            uint[] x131 = x60;
+            Curve25519Field.SquareN(x120, 11, x131);
+            Curve25519Field.Multiply(x131, x11, x131);
+            uint[] x251 = x11;
+            Curve25519Field.SquareN(x131, 120, x251);
+            Curve25519Field.Multiply(x251, x120, x251);
+
+            uint[] t1 = x251;
+            Curve25519Field.Square(t1, t1);
+
+            uint[] 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 override bool Equals(object obj)
+        {
+            return Equals(obj as Curve25519FieldElement);
+        }
+
+        public override bool Equals(ECFieldElement other)
+        {
+            return Equals(other as Curve25519FieldElement);
+        }
+
+        public virtual bool Equals(Curve25519FieldElement other)
+        {
+            if (this == other)
+                return true;
+            if (null == other)
+                return false;
+            return Nat256.Eq(x, other.x);
+        }
+
+        public override int GetHashCode()
+        {
+            return Q.GetHashCode() ^ Arrays.GetHashCode(x, 0, 8);
+        }
+    }
+}
diff --git a/crypto/src/math/ec/custom/djb/Curve25519Point.cs b/crypto/src/math/ec/custom/djb/Curve25519Point.cs
new file mode 100644
index 000000000..65b6792eb
--- /dev/null
+++ b/crypto/src/math/ec/custom/djb/Curve25519Point.cs
@@ -0,0 +1,264 @@
+using System;
+
+using Org.BouncyCastle.Math.EC.Custom.Sec;
+
+namespace Org.BouncyCastle.Math.EC.Custom.Djb
+{
+    internal class Curve25519Point
+        :   ECPointBase
+    {
+        /**
+         * 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(bool)}
+         */
+        public Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression)
+            :   base(curve, x, y, withCompression)
+        {
+            if ((x == null) != (y == null))
+                throw new ArgumentException("Exactly one of the field elements is null");
+        }
+
+        internal Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression)
+            : base(curve, x, y, zs, withCompression)
+        {
+        }
+
+        protected override ECPoint Detach()
+        {
+            return new Curve25519Point(null, AffineXCoord, AffineYCoord);
+        }
+
+        protected internal override bool CompressionYTilde
+        {
+            get { return this.AffineYCoord.TestBitZero(); }
+        }
+
+        public override ECFieldElement GetZCoord(int index)
+        {
+            if (index == 1)
+            {
+                return GetJacobianModifiedW();
+            }
+
+            return base.GetZCoord(index);
+        }
+
+        public override ECPoint Add(ECPoint b)
+        {
+            if (this.IsInfinity)
+                return b;
+            if (b.IsInfinity)
+                return this;
+            if (this == b)
+                return Twice();
+
+            ECCurve curve = this.Curve;
+
+            ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord;
+            ECFieldElement X2 = b.RawXCoord, Y2 = b.RawYCoord;
+
+            ECFieldElement Z1 = this.RawZCoords[0];
+            ECFieldElement Z2 = b.RawZCoords[0];
+
+            bool 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);
+            }
+
+            bool 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.Infinity;
+            }
+
+            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, IsCompressed);
+        }
+
+        public override ECPoint Twice()
+        {
+            if (this.IsInfinity)
+                return this;
+
+            ECCurve curve = this.Curve;
+
+            ECFieldElement Y1 = this.RawYCoord;
+            if (Y1.IsZero) 
+                return curve.Infinity;
+
+            return TwiceJacobianModified(true);
+        }
+
+        public override ECPoint TwicePlus(ECPoint b)
+        {
+            if (this == b)
+                return ThreeTimes();
+            if (this.IsInfinity)
+                return b;
+            if (b.IsInfinity)
+                return Twice();
+
+            ECFieldElement Y1 = this.RawYCoord;
+            if (Y1.IsZero) 
+                return b;
+
+            return TwiceJacobianModified(false).Add(b);
+        }
+
+        public override ECPoint ThreeTimes()
+        {
+            if (this.IsInfinity || this.RawYCoord.IsZero)
+                return this;
+
+            return TwiceJacobianModified(false).Add(this);
+        }
+
+        protected virtual ECFieldElement Two(ECFieldElement x)
+        {
+            return x.Add(x);
+        }
+
+        protected virtual ECFieldElement Three(ECFieldElement x)
+        {
+            return Two(x).Add(x);
+        }
+
+        public override ECPoint Subtract(ECPoint b)
+        {
+            if (b.IsInfinity)
+                return this;
+
+            return Add(b.Negate());
+        }
+
+        public override ECPoint Negate()
+        {
+            if (IsInfinity)
+                return this;
+
+            return new Curve25519Point(Curve, RawXCoord, RawYCoord.Negate(), RawZCoords, IsCompressed);
+        }
+
+        protected virtual ECFieldElement CalculateJacobianModifiedW(ECFieldElement Z, ECFieldElement ZSquared)
+        {
+            ECFieldElement a4 = this.Curve.A;
+            if (Z.IsOne)
+                return a4;
+
+            if (ZSquared == null)
+            {
+                ZSquared = Z.Square();
+            }
+
+            return ZSquared.Square().Multiply(a4);
+        }
+
+        protected virtual ECFieldElement GetJacobianModifiedW()
+        {
+            ECFieldElement[] ZZ = this.RawZCoords;
+            ECFieldElement W = ZZ[1];
+            if (W == null)
+            {
+                // NOTE: Rarely, TwicePlus will result in the need for a lazy W1 calculation here
+                ZZ[1] = W = CalculateJacobianModifiedW(ZZ[0], null);
+            }
+            return W;
+        }
+
+        protected virtual Curve25519Point TwiceJacobianModified(bool calculateW)
+        {
+            ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord, Z1 = this.RawZCoords[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.Curve, X3, Y3, new ECFieldElement[] { Z3, W3 }, IsCompressed);
+        }
+    }
+}