EC wNAF-related updates from bc-java

- better control of window size limits
- callers take advantage of available larger precomps
- provide ConfigureBasepoint to mark points for larger precomp
- mark built-in curve basepoints for larger default wNAF width

4 files changed, 172 insertions, 59 deletions

diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index b05c0201a..14658ac81 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -268,11 +268,14 @@ namespace Org.BouncyCastle.Math.EC
             k = k.Abs();
             l = l.Abs();
 
-            int widthP = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(k.BitLength)));
-            int widthQ = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(l.BitLength)));
+            int minWidthP = WNafUtilities.GetWindowSize(k.BitLength, 8);
+            int minWidthQ = WNafUtilities.GetWindowSize(l.BitLength, 8);
 
-            WNafPreCompInfo infoP = WNafUtilities.Precompute(P, widthP, true);
-            WNafPreCompInfo infoQ = WNafUtilities.Precompute(Q, widthQ, true);
+            WNafPreCompInfo infoP = WNafUtilities.Precompute(P, minWidthP, true);
+            WNafPreCompInfo infoQ = WNafUtilities.Precompute(Q, minWidthQ, true);
+
+            int widthP = System.Math.Min(8, infoP.Width);
+            int widthQ = System.Math.Min(8, infoQ.Width);
 
             ECPoint[] preCompP = negK ? infoP.PreCompNeg : infoP.PreComp;
             ECPoint[] preCompQ = negL ? infoQ.PreCompNeg : infoQ.PreComp;
@@ -292,19 +295,22 @@ namespace Org.BouncyCastle.Math.EC
             k = k.Abs();
             l = l.Abs();
 
-            int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(System.Math.Max(k.BitLength, l.BitLength))));
+            int minWidth = WNafUtilities.GetWindowSize(System.Math.Max(k.BitLength, l.BitLength), 8);
 
-            ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMapQ);
+            ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, minWidth, true, pointMapQ); 
             WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P);
             WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q);
 
+            int widthP = System.Math.Min(8, infoP.Width);
+            int widthQ = System.Math.Min(8, infoQ.Width);
+
             ECPoint[] preCompP = negK ? infoP.PreCompNeg : infoP.PreComp;
             ECPoint[] preCompQ = negL ? infoQ.PreCompNeg : infoQ.PreComp;
             ECPoint[] preCompNegP = negK ? infoP.PreComp : infoP.PreCompNeg;
             ECPoint[] preCompNegQ = negL ? infoQ.PreComp : infoQ.PreCompNeg;
 
-            byte[] wnafP = WNafUtilities.GenerateWindowNaf(width, k);
-            byte[] wnafQ = WNafUtilities.GenerateWindowNaf(width, l);
+            byte[] wnafP = WNafUtilities.GenerateWindowNaf(widthP, k);
+            byte[] wnafQ = WNafUtilities.GenerateWindowNaf(widthQ, l);
 
             return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
         }
@@ -373,8 +379,12 @@ namespace Org.BouncyCastle.Math.EC
             {
                 BigInteger ki = ks[i]; negs[i] = ki.SignValue < 0; ki = ki.Abs();
 
-                int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(ki.BitLength)));
-                infos[i] = WNafUtilities.Precompute(ps[i], width, true);
+                int minWidth = WNafUtilities.GetWindowSize(ki.BitLength, 8);
+                WNafPreCompInfo info = WNafUtilities.Precompute(ps[i], minWidth, true);
+
+                int width = System.Math.Min(8, info.Width);
+
+                infos[i] = info; 
                 wnafs[i] = WNafUtilities.GenerateWindowNaf(width, ki);
             }
 
@@ -427,13 +437,19 @@ namespace Org.BouncyCastle.Math.EC
                 BigInteger kj0 = ks[j0]; negs[j0] = kj0.SignValue < 0; kj0 = kj0.Abs();
                 BigInteger kj1 = ks[j1]; negs[j1] = kj1.SignValue < 0; kj1 = kj1.Abs();
 
-                int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(System.Math.Max(kj0.BitLength, kj1.BitLength))));
+                int minWidth = WNafUtilities.GetWindowSize(System.Math.Max(kj0.BitLength, kj1.BitLength), 8);
+                ECPoint P = ps[i], Q = WNafUtilities.MapPointWithPrecomp(P, minWidth, true, pointMap);
+
+                WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P);
+                WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q);
+
+                int widthP = System.Math.Min(8, infoP.Width);
+                int widthQ = System.Math.Min(8, infoQ.Width);
 
