diff options
Diffstat (limited to 'crypto/src/math')
| -rw-r--r-- | crypto/src/math/ec/ECAlgorithms.cs | 50 | ||||
| -rw-r--r-- | crypto/src/math/ec/ECCurve.cs | 92 | ||||
| -rw-r--r-- | crypto/src/math/ec/ECPoint.cs | 352 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/ECMultiplier.cs | 30 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/FpNafMultiplier.cs | 41 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/ReferenceMultiplier.cs | 61 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafMultiplier.cs | 274 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafPreCompInfo.cs | 76 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafUtilities.cs | 394 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WTauNafMultiplier.cs | 207 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs | 57 |
11 files changed, 1056 insertions, 578 deletions
diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs index 070c8326c..a7030700e 100644 --- a/crypto/src/math/ec/ECAlgorithms.cs +++ b/crypto/src/math/ec/ECAlgorithms.cs @@ -1,5 +1,6 @@ using System; +using Org.BouncyCastle.Math.EC.Multiplier; using Org.BouncyCastle.Math.Field; namespace Org.BouncyCastle.Math.EC @@ -105,32 +106,35 @@ namespace Org.BouncyCastle.Math.EC internal 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; + ECCurve curve = P.Curve; + ECPoint infinity = curve.Infinity; - for (int i = m - 1; i >= 0; --i) + // TODO conjugate co-Z addition (ZADDC) can return both of these + ECPoint PaddQ = P.Add(Q); + ECPoint PsubQ = P.Subtract(Q); + + ECPoint[] points = new ECPoint[] { Q, PsubQ, P, PaddQ }; + curve.NormalizeAll(points); + + ECPoint[] table = new ECPoint[] { + points[3].Negate(), points[2].Negate(), points[1].Negate(), + points[0].Negate(), infinity, points[0], + points[1], points[2], points[3] }; + + byte[] jsf = WNafUtilities.GenerateJsf(k, l); + + ECPoint R = infinity; + + int i = jsf.Length; + while (--i >= 0) { - R = R.Twice(); + int jsfi = jsf[i]; - 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); - } - } + // NOTE: The shifting ensures the sign is extended correctly + int kDigit = ((jsfi << 24) >> 28), lDigit = ((jsfi << 28) >> 28); + + int index = 4 + (kDigit * 3) + lDigit; + R = R.TwicePlus(table[index]); } return R; diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 2db6bdc80..38daa719c 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -109,6 +109,28 @@ namespace Org.BouncyCastle.Math.EC return coord == COORD_AFFINE; } + public virtual PreCompInfo GetPreCompInfo(ECPoint p) + { + CheckPoint(p); + return p.m_preCompInfo; + } + + /** + * Sets the <code>PreCompInfo</code> for a point on this curve. Used by + * <code>ECMultiplier</code>s to save the precomputation for this <code>ECPoint</code> for use + * by subsequent multiplication. + * + * @param point + * The <code>ECPoint</code> to store precomputations for. + * @param preCompInfo + * The values precomputed by the <code>ECMultiplier</code>. + */ + public virtual void SetPreCompInfo(ECPoint point, PreCompInfo preCompInfo) + { + CheckPoint(point); + point.m_preCompInfo = preCompInfo; + } + public virtual ECPoint ImportPoint(ECPoint p) { if (this == p.Curve) @@ -123,7 +145,56 @@ namespace Org.BouncyCastle.Math.EC // TODO Default behaviour could be improved if the two curves have the same coordinate system by copying any Z coordinates. p = p.Normalize(); - return CreatePoint(p.X.ToBigInteger(), p.Y.ToBigInteger(), p.withCompression); + return CreatePoint(p.X.ToBigInteger(), p.Y.ToBigInteger(), p.IsCompressed); + } + + /** + * Normalization ensures that any projective coordinate is 1, and therefore that the x, y + * coordinates reflect those of the equivalent point in an affine coordinate system. Where more + * than one point is to be normalized, this method will generally be more efficient than + * normalizing each point separately. + * + * @param points + * An array of points that will be updated in place with their normalized versions, + * where necessary + */ + public virtual void NormalizeAll(ECPoint[] points) + { + CheckPoints(points); + + if (this.CoordinateSystem == ECCurve.COORD_AFFINE) + { + return; + } + + /* + * Figure out which of the points actually need to be normalized + */ + ECFieldElement[] zs = new ECFieldElement[points.Length]; + int[] indices = new int[points.Length]; + int count = 0; + for (int i = 0; i < points.Length; ++i) + { + ECPoint p = points[i]; + if (null != p && !p.IsNormalized()) + { + zs[count] = p.GetZCoord(0); + indices[count++] = i; + } + } + + if (count == 0) + { + return; + } + + ECAlgorithms.MontgomeryTrick(zs, 0, count); + + for (int j = 0; j < count; ++j) + { + int index = indices[j]; + points[index] = points[index].Normalize(zs[j]); + } } public abstract ECPoint Infinity { get; } @@ -148,6 +219,25 @@ namespace Org.BouncyCastle.Math.EC get { return m_coord; } } + protected virtual void CheckPoint(ECPoint point) + { + if (null == point || (this != point.Curve)) + throw new ArgumentException("must be non-null and on this curve", "point"); + } + + protected virtual void CheckPoints(ECPoint[] points) + { + if (points == null) + throw new ArgumentNullException("points"); + + for (int i = 0; i < points.Length; ++i) + { + ECPoint point = points[i]; + if (null != point && this != point.Curve) + throw new ArgumentException("entries must be null or on this curve", "points"); + } + } + public virtual bool Equals(ECCurve other) { if (this == other) diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index 1b00b764f..7a4450ac1 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -2,8 +2,6 @@ using System; using System.Collections; using System.Diagnostics; -using Org.BouncyCastle.Asn1.X9; - using Org.BouncyCastle.Math.EC.Multiplier; namespace Org.BouncyCastle.Math.EC @@ -13,41 +11,122 @@ namespace Org.BouncyCastle.Math.EC */ public abstract class ECPoint { - internal readonly ECCurve curve; - internal readonly ECFieldElement x, y; - internal readonly bool withCompression; - internal PreCompInfo preCompInfo = null; + protected static ECFieldElement[] EMPTY_ZS = new ECFieldElement[0]; + + protected static ECFieldElement[] GetInitialZCoords(ECCurve curve) + { + // Cope with null curve, most commonly used by implicitlyCa + int coord = null == curve ? ECCurve.COORD_AFFINE : curve.CoordinateSystem; + + switch (coord) + { + case ECCurve.COORD_AFFINE: + case ECCurve.COORD_LAMBDA_AFFINE: + return EMPTY_ZS; + default: + break; + } + + ECFieldElement one = curve.FromBigInteger(BigInteger.One); + + switch (coord) + { + case ECCurve.COORD_HOMOGENEOUS: + case ECCurve.COORD_JACOBIAN: + case ECCurve.COORD_LAMBDA_PROJECTIVE: + return new ECFieldElement[] { one }; + case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: + return new ECFieldElement[] { one, one, one }; + case ECCurve.COORD_JACOBIAN_MODIFIED: + return new ECFieldElement[] { one, curve.A }; + default: + throw new ArgumentException("unknown coordinate system"); + } + } + + protected internal readonly ECCurve m_curve; + protected internal readonly ECFieldElement m_x, m_y; + protected internal readonly ECFieldElement[] m_zs; + protected internal readonly bool m_withCompression; - protected internal ECPoint( + protected internal PreCompInfo m_preCompInfo = null; + + protected ECPoint( ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) { - if (curve == null) - throw new ArgumentNullException("curve"); + this.m_curve = curve; + this.m_x = x; + this.m_y = y; + this.m_withCompression = withCompression; + } + + protected ECPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs) + { + this.m_curve = curve; + this.m_x = x; + this.m_y = y; + this.m_zs = zs; + } - this.curve = curve; - this.x = x; - this.y = y; - this.withCompression = withCompression; + public virtual ECCurve Curve + { + get { return m_curve; } } - public ECCurve Curve + protected virtual int CurveCoordinateSystem { - get { return curve; } + get + { + // Cope with null curve, most commonly used by implicitlyCa + return null == m_curve ? ECCurve.COORD_AFFINE : m_curve.CoordinateSystem; + } } - public ECFieldElement X + public virtual ECFieldElement X { - get { return x; } + get { return m_x; } } - public ECFieldElement Y + public virtual ECFieldElement Y { - get { return y; } + get { return m_y; } } + public virtual ECFieldElement GetZCoord(int index) + { + return (index < 0 || index >= m_zs.Length) ? null : m_zs[index]; + } + + public virtual ECFieldElement[] GetZCoords() + { + int zsLen = m_zs.Length; + if (zsLen == 0) + { + return m_zs; + } + ECFieldElement[] copy = new ECFieldElement[zsLen]; + Array.Copy(m_zs, 0, copy, 0, zsLen); + return copy; + } + + protected virtual void CheckNormalized() + { + if (!IsNormalized()) + throw new InvalidOperationException("point not in normal form"); + } + + public virtual bool IsNormalized() + { + int coord = this.CurveCoordinateSystem; + + return coord == ECCurve.COORD_AFFINE + || coord == ECCurve.COORD_LAMBDA_AFFINE + || IsInfinity; + //|| zs[0].isOne(); + } /** * Normalization ensures that any projective coordinate is 1, and therefore that the x, y @@ -57,17 +136,64 @@ namespace Org.BouncyCastle.Math.EC */ public virtual ECPoint Normalize() { - return this; + if (this.IsInfinity) + { + return this; + } + + switch (this.CurveCoordinateSystem) + { + case ECCurve.COORD_AFFINE: + case ECCurve.COORD_LAMBDA_AFFINE: + { + return this; + } + default: + { + ECFieldElement Z1 = GetZCoord(0); + if (Z1.IsOne) + { + return this; + } + + return Normalize(Z1.Invert()); + } + } + } + + internal virtual ECPoint Normalize(ECFieldElement zInv) + { + throw new InvalidOperationException("not a projective coordinate system"); + + //switch (this.CurveCoordinateSystem) + //{ + // case ECCurve.COORD_HOMOGENEOUS: + // case ECCurve.COORD_LAMBDA_PROJECTIVE: + // { + // return CreateScaledPoint(zInv, zInv); + // } + // case ECCurve.COORD_JACOBIAN: + // case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: + // case ECCurve.COORD_JACOBIAN_MODIFIED: + // { + // ECFieldElement zInv2 = zInv.Square(), zInv3 = zInv2.Multiply(zInv); + // return CreateScaledPoint(zInv2, zInv3); + // } + // default: + // { + // throw new InvalidOperationException("not a projective coordinate system"); + // } + //} } public bool IsInfinity { - get { return x == null && y == null; } + get { return m_x == null && m_y == null; } } public bool IsCompressed { - get { return withCompression; } + get { return m_withCompression; } } public override bool Equals(object obj) @@ -102,29 +228,32 @@ namespace Org.BouncyCastle.Math.EC return hc; } - /** - * Sets the <code>PreCompInfo</code>. Used by <code>ECMultiplier</code>s - * to save the precomputation for this <code>ECPoint</code> to store the - * precomputation result for use by subsequent multiplication. - * @param preCompInfo The values precomputed by the - * <code>ECMultiplier</code>. - */ - internal void SetPreCompInfo( - PreCompInfo preCompInfo) - { - this.preCompInfo = preCompInfo; - } - public virtual byte[] GetEncoded() { - return GetEncoded(withCompression); + return GetEncoded(m_withCompression); } public abstract byte[] GetEncoded(bool compressed); + protected internal abstract bool CompressionYTilde { get; } + public abstract ECPoint Add(ECPoint b); public abstract ECPoint Subtract(ECPoint b); public abstract ECPoint Negate(); + + public virtual ECPoint TimesPow2(int e) + { + if (e < 0) + throw new ArgumentException("cannot be negative", "e"); + + ECPoint p = this; + while (--e >= 0) + { + p = p.Twice(); + } + return p; + } + public abstract ECPoint Twice(); public abstract ECPoint Multiply(BigInteger b); @@ -151,41 +280,37 @@ namespace Org.BouncyCastle.Math.EC { } - protected internal abstract bool YTilde { get; } - /** * return the field element encoded with point compression. (S 4.3.6) */ public override byte[] GetEncoded(bool compressed) { if (this.IsInfinity) + { return new byte[1]; + } + + ECPoint normed = Normalize(); - // Note: some of the tests rely on calculating byte length from the field element - // (since the test cases use mismatching fields for curve/elements) - int byteLength = X9IntegerConverter.GetByteLength(x); - byte[] X = X9IntegerConverter.IntegerToBytes(this.X.ToBigInteger(), byteLength); - byte[] PO; + byte[] X = normed.X.GetEncoded(); if (compressed) { - PO = new byte[1 + X.Length]; - - PO[0] = (byte)(YTilde ? 0x03 : 0x02); + byte[] PO = new byte[X.Length + 1]; + PO[0] = (byte)(normed.CompressionYTilde ? 0x03 : 0x02); + Array.Copy(X, 0, PO, 1, X.Length); + return PO; } - else - { - byte[] Y = X9IntegerConverter.IntegerToBytes(this.Y.ToBigInteger(), byteLength); - PO = new byte[1 + X.Length + Y.Length]; - PO[0] = 0x04; + byte[] Y = normed.Y.GetEncoded(); - Y.CopyTo(PO, 1 + X.Length); + { + byte[] PO = new byte[X.Length + Y.Length + 1]; + PO[0] = 0x04; + Array.Copy(X, 0, PO, 1, X.Length); + Array.Copy(Y, 0, PO, X.Length + 1, Y.Length); + return PO; } - - X.CopyTo(PO, 1); - - return PO; } /** @@ -203,9 +328,9 @@ namespace Org.BouncyCastle.Math.EC return this; if (k.SignValue == 0) - return this.curve.Infinity; + return Curve.Infinity; - return this.Curve.GetMultiplier().Multiply(this, k, preCompInfo); + return Curve.GetMultiplier().Multiply(this, k); } } @@ -249,12 +374,9 @@ namespace Org.BouncyCastle.Math.EC throw new ArgumentException("Exactly one of the field elements is null"); } - protected internal override bool YTilde + protected internal override bool CompressionYTilde { - get - { - return this.Y.TestBitZero(); - } + get { return this.Y.TestBitZero(); } } // B.3 pg 62 @@ -274,8 +396,8 @@ namespace Org.BouncyCastle.Math.EC return Twice(); } - ECFieldElement X1 = this.x, Y1 = this.y; - ECFieldElement X2 = b.x, Y2 = b.y; + ECFieldElement X1 = this.X, Y1 = this.Y; + ECFieldElement X2 = b.X, Y2 = b.Y; ECFieldElement dx = X2.Subtract(X1), dy = Y2.Subtract(Y1); @@ -288,14 +410,14 @@ namespace Org.BouncyCastle.Math.EC } // this == -b, i.e. the result is the point at infinity - return curve.Infinity; + return Curve.Infinity; } ECFieldElement gamma = dy.Divide(dx); ECFieldElement X3 = gamma.Square().Subtract(X1).Subtract(X2); ECFieldElement Y3 = gamma.Multiply(X1.Subtract(X3)).Subtract(Y1); - return new FpPoint(curve, X3, Y3, this.withCompression); + return new FpPoint(Curve, X3, Y3, IsCompressed); } // B.3 pg 62 @@ -306,20 +428,20 @@ namespace Org.BouncyCastle.Math.EC return this; } - ECFieldElement Y1 = this.y; + ECFieldElement Y1 = this.Y; if (Y1.IsZero) { - return curve.Infinity; + return Curve.Infinity; } - ECFieldElement X1 = this.x; + ECFieldElement X1 = this.X; ECFieldElement X1Squared = X1.Square(); ECFieldElement gamma = Three(X1Squared).Add(this.Curve.A).Divide(Two(Y1)); ECFieldElement X3 = gamma.Square().Subtract(Two(X1)); ECFieldElement Y3 = gamma.Multiply(X1.Subtract(X3)).Subtract(Y1); - return new FpPoint(curve, X3, Y3, this.withCompression); + return new FpPoint(Curve, X3, Y3, IsCompressed); } public override ECPoint TwicePlus(ECPoint b) @@ -337,14 +459,14 @@ namespace Org.BouncyCastle.Math.EC return Twice(); } - ECFieldElement Y1 = this.y; + ECFieldElement Y1 = this.Y; if (Y1.IsZero) { return b; } - ECFieldElement X1 = this.x; - ECFieldElement X2 = b.x, Y2 = b.y; + ECFieldElement X1 = this.X; + ECFieldElement X2 = b.X, Y2 = b.Y; ECFieldElement dx = X2.Subtract(X1), dy = Y2.Subtract(Y1); @@ -369,7 +491,7 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement d = X.Multiply(Two(X1).Add(X2)).Subtract(Y); if (d.IsZero) { - return curve.Infinity; + return Curve.Infinity; } ECFieldElement D = d.Multiply(dx); @@ -379,27 +501,27 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement X4 = (L2.Subtract(L1)).Multiply(L1.Add(L2)).Add(X2); ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1); - return new FpPoint(curve, X4, Y4, this.withCompression); + return new FpPoint(Curve, X4, Y4, IsCompressed); } public override ECPoint ThreeTimes() { - if (this.IsInfinity || this.y.IsZero) + if (IsInfinity || this.Y.IsZero) { return this; } - ECFieldElement X1 = this.x, Y1 = this.y; + ECFieldElement X1 = this.X, Y1 = this.Y; ECFieldElement _2Y1 = Two(Y1); ECFieldElement X = _2Y1.Square(); - ECFieldElement Z = Three(X1.Square()).Add(this.Curve.A); + ECFieldElement Z = Three(X1.Square()).Add(Curve.A); ECFieldElement Y = Z.Square(); ECFieldElement d = Three(X1).Multiply(X).Subtract(Y); if (d.IsZero) { - return this.Curve.Infinity; + return Curve.Infinity; } ECFieldElement D = d.Multiply(_2Y1); @@ -409,7 +531,7 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement X4 = (L2.Subtract(L1)).Multiply(L1.Add(L2)).Add(X1); ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1); - return new FpPoint(curve, X4, Y4, this.withCompression); + return new FpPoint(Curve, X4, Y4, IsCompressed); } protected virtual ECFieldElement Two(ECFieldElement x) @@ -455,7 +577,20 @@ namespace Org.BouncyCastle.Math.EC public override ECPoint Negate() { - return new FpPoint(this.curve, this.x, this.y.Negate(), this.withCompression); + if (IsInfinity) + { + return this; + } + + ECCurve curve = this.Curve; + //int coord = curve.CoordinateSystem; + + //if (ECCurve.COORD_AFFINE != coord) + //{ + // return new FpPoint(curve, X, Y.Negate(), this.m_zs, IsCompressed); + //} + + return new FpPoint(curve, X, Y.Negate(), IsCompressed); } } @@ -499,10 +634,10 @@ namespace Org.BouncyCastle.Math.EC if (x != null) { // Check if x and y are elements of the same field - F2mFieldElement.CheckFieldElements(this.x, this.y); + F2mFieldElement.CheckFieldElements(x, y); // Check if x and a are elements of the same field - F2mFieldElement.CheckFieldElements(this.x, this.curve.A); + F2mFieldElement.CheckFieldElements(x, curve.A); } } @@ -516,7 +651,7 @@ namespace Org.BouncyCastle.Math.EC { } - protected internal override bool YTilde + protected internal override bool CompressionYTilde { get { @@ -539,7 +674,7 @@ namespace Org.BouncyCastle.Math.EC ECPoint b) { // Check, if points are on the same curve - if (!a.curve.Equals(b.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); @@ -575,28 +710,28 @@ namespace Org.BouncyCastle.Math.EC F2mFieldElement y2 = (F2mFieldElement) b.Y; // Check if b == this or b == -this - if (this.x.Equals(x2)) + if (this.X.Equals(x2)) { // this == b, i.e. this must be doubled - if (this.y.Equals(y2)) + if (this.Y.Equals(y2)) return (F2mPoint) this.Twice(); // this = -other, i.e. the result is the point at infinity - return (F2mPoint) this.curve.Infinity; + return (F2mPoint) Curve.Infinity; } - ECFieldElement xSum = this.x.Add(x2); + ECFieldElement xSum = this.X.Add(x2); F2mFieldElement lambda - = (F2mFieldElement)(this.y.Add(y2)).Divide(xSum); + = (F2mFieldElement)(this.Y.Add(y2)).Divide(xSum); F2mFieldElement x3 - = (F2mFieldElement)lambda.Square().Add(lambda).Add(xSum).Add(this.curve.A); + = (F2mFieldElement)lambda.Square().Add(lambda).Add(xSum).Add(Curve.A); F2mFieldElement y3 - = (F2mFieldElement)lambda.Multiply(this.x.Add(x3)).Add(x3).Add(this.y); + = (F2mFieldElement)lambda.Multiply(this.X.Add(x3)).Add(x3).Add(this.Y); - return new F2mPoint(curve, x3, y3, withCompression); + return new F2mPoint(Curve, x3, y3, IsCompressed); } /* (non-Javadoc) @@ -639,21 +774,34 @@ namespace Org.BouncyCastle.Math.EC // if x1 == 0, then (x1, y1) == (x1, x1 + y1) // and hence this = -this and thus 2(x1, y1) == infinity - if (this.x.IsZero) - return this.curve.Infinity; + if (this.X.IsZero) + { + return Curve.Infinity; + } - F2mFieldElement lambda = (F2mFieldElement) this.x.Add(this.y.Divide(this.x)); - F2mFieldElement x2 = (F2mFieldElement)lambda.Square().Add(lambda).Add(this.curve.A); - ECFieldElement ONE = this.curve.FromBigInteger(BigInteger.One); - F2mFieldElement y2 = (F2mFieldElement)this.x.Square().Add( + F2mFieldElement lambda = (F2mFieldElement) this.X.Add(this.Y.Divide(this.X)); + F2mFieldElement x2 = (F2mFieldElement)lambda.Square().Add(lambda).Add(Curve.A); + ECFieldElement ONE = Curve.FromBigInteger(BigInteger.One); + F2mFieldElement y2 = (F2mFieldElement)this.X.Square().Add( x2.Multiply(lambda.Add(ONE))); - return new F2mPoint(this.curve, x2, y2, withCompression); + return new F2mPoint(Curve, x2, y2, IsCompressed); } public override ECPoint Negate() { - return new F2mPoint(curve, this.x, this.x.Add(this.y), withCompression); + if (IsInfinity) + { + return this; + } + + ECFieldElement X1 = this.X; + if (X1.IsZero) + { + return this; + } + + return new F2mPoint(Curve, X1, X1.Add(this.Y), IsCompressed); } } } diff --git a/crypto/src/math/ec/multiplier/ECMultiplier.cs b/crypto/src/math/ec/multiplier/ECMultiplier.cs index ad576ff55..8d6136b34 100644 --- a/crypto/src/math/ec/multiplier/ECMultiplier.cs +++ b/crypto/src/math/ec/multiplier/ECMultiplier.cs @@ -1,18 +1,18 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Interface for classes encapsulating a point multiplication algorithm - * for <code>ECPoint</code>s. - */ - public interface ECMultiplier - { - /** - * Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e. - * <code>p</code> is added <code>k</code> times to itself. - * @param p The <code>ECPoint</code> to be multiplied. - * @param k The factor by which <code>p</code> i multiplied. - * @return <code>p</code> multiplied by <code>k</code>. - */ - ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo); - } + /** + * Interface for classes encapsulating a point multiplication algorithm + * for <code>ECPoint</code>s. + */ + public interface ECMultiplier + { + /** + * Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e. + * <code>p</code> is added <code>k</code> times to itself. + * @param p The <code>ECPoint</code> to be multiplied. + * @param k The factor by which <code>p</code> is multiplied. + * @return <code>p</code> multiplied by <code>k</code>. + */ + ECPoint Multiply(ECPoint p, BigInteger k); + } } diff --git a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs index 3453e5600..e7efa2a44 100644 --- a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs @@ -1,38 +1,27 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { /** - * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm. - */ - internal class FpNafMultiplier + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right). + */ + public class FpNafMultiplier : ECMultiplier { - /** - * D.3.2 pg 101 - * @see org.bouncycastle.math.ec.multiplier.ECMultiplier#multiply(org.bouncycastle.math.ec.ECPoint, java.math.BigInteger) - */ - public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) + public virtual ECPoint Multiply(ECPoint p, BigInteger k) { - // TODO Probably should try to add this - // BigInteger e = k.Mod(n); // n == order of p - BigInteger e = k; - BigInteger h = e.Multiply(BigInteger.Three); + int[] naf = WNafUtilities.GenerateCompactNaf(k); - ECPoint neg = p.Negate(); - ECPoint R = p; + ECPoint addP = p.Normalize(), subP = addP.Negate(); - for (int i = h.BitLength - 2; i > 0; --i) - { - bool hBit = h.TestBit(i); - bool eBit = e.TestBit(i); + ECPoint R = p.Curve.Infinity; - if (hBit == eBit) - { - R = R.Twice(); - } - else - { - R = R.TwicePlus(hBit ? p : neg); - } + int i = naf.Length; + while (--i >= 0) + { + int ni = naf[i]; + int digit = ni >> 16, zeroes = ni & 0xFFFF; + + R = R.TwicePlus(digit < 0 ? subP : addP); + R = R.TimesPow2(zeroes); } return R; diff --git a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs index cdccffc2d..a3763848e 100644 --- a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs +++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs @@ -1,30 +1,37 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - internal class ReferenceMultiplier - : ECMultiplier - { - /** - * Simple shift-and-add multiplication. Serves as reference implementation - * to verify (possibly faster) implementations in - * {@link org.bouncycastle.math.ec.ECPoint ECPoint}. - * - * @param p The point to multiply. - * @param k The factor by which to multiply. - * @return The result of the point multiplication <code>k * p</code>. - */ - public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) - { - ECPoint q = p.Curve.Infinity; - int t = k.BitLength; - for (int i = 0; i < t; i++) - { - if (k.TestBit(i)) - { - q = q.Add(p); - } - p = p.Twice(); - } - return q; - } - } + public class ReferenceMultiplier + : ECMultiplier + { + /** + * Simple shift-and-add multiplication. Serves as reference implementation + * to verify (possibly faster) implementations in + * {@link org.bouncycastle.math.ec.ECPoint ECPoint}. + * + * @param p The point to multiply. + * @param k The factor by which to multiply. + * @return The result of the point multiplication <code>k * p</code>. + */ + public virtual ECPoint Multiply(ECPoint p, BigInteger k) + { + ECPoint q = p.Curve.Infinity; + int t = k.BitLength; + if (t > 0) + { + if (k.TestBit(0)) + { + q = p; + } + for (int i = 1; i < t; i++) + { + p = p.Twice(); + if (k.TestBit(i)) + { + q = q.Add(p); + } + } + } + return q; + } + } } diff --git a/crypto/src/math/ec/multiplier/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafMultiplier.cs index 570ceee95..c2bb8c465 100644 --- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WNafMultiplier.cs @@ -6,238 +6,98 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * Class implementing the WNAF (Window Non-Adjacent Form) multiplication * algorithm. */ - internal class WNafMultiplier - : ECMultiplier + public class WNafMultiplier + : ECMultiplier { /** - * Computes the Window NAF (non-adjacent Form) of an integer. - * @param width The width <code>w</code> of the Window NAF. The width is - * defined as the minimal number <code>w</code>, such that for any - * <code>w</code> consecutive digits in the resulting representation, at - * most one is non-zero. - * @param k The integer of which the Window NAF is computed. - * @return The Window NAF of the given width, such that the following holds: - * <code>k = −<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup> - * </code>, where the <code>k<sub>i</sub></code> denote the elements of the - * returned <code>sbyte[]</code>. - */ - public sbyte[] WindowNaf(sbyte width, BigInteger k) + * Multiplies <code>this</code> by an integer <code>k</code> using the + * Window NAF method. + * @param k The integer by which <code>this</code> is multiplied. + * @return A new <code>ECPoint</code> which equals <code>this</code> + * multiplied by <code>k</code>. + */ + public virtual ECPoint Multiply(ECPoint p, BigInteger k) { - // The window NAF is at most 1 element longer than the binary - // representation of the integer k. sbyte can be used instead of short or - // int unless the window width is larger than 8. For larger width use - // short or int. However, a width of more than 8 is not efficient for - // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than - // 1000 Bits are currently not used in practice. - sbyte[] wnaf = new sbyte[k.BitLength + 1]; + // Clamp the window width in the range [2, 16] + int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength))); - // 2^width as short and BigInteger - short pow2wB = (short)(1 << width); - BigInteger pow2wBI = BigInteger.ValueOf(pow2wB); + WNafPreCompInfo wnafPreCompInfo = WNafUtilities.Precompute(p, width, true); + ECPoint[] preComp = wnafPreCompInfo.PreComp; + ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg; - int i = 0; + int[] wnaf = WNafUtilities.GenerateCompactWindowNaf(width, k); - // The actual length of the WNAF - int length = 0; + ECPoint R = p.Curve.Infinity; - // while k >= 1 - while (k.SignValue > 0) - { - // if k is odd - if (k.TestBit(0)) - { - // k Mod 2^width - BigInteger remainder = k.Mod(pow2wBI); - - // if remainder > 2^(width - 1) - 1 - if (remainder.TestBit(width - 1)) - { - wnaf[i] = (sbyte)(remainder.IntValue - pow2wB); - } - else - { - wnaf[i] = (sbyte)remainder.IntValue; - } - // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1] - - k = k.Subtract(BigInteger.ValueOf(wnaf[i])); - length = i; - } - else - { - wnaf[i] = 0; - } - - // k = k/2 - k = k.ShiftRight(1); - i++; - } - - length++; - - // Reduce the WNAF array to its actual length - sbyte[] wnafShort = new sbyte[length]; - Array.Copy(wnaf, 0, wnafShort, 0, length); - return wnafShort; - } + int i = wnaf.Length; - /** - * Multiplies <code>this</code> by an integer <code>k</code> using the - * Window NAF method. - * @param k The integer by which <code>this</code> is multiplied. - * @return A new <code>ECPoint</code> which equals <code>this</code> - * multiplied by <code>k</code>. - */ - public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) - { - WNafPreCompInfo wnafPreCompInfo; - - if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo)) + /* + * NOTE This code optimizes the first window using the precomputed points to substitute an + * addition for 2 or more doublings. + */ + if (i > 1) { - wnafPreCompInfo = (WNafPreCompInfo)preCompInfo; - } - else - { - // Ignore empty PreCompInfo or PreCompInfo of incorrect type - wnafPreCompInfo = new WNafPreCompInfo(); - } - - // floor(log2(k)) - int m = k.BitLength; + int wi = wnaf[--i]; + int digit = wi >> 16, zeroes = wi & 0xFFFF; + + int n = System.Math.Abs(digit); + ECPoint[] table = digit < 0 ? preCompNeg : preComp; + + /* + * NOTE: We use this optimization conservatively, since some coordinate systems have + * significantly cheaper doubling relative to addition. + * + * (n << 2) selects precomputed values in the lower half of the table + * (n << 3) selects precomputed values in the lower quarter of the table + */ + //if ((n << 2) < (1 << width)) + if ((n << 3) < (1 << width)) + { + int highest = LongArray.BitLengths[n]; + int lowBits = n ^ (1 << (highest - 1)); + int scale = width - highest; - // width of the Window NAF - sbyte width; + int i1 = ((1 << (width - 1)) - 1); + int i2 = (lowBits << scale) + 1; + R = table[i1 >> 1].Add(table[i2 >> 1]); - // Required length of precomputation array - int reqPreCompLen; + zeroes -= scale; - // Determine optimal width and corresponding length of precomputation - // array based on literature values - if (m < 13) - { - width = 2; - reqPreCompLen = 1; - } - else - { - if (m < 41) - { - width = 3; - reqPreCompLen = 2; + // Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); } else { - if (m < 121) - { - width = 4; - reqPreCompLen = 4; - } - else - { - if (m < 337) - { - width = 5; - reqPreCompLen = 8; - } - else - { - if (m < 897) - { - width = 6; - reqPreCompLen = 16; - } - else - { - if (m < 2305) - { - width = 7; - reqPreCompLen = 32; - } - else - { - width = 8; - reqPreCompLen = 127; - } - } - } - } + R = table[n >> 1]; } - } - - // The length of the precomputation array - int preCompLen = 1; - ECPoint[] preComp = wnafPreCompInfo.GetPreComp(); - ECPoint twiceP = wnafPreCompInfo.GetTwiceP(); - - // Check if the precomputed ECPoints already exist - if (preComp == null) - { - // Precomputation must be performed from scratch, create an empty - // precomputation array of desired length - preComp = new ECPoint[]{ p }; - } - else - { - // Take the already precomputed ECPoints to start with - preCompLen = preComp.Length; + R = R.TimesPow2(zeroes); } - if (twiceP == null) + while (i > 0) { - // Compute twice(p) - twiceP = p.Twice(); - } + int wi = wnaf[--i]; + int digit = wi >> 16, zeroes = wi & 0xFFFF; - if (preCompLen < reqPreCompLen) - { - // Precomputation array must be made bigger, copy existing preComp - // array into the larger new preComp array - ECPoint[] oldPreComp = preComp; - preComp = new ECPoint[reqPreCompLen]; - Array.Copy(oldPreComp, 0, preComp, 0, preCompLen); + int n = System.Math.Abs(digit); + ECPoint[] table = digit < 0 ? preCompNeg : preComp; + ECPoint r = table[n >> 1]; - for (int i = preCompLen; i < reqPreCompLen; i++) - { - // Compute the new ECPoints for the precomputation array. - // The values 1, 3, 5, ..., 2^(width-1)-1 times p are - // computed - preComp[i] = twiceP.Add(preComp[i - 1]); - } + R = R.TwicePlus(r); + R = R.TimesPow2(zeroes); } - // Compute the Window NAF of the desired width - sbyte[] wnaf = WindowNaf(width, k); - int l = wnaf.Length; - - // Apply the Window NAF to p using the precomputed ECPoint values. - ECPoint q = p.Curve.Infinity; - for (int i = l - 1; i >= 0; i--) - { - int wi = wnaf[i]; - if (wi == 0) - { - q = q.Twice(); - } - else - { - int n = System.Math.Abs(wi); - ECPoint r = preComp[n >> 1]; - if (wi < 0) - { - r = r.Negate(); - } - - q = q.TwicePlus(r); - } - } + return R; + } - // Set PreCompInfo in ECPoint, such that it is available for next - // multiplication. - wnafPreCompInfo.SetPreComp(preComp); - wnafPreCompInfo.SetTwiceP(twiceP); - p.SetPreCompInfo(wnafPreCompInfo); - return q; + /** + * Determine window width to use for a scalar multiplication of the given size. + * + * @param bits the bit-length of the scalar to multiply by + * @return the window size to use + */ + protected virtual int GetWindowSize(int bits) + { + return WNafUtilities.GetWindowSize(bits); } } } diff --git a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs index d9305dace..7e0a73154 100644 --- a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs +++ b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs @@ -1,46 +1,46 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Class holding precomputation data for the WNAF (Window Non-Adjacent Form) - * algorithm. - */ - internal class WNafPreCompInfo - : PreCompInfo - { - /** - * Array holding the precomputed <code>ECPoint</code>s used for the Window - * NAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply() - * WNafMultiplier.multiply()}</code>. - */ - private ECPoint[] preComp = null; + /** + * Class holding precomputation data for the WNAF (Window Non-Adjacent Form) + * algorithm. + */ + public class WNafPreCompInfo + : PreCompInfo + { + /** + * Array holding the precomputed <code>ECPoint</code>s used for a Window + * NAF multiplication. + */ + protected ECPoint[] m_preComp = null; - /** - * Holds an <code>ECPoint</code> representing twice(this). Used for the - * Window NAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply() - * WNafMultiplier.multiply()}</code>. - */ - private ECPoint twiceP = null; + /** + * Array holding the negations of the precomputed <code>ECPoint</code>s used + * for a Window NAF multiplication. + */ + protected ECPoint[] m_preCompNeg = null; - internal ECPoint[] GetPreComp() - { - return preComp; - } + /** + * Holds an <code>ECPoint</code> representing Twice(this). Used for the + * Window NAF multiplication to create or extend the precomputed values. + */ + protected ECPoint m_twice = null; - internal void SetPreComp(ECPoint[] preComp) - { - this.preComp = preComp; - } + public virtual ECPoint[] PreComp + { + get { return m_preComp; } + set { this.m_preComp = value; } + } - internal ECPoint GetTwiceP() - { - return twiceP; - } + public virtual ECPoint[] PreCompNeg + { + get { return m_preCompNeg; } + set { this.m_preCompNeg = value; } + } - internal void SetTwiceP(ECPoint twiceThis) - { - this.twiceP = twiceThis; - } - } + public virtual ECPoint Twice + { + get { return m_twice; } + set { this.m_twice = value; } + } + } } diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs new file mode 100644 index 000000000..d8b0c6e6a --- /dev/null +++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs @@ -0,0 +1,394 @@ +using System; + +using Org.BouncyCastle.Math; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public abstract class WNafUtilities + { + private static int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 }; + + public static int[] GenerateCompactNaf(BigInteger k) + { + if ((k.BitLength >> 16) != 0) + throw new ArgumentException("must have bitlength < 2^16", "k"); + + BigInteger _3k = k.ShiftLeft(1).Add(k); + + int digits = _3k.BitLength - 1; + int[] naf = new int[(digits + 1) >> 1]; + + int length = 0, zeroes = 0; + for (int i = 1; i <= digits; ++i) + { + bool _3kBit = _3k.TestBit(i); + bool kBit = k.TestBit(i); + + if (_3kBit == kBit) + { + ++zeroes; + } + else + { + int digit = kBit ? -1 : 1; + naf[length++] = (digit << 16) | zeroes; + zeroes = 0; + } + } + + if (naf.Length > length) + { + naf = Trim(naf, length); + } + + return naf; + } + + public static int[] GenerateCompactWindowNaf(int width, BigInteger k) + { + if (width == 2) + { + return GenerateCompactNaf(k); + } + + if (width < 2 || width > 16) + throw new ArgumentException("must be in the range [2, 16]", "width"); + if ((k.BitLength >> 16) != 0) + throw new ArgumentException("must have bitlength < 2^16", "k"); + + int[] wnaf = new int[k.BitLength / width + 1]; + + // 2^width and a mask and sign bit set accordingly + int pow2 = 1 << width; + int mask = pow2 - 1; + int sign = pow2 >> 1; + + bool carry = false; + int length = 0, pos = 0; + + while (pos <= k.BitLength) + { + if (k.TestBit(pos) == carry) + { + ++pos; + continue; + } + + k = k.ShiftRight(pos); + + int digit = k.IntValue & mask; + if (carry) + { + ++digit; + } + + carry = (digit & sign) != 0; + if (carry) + { + digit -= pow2; + } + + int zeroes = length > 0 ? pos - 1 : pos; + wnaf[length++] = (digit << 16) | zeroes; + pos = width; + } + + // Reduce the WNAF array to its actual length + if (wnaf.Length > length) + { + wnaf = Trim(wnaf, length); + } + + return wnaf; + } + + public static byte[] GenerateJsf(BigInteger g, BigInteger h) + { + int digits = System.Math.Max(g.BitLength, h.BitLength) + 1; + byte[] jsf = new byte[digits]; + + BigInteger k0 = g, k1 = h; + int j = 0, d0 = 0, d1 = 0; + + int offset = 0; + while ((d0 | d1) != 0 || k0.BitLength > offset || k1.BitLength > offset) + { + int n0 = ((int)((uint)k0.IntValue >> offset) + d0) & 7; + int n1 = ((int)((uint)k1.IntValue >> offset) + d1) & 7; + + int u0 = n0 & 1; + if (u0 != 0) + { + u0 -= (n0 & 2); + if ((n0 + u0) == 4 && (n1 & 3) == 2) + { + u0 = -u0; + } + } + + int u1 = n1 & 1; + if (u1 != 0) + { + u1 -= (n1 & 2); + if ((n1 + u1) == 4 && (n0 & 3) == 2) + { + u1 = -u1; + } + } + + if ((d0 << 1) == 1 + u0) + { + d0 ^= 1; + } + if ((d1 << 1) == 1 + u1) + { + d1 ^= 1; + } + + if (++offset == 30) + { + offset = 0; + k0 = k0.ShiftRight(30); + k1 = k1.ShiftRight(30); + } + + jsf[j++] = (byte)((u0 << 4) | (u1 & 0xF)); + } + + // Reduce the JSF array to its actual length + if (jsf.Length > j) + { + jsf = Trim(jsf, j); + } + + return jsf; + } + + public static byte[] GenerateNaf(BigInteger k) + { + BigInteger _3k = k.ShiftLeft(1).Add(k); + + int digits = _3k.BitLength - 1; + byte[] naf = new byte[digits]; + + for (int i = 1; i <= digits; ++i) + { + bool _3kBit = _3k.TestBit(i); + bool kBit = k.TestBit(i); + + naf[i - 1] = (byte)(_3kBit == kBit ? 0 : kBit ? -1 : 1); + } + + return naf; + } + + /** + * Computes the Window NAF (non-adjacent Form) of an integer. + * @param width The width <code>w</code> of the Window NAF. The width is + * defined as the minimal number <code>w</code>, such that for any + * <code>w</code> consecutive digits in the resulting representation, at + * most one is non-zero. + * @param k The integer of which the Window NAF is computed. + * @return The Window NAF of the given width, such that the following holds: + * <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup> + * </code>, where the <code>k<sub>i</sub></code> denote the elements of the + * returned <code>byte[]</code>. + */ + public static byte[] GenerateWindowNaf(int width, BigInteger k) + { + if (width == 2) + { + return GenerateNaf(k); + } + + if (width < 2 || width > 8) + throw new ArgumentException("must be in the range [2, 8]", "width"); + + byte[] wnaf = new byte[k.BitLength + 1]; + + // 2^width and a mask and sign bit set accordingly + int pow2 = 1 << width; + int mask = pow2 - 1; + int sign = pow2 >> 1; + + bool carry = false; + int length = 0, pos = 0; + + while (pos <= k.BitLength) + { + if (k.TestBit(pos) == carry) + { + ++pos; + continue; + } + + k = k.ShiftRight(pos); + + int digit = k.IntValue & mask; + if (carry) + { + ++digit; + } + + carry = (digit & sign) != 0; + if (carry) + { + digit -= pow2; + } + + length += (length > 0) ? pos - 1 : pos; + wnaf[length++] = (byte)digit; + pos = width; + } + + // Reduce the WNAF array to its actual length + if (wnaf.Length > length) + { + wnaf = Trim(wnaf, length); + } + + return wnaf; + } + + public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo) + { + if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo)) + { + return (WNafPreCompInfo)preCompInfo; + } + + return new WNafPreCompInfo(); + } + + /** + * Determine window width to use for a scalar multiplication of the given size. + * + * @param bits the bit-length of the scalar to multiply by + * @return the window size to use + */ + public static int GetWindowSize(int bits) + { + return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS); + } + + /** + * Determine window width to use for a scalar multiplication of the given size. + * + * @param bits the bit-length of the scalar to multiply by + * @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width + * @return the window size to use + */ + public static int GetWindowSize(int bits, int[] windowSizeCutoffs) + { + int w = 0; + for (; w < windowSizeCutoffs.Length; ++w) + { + if (bits < windowSizeCutoffs[w]) + { + break; + } + } + return w + 2; + } + + public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated) + { + ECCurve c = p.Curve; + WNafPreCompInfo wnafPreCompInfo = GetWNafPreCompInfo(c.GetPreCompInfo(p)); + + ECPoint[] preComp = wnafPreCompInfo.PreComp; + if (preComp == null) + { + preComp = new ECPoint[]{ p }; + } + + int preCompLen = preComp.Length; + int reqPreCompLen = 1 << System.Math.Max(0, width - 2); + + if (preCompLen < reqPreCompLen) + { + ECPoint twiceP = wnafPreCompInfo.Twice; + if (twiceP == null) + { + twiceP = preComp[0].Twice().Normalize(); + wnafPreCompInfo.Twice = twiceP; + } + + preComp = ResizeTable(preComp, reqPreCompLen); + + /* + * TODO Okeya/Sakurai paper has precomputation trick and "Montgomery's Trick" to speed this up. + * Also, co-Z arithmetic could avoid the subsequent normalization too. + */ + for (int i = preCompLen; i < reqPreCompLen; i++) + { + /* + * Compute the new ECPoints for the precomputation array. The values 1, 3, 5, ..., + * 2^(width-1)-1 times p are computed + */ + preComp[i] = twiceP.Add(preComp[i - 1]); + } + + /* + * Having oft-used operands in affine form makes operations faster. + */ + c.NormalizeAll(preComp); + } + + wnafPreCompInfo.PreComp = preComp; + + if (includeNegated) + { + ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg; + + int pos; + if (preCompNeg == null) + { + pos = 0; + preCompNeg = new ECPoint[reqPreCompLen]; + } + else + { + pos = preCompNeg.Length; + if (pos < reqPreCompLen) + { + preCompNeg = ResizeTable(preCompNeg, reqPreCompLen); + } + } + + while (pos < reqPreCompLen) + { + preCompNeg[pos] = preComp[pos].Negate(); + ++pos; + } + + wnafPreCompInfo.PreCompNeg = preCompNeg; + } + + c.SetPreCompInfo(p, wnafPreCompInfo); + + return wnafPreCompInfo; + } + + private static byte[] Trim(byte[] a, int length) + { + byte[] result = new byte[length]; + Array.Copy(a, 0, result, 0, result.Length); + return result; + } + + private static int[] Trim(int[] a, int length) + { + int[] result = new int[length]; + Array.Copy(a, 0, result, 0, result.Length); + return result; + } + + private static ECPoint[] ResizeTable(ECPoint[] a, int length) + { + ECPoint[] result = new ECPoint[length]; + Array.Copy(a, 0, result, 0, a.Length); + return result; + } + } +} diff --git a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs index f1a605770..c2f78da93 100644 --- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs @@ -4,117 +4,120 @@ using Org.BouncyCastle.Math.EC.Abc; namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Class implementing the WTNAF (Window - * <code>τ</code>-adic Non-Adjacent Form) algorithm. - */ - internal class WTauNafMultiplier - : ECMultiplier - { - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by <code>k</code> using the reduced <code>τ</code>-adic NAF (RTNAF) - * method. - * @param p The F2mPoint to multiply. - * @param k The integer by which to multiply <code>k</code>. - * @return <code>p</code> multiplied by <code>k</code>. - */ - public ECPoint Multiply(ECPoint point, BigInteger k, PreCompInfo preCompInfo) - { - if (!(point is F2mPoint)) - throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); + /** + * Class implementing the WTNAF (Window + * <code>τ</code>-adic Non-Adjacent Form) algorithm. + */ + public class WTauNafMultiplier + : ECMultiplier + { + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by <code>k</code> using the reduced <code>τ</code>-adic NAF (RTNAF) + * method. + * @param p The F2mPoint to multiply. + * @param k The integer by which to multiply <code>k</code>. + * @return <code>p</code> multiplied by <code>k</code>. + */ + public virtual ECPoint Multiply(ECPoint point, BigInteger k) + { + if (!(point is F2mPoint)) + throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); - F2mPoint p = (F2mPoint)point; + F2mPoint p = (F2mPoint)point; - F2mCurve curve = (F2mCurve) p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - BigInteger[] s = curve.GetSi(); + F2mCurve curve = (F2mCurve) p.Curve; + int m = curve.M; + sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; + sbyte mu = curve.GetMu(); + BigInteger[] s = curve.GetSi(); - ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10); + ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10); - return MultiplyWTnaf(p, rho, preCompInfo, a, mu); - } + return MultiplyWTnaf(p, rho, curve.GetPreCompInfo(p), a, mu); + } - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> using - * the <code>τ</code>-adic NAF (TNAF) method. - * @param p The F2mPoint to multiply. - * @param lambda The element <code>λ</code> of - * <code><b>Z</b>[τ]</code> of which to compute the - * <code>[τ]</code>-adic NAF. - * @return <code>p</code> multiplied by <code>λ</code>. - */ - private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda, - PreCompInfo preCompInfo, sbyte a, sbyte mu) - { - ZTauElement[] alpha; - if (a == 0) - { - alpha = Tnaf.Alpha0; - } - else - { - // a == 1 - alpha = Tnaf.Alpha1; - } + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> using + * the <code>τ</code>-adic NAF (TNAF) method. + * @param p The F2mPoint to multiply. + * @param lambda The element <code>λ</code> of + * <code><b>Z</b>[τ]</code> of which to compute the + * <code>[τ]</code>-adic NAF. + * @return <code>p</code> multiplied by <code>λ</code>. + */ + private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda, + PreCompInfo preCompInfo, sbyte a, sbyte mu) + { + ZTauElement[] alpha; + if (a == 0) + { + alpha = Tnaf.Alpha0; + } + else + { + // a == 1 + alpha = Tnaf.Alpha1; + } - BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width); + BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width); - sbyte[]u = Tnaf.TauAdicWNaf(mu, lambda, Tnaf.Width, - BigInteger.ValueOf(Tnaf.Pow2Width), tw, alpha); + sbyte[]u = Tnaf.TauAdicWNaf(mu, lambda, Tnaf.Width, + BigInteger.ValueOf(Tnaf.Pow2Width), tw, alpha); - return MultiplyFromWTnaf(p, u, preCompInfo); - } - - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> - * using the window <code>τ</code>-adic NAF (TNAF) method, given the - * WTNAF of <code>λ</code>. - * @param p The F2mPoint to multiply. - * @param u The the WTNAF of <code>λ</code>.. - * @return <code>λ * p</code> - */ - private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, - PreCompInfo preCompInfo) - { - F2mCurve curve = (F2mCurve)p.Curve; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; + return MultiplyFromWTnaf(p, u, preCompInfo); + } + + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> + * using the window <code>τ</code>-adic NAF (TNAF) method, given the + * WTNAF of <code>λ</code>. + * @param p The F2mPoint to multiply. + * @param u The the WTNAF of <code>λ</code>.. + * @return <code>λ * p</code> + */ + private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, + PreCompInfo preCompInfo) + { + F2mCurve curve = (F2mCurve)p.Curve; + sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - F2mPoint[] pu; - if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo)) - { - pu = Tnaf.GetPreComp(p, a); - p.SetPreCompInfo(new WTauNafPreCompInfo(pu)); - } - else - { - pu = ((WTauNafPreCompInfo)preCompInfo).GetPreComp(); - } + F2mPoint[] pu; + if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo)) + { + pu = Tnaf.GetPreComp(p, a); - // q = infinity - F2mPoint q = (F2mPoint) p.Curve.Infinity; - for (int i = u.Length - 1; i >= 0; i--) - { - q = Tnaf.Tau(q); - if (u[i] != 0) - { - if (u[i] > 0) - { - q = q.AddSimple(pu[u[i]]); - } - else - { - // u[i] < 0 - q = q.SubtractSimple(pu[-u[i]]); - } - } - } + WTauNafPreCompInfo pre = new WTauNafPreCompInfo(); + pre.PreComp = pu; + curve.SetPreCompInfo(p, pre); + } + else + { + pu = ((WTauNafPreCompInfo)preCompInfo).PreComp; + } - return q; - } - } + // q = infinity + F2mPoint q = (F2mPoint) p.Curve.Infinity; + for (int i = u.Length - 1; i >= 0; i--) + { + q = Tnaf.Tau(q); + if (u[i] != 0) + { + if (u[i] > 0) + { + q = q.AddSimple(pu[u[i]]); + } + else + { + // u[i] < 0 + q = q.SubtractSimple(pu[-u[i]]); + } + } + } + + return q; + } + } } diff --git a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs index cede4a05d..3c18404c0 100644 --- a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs +++ b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs @@ -1,41 +1,24 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Class holding precomputation data for the WTNAF (Window - * <code>τ</code>-adic Non-Adjacent Form) algorithm. - */ - internal class WTauNafPreCompInfo - : PreCompInfo - { - /** - * Array holding the precomputed <code>F2mPoint</code>s used for the - * WTNAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() - * WTauNafMultiplier.multiply()}</code>. - */ - private readonly F2mPoint[] preComp; + /** + * Class holding precomputation data for the WTNAF (Window + * <code>τ</code>-adic Non-Adjacent Form) algorithm. + */ + public class WTauNafPreCompInfo + : PreCompInfo + { + /** + * Array holding the precomputed <code>F2mPoint</code>s used for the + * WTNAF multiplication in <code> + * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() + * WTauNafMultiplier.multiply()}</code>. + */ + protected F2mPoint[] m_preComp; - /** - * Constructor for <code>WTauNafPreCompInfo</code> - * @param preComp Array holding the precomputed <code>F2mPoint</code>s - * used for the WTNAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() - * WTauNafMultiplier.multiply()}</code>. - */ - internal WTauNafPreCompInfo(F2mPoint[] preComp) - { - this.preComp = preComp; - } - - /** - * @return the array holding the precomputed <code>F2mPoint</code>s - * used for the WTNAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() - * WTauNafMultiplier.multiply()}</code>. - */ - internal F2mPoint[] GetPreComp() - { - return preComp; - } - } + public virtual F2mPoint[] PreComp + { + get { return m_preComp; } + set { this.m_preComp = value; } + } + } } |