Implement promotion for ECPoint precomputations

- a point is promoted after repeated use (e.g. in ECDSA verification)
- promoted points are eligible for extra precomp => faster algorithms

3 files changed, 128 insertions, 7 deletions

diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 69139df01..8b7184006 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -3,6 +3,7 @@ using System;
 using Org.BouncyCastle.Math.EC.Endo;
 using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Math.Field;
+using Org.BouncyCastle.Math.Raw;
 
 namespace Org.BouncyCastle.Math.EC
 {
@@ -265,15 +266,26 @@ namespace Org.BouncyCastle.Math.EC
         {
             bool negK = k.SignValue < 0, negL = l.SignValue < 0;
 
-            k = k.Abs();
-            l = l.Abs();
+            BigInteger kAbs = k.Abs(), lAbs = l.Abs();
 
-            int minWidthP = WNafUtilities.GetWindowSize(k.BitLength, 8);
-            int minWidthQ = WNafUtilities.GetWindowSize(l.BitLength, 8);
+            int minWidthP = WNafUtilities.GetWindowSize(kAbs.BitLength, 8);
+            int minWidthQ = WNafUtilities.GetWindowSize(lAbs.BitLength, 8);
 
             WNafPreCompInfo infoP = WNafUtilities.Precompute(P, minWidthP, true);
             WNafPreCompInfo infoQ = WNafUtilities.Precompute(Q, minWidthQ, true);
 
+            // When P, Q are 'promoted' (i.e. reused several times), switch to fixed-point algorithm
+            {
+                ECCurve c = P.Curve;
+                int combSize = FixedPointUtilities.GetCombSize(c);
+                if (!negK && !negL
+                    && k.BitLength <= combSize && l.BitLength <= combSize
+                    && infoP.IsPromoted && infoQ.IsPromoted)
+                {
+                    return ImplShamirsTrickFixedPoint(P, k, Q, l);
+                }
+            }
+
             int widthP = System.Math.Min(8, infoP.Width);
             int widthQ = System.Math.Min(8, infoQ.Width);
 
@@ -282,8 +294,8 @@ namespace Org.BouncyCastle.Math.EC
             ECPoint[] preCompNegP = negK ? infoP.PreComp : infoP.PreCompNeg;
             ECPoint[] preCompNegQ = negL ? infoQ.PreComp : infoQ.PreCompNeg;
 
-            byte[] wnafP = WNafUtilities.GenerateWindowNaf(widthP, k);
-            byte[] wnafQ = WNafUtilities.GenerateWindowNaf(widthQ, l);
+            byte[] wnafP = WNafUtilities.GenerateWindowNaf(widthP, kAbs);
+            byte[] wnafQ = WNafUtilities.GenerateWindowNaf(widthQ, lAbs);
 
             return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
         }
@@ -511,5 +523,78 @@ namespace Org.BouncyCastle.Math.EC
 
             return R;
         }
