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