-                ECPoint P = ps[i], Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMap);
-                infos[j0] = WNafUtilities.GetWNafPreCompInfo(P);
-                infos[j1] = WNafUtilities.GetWNafPreCompInfo(Q);
-                wnafs[j0] = WNafUtilities.GenerateWindowNaf(width, kj0);
-                wnafs[j1] = WNafUtilities.GenerateWindowNaf(width, kj1);
+                infos[j0] = infoP;
+                infos[j1] = infoQ;
+                wnafs[j0] = WNafUtilities.GenerateWindowNaf(widthP, kj0);
+                wnafs[j1] = WNafUtilities.GenerateWindowNaf(widthQ, kj1);
             }
 
             return ImplSumOfMultiplies(negs, infos, wnafs);
diff --git a/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs
index f671f6a5c..833bbb5ea 100644
--- a/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs
@@ -1,5 +1,7 @@
 using System;
 
+using Org.BouncyCastle.Utilities;
+
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
     /**
@@ -18,12 +20,12 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
          */
         protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
         {
-            // Clamp the window width in the range [2, 16]
-            int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength)));
+            int minWidth = WNafUtilities.GetWindowSize(k.BitLength);
 
-            WNafPreCompInfo wnafPreCompInfo = WNafUtilities.Precompute(p, width, true);
-            ECPoint[] preComp = wnafPreCompInfo.PreComp;
-            ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg;
+            WNafPreCompInfo info = WNafUtilities.Precompute(p, minWidth, true);
+            ECPoint[] preComp = info.PreComp;
+            ECPoint[] preCompNeg = info.PreCompNeg;
+            int width = info.Width;
 
             int[] wnaf = WNafUtilities.GenerateCompactWindowNaf(width, k);
 
@@ -46,7 +48,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                 // Optimization can only be used for values in the lower half of the table
                 if ((n << 2) < (1 << width))
                 {
-                    int highest = LongArray.BitLengths[n];
+                    int highest = 32 - Integers.NumberOfLeadingZeros(n);
 
                     // TODO Get addition/doubling cost ratio from curve and compare to 'scale' to see if worth substituting?
                     int scale = width - highest;
@@ -83,16 +85,5 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
             return R;
         }
-
-        /**
-         * 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 7e0a73154..fb3cb57cd 100644
--- a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
+++ b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
@@ -7,6 +7,8 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     public class WNafPreCompInfo
         : PreCompInfo 
     {
+        protected int m_confWidth = -1;
+
         /**
          * Array holding the precomputed <code>ECPoint</code>s used for a Window
          * NAF multiplication.
@@ -25,6 +27,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
          */
         protected ECPoint m_twice = null;
 
+        protected int m_width = -1;
+
+        public virtual int ConfWidth
+        {
+            get { return m_confWidth; }
+            set { this.m_confWidth = value; }
+        }
+
         public virtual ECPoint[] PreComp
         {
             get { return m_preComp; }
@@ -42,5 +52,11 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             get { return m_twice; }
             set { this.m_twice = value; }
         }
+
+        public virtual int Width
+        {
+            get { return m_width; }
+            set { this.m_width = value; }
+        }
     }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 24646deb2..01599d777 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -9,9 +9,23 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
         public static readonly string PRECOMP_NAME = "bc_wnaf";
 
         private static readonly int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 };
+        private static readonly int MAX_WIDTH = 16;
 
         private static readonly ECPoint[] EMPTY_POINTS = new ECPoint[0];
 
