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; }
+ }
+ }
}
|
