diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 865b9073e..5491297d7 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -10,6 +10,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
private static readonly byte[] EMPTY_BYTES = new byte[0];
private static readonly int[] EMPTY_INTS = new int[0];
+ private static readonly ECPoint[] EMPTY_POINTS = new ECPoint[0];
public static int[] GenerateCompactNaf(BigInteger k)
{
@@ -368,46 +369,100 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
{
ECCurve c = p.Curve;
WNafPreCompInfo wnafPreCompInfo = GetWNafPreCompInfo(c.GetPreCompInfo(p, PRECOMP_NAME));
-
+
+ int iniPreCompLen = 0, reqPreCompLen = 1 << System.Math.Max(0, width - 2);
+
ECPoint[] preComp = wnafPreCompInfo.PreComp;
if (preComp == null)
{
- preComp = new ECPoint[]{ p };
+ preComp = EMPTY_POINTS;
+ }
+ else
+ {
+ iniPreCompLen = preComp.Length;
}
- int preCompLen = preComp.Length;
- int reqPreCompLen = 1 << System.Math.Max(0, width - 2);
-
- if (preCompLen < reqPreCompLen)
+ if (iniPreCompLen < reqPreCompLen)
{
preComp = ResizeTable(preComp, reqPreCompLen);
- if (reqPreCompLen == 2)
+
+ if (reqPreCompLen == 1)
{
- preComp[1] = preComp[0].ThreeTimes();
+ preComp[0] = p.Normalize();
}
else
{
- ECPoint twiceP = wnafPreCompInfo.Twice;
- if (twiceP == null)
+ int curPreCompLen = iniPreCompLen;
+ if (curPreCompLen == 0)
{
- twiceP = preComp[0].Twice();
- wnafPreCompInfo.Twice = twiceP;
+ preComp[0] = p;
+ curPreCompLen = 1;
}
- for (int i = preCompLen; i < reqPreCompLen; i++)
+ ECFieldElement iso = null;
+
+ if (reqPreCompLen == 2)
{
- /*
- * 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]);
+ preComp[1] = p.ThreeTimes();
+ }
+ else
+ {
+ ECPoint twiceP = wnafPreCompInfo.Twice, last = preComp[curPreCompLen - 1];
+ if (twiceP == null)
+ {
+ twiceP = preComp[0].Twice();
+ wnafPreCompInfo.Twice = twiceP;
+
+ /*
+ * For Fp curves with Jacobian projective coordinates, use a (quasi-)isomorphism
+ * where 'twiceP' is "affine", so that the subsequent additions are cheaper. This
+ * also requires scaling the initial point's X, Y coordinates, and reversing the
+ * isomorphism as part of the subsequent normalization.
+ *
+ * NOTE: The correctness of this optimization depends on:
+ * 1) additions do not use the curve's A, B coefficients.
+ * 2) no special cases (i.e. Q +/- Q) when calculating 1P, 3P, 5P, ...
+ */
+ if (ECAlgorithms.IsFpCurve(c) && c.FieldSize >= 64)
+ {
+ switch (c.CoordinateSystem)
+ {
+ case ECCurve.COORD_JACOBIAN:
+ case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
+ case ECCurve.COORD_JACOBIAN_MODIFIED:
+ {
+ iso = twiceP.GetZCoord(0);
+ twiceP = c.CreatePoint(twiceP.XCoord.ToBigInteger(),
+ twiceP.YCoord.ToBigInteger());
+
+ ECFieldElement iso2 = iso.Square(), iso3 = iso2.Multiply(iso);
+ last = last.ScaleX(iso2).ScaleY(iso3);
+
+ if (iniPreCompLen == 0)
+ {
+ preComp[0] = last;
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ while (curPreCompLen < reqPreCompLen)
+ {
+ /*
+ * Compute the new ECPoints for the precomputation array. The values 1, 3,
+ * 5, ..., 2^(width-1)-1 times p are computed
+ */
+ preComp[curPreCompLen++] = last = last.Add(twiceP);
+ }
}
- }
- /*
- * Having oft-used operands in affine form makes operations faster.
- */
- c.NormalizeAll(preComp);
+ /*
+ * Having oft-used operands in affine form makes operations faster.
+ */
+ c.NormalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso);
+ }
}
wnafPreCompInfo.PreComp = preComp;
|
