Initial import of old CVS repository

1 files changed, 651 insertions, 0 deletions

diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
new file mode 100644
index 000000000..396d42f28
--- /dev/null
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -0,0 +1,651 @@
+using System;
+using System.Collections;
+
+using Org.BouncyCastle.Math.EC.Abc;
+
+namespace Org.BouncyCastle.Math.EC
+{
+    /// <remarks>Base class for an elliptic curve.</remarks>
+    public abstract class ECCurve
+    {
+        internal ECFieldElement a, b;
+
+        public abstract int FieldSize { get; }
+        public abstract ECFieldElement FromBigInteger(BigInteger x);
+        public abstract ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression);
+        public abstract ECPoint Infinity { get; }
+
+        public ECFieldElement A
+        {
+            get { return a; }
+        }
+
+        public ECFieldElement B
+        {
+            get { return b; }
+        }
+
+        public override bool Equals(
+            object obj)
+        {
+            if (obj == this)
+                return true;
+
+            ECCurve other = obj as ECCurve;
+
+            if (other == null)
+                return false;
+
+            return Equals(other);
+        }
+
+        protected bool Equals(
+            ECCurve other)
+        {
+            return a.Equals(other.a) && b.Equals(other.b);
+        }
+
+        public override int GetHashCode()
+        {
+            return a.GetHashCode() ^ b.GetHashCode();
+        }
+
+        protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1);
+
+        /**
+         * Decode a point on this curve from its ASN.1 encoding. The different
+         * encodings are taken account of, including point compression for
+         * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17).
+         * @return The decoded point.
+         */
+        public virtual ECPoint DecodePoint(byte[] encoded)
+        {
+            ECPoint p = null;
+            int expectedLength = (FieldSize + 7) / 8;
+
+            switch (encoded[0])
+            {
+                case 0x00: // infinity
+                {
+                    if (encoded.Length != 1)
+                        throw new ArgumentException("Incorrect length for infinity encoding", "encoded");
+
+                    p = Infinity;
+                    break;
+                }
+
+                case 0x02: // compressed
+                case 0x03: // compressed
+                {
+                    if (encoded.Length != (expectedLength + 1))
+                        throw new ArgumentException("Incorrect length for compressed encoding", "encoded");
+
+                    int yTilde = encoded[0] & 1;
+                    BigInteger X1 = new BigInteger(1, encoded, 1, expectedLength);
+
+                    p = DecompressPoint(yTilde, X1);
+                    break;
+                }
+
+                case 0x04: // uncompressed
+                case 0x06: // hybrid
+                case 0x07: // hybrid
+                {
+                    if (encoded.Length != (2 * expectedLength + 1))
+                        throw new ArgumentException("Incorrect length for uncompressed/hybrid encoding", "encoded");
+
+                    BigInteger X1 = new BigInteger(1, encoded, 1, expectedLength);
+                    BigInteger Y1 = new BigInteger(1, encoded, 1 + expectedLength, expectedLength);
+
+                    p = CreatePoint(X1, Y1, false);
+                    break;
+                }
+
+                default:
+                    throw new FormatException("Invalid point encoding " + encoded[0]);
+            }
+
+            return p;
+        }
+    }
+
+    /**
+     * Elliptic curve over Fp
+     */
+    public class FpCurve : ECCurve
+    {
+        private readonly BigInteger q;
+        private readonly FpPoint infinity;
+
+        public FpCurve(BigInteger q, BigInteger a, BigInteger b)
+        {
+            this.q = q;
+            this.a = FromBigInteger(a);
+            this.b = FromBigInteger(b);
+            this.infinity = new FpPoint(this, null, null);
+        }
+
+        public BigInteger Q
+        {
+            get { return q; }
+        }
+
+        public override ECPoint Infinity
+        {
+            get { return infinity; }
+        }
+
+        public override int FieldSize
+        {
+            get { return q.BitLength; }
+        }
+
+        public override ECFieldElement FromBigInteger(BigInteger x)
+        {
+            return new FpFieldElement(this.q, x);
+        }
+
+        public override ECPoint CreatePoint(
+            BigInteger	X1,
+            BigInteger	Y1,
+            bool		withCompression)
+        {
+            // TODO Validation of X1, Y1?
+            return new FpPoint(
+                this,
+                FromBigInteger(X1),
+                FromBigInteger(Y1),
+                withCompression);
+        }
+
+        protected override ECPoint DecompressPoint(
+            int			yTilde,
+            BigInteger	X1)
+        {
+            ECFieldElement x = FromBigInteger(X1);
+            ECFieldElement alpha = x.Multiply(x.Square().Add(a)).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");
+
+            BigInteger betaValue = beta.ToBigInteger();
+            int bit0 = betaValue.TestBit(0) ? 1 : 0;
+
+            if (bit0 != yTilde)
+            {
+                // Use the other root
+                beta = FromBigInteger(q.Subtract(betaValue));
+            }
+
+            return new FpPoint(this, x, beta, true);
+        }
+
+        public override bool Equals(
+            object obj)
+        {
+            if (obj == this)
+                return true;
+
+            FpCurve other = obj as FpCurve;
+
+            if (other == null)
+                return false;
+
+            return Equals(other);
+        }
+
+        protected bool Equals(
+            FpCurve other)
+        {
+            return base.Equals(other) && q.Equals(other.q);
+        }
+
+        public override int GetHashCode()
+        {
+            return base.GetHashCode() ^ q.GetHashCode();
+        }
+    }
+
+    /**
+     * Elliptic curves over F2m. The Weierstrass equation is given by
+     * <code>y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b</code>.
+     */
+    public class F2mCurve : ECCurve
+    {
+        /**
+         * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
+         */
+        private readonly int m;
+
+        /**
+         * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
+         * x<sup>k</sup> + 1</code> represents the reduction polynomial
+         * <code>f(z)</code>.<br/>
+         * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.<br/>
+         */
+        private readonly int k1;
+
+        /**
+         * TPB: Always set to <code>0</code><br/>
+         * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.<br/>
+         */
+        private readonly int k2;
+
+        /**
+         * TPB: Always set to <code>0</code><br/>
+         * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.<br/>
+         */
+        private readonly int k3;
+
+        /**
+         * The order of the base point of the curve.
+         */
+        private readonly BigInteger n;
+
+        /**
+         * The cofactor of the curve.
+         */
+        private readonly BigInteger h;
+
+        /**
+         * The point at infinity on this curve.
+         */
+        private readonly F2mPoint infinity;
+
+        /**
+         * The parameter <code>&#956;</code> of the elliptic curve if this is
+         * a Koblitz curve.
+         */
+        private sbyte mu = 0;
+
+        /**
+         * The auxiliary values <code>s<sub>0</sub></code> and
+         * <code>s<sub>1</sub></code> used for partial modular reduction for
+         * Koblitz curves.
+         */
+        private BigInteger[] si = null;
+
+        /**
+         * Constructor for Trinomial Polynomial Basis (TPB).
+         * @param m  The exponent <code>m</code> of
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
+         * x<sup>k</sup> + 1</code> represents the reduction
+         * polynomial <code>f(z)</code>.
+         * @param a The coefficient <code>a</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param b The coefficient <code>b</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         */
+        public F2mCurve(
+            int			m,
+            int			k,
+            BigInteger	a,
+            BigInteger	b)
+            : this(m, k, 0, 0, a, b, null, null)
+        {
+        }
+
+        /**
+         * Constructor for Trinomial Polynomial Basis (TPB).
+         * @param m  The exponent <code>m</code> of
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
+         * x<sup>k</sup> + 1</code> represents the reduction
+         * polynomial <code>f(z)</code>.
+         * @param a The coefficient <code>a</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param b The coefficient <code>b</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param n The order of the main subgroup of the elliptic curve.
+         * @param h The cofactor of the elliptic curve, i.e.
+         * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>.
+         */
+        public F2mCurve(
+            int			m, 
+            int			k, 
+            BigInteger	a, 
+            BigInteger	b,
+            BigInteger	n,
+            BigInteger	h)
+            : this(m, k, 0, 0, a, b, n, h)
+        {
+        }
+
+        /**
+         * Constructor for Pentanomial Polynomial Basis (PPB).
+         * @param m  The exponent <code>m</code> of
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.
+         * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.
+         * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.
+         * @param a The coefficient <code>a</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param b The coefficient <code>b</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         */
+        public F2mCurve(
+            int			m,
+            int			k1,
+            int			k2,
+            int			k3,
+            BigInteger	a,
+            BigInteger	b)
+            : this(m, k1, k2, k3, a, b, null, null)
+        {
+        }
+
+        /**
+         * Constructor for Pentanomial Polynomial Basis (PPB).
+         * @param m  The exponent <code>m</code> of
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.
+         * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.
+         * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
+         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+         * represents the reduction polynomial <code>f(z)</code>.
+         * @param a The coefficient <code>a</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param b The coefficient <code>b</code> in the Weierstrass equation
+         * for non-supersingular elliptic curves over
+         * <code>F<sub>2<sup>m</sup></sub></code>.
+         * @param n The order of the main subgroup of the elliptic curve.
+         * @param h The cofactor of the elliptic curve, i.e.
+         * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>.
+         */
+        public F2mCurve(
+            int			m, 
+            int			k1, 
+            int			k2, 
+            int			k3,
+            BigInteger	a, 
+            BigInteger	b,
+            BigInteger	n,
+            BigInteger	h)
+        {
+            this.m = m;
+            this.k1 = k1;
+            this.k2 = k2;
+            this.k3 = k3;
+            this.n = n;
+            this.h = h;
+            this.infinity = new F2mPoint(this, null, null);
+
+            if (k1 == 0)
+                throw new ArgumentException("k1 must be > 0");
+
+            if (k2 == 0)
+            {
+                if (k3 != 0)
+                    throw new ArgumentException("k3 must be 0 if k2 == 0");
+            }
+            else
+            {
+                if (k2 <= k1)
+                    throw new ArgumentException("k2 must be > k1");
+
+                if (k3 <= k2)
+                    throw new ArgumentException("k3 must be > k2");
+            }
+
+            this.a = FromBigInteger(a);
+            this.b = FromBigInteger(b);
+        }
+
+        public override ECPoint Infinity
+        {
+            get { return infinity; }
+        }
+
+        public override int FieldSize
+        {
+            get { return m; }
+        }
+
+        public override ECFieldElement FromBigInteger(BigInteger x)
+        {
+            return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, x);
+        }
+
+        /**
+         * Returns true if this is a Koblitz curve (ABC curve).
+         * @return true if this is a Koblitz curve (ABC curve), false otherwise
+         */
+        public bool IsKoblitz
+        {
+            get
+            {
+                return n != null && h != null
+                    && (a.ToBigInteger().Equals(BigInteger.Zero)
+                        || a.ToBigInteger().Equals(BigInteger.One))
+                    && b.ToBigInteger().Equals(BigInteger.One);
+            }
+        }
+
+        /**
+         * Returns the parameter <code>&#956;</code> of the elliptic curve.
+         * @return <code>&#956;</code> of the elliptic curve.
+         * @throws ArgumentException if the given ECCurve is not a
+         * Koblitz curve.
+         */
+        internal sbyte GetMu()
+        {
+            if (mu == 0)
+            {
+                lock (this)
+                {
+                    if (mu == 0)
+                    {
+                        mu = Tnaf.GetMu(this);
+                    }
+                }
+            }
+
+            return mu;
+        }
+
+        /**
+         * @return the auxiliary values <code>s<sub>0</sub></code> and
+         * <code>s<sub>1</sub></code> used for partial modular reduction for
+         * Koblitz curves.
+         */
+        internal BigInteger[] GetSi()
+        {
+            if (si == null)
+            {
+                lock (this)
+                {
+                    if (si == null)
+                    {
+                        si = Tnaf.GetSi(this);
+                    }
+                }
+            }
+            return si;
+        }
+
+        public override ECPoint CreatePoint(
+            BigInteger	X1,
+            BigInteger	Y1,
+            bool		withCompression)
+        {
+            // TODO Validation of X1, Y1?
+            return new F2mPoint(
+                this,
+                FromBigInteger(X1),
+                FromBigInteger(Y1),
+                withCompression);
+        }
+
+        protected override ECPoint DecompressPoint(
+            int			yTilde,
+            BigInteger	X1)
+        {
+            ECFieldElement xp = FromBigInteger(X1);
+            ECFieldElement yp = null;
+            if (xp.ToBigInteger().SignValue == 0)
+            {
+                yp = (F2mFieldElement)b;
+                for (int i = 0; i < m - 1; i++)
+                {
+                    yp = yp.Square();
+                }
+            }
+            else
+            {
+                ECFieldElement beta = xp.Add(a).Add(b.Multiply(xp.Square().Invert()));
+                ECFieldElement z = solveQuadradicEquation(beta);
+
+                if (z == null)
+                    throw new ArithmeticException("Invalid point compression");
+
+                int zBit = z.ToBigInteger().TestBit(0) ? 1 : 0;
+                if (zBit != yTilde)
+                {
+                    z = z.Add(FromBigInteger(BigInteger.One));
+                }
+
+                yp = xp.Multiply(z);
+            }
+
+            return new F2mPoint(this, xp, yp, true);
+        }
+
+        /**
+         * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62
+         * D.1.6) The other solution is <code>z + 1</code>.
+         *
+         * @param beta
+         *            The value to solve the qradratic equation for.
+         * @return the solution for <code>z<sup>2</sup> + z = beta</code> or
+         *         <code>null</code> if no solution exists.
+         */
+        private ECFieldElement solveQuadradicEquation(ECFieldElement beta)
+        {
+            if (beta.ToBigInteger().SignValue == 0)
+            {
+                return FromBigInteger(BigInteger.Zero);
+            }
+
+            ECFieldElement z = null;
+            ECFieldElement gamma = FromBigInteger(BigInteger.Zero);
+
+            while (gamma.ToBigInteger().SignValue == 0)
+            {
+                ECFieldElement t = FromBigInteger(new BigInteger(m, new Random()));
+                z = FromBigInteger(BigInteger.Zero);
+
+                ECFieldElement w = beta;
+                for (int i = 1; i <= m - 1; i++)
+                {
+                    ECFieldElement w2 = w.Square();
+                    z = z.Square().Add(w2.Multiply(t));
+                    w = w2.Add(beta);
+                }
+                if (w.ToBigInteger().SignValue != 0)
+                {
+                    return null;
+                }
+                gamma = z.Square().Add(z);
+            }
+            return z;
+        }
+
+        public override bool Equals(
+            object obj)
+        {
+            if (obj == this)
+                return true;
+
+            F2mCurve other = obj as F2mCurve;
+
+            if (other == null)
+                return false;
+
+            return Equals(other);
+        }
+
+        protected bool Equals(
+            F2mCurve other)
+        {
+            return m == other.m
+                && k1 == other.k1
+                && k2 == other.k2
+                && k3 == other.k3
+                && base.Equals(other);
+        }
+
+        public override int GetHashCode()
+        {
+            return base.GetHashCode() ^ m ^ k1 ^ k2 ^ k3;
+        }
+
+        public int M
+        {
+            get { return m; }
+        }
+
+        /**
+         * Return true if curve uses a Trinomial basis.
+         *
+         * @return true if curve Trinomial, false otherwise.
+         */
+        public bool IsTrinomial()
+        {
+            return k2 == 0 && k3 == 0;
+        }
+
+        public int K1
+        {
+            get { return k1; }
+        }
+
+        public int K2
+        {
+            get { return k2; }
+        }
+
+        public int K3
+        {
+            get { return k3; }
+        }
+
+        public BigInteger N
+        {
+            get { return n; }
+        }
+
+        public BigInteger H
+        {
+            get { return h; }
+        }
+    }
+}