diff options
Diffstat (limited to 'crypto/src/math/ec')
| -rw-r--r-- | crypto/src/math/ec/ECAlgorithms.cs | 27 | ||||
| -rw-r--r-- | crypto/src/math/ec/endo/EndoPreCompInfo.cs | 26 | ||||
| -rw-r--r-- | crypto/src/math/ec/endo/EndoUtilities.cs | 47 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/GlvMultiplier.cs | 7 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafUtilities.cs | 91 |
5 files changed, 179 insertions, 19 deletions
diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs index 14658ac81..69139df01 100644 --- a/crypto/src/math/ec/ECAlgorithms.cs +++ b/crypto/src/math/ec/ECAlgorithms.cs @@ -288,7 +288,7 @@ namespace Org.BouncyCastle.Math.EC return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); } - internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l) + internal static ECPoint ImplShamirsTrickWNaf(ECEndomorphism endomorphism, ECPoint P, BigInteger k, BigInteger l) { bool negK = k.SignValue < 0, negL = l.SignValue < 0; @@ -297,9 +297,9 @@ namespace Org.BouncyCastle.Math.EC int minWidth = WNafUtilities.GetWindowSize(System.Math.Max(k.BitLength, l.BitLength), 8); - ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, minWidth, true, pointMapQ); - WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P); - WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q); + WNafPreCompInfo infoP = WNafUtilities.Precompute(P, minWidth, true); + ECPoint Q = EndoUtilities.MapPoint(endomorphism, P); + WNafPreCompInfo infoQ = WNafUtilities.PrecomputeWithPointMap(Q, endomorphism.PointMap, infoP, true); int widthP = System.Math.Min(8, infoP.Width); int widthQ = System.Math.Min(8, infoQ.Width); @@ -405,24 +405,24 @@ namespace Org.BouncyCastle.Math.EC abs[j++] = ab[1]; } - ECPointMap pointMap = glvEndomorphism.PointMap; if (glvEndomorphism.HasEfficientPointMap) { - return ECAlgorithms.ImplSumOfMultiplies(ps, pointMap, abs); + return ImplSumOfMultiplies(glvEndomorphism, ps, abs); } ECPoint[] pqs = new ECPoint[len << 1]; for (int i = 0, j = 0; i < len; ++i) { - ECPoint p = ps[i], q = pointMap.Map(p); + ECPoint p = ps[i]; + ECPoint q = EndoUtilities.MapPoint(glvEndomorphism, p); pqs[j++] = p; pqs[j++] = q; } - return ECAlgorithms.ImplSumOfMultiplies(pqs, abs); + return ImplSumOfMultiplies(pqs, abs); } - internal static ECPoint ImplSumOfMultiplies(ECPoint[] ps, ECPointMap pointMap, BigInteger[] ks) + internal static ECPoint ImplSumOfMultiplies(ECEndomorphism endomorphism, ECPoint[] ps, BigInteger[] ks) { int halfCount = ps.Length, fullCount = halfCount << 1; @@ -430,6 +430,8 @@ namespace Org.BouncyCastle.Math.EC WNafPreCompInfo[] infos = new WNafPreCompInfo[fullCount]; byte[][] wnafs = new byte[fullCount][]; + ECPointMap pointMap = endomorphism.PointMap; + for (int i = 0; i < halfCount; ++i) { int j0 = i << 1, j1 = j0 + 1; @@ -438,10 +440,11 @@ namespace Org.BouncyCastle.Math.EC BigInteger kj1 = ks[j1]; negs[j1] = kj1.SignValue < 0; kj1 = kj1.Abs(); 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); + ECPoint P = ps[i]; + WNafPreCompInfo infoP = WNafUtilities.Precompute(P, minWidth, true); + ECPoint Q = EndoUtilities.MapPoint(endomorphism, P); + WNafPreCompInfo infoQ = WNafUtilities.PrecomputeWithPointMap(Q, pointMap, infoP, true); int widthP = System.Math.Min(8, infoP.Width); int widthQ = System.Math.Min(8, infoQ.Width); diff --git a/crypto/src/math/ec/endo/EndoPreCompInfo.cs b/crypto/src/math/ec/endo/EndoPreCompInfo.cs new file mode 100644 index 000000000..cb926fc98 --- /dev/null +++ b/crypto/src/math/ec/endo/EndoPreCompInfo.cs @@ -0,0 +1,26 @@ +using System; + +using Org.BouncyCastle.Math.EC.Multiplier; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public class EndoPreCompInfo + : PreCompInfo + { + protected ECEndomorphism m_endomorphism; + + protected ECPoint m_mappedPoint; + + public virtual ECEndomorphism Endomorphism + { + get { return m_endomorphism; } + set { this.m_endomorphism = value; } + } + + public virtual ECPoint MappedPoint + { + get { return m_mappedPoint; } + set { this.m_mappedPoint = value; } + } + } +} diff --git a/crypto/src/math/ec/endo/EndoUtilities.cs b/crypto/src/math/ec/endo/EndoUtilities.cs index 16916e632..843103bca 100644 --- a/crypto/src/math/ec/endo/EndoUtilities.cs +++ b/crypto/src/math/ec/endo/EndoUtilities.cs @@ -1,11 +1,13 @@ using System; -using Org.BouncyCastle.Math; +using Org.BouncyCastle.Math.EC.Multiplier; namespace Org.BouncyCastle.Math.EC.Endo { public abstract class EndoUtilities { + public static readonly string PRECOMP_NAME = "bc_endo"; + public static BigInteger[] DecomposeScalar(ScalarSplitParameters p, BigInteger k) { int bits = p.Bits; @@ -18,6 +20,13 @@ namespace Org.BouncyCastle.Math.EC.Endo return new BigInteger[]{ a, b }; } + public static ECPoint MapPoint(ECEndomorphism endomorphism, ECPoint p) + { + EndoPreCompInfo precomp = (EndoPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, + new MapPointCallback(endomorphism, p)); + return precomp.MappedPoint; + } + private static BigInteger CalculateB(BigInteger k, BigInteger g, int t) { bool negative = (g.SignValue < 0); @@ -30,5 +39,41 @@ namespace Org.BouncyCastle.Math.EC.Endo } return negative ? b.Negate() : b; } + + private class MapPointCallback + : IPreCompCallback + { + private readonly ECEndomorphism m_endomorphism; + private readonly ECPoint m_point; + + internal MapPointCallback(ECEndomorphism endomorphism, ECPoint point) + { + this.m_endomorphism = endomorphism; + this.m_point = point; + } + + public PreCompInfo Precompute(PreCompInfo existing) + { + EndoPreCompInfo existingEndo = existing as EndoPreCompInfo; + + if (CheckExisting(existingEndo, m_endomorphism)) + return existingEndo; + + ECPoint mappedPoint = m_endomorphism.PointMap.Map(m_point); + + EndoPreCompInfo result = new EndoPreCompInfo(); + result.Endomorphism = m_endomorphism; + result.MappedPoint = mappedPoint; + return result; + } + + private bool CheckExisting(EndoPreCompInfo existingEndo, ECEndomorphism endomorphism) + { + return null != existingEndo + && existingEndo.Endomorphism == endomorphism + && existingEndo.MappedPoint != null; + } + + } } } diff --git a/crypto/src/math/ec/multiplier/GlvMultiplier.cs b/crypto/src/math/ec/multiplier/GlvMultiplier.cs index f19049474..9ef7d6e24 100644 --- a/crypto/src/math/ec/multiplier/GlvMultiplier.cs +++ b/crypto/src/math/ec/multiplier/GlvMultiplier.cs @@ -28,13 +28,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier BigInteger[] ab = glvEndomorphism.DecomposeScalar(k.Mod(n)); BigInteger a = ab[0], b = ab[1]; - ECPointMap pointMap = glvEndomorphism.PointMap; if (glvEndomorphism.HasEfficientPointMap) { - return ECAlgorithms.ImplShamirsTrickWNaf(p, a, pointMap, b); + return ECAlgorithms.ImplShamirsTrickWNaf(glvEndomorphism, p, a, b); } - return ECAlgorithms.ImplShamirsTrickWNaf(p, a, pointMap.Map(p), b); + ECPoint q = EndoUtilities.MapPoint(glvEndomorphism, p); + + return ECAlgorithms.ImplShamirsTrickWNaf(p, a, q, b); } } } diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs index 01599d777..65d876449 100644 --- a/crypto/src/math/ec/multiplier/WNafUtilities.cs +++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs @@ -361,6 +361,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier return System.Math.Max(2, System.Math.Min(maxWidth, w + 2)); } + [Obsolete] public static ECPoint MapPointWithPrecomp(ECPoint p, int minWidth, bool includeNegated, ECPointMap pointMap) { @@ -374,7 +375,15 @@ namespace Org.BouncyCastle.Math.EC.Multiplier public static WNafPreCompInfo Precompute(ECPoint p, int minWidth, bool includeNegated) { - return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, new WNafCallback(p, minWidth, includeNegated)); + return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, + new PrecomputeCallback(p, minWidth, includeNegated)); + } + + public static WNafPreCompInfo PrecomputeWithPointMap(ECPoint p, ECPointMap pointMap, WNafPreCompInfo fromWNaf, + bool includeNegated) + { + return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, + new PrecomputeWithPointMapCallback(p, pointMap, fromWNaf, includeNegated)); } private static byte[] Trim(byte[] a, int length) @@ -485,14 +494,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier } } - private class WNafCallback + private class PrecomputeCallback : IPreCompCallback { private readonly ECPoint m_p; private readonly int m_minWidth; private readonly bool m_includeNegated; - internal WNafCallback(ECPoint p, int minWidth, bool includeNegated) + internal PrecomputeCallback(ECPoint p, int minWidth, bool includeNegated) { this.m_p = p; this.m_minWidth = minWidth; @@ -665,5 +674,81 @@ namespace Org.BouncyCastle.Math.EC.Multiplier return null != table && table.Length >= reqLen; } } + + private class PrecomputeWithPointMapCallback + : IPreCompCallback + { + private readonly ECPoint m_point; + private readonly ECPointMap m_pointMap; + private readonly WNafPreCompInfo m_fromWNaf; + private readonly bool m_includeNegated; + + internal PrecomputeWithPointMapCallback(ECPoint point, ECPointMap pointMap, WNafPreCompInfo fromWNaf, + bool includeNegated) + { + this.m_point = point; + this.m_pointMap = pointMap; + this.m_fromWNaf = fromWNaf; + this.m_includeNegated = includeNegated; + } + + public PreCompInfo Precompute(PreCompInfo existing) + { + WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo; + + int width = m_fromWNaf.Width; + int reqPreCompLen = m_fromWNaf.PreComp.Length; + + if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated)) + return existingWNaf; + + /* + * TODO Ideally this method would support incremental calculation, but given the + * existing use-cases it would be of little-to-no benefit. + */ + WNafPreCompInfo result = new WNafPreCompInfo(); + + ECPoint twiceFrom = m_fromWNaf.Twice; + if (null != twiceFrom) + { + ECPoint twice = m_pointMap.Map(twiceFrom); + result.Twice = twice; + } + + ECPoint[] preCompFrom = m_fromWNaf.PreComp; + ECPoint[] preComp = new ECPoint[preCompFrom.Length]; + for (int i = 0; i < preCompFrom.Length; ++i) + { + preComp[i] = m_pointMap.Map(preCompFrom[i]); + } + result.PreComp = preComp; + result.Width = width; + + if (m_includeNegated) + { + ECPoint[] preCompNeg = new ECPoint[preComp.Length]; + for (int i = 0; i < preCompNeg.Length; ++i) + { + preCompNeg[i] = preComp[i].Negate(); + } + result.PreCompNeg = preCompNeg; + } + + return result; + } + + private bool CheckExisting(WNafPreCompInfo existingWNaf, int width, int reqPreCompLen, bool includeNegated) + { + return null != existingWNaf + && existingWNaf.Width >= width + && CheckTable(existingWNaf.PreComp, reqPreCompLen) + && (!includeNegated || CheckTable(existingWNaf.PreCompNeg, reqPreCompLen)); + } + + private bool CheckTable(ECPoint[] table, int reqLen) + { + return null != table && table.Length >= reqLen; + } + } } } |