diff options
Diffstat (limited to 'Crypto/src/math/ec/ECCurve.cs')
| -rw-r--r-- | Crypto/src/math/ec/ECCurve.cs | 661 |
1 files changed, 661 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..4dd5e74e2 --- /dev/null +++ b/Crypto/src/math/ec/ECCurve.cs @@ -0,0 +1,661 @@ +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 DecodePoint(byte[] encoded); + 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(); + } + } + + public abstract class ECCurveBase : ECCurve + { + protected internal ECCurveBase() + { + } + + protected internal 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 override 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, encoded.Length - 1); + + 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 : ECCurveBase + { + 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 internal 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 : ECCurveBase + { + /** + * 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>μ</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>μ</code> of the elliptic curve. + * @return <code>μ</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 internal 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; } + } + } +} |