+        public static void ConfigureBasepoint(ECPoint p)
+        {
+            ECCurve c = p.Curve;
+            if (null == c)
+                return;
+
+            BigInteger n = c.Order;
+            int bits = (null == n) ? c.FieldSize + 1 : n.BitLength;
+            int confWidth = System.Math.Min(MAX_WIDTH, GetWindowSize(bits) + 3);
+
+            c.Precompute(p, PRECOMP_NAME, new ConfigureBasepointCallback(c, confWidth));
+        }
+
         public static int[] GenerateCompactNaf(BigInteger k)
         {
             if ((k.BitLength >> 16) != 0)
@@ -298,7 +312,19 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
          */
         public static int GetWindowSize(int bits)
         {
-            return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS);
+            return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS, MAX_WIDTH);
+        }
+
+        /**
+         * 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 maxWidth the maximum window width to return 
+         * @return the window size to use
+         */
+        public static int GetWindowSize(int bits, int maxWidth)
+        {
+            return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS, maxWidth);
         }
 
         /**
@@ -310,6 +336,19 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
          */
         public static int GetWindowSize(int bits, int[] windowSizeCutoffs)
         {
+            return GetWindowSize(bits, windowSizeCutoffs, MAX_WIDTH);
+        }
+
+        /**
+         * 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
+         * @param maxWidth the maximum window width to return 
+         * @return the window size to use
+         */
+        public static int GetWindowSize(int bits, int[] windowSizeCutoffs, int maxWidth)
+        {
             int w = 0;
             for (; w < windowSizeCutoffs.Length; ++w)
             {
@@ -318,23 +357,24 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                     break;
                 }
             }
-            return w + 2;
+
+            return System.Math.Max(2, System.Math.Min(maxWidth, w + 2));
         }
 
-        public static ECPoint MapPointWithPrecomp(ECPoint p, int width, bool includeNegated,
+        public static ECPoint MapPointWithPrecomp(ECPoint p, int minWidth, bool includeNegated,
             ECPointMap pointMap)
         {
             ECCurve c = p.Curve;
-            WNafPreCompInfo wnafPreCompP = Precompute(p, width, includeNegated);
+            WNafPreCompInfo infoP = Precompute(p, minWidth, includeNegated);
 
             ECPoint q = pointMap.Map(p);
-            c.Precompute(q, PRECOMP_NAME, new MapPointCallback(wnafPreCompP, includeNegated, pointMap));
+            c.Precompute(q, PRECOMP_NAME, new MapPointCallback(infoP, includeNegated, pointMap));
             return q;
         }
 
-        public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated)
+        public static WNafPreCompInfo Precompute(ECPoint p, int minWidth, bool includeNegated)
         {
-            return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, new WNafCallback(p, width, includeNegated));
+            return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, new WNafCallback(p, minWidth, includeNegated));
         }
 
         private static byte[] Trim(byte[] a, int length)
@@ -358,16 +398,53 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             return result;
         }
 
