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)
{
|
