From 73cb18129e632b44ddae7f9c589fd9c17c77d3ca Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Wed, 22 Jan 2014 11:40:05 +0700 Subject: Use new Math.Field classes in EC curves, and avoid casting in client code --- crypto/src/math/ec/ECAlgorithms.cs | 170 ++++++++++++++++++++----------------- crypto/src/math/ec/ECCurve.cs | 153 +++++++++++++++------------------ 2 files changed, 161 insertions(+), 162 deletions(-) (limited to 'crypto/src/math') diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs index be4fd1b14..06288132b 100644 --- a/crypto/src/math/ec/ECAlgorithms.cs +++ b/crypto/src/math/ec/ECAlgorithms.cs @@ -1,93 +1,105 @@ using System; -using Org.BouncyCastle.Math; +using Org.BouncyCastle.Math.Field; namespace Org.BouncyCastle.Math.EC { - public class ECAlgorithms - { - public static ECPoint SumOfTwoMultiplies(ECPoint P, BigInteger a, - ECPoint Q, BigInteger b) - { - ECCurve c = P.Curve; - if (!c.Equals(Q.Curve)) - throw new ArgumentException("P and Q must be on same curve"); + public class ECAlgorithms + { + public static bool IsF2mCurve(ECCurve c) + { + IFiniteField field = c.Field; + return field.Dimension > 1 && field.Characteristic.Equals(BigInteger.Two) + && field is IPolynomialExtensionField; + } - // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick - if (c is F2mCurve) - { - F2mCurve f2mCurve = (F2mCurve) c; - if (f2mCurve.IsKoblitz) - { - return P.Multiply(a).Add(Q.Multiply(b)); - } - } + public static bool IsFpCurve(ECCurve c) + { + return c.Field.Dimension == 1; + } - return ImplShamirsTrick(P, a, Q, b); - } + public static ECPoint SumOfTwoMultiplies(ECPoint P, BigInteger a, + ECPoint Q, BigInteger b) + { + ECCurve c = P.Curve; + if (!c.Equals(Q.Curve)) + throw new ArgumentException("P and Q must be on same curve"); - /* - * "Shamir's Trick", originally due to E. G. Straus - * (Addition chains of vectors. American Mathematical Monthly, - * 71(7):806-808, Aug./Sept. 1964) - * - * Input: The points P, Q, scalar k = (km?, ... , k1, k0) - * and scalar l = (lm?, ... , l1, l0). - * Output: R = k * P + l * Q. - * 1: Z <- P + Q - * 2: R <- O - * 3: for i from m-1 down to 0 do - * 4: R <- R + R {point doubling} - * 5: if (ki = 1) and (li = 0) then R <- R + P end if - * 6: if (ki = 0) and (li = 1) then R <- R + Q end if - * 7: if (ki = 1) and (li = 1) then R <- R + Z end if - * 8: end for - * 9: return R - */ - public static ECPoint ShamirsTrick( - ECPoint P, - BigInteger k, - ECPoint Q, - BigInteger l) - { - if (!P.Curve.Equals(Q.Curve)) - throw new ArgumentException("P and Q must be on same curve"); + // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick + if (c is F2mCurve) + { + F2mCurve f2mCurve = (F2mCurve) c; + if (f2mCurve.IsKoblitz) + { + return P.Multiply(a).Add(Q.Multiply(b)); + } + } - return ImplShamirsTrick(P, k, Q, l); - } + return ImplShamirsTrick(P, a, Q, b); + } - private static ECPoint ImplShamirsTrick(ECPoint P, BigInteger k, - ECPoint Q, BigInteger l) - { - int m = System.Math.Max(k.BitLength, l.BitLength); - ECPoint Z = P.Add(Q); - ECPoint R = P.Curve.Infinity; + /* + * "Shamir's Trick", originally due to E. G. Straus + * (Addition chains of vectors. American Mathematical Monthly, + * 71(7):806-808, Aug./Sept. 1964) + * + * Input: The points P, Q, scalar k = (km?, ... , k1, k0) + * and scalar l = (lm?, ... , l1, l0). + * Output: R = k * P + l * Q. + * 1: Z <- P + Q + * 2: R <- O + * 3: for i from m-1 down to 0 do + * 4: R <- R + R {point doubling} + * 5: if (ki = 1) and (li = 0) then R <- R + P end if + * 6: if (ki = 0) and (li = 1) then R <- R + Q end if + * 7: if (ki = 1) and (li = 1) then R <- R + Z end if + * 8: end for + * 9: return R + */ + public static ECPoint ShamirsTrick( + ECPoint P, + BigInteger k, + ECPoint Q, + BigInteger l) + { + if (!P.Curve.Equals(Q.Curve)) + throw new ArgumentException("P and Q must be on same curve"); - for (int i = m - 1; i >= 0; --i) - { - R = R.Twice(); + return ImplShamirsTrick(P, k, Q, l); + } - if (k.TestBit(i)) - { - if (l.TestBit(i)) - { - R = R.Add(Z); - } - else - { - R = R.Add(P); - } - } - else - { - if (l.TestBit(i)) - { - R = R.Add(Q); - } - } - } + private static ECPoint ImplShamirsTrick(ECPoint P, BigInteger k, + ECPoint Q, BigInteger l) + { + int m = System.Math.Max(k.BitLength, l.BitLength); + ECPoint Z = P.Add(Q); + ECPoint R = P.Curve.Infinity; - return R; - } - } + for (int i = m - 1; i >= 0; --i) + { + R = R.Twice(); + + if (k.TestBit(i)) + { + if (l.TestBit(i)) + { + R = R.Add(Z); + } + else + { + R = R.Add(P); + } + } + else + { + if (l.TestBit(i)) + { + R = R.Add(Q); + } + } + } + + return R; + } + } } diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index ab98af8f1..6f4492e5c 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -2,52 +2,63 @@ using System; using System.Collections; using Org.BouncyCastle.Math.EC.Abc; +using Org.BouncyCastle.Math.Field; +using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Math.EC { /// Base class for an elliptic curve. public abstract class ECCurve { - internal ECFieldElement a, b; + protected IFiniteField m_field; + protected ECFieldElement m_a, m_b; + + protected ECCurve(IFiniteField field) + { + this.m_field = field; + } 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 + public virtual IFiniteField Field { - get { return a; } + get { return m_field; } } - public ECFieldElement B + public virtual ECFieldElement A { - get { return b; } + get { return m_a; } } - public override bool Equals( - object obj) + public virtual ECFieldElement B { - if (obj == this) - return true; - - ECCurve other = obj as ECCurve; + get { return m_b; } + } - if (other == null) + public virtual bool Equals(ECCurve other) + { + if (this == other) + return true; + if (null == other) return false; - - return Equals(other); + return Field.Equals(other.Field) + && A.Equals(other.A) + && B.Equals(other.B); } - protected bool Equals( - ECCurve other) + public override bool Equals(object obj) { - return a.Equals(other.a) && b.Equals(other.b); + return Equals(obj as ECCurve); } public override int GetHashCode() { - return a.GetHashCode() ^ b.GetHashCode(); + return Field.GetHashCode() + ^ Integers.RotateLeft(A.GetHashCode(), 8) + ^ Integers.RotateLeft(B.GetHashCode(), 16); } protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1); @@ -112,17 +123,19 @@ namespace Org.BouncyCastle.Math.EC /** * Elliptic curve over Fp */ - public class FpCurve : ECCurve + public class FpCurve + : ECCurve { private readonly BigInteger q, r; private readonly FpPoint infinity; public FpCurve(BigInteger q, BigInteger a, BigInteger b) + : base(FiniteFields.GetPrimeField(q)) { this.q = q; this.r = FpFieldElement.CalculateResidue(q); - this.a = FromBigInteger(a); - this.b = FromBigInteger(b); + this.m_a = FromBigInteger(a); + this.m_b = FromBigInteger(b); this.infinity = new FpPoint(this, null, null); } @@ -164,7 +177,7 @@ namespace Org.BouncyCastle.Math.EC BigInteger X1) { ECFieldElement x = FromBigInteger(X1); - ECFieldElement alpha = x.Multiply(x.Square().Add(a)).Add(b); + ECFieldElement alpha = x.Multiply(x.Square().Add(m_a)).Add(m_b); ECFieldElement beta = alpha.Sqrt(); // @@ -185,39 +198,44 @@ namespace Org.BouncyCastle.Math.EC return new FpPoint(this, x, beta, true); } + } - public override bool Equals( - object obj) + /** + * Elliptic curves over F2m. The Weierstrass equation is given by + * y2 + xy = x3 + ax2 + b. + */ + public class F2mCurve : ECCurve + { + private static IFiniteField BuildField(int m, int k1, int k2, int k3) { - if (obj == this) - return true; + if (k1 == 0) + { + throw new ArgumentException("k1 must be > 0"); + } - FpCurve other = obj as FpCurve; + if (k2 == 0) + { + if (k3 != 0) + { + throw new ArgumentException("k3 must be 0 if k2 == 0"); + } - if (other == null) - return false; + return FiniteFields.GetBinaryExtensionField(new int[]{ 0, k1, m }); + } - return Equals(other); - } + if (k2 <= k1) + { + throw new ArgumentException("k2 must be > k1"); + } - protected bool Equals( - FpCurve other) - { - return base.Equals(other) && q.Equals(other.q); - } + if (k3 <= k2) + { + throw new ArgumentException("k3 must be > k2"); + } - public override int GetHashCode() - { - return base.GetHashCode() ^ q.GetHashCode(); + return FiniteFields.GetBinaryExtensionField(new int[]{ 0, k1, k2, k3, m }); } - } - /** - * Elliptic curves over F2m. The Weierstrass equation is given by - * y2 + xy = x3 + ax2 + b. - */ - public class F2mCurve : ECCurve - { /** * The exponent m of F2m. */ @@ -391,6 +409,7 @@ namespace Org.BouncyCastle.Math.EC BigInteger b, BigInteger n, BigInteger h) + : base(BuildField(m, k1, k2, k3)) { this.m = m; this.k1 = k1; @@ -417,8 +436,8 @@ namespace Org.BouncyCastle.Math.EC throw new ArgumentException("k3 must be > k2"); } - this.a = FromBigInteger(a); - this.b = FromBigInteger(b); + this.m_a = FromBigInteger(a); + this.m_b = FromBigInteger(b); } public override ECPoint Infinity @@ -444,10 +463,7 @@ namespace Org.BouncyCastle.Math.EC { get { - return n != null && h != null - && (a.ToBigInteger().Equals(BigInteger.Zero) - || a.ToBigInteger().Equals(BigInteger.One)) - && b.ToBigInteger().Equals(BigInteger.One); + return n != null && h != null && m_a.BitLength <= 1 && m_b.IsOne; } } @@ -514,7 +530,7 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement yp = null; if (xp.ToBigInteger().SignValue == 0) { - yp = (F2mFieldElement)b; + yp = (F2mFieldElement)m_b; for (int i = 0; i < m - 1; i++) { yp = yp.Square(); @@ -522,7 +538,7 @@ namespace Org.BouncyCastle.Math.EC } else { - ECFieldElement beta = xp.Add(a).Add(b.Multiply(xp.Square().Invert())); + ECFieldElement beta = xp.Add(m_a).Add(m_b.Multiply(xp.Square().Invert())); ECFieldElement z = solveQuadradicEquation(beta); if (z == null) @@ -580,35 +596,6 @@ namespace Org.BouncyCastle.Math.EC 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; } -- cgit 1.4.1