+        private class ConfigureBasepointCallback
+            : IPreCompCallback
+        {
+            private readonly ECCurve m_curve;
+            private readonly int m_confWidth;
+
+            internal ConfigureBasepointCallback(ECCurve curve, int confWidth)
+            {
+                this.m_curve = curve;
+                this.m_confWidth = confWidth;
+            }
+
+            public PreCompInfo Precompute(PreCompInfo existing)
+            {
+                WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo;
+
+                if (null != existingWNaf && existingWNaf.ConfWidth == m_confWidth)
+                {
+                    return existingWNaf;
+                }
+
+                WNafPreCompInfo result = new WNafPreCompInfo();
+
+                result.ConfWidth = m_confWidth;
+
+                if (null != existingWNaf)
+                {
+                    result.PreComp = existingWNaf.PreComp;
+                    result.PreCompNeg = existingWNaf.PreCompNeg;
+                    result.Twice = existingWNaf.Twice;
+                    result.Width = existingWNaf.Width;
+                }
+
+                return result;
+            }
+        }
+
         private class MapPointCallback
             : IPreCompCallback
         {
-            private readonly WNafPreCompInfo m_wnafPreCompP;
+            private readonly WNafPreCompInfo m_infoP;
             private readonly bool m_includeNegated;
             private readonly ECPointMap m_pointMap;
 
-            internal MapPointCallback(WNafPreCompInfo wnafPreCompP, bool includeNegated, ECPointMap pointMap)
+            internal MapPointCallback(WNafPreCompInfo infoP, bool includeNegated, ECPointMap pointMap)
             {
-                this.m_wnafPreCompP = wnafPreCompP;
+                this.m_infoP = infoP;
                 this.m_includeNegated = includeNegated;
                 this.m_pointMap = pointMap;
             }
@@ -376,20 +453,23 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             {
                 WNafPreCompInfo result = new WNafPreCompInfo();
 
-                ECPoint twiceP = m_wnafPreCompP.Twice;
-                if (twiceP != null)
+                result.ConfWidth = m_infoP.ConfWidth;
+
+                ECPoint twiceP = m_infoP.Twice;
+                if (null != twiceP)
                 {
                     ECPoint twiceQ = m_pointMap.Map(twiceP);
                     result.Twice = twiceQ;
                 }
 
-                ECPoint[] preCompP = m_wnafPreCompP.PreComp;
+                ECPoint[] preCompP = m_infoP.PreComp;
                 ECPoint[] preCompQ = new ECPoint[preCompP.Length];
                 for (int i = 0; i < preCompP.Length; ++i)
                 {
                     preCompQ[i] = m_pointMap.Map(preCompP[i]);
                 }
                 result.PreComp = preCompQ;
+                result.Width = m_infoP.Width;
 
                 if (m_includeNegated)
                 {
@@ -409,13 +489,13 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             : IPreCompCallback
         {
             private readonly ECPoint m_p;
-            private readonly int m_width;
+            private readonly int m_minWidth;
             private readonly bool m_includeNegated;
 
-            internal WNafCallback(ECPoint p, int width, bool includeNegated)
+            internal WNafCallback(ECPoint p, int minWidth, bool includeNegated)
             {
                 this.m_p = p;
-                this.m_width = width;
+                this.m_minWidth = minWidth;
                 this.m_includeNegated = includeNegated;
             }
 
@@ -423,24 +503,33 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             {
                 WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo;
 
-                int reqPreCompLen = 1 << System.Math.Max(0, m_width - 2);
+                int width = System.Math.Max(2, System.Math.Min(MAX_WIDTH, m_minWidth));
+                int reqPreCompLen = 1 << (width - 2);
 
-                if (CheckExisting(existingWNaf, reqPreCompLen, m_includeNegated))
+                if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated))
                     return existingWNaf;
 
+                WNafPreCompInfo result = new WNafPreCompInfo();
+
                 ECCurve c = m_p.Curve;
                 ECPoint[] preComp = null, preCompNeg = null;
                 ECPoint twiceP = null;
 
-                if (existingWNaf != null)
+                if (null != existingWNaf)
                 {
+                    int confWidth = existingWNaf.ConfWidth;
+                    result.ConfWidth = confWidth;
+
                     preComp = existingWNaf.PreComp;
                     preCompNeg = existingWNaf.PreCompNeg;
                     twiceP = existingWNaf.Twice;
                 }
 
+                width = System.Math.Min(MAX_WIDTH, System.Math.Max(result.ConfWidth, width));
+                reqPreCompLen = 1 << (width - 2);
+
                 int iniPreCompLen = 0;
-                if (preComp == null)
+                if (null == preComp)
                 {
                     preComp = EMPTY_POINTS;
                 }
@@ -475,7 +564,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                         else
                         {
                             ECPoint isoTwiceP = twiceP, last = preComp[curPreCompLen - 1];
-                            if (isoTwiceP == null)
+                            if (null == isoTwiceP)
                             {
                                 isoTwiceP = preComp[0].Twice();
                                 twiceP = isoTwiceP;
@@ -535,7 +624,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                 if (m_includeNegated)
                 {
                     int pos;
-                    if (preCompNeg == null)
+                    if (null == preCompNeg)
                     {
                         pos = 0;
                         preCompNeg = new ECPoint[reqPreCompLen]; 
@@ -556,23 +645,24 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                     }
                 }
 
-                WNafPreCompInfo result = new WNafPreCompInfo();
                 result.PreComp = preComp;
                 result.PreCompNeg = preCompNeg;
                 result.Twice = twiceP;
+                result.Width = width;
                 return result;
             }
 
-            private bool CheckExisting(WNafPreCompInfo existingWNaf, int reqPreCompLen, bool includeNegated)
+            private bool CheckExisting(WNafPreCompInfo existingWNaf, int width, int reqPreCompLen, bool includeNegated)
             {
-                return existingWNaf != null
+                return null != existingWNaf
+                    && existingWNaf.Width >= System.Math.Max(existingWNaf.ConfWidth, width) 
                     && CheckTable(existingWNaf.PreComp, reqPreCompLen)
                     && (!includeNegated || CheckTable(existingWNaf.PreCompNeg, reqPreCompLen));
             }
 
             private bool CheckTable(ECPoint[] table, int reqLen)
             {
-                return table != null && table.Length >= reqLen;
+                return null != table && table.Length >= reqLen;
             }
         }
     }