+
+        private static ECPoint ImplShamirsTrickFixedPoint(ECPoint p, BigInteger k, ECPoint q, BigInteger l)
+        {
+            ECCurve c = p.Curve;
+            int combSize = FixedPointUtilities.GetCombSize(c);
+
+            if (k.BitLength > combSize || l.BitLength > combSize)
+            {
+                /*
+                 * TODO The comb works best when the scalars are less than the (possibly unknown) order.
+                 * Still, if we want to handle larger scalars, we could allow customization of the comb
+                 * size, or alternatively we could deal with the 'extra' bits either by running the comb
+                 * multiple times as necessary, or by using an alternative multiplier as prelude.
+                 */
+                throw new InvalidOperationException("fixed-point comb doesn't support scalars larger than the curve order");
+            }
+
+            FixedPointPreCompInfo infoP = FixedPointUtilities.Precompute(p);
+            FixedPointPreCompInfo infoQ = FixedPointUtilities.Precompute(q);
+
+            ECLookupTable lookupTableP = infoP.LookupTable;
+            ECLookupTable lookupTableQ = infoQ.LookupTable;
+
+            int widthP = infoP.Width;
+            int widthQ = infoQ.Width;
+
+            // TODO This shouldn't normally happen, but a better "solution" is desirable anyway
+            if (widthP != widthQ)
+            {
+                FixedPointCombMultiplier m = new FixedPointCombMultiplier();
+                ECPoint r1 = m.Multiply(p, k);
+                ECPoint r2 = m.Multiply(q, l);
+                return r1.Add(r2);
+            }
+
+            int width = widthP;
+
+            int d = (combSize + width - 1) / width;
+
+            ECPoint R = c.Infinity;
+
+            int fullComb = d * width;
+            uint[] K = Nat.FromBigInteger(fullComb, k);
+            uint[] L = Nat.FromBigInteger(fullComb, l);
+
+            int top = fullComb - 1; 
+            for (int i = 0; i < d; ++i)
+            {
+                uint secretIndexK = 0, secretIndexL = 0;
+
+                for (int j = top - i; j >= 0; j -= d)
+                {
+                    uint secretBitK = K[j >> 5] >> (j & 0x1F);
+                    secretIndexK ^= secretBitK >> 1;
+                    secretIndexK <<= 1;
+                    secretIndexK ^= secretBitK;
+
+                    uint secretBitL = L[j >> 5] >> (j & 0x1F);
+                    secretIndexL ^= secretBitL >> 1;
+                    secretIndexL <<= 1;
+                    secretIndexL ^= secretBitL;
+                }
+
+                ECPoint addP = lookupTableP.Lookup((int)secretIndexK);
+                ECPoint addQ = lookupTableQ.Lookup((int)secretIndexL);
+
+                ECPoint T = addP.Add(addQ);
+
+                R = R.TwicePlus(T);
+            }
+
+            return R.Add(infoP.Offset).Add(infoQ.Offset);
+        }
     }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
index fb3cb57cd..f979f33d9 100644
--- a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
+++ b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
@@ -5,8 +5,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     * algorithm.
     */
     public class WNafPreCompInfo
-        : PreCompInfo 
+        : PreCompInfo
     {
+        internal volatile int m_promotionCountdown = 4;
+
         protected int m_confWidth = -1;
 
         /**
@@ -29,6 +31,27 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
         protected int m_width = -1;
 
+        internal int DecrementPromotionCountdown()
+        {
+            int t = m_promotionCountdown;
+            if (t > 0)
+            {
+                m_promotionCountdown = --t;
+            }
+            return t;
+        }
+
+        internal int PromotionCountdown
+        {
+            get { return m_promotionCountdown; }
+            set { this.m_promotionCountdown = value; }
+        }
+
+        public virtual bool IsPromoted
+        {
+            get { return m_promotionCountdown <= 0; }
+        }
+
         public virtual int ConfWidth
         {
             get { return m_confWidth; }
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 65d876449..42265b2d6 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -425,11 +425,13 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
                 if (null != existingWNaf && existingWNaf.ConfWidth == m_confWidth)
                 {
+                    existingWNaf.PromotionCountdown = 0;
                     return existingWNaf;
                 }
 
                 WNafPreCompInfo result = new WNafPreCompInfo();
 
+                result.PromotionCountdown = 0;
                 result.ConfWidth = m_confWidth;
 
                 if (null != existingWNaf)
@@ -516,7 +518,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                 int reqPreCompLen = 1 << (width - 2);
 
                 if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated))
+                {
+                    existingWNaf.DecrementPromotionCountdown();
                     return existingWNaf;
+                }
 
                 WNafPreCompInfo result = new WNafPreCompInfo();
 
@@ -526,6 +531,9 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
                 if (null != existingWNaf)
                 {
+                    int promotionCountdown = existingWNaf.DecrementPromotionCountdown();
+                    result.PromotionCountdown = promotionCountdown;
+
                     int confWidth = existingWNaf.ConfWidth;
                     result.ConfWidth = confWidth;
 
@@ -700,7 +708,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                 int reqPreCompLen = m_fromWNaf.PreComp.Length;
 
                 if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated))
+                {
+                    existingWNaf.DecrementPromotionCountdown();
                     return existingWNaf;
+                }
 
                 /*
                  * TODO Ideally this method would support incremental calculation, but given the
@@ -708,6 +719,8 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                  */
                 WNafPreCompInfo result = new WNafPreCompInfo();
 
+                result.PromotionCountdown = m_fromWNaf.PromotionCountdown;
+
                 ECPoint twiceFrom = m_fromWNaf.Twice;
                 if (null != twiceFrom)
                 {