Port of WNaf precomp optimization from Java

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;