From bca3fd0a7dd9722c1f7ce5b286543f330ca2a3ae Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Mon, 23 Mar 2015 20:16:34 +0700 Subject: F2m changes in preparation for custom binary curves --- crypto/src/math/ec/ECCurve.cs | 175 +++++------- crypto/src/math/ec/ECPoint.cs | 307 ++++++++++----------- crypto/src/math/ec/abc/Tnaf.cs | 171 ++++++------ crypto/src/math/ec/multiplier/WTauNafMultiplier.cs | 71 ++--- .../src/math/ec/multiplier/WTauNafPreCompInfo.cs | 6 +- 5 files changed, 354 insertions(+), 376 deletions(-) (limited to 'crypto/src/math/ec') diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 339d37f7c..9fe9e32fd 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -623,6 +623,18 @@ namespace Org.BouncyCastle.Math.EC public abstract class AbstractF2mCurve : ECCurve { + public static BigInteger Inverse(int m, int[] ks, BigInteger x) + { + return new LongArray(x).ModInverse(m, ks).ToBigInteger(); + } + + /** + * The auxiliary values s0 and + * s1 used for partial modular reduction for + * Koblitz curves. + */ + private BigInteger[] si = null; + private static IFiniteField BuildField(int m, int k1, int k2, int k3) { if (k1 == 0) @@ -657,6 +669,69 @@ namespace Org.BouncyCastle.Math.EC : base(BuildField(m, k1, k2, k3)) { } + + [Obsolete("Per-point compression property will be removed")] + public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) + { + ECFieldElement X = FromBigInteger(x), Y = FromBigInteger(y); + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + if (X.IsZero) + { + if (!Y.Square().Equals(B)) + throw new ArgumentException(); + } + else + { + // Y becomes Lambda (X + Y/X) here + Y = Y.Divide(X).Add(X); + } + break; + } + default: + { + break; + } + } + + return CreateRawPoint(X, Y, withCompression); + } + + /** + * @return the auxiliary values s0 and + * s1 used for partial modular reduction for + * Koblitz curves. + */ + internal virtual BigInteger[] GetSi() + { + if (si == null) + { + lock (this) + { + if (si == null) + { + si = Tnaf.GetSi(this); + } + } + } + return si; + } + + /** + * Returns true if this is a Koblitz curve (ABC curve). + * @return true if this is a Koblitz curve (ABC curve), false otherwise + */ + public virtual bool IsKoblitz + { + get + { + return m_order != null && m_cofactor != null && m_b.IsOne && (m_a.IsZero || m_a.IsOne); + } + } } /** @@ -704,19 +779,6 @@ namespace Org.BouncyCastle.Math.EC */ protected readonly F2mPoint m_infinity; - /** - * The parameter μ of the elliptic curve if this is - * a Koblitz curve. - */ - private sbyte mu = 0; - - /** - * The auxiliary values s0 and - * s1 used for partial modular reduction for - * Koblitz curves. - */ - private BigInteger[] si = null; - /** * Constructor for Trinomial Polynomial Basis (TPB). * @param m The exponent m of @@ -917,37 +979,6 @@ namespace Org.BouncyCastle.Math.EC return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, x); } - [Obsolete("Per-point compression property will be removed")] - public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) - { - ECFieldElement X = FromBigInteger(x), Y = FromBigInteger(y); - - switch (this.CoordinateSystem) - { - case COORD_LAMBDA_AFFINE: - case COORD_LAMBDA_PROJECTIVE: - { - if (X.IsZero) - { - if (!Y.Square().Equals(B)) - throw new ArgumentException(); - } - else - { - // Y becomes Lambda (X + Y/X) here - Y = Y.Divide(X).Add(X); - } - break; - } - default: - { - break; - } - } - - return CreateRawPoint(X, Y, withCompression); - } - protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) { return new F2mPoint(this, x, y, withCompression); @@ -963,60 +994,6 @@ namespace Org.BouncyCastle.Math.EC get { return m_infinity; } } - /** - * Returns true if this is a Koblitz curve (ABC curve). - * @return true if this is a Koblitz curve (ABC curve), false otherwise - */ - public virtual bool IsKoblitz - { - get - { - return m_order != null && m_cofactor != null && m_b.IsOne && (m_a.IsZero || m_a.IsOne); - } - } - - /** - * Returns the parameter μ of the elliptic curve. - * @return μ of the elliptic curve. - * @throws ArgumentException if the given ECCurve is not a - * Koblitz curve. - */ - internal virtual sbyte GetMu() - { - if (mu == 0) - { - lock (this) - { - if (mu == 0) - { - mu = Tnaf.GetMu(this); - } - } - } - - return mu; - } - - /** - * @return the auxiliary values s0 and - * s1 used for partial modular reduction for - * Koblitz curves. - */ - internal virtual BigInteger[] GetSi() - { - if (si == null) - { - lock (this) - { - if (si == null) - { - si = Tnaf.GetSi(this); - } - } - } - return si; - } - protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) { ECFieldElement xp = FromBigInteger(X1), yp = null; @@ -1086,7 +1063,7 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement t = FromBigInteger(new BigInteger(m, rand)); z = zeroElement; ECFieldElement w = beta; - for (int i = 1; i <= m - 1; i++) + for (int i = 1; i < m; i++) { ECFieldElement w2 = w.Square(); z = z.Square().Add(w2.Multiply(t)); diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index 3e206e65f..a5ba515c5 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -1383,6 +1383,139 @@ namespace Org.BouncyCastle.Math.EC return lhs.Equals(rhs); } + + public override ECPoint ScaleX(ECFieldElement scale) + { + if (this.IsInfinity) + return this; + + switch (CurveCoordinateSystem) + { + case ECCurve.COORD_LAMBDA_AFFINE: + { + // Y is actually Lambda (X + Y/X) here + ECFieldElement X = RawXCoord, L = RawYCoord; + + ECFieldElement X2 = X.Multiply(scale); + ECFieldElement L2 = L.Add(X).Divide(scale).Add(X2); + + return Curve.CreateRawPoint(X, L2, RawZCoords, IsCompressed); + } + case ECCurve.COORD_LAMBDA_PROJECTIVE: + { + // Y is actually Lambda (X + Y/X) here + ECFieldElement X = RawXCoord, L = RawYCoord, Z = RawZCoords[0]; + + // We scale the Z coordinate also, to avoid an inversion + ECFieldElement X2 = X.Multiply(scale.Square()); + ECFieldElement L2 = L.Add(X).Add(X2); + ECFieldElement Z2 = Z.Multiply(scale); + + return Curve.CreateRawPoint(X, L2, new ECFieldElement[] { Z2 }, IsCompressed); + } + default: + { + return base.ScaleX(scale); + } + } + } + + public override ECPoint ScaleY(ECFieldElement scale) + { + if (this.IsInfinity) + return this; + + switch (CurveCoordinateSystem) + { + case ECCurve.COORD_LAMBDA_AFFINE: + case ECCurve.COORD_LAMBDA_PROJECTIVE: + { + ECFieldElement X = RawXCoord, L = RawYCoord; + + // Y is actually Lambda (X + Y/X) here + ECFieldElement L2 = L.Add(X).Multiply(scale).Add(X); + + return Curve.CreateRawPoint(X, L2, RawZCoords, IsCompressed); + } + default: + { + return base.ScaleY(scale); + } + } + } + + public override ECPoint Subtract(ECPoint b) + { + if (b.IsInfinity) + return this; + + // Add -b + return Add(b.Negate()); + } + + public virtual AbstractF2mPoint Tau() + { + if (this.IsInfinity) + return this; + + ECCurve curve = this.Curve; + int coord = curve.CoordinateSystem; + + ECFieldElement X1 = this.RawXCoord; + + switch (coord) + { + case ECCurve.COORD_AFFINE: + case ECCurve.COORD_LAMBDA_AFFINE: + { + ECFieldElement Y1 = this.RawYCoord; + return (AbstractF2mPoint)curve.CreateRawPoint(X1.Square(), Y1.Square(), IsCompressed); + } + case ECCurve.COORD_HOMOGENEOUS: + case ECCurve.COORD_LAMBDA_PROJECTIVE: + { + ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + return (AbstractF2mPoint)curve.CreateRawPoint(X1.Square(), Y1.Square(), + new ECFieldElement[] { Z1.Square() }, IsCompressed); + } + default: + { + throw new InvalidOperationException("unsupported coordinate system"); + } + } + } + + public virtual AbstractF2mPoint TauPow(int pow) + { + if (this.IsInfinity) + return this; + + ECCurve curve = this.Curve; + int coord = curve.CoordinateSystem; + + ECFieldElement X1 = this.RawXCoord; + + switch (coord) + { + case ECCurve.COORD_AFFINE: + case ECCurve.COORD_LAMBDA_AFFINE: + { + ECFieldElement Y1 = this.RawYCoord; + return (AbstractF2mPoint)curve.CreateRawPoint(X1.SquarePow(pow), Y1.SquarePow(pow), IsCompressed); + } + case ECCurve.COORD_HOMOGENEOUS: + case ECCurve.COORD_LAMBDA_PROJECTIVE: + { + ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + return (AbstractF2mPoint)curve.CreateRawPoint(X1.SquarePow(pow), Y1.SquarePow(pow), + new ECFieldElement[] { Z1.SquarePow(pow) }, IsCompressed); + } + default: + { + throw new InvalidOperationException("unsupported coordinate system"); + } + } + } } /** @@ -1491,66 +1624,6 @@ namespace Org.BouncyCastle.Math.EC } } - public override ECPoint ScaleX(ECFieldElement scale) - { - if (this.IsInfinity) - return this; - - switch (CurveCoordinateSystem) - { - case ECCurve.COORD_LAMBDA_AFFINE: - { - // Y is actually Lambda (X + Y/X) here - ECFieldElement X = RawXCoord, L = RawYCoord; - - ECFieldElement X2 = X.Multiply(scale); - ECFieldElement L2 = L.Add(X).Divide(scale).Add(X2); - - return Curve.CreateRawPoint(X, L2, RawZCoords, IsCompressed); - } - case ECCurve.COORD_LAMBDA_PROJECTIVE: - { - // Y is actually Lambda (X + Y/X) here - ECFieldElement X = RawXCoord, L = RawYCoord, Z = RawZCoords[0]; - - // We scale the Z coordinate also, to avoid an inversion - ECFieldElement X2 = X.Multiply(scale.Square()); - ECFieldElement L2 = L.Add(X).Add(X2); - ECFieldElement Z2 = Z.Multiply(scale); - - return Curve.CreateRawPoint(X, L2, new ECFieldElement[] { Z2 }, IsCompressed); - } - default: - { - return base.ScaleX(scale); - } - } - } - - public override ECPoint ScaleY(ECFieldElement scale) - { - if (this.IsInfinity) - return this; - - switch (CurveCoordinateSystem) - { - case ECCurve.COORD_LAMBDA_AFFINE: - case ECCurve.COORD_LAMBDA_PROJECTIVE: - { - ECFieldElement X = RawXCoord, L = RawYCoord; - - // Y is actually Lambda (X + Y/X) here - ECFieldElement L2 = L.Add(X).Multiply(scale).Add(X); - - return Curve.CreateRawPoint(X, L2, RawZCoords, IsCompressed); - } - default: - { - return base.ScaleY(scale); - } - } - } - protected internal override bool CompressionYTilde { get @@ -1579,43 +1652,7 @@ namespace Org.BouncyCastle.Math.EC } } - /** - * Check, if two ECPoints can be added or subtracted. - * @param a The first ECPoint to check. - * @param b The second ECPoint to check. - * @throws IllegalArgumentException if a and b - * cannot be added. - */ - private static void CheckPoints( - ECPoint a, - ECPoint b) - { - // Check, if points are on the same curve - if (!a.Curve.Equals(b.Curve)) - throw new ArgumentException("Only points on the same curve can be added or subtracted"); - -// F2mFieldElement.CheckFieldElements(a.x, b.x); - } - - /* (non-Javadoc) - * @see org.bouncycastle.math.ec.ECPoint#add(org.bouncycastle.math.ec.ECPoint) - */ public override ECPoint Add(ECPoint b) - { - CheckPoints(this, b); - return AddSimple((F2mPoint) b); - } - - /** - * Adds another ECPoints.F2m to this without - * checking if both points are on the same curve. Used by multiplication - * algorithms, because there all points are a multiple of the same point - * and hence the checks can be omitted. - * @param b The other ECPoints.F2m to add to - * this. - * @return this + b - */ - internal F2mPoint AddSimple(F2mPoint b) { if (this.IsInfinity) return b; @@ -1640,10 +1677,10 @@ namespace Org.BouncyCastle.Math.EC { if (dy.IsZero) { - return (F2mPoint)Twice(); + return Twice(); } - return (F2mPoint)curve.Infinity; + return curve.Infinity; } ECFieldElement L = dy.Divide(dx); @@ -1681,10 +1718,10 @@ namespace Org.BouncyCastle.Math.EC { if (U.IsZero) { - return (F2mPoint)Twice(); + return Twice(); } - return (F2mPoint)curve.Infinity; + return curve.Infinity; } ECFieldElement VSq = V.Square(); @@ -1705,9 +1742,9 @@ namespace Org.BouncyCastle.Math.EC if (X1.IsZero) { if (X2.IsZero) - return (F2mPoint)curve.Infinity; + return curve.Infinity; - return b.AddSimple(this); + return b.Add(this); } ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; @@ -1736,10 +1773,10 @@ namespace Org.BouncyCastle.Math.EC { if (A.IsZero) { - return (F2mPoint)Twice(); + return Twice(); } - return (F2mPoint)curve.Infinity; + return curve.Infinity; } ECFieldElement X3, L3, Z3; @@ -1800,68 +1837,6 @@ namespace Org.BouncyCastle.Math.EC } } - /* (non-Javadoc) - * @see org.bouncycastle.math.ec.ECPoint#subtract(org.bouncycastle.math.ec.ECPoint) - */ - public override ECPoint Subtract( - ECPoint b) - { - CheckPoints(this, b); - return SubtractSimple((F2mPoint) b); - } - - /** - * Subtracts another ECPoints.F2m from this - * without checking if both points are on the same curve. Used by - * multiplication algorithms, because there all points are a multiple - * of the same point and hence the checks can be omitted. - * @param b The other ECPoints.F2m to subtract from - * this. - * @return this - b - */ - internal F2mPoint SubtractSimple( - F2mPoint b) - { - if (b.IsInfinity) - return this; - - // Add -b - return AddSimple((F2mPoint) b.Negate()); - } - - public virtual F2mPoint Tau() - { - if (this.IsInfinity) - { - return this; - } - - ECCurve curve = this.Curve; - int coord = curve.CoordinateSystem; - - ECFieldElement X1 = this.RawXCoord; - - switch (coord) - { - case ECCurve.COORD_AFFINE: - case ECCurve.COORD_LAMBDA_AFFINE: - { - ECFieldElement Y1 = this.RawYCoord; - return new F2mPoint(curve, X1.Square(), Y1.Square(), IsCompressed); - } - case ECCurve.COORD_HOMOGENEOUS: - case ECCurve.COORD_LAMBDA_PROJECTIVE: - { - ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; - return new F2mPoint(curve, X1.Square(), Y1.Square(), new ECFieldElement[] { Z1.Square() }, IsCompressed); - } - default: - { - throw new InvalidOperationException("unsupported coordinate system"); - } - } - } - /* (non-Javadoc) * @see Org.BouncyCastle.Math.EC.ECPoint#twice() */ diff --git a/crypto/src/math/ec/abc/Tnaf.cs b/crypto/src/math/ec/abc/Tnaf.cs index 9f16886f5..b6e792aa4 100644 --- a/crypto/src/math/ec/abc/Tnaf.cs +++ b/crypto/src/math/ec/abc/Tnaf.cs @@ -384,11 +384,11 @@ namespace Org.BouncyCastle.Math.EC.Abc /** * Applies the operation τ() to an - * F2mPoint. - * @param p The F2mPoint to which τ() is applied. + * AbstractF2mPoint. + * @param p The AbstractF2mPoint to which τ() is applied. * @return τ(p) */ - public static F2mPoint Tau(F2mPoint p) + public static AbstractF2mPoint Tau(AbstractF2mPoint p) { return p.Tau(); } @@ -403,7 +403,7 @@ namespace Org.BouncyCastle.Math.EC.Abc * @throws ArgumentException if the given ECCurve is not a Koblitz * curve. */ - public static sbyte GetMu(F2mCurve curve) + public static sbyte GetMu(AbstractF2mCurve curve) { BigInteger a = curve.A.ToBigInteger(); @@ -423,6 +423,16 @@ namespace Org.BouncyCastle.Math.EC.Abc return mu; } + public static sbyte GetMu(ECFieldElement curveA) + { + return (sbyte)(curveA.IsZero ? -1 : 1); + } + + public static sbyte GetMu(int curveA) + { + return (sbyte)(curveA == 0 ? -1 : 1); + } + /** * Calculates the Lucas Sequence elements Uk-1 and * Uk or Vk-1 and @@ -526,53 +536,60 @@ namespace Org.BouncyCastle.Math.EC.Abc * @throws ArgumentException if curve is not a * Koblitz curve (Anomalous Binary Curve, ABC). */ - public static BigInteger[] GetSi(F2mCurve curve) + public static BigInteger[] GetSi(AbstractF2mCurve curve) { if (!curve.IsKoblitz) throw new ArgumentException("si is defined for Koblitz curves only"); - int m = curve.M; + int m = curve.FieldSize; int a = curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - int h = curve.Cofactor.IntValue; + sbyte mu = GetMu(a); + int shifts = GetShiftsForCofactor(curve.Cofactor); int index = m + 3 - a; BigInteger[] ui = GetLucas(mu, index, false); - BigInteger dividend0; - BigInteger dividend1; if (mu == 1) { - dividend0 = BigInteger.One.Subtract(ui[1]); - dividend1 = BigInteger.One.Subtract(ui[0]); - } - else if (mu == -1) - { - dividend0 = BigInteger.One.Add(ui[1]); - dividend1 = BigInteger.One.Add(ui[0]); - } - else - { - throw new ArgumentException("mu must be 1 or -1"); + ui[0] = ui[0].Negate(); + ui[1] = ui[1].Negate(); } - BigInteger[] si = new BigInteger[2]; + BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts); + BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate(); - if (h == 2) - { - si[0] = dividend0.ShiftRight(1); - si[1] = dividend1.ShiftRight(1).Negate(); - } - else if (h == 4) + return new BigInteger[] { dividend0, dividend1 }; + } + + public static BigInteger[] GetSi(int fieldSize, int curveA, BigInteger cofactor) + { + sbyte mu = GetMu(curveA); + int shifts = GetShiftsForCofactor(cofactor); + int index = fieldSize + 3 - curveA; + BigInteger[] ui = GetLucas(mu, index, false); + if (mu == 1) { - si[0] = dividend0.ShiftRight(2); - si[1] = dividend1.ShiftRight(2).Negate(); + ui[0] = ui[0].Negate(); + ui[1] = ui[1].Negate(); } - else + + BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts); + BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate(); + + return new BigInteger[] { dividend0, dividend1 }; + } + + protected static int GetShiftsForCofactor(BigInteger h) + { + if (h != null && h.BitLength < 4) { - throw new ArgumentException("h (Cofactor) must be 2 or 4"); + int hi = h.IntValue; + if (hi == 2) + return 1; + if (hi == 4) + return 2; } - return si; + throw new ArgumentException("h (Cofactor) must be 2 or 4"); } /** @@ -624,70 +641,77 @@ namespace Org.BouncyCastle.Math.EC.Abc } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by a BigInteger using the reduced τ-adic * NAF (RTNAF) method. - * @param p The F2mPoint to Multiply. + * @param p The AbstractF2mPoint to Multiply. * @param k The BigInteger by which to Multiply p. * @return k * p */ - public static F2mPoint MultiplyRTnaf(F2mPoint p, BigInteger k) + public static AbstractF2mPoint MultiplyRTnaf(AbstractF2mPoint p, BigInteger k) { - F2mCurve curve = (F2mCurve) p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); + AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; + int m = curve.FieldSize; + int a = curve.A.ToBigInteger().IntValue; + sbyte mu = GetMu(a); BigInteger[] s = curve.GetSi(); - ZTauElement rho = PartModReduction(k, m, a, s, mu, (sbyte)10); + ZTauElement rho = PartModReduction(k, m, (sbyte)a, s, mu, (sbyte)10); return MultiplyTnaf(p, rho); } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element λ of Z[τ] * using the τ-adic NAF (TNAF) method. - * @param p The F2mPoint to Multiply. + * @param p The AbstractF2mPoint to Multiply. * @param lambda The element λ of * Z[τ]. * @return λ * p */ - public static F2mPoint MultiplyTnaf(F2mPoint p, ZTauElement lambda) + public static AbstractF2mPoint MultiplyTnaf(AbstractF2mPoint p, ZTauElement lambda) { - F2mCurve curve = (F2mCurve)p.Curve; - sbyte mu = curve.GetMu(); + AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; + sbyte mu = GetMu(curve.A); sbyte[] u = TauAdicNaf(mu, lambda); - F2mPoint q = MultiplyFromTnaf(p, u); + AbstractF2mPoint q = MultiplyFromTnaf(p, u); return q; } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element λ of Z[τ] * using the τ-adic NAF (TNAF) method, given the TNAF * of λ. - * @param p The F2mPoint to Multiply. + * @param p The AbstractF2mPoint to Multiply. * @param u The the TNAF of λ.. * @return λ * p */ - public static F2mPoint MultiplyFromTnaf(F2mPoint p, sbyte[] u) + public static AbstractF2mPoint MultiplyFromTnaf(AbstractF2mPoint p, sbyte[] u) { - F2mCurve curve = (F2mCurve)p.Curve; - F2mPoint q = (F2mPoint) curve.Infinity; + ECCurve curve = p.Curve; + AbstractF2mPoint q = (AbstractF2mPoint)curve.Infinity; + AbstractF2mPoint pNeg = (AbstractF2mPoint)p.Negate(); + int tauCount = 0; for (int i = u.Length - 1; i >= 0; i--) { - q = Tau(q); - if (u[i] == 1) - { - q = (F2mPoint)q.AddSimple(p); - } - else if (u[i] == -1) + ++tauCount; + sbyte ui = u[i]; + if (ui != 0) { - q = (F2mPoint)q.SubtractSimple(p); + q = q.TauPow(tauCount); + tauCount = 0; + + ECPoint x = ui > 0 ? p : pNeg; + q = (AbstractF2mPoint)q.Add(x); } } + if (tauCount > 0) + { + q = q.TauPow(tauCount); + } return q; } @@ -800,28 +824,21 @@ namespace Org.BouncyCastle.Math.EC.Abc * @param a The parameter a of the elliptic curve. * @return The precomputation array for p. */ - public static F2mPoint[] GetPreComp(F2mPoint p, sbyte a) + public static AbstractF2mPoint[] GetPreComp(AbstractF2mPoint p, sbyte a) { - F2mPoint[] pu; - pu = new F2mPoint[16]; - pu[1] = p; - sbyte[][] alphaTnaf; - if (a == 0) - { - alphaTnaf = Tnaf.Alpha0Tnaf; - } - else - { - // a == 1 - alphaTnaf = Tnaf.Alpha1Tnaf; - } + sbyte[][] alphaTnaf = (a == 0) ? Tnaf.Alpha0Tnaf : Tnaf.Alpha1Tnaf; + + AbstractF2mPoint[] pu = new AbstractF2mPoint[(uint)(alphaTnaf.Length + 1) >> 1]; + pu[0] = p; - int precompLen = alphaTnaf.Length; - for (int i = 3; i < precompLen; i = i + 2) + uint precompLen = (uint)alphaTnaf.Length; + for (uint i = 3; i < precompLen; i += 2) { - pu[i] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); + pu[i >> 1] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); } - + + p.Curve.NormalizeAll(pu); + return pu; } } diff --git a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs index dda778eea..1e7ddae91 100644 --- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs @@ -15,23 +15,23 @@ namespace Org.BouncyCastle.Math.EC.Multiplier internal static readonly string PRECOMP_NAME = "bc_wtnaf"; /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by k using the reduced τ-adic NAF (RTNAF) * method. - * @param p The F2mPoint to multiply. + * @param p The AbstractF2mPoint to multiply. * @param k The integer by which to multiply k. * @return p multiplied by k. */ protected override ECPoint MultiplyPositive(ECPoint point, BigInteger k) { - if (!(point is F2mPoint)) - throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); - - F2mPoint p = (F2mPoint)point; - F2mCurve curve = (F2mCurve)p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); + if (!(point is AbstractF2mPoint)) + throw new ArgumentException("Only AbstractF2mPoint can be used in WTauNafMultiplier"); + + AbstractF2mPoint p = (AbstractF2mPoint)point; + AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; + int m = curve.FieldSize; + sbyte a = (sbyte)curve.A.ToBigInteger().IntValue; + sbyte mu = Tnaf.GetMu(a); BigInteger[] s = curve.GetSi(); ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10); @@ -40,16 +40,16 @@ namespace Org.BouncyCastle.Math.EC.Multiplier } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element λ of Z[τ] using * the τ-adic NAF (TNAF) method. - * @param p The F2mPoint to multiply. + * @param p The AbstractF2mPoint to multiply. * @param lambda The element λ of * Z[τ] of which to compute the * [τ]-adic NAF. * @return p multiplied by λ. */ - private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda, + private AbstractF2mPoint MultiplyWTnaf(AbstractF2mPoint p, ZTauElement lambda, PreCompInfo preCompInfo, sbyte a, sbyte mu) { ZTauElement[] alpha = (a == 0) ? Tnaf.Alpha0 : Tnaf.Alpha1; @@ -63,20 +63,20 @@ namespace Org.BouncyCastle.Math.EC.Multiplier } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element λ of Z[τ] * using the window τ-adic NAF (TNAF) method, given the * WTNAF of λ. - * @param p The F2mPoint to multiply. + * @param p The AbstractF2mPoint to multiply. * @param u The the WTNAF of λ.. * @return λ * p */ - private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, PreCompInfo preCompInfo) + private static AbstractF2mPoint MultiplyFromWTnaf(AbstractF2mPoint p, sbyte[] u, PreCompInfo preCompInfo) { - F2mCurve curve = (F2mCurve)p.Curve; + AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; sbyte a = (sbyte)curve.A.ToBigInteger().IntValue; - F2mPoint[] pu; + AbstractF2mPoint[] pu; if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo)) { pu = Tnaf.GetPreComp(p, a); @@ -90,26 +90,35 @@ namespace Org.BouncyCastle.Math.EC.Multiplier pu = ((WTauNafPreCompInfo)preCompInfo).PreComp; } + // TODO Include negations in precomp (optionally) and use from here + AbstractF2mPoint[] puNeg = new AbstractF2mPoint[pu.Length]; + for (int i = 0; i < pu.Length; ++i) + { + puNeg[i] = (AbstractF2mPoint)pu[i].Negate(); + } + + // q = infinity - F2mPoint q = (F2mPoint)curve.Infinity; + AbstractF2mPoint q = (AbstractF2mPoint) p.Curve.Infinity; + + int tauCount = 0; for (int i = u.Length - 1; i >= 0; i--) { - q = Tnaf.Tau(q); - sbyte ui = u[i]; + ++tauCount; + int ui = u[i]; if (ui != 0) { - if (ui > 0) - { - q = q.AddSimple(pu[ui]); - } - else - { - // u[i] < 0 - q = q.SubtractSimple(pu[-ui]); - } + q = q.TauPow(tauCount); + tauCount = 0; + + ECPoint x = ui > 0 ? pu[ui >> 1] : puNeg[(-ui) >> 1]; + q = (AbstractF2mPoint)q.Add(x); } } - + if (tauCount > 0) + { + q = q.TauPow(tauCount); + } return q; } } diff --git a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs index 3c18404c0..72659b3ec 100644 --- a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs +++ b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs @@ -8,14 +8,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier : PreCompInfo { /** - * Array holding the precomputed F2mPoints used for the + * Array holding the precomputed AbstractF2mPoints used for the * WTNAF multiplication in * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() * WTauNafMultiplier.multiply()}. */ - protected F2mPoint[] m_preComp; + protected AbstractF2mPoint[] m_preComp; - public virtual F2mPoint[] PreComp + public virtual AbstractF2mPoint[] PreComp { get { return m_preComp; } set { this.m_preComp = value; } -- cgit 1.4.1