diff options
Diffstat (limited to 'crypto/src/math/ec/multiplier/WNafUtilities.cs')
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafUtilities.cs | 101 |
1 files changed, 78 insertions, 23 deletions
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; |