Port GLV implementation from Java

10 files changed, 296 insertions, 9 deletions

diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 0b8836b6b..628680e24 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -168,25 +168,61 @@ namespace Org.BouncyCastle.Math.EC
             return R;
         }
 
-        internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPoint Q, BigInteger l)
+        internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k,
+            ECPoint Q, BigInteger l)
         {
+            bool negK = k.SignValue < 0, negL = l.SignValue < 0;
+
+            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)));
 
             WNafPreCompInfo infoP = WNafUtilities.Precompute(P, widthP, true);
             WNafPreCompInfo infoQ = WNafUtilities.Precompute(Q, widthQ, true);
 
-            ECPoint[] preCompP = infoP.PreComp;
-            ECPoint[] preCompQ = infoQ.PreComp;
-            ECPoint[] preCompNegP = infoP.PreCompNeg;
-            ECPoint[] preCompNegQ = infoQ.PreCompNeg;
+            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(widthP, k);
             byte[] wnafQ = WNafUtilities.GenerateWindowNaf(widthQ, l);
 
+            return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
+        }
+
+        internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l)
+        {
+            bool negK = k.SignValue < 0, negL = l.SignValue < 0;
+
+            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))));
+
+            ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMapQ);
+            WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P);
+            WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q);
+
+            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);
+
+            return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
+        }
+
+        private static ECPoint ImplShamirsTrickWNaf(ECPoint[] preCompP, ECPoint[] preCompNegP, byte[] wnafP,
+            ECPoint[] preCompQ, ECPoint[] preCompNegQ, byte[] wnafQ)
+        {
             int len = System.Math.Max(wnafP.Length, wnafQ.Length);
 
-            ECCurve curve = P.Curve;
+            ECCurve curve = preCompP[0].Curve;
             ECPoint infinity = curve.Infinity;
 
             ECPoint R = infinity;
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index a84863ce6..50ff88e82 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -2,6 +2,7 @@ using System;
 using System.Collections;
 
 using Org.BouncyCastle.Math.EC.Abc;
+using Org.BouncyCastle.Math.EC.Endo;
 using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Math.Field;
 using Org.BouncyCastle.Utilities;
@@ -30,12 +31,14 @@ namespace Org.BouncyCastle.Math.EC
         {
             protected ECCurve outer;
             protected int coord;
+            protected ECEndomorphism endomorphism;
             protected ECMultiplier multiplier;
 
-            internal Config(ECCurve outer, int coord, ECMultiplier multiplier)
+            internal Config(ECCurve outer, int coord, ECEndomorphism endomorphism, ECMultiplier multiplier)
             {
                 this.outer = outer;
                 this.coord = coord;
+                this.endomorphism = endomorphism;
                 this.multiplier = multiplier;
             }
 
@@ -45,6 +48,12 @@ namespace Org.BouncyCastle.Math.EC
                 return this;
             }
 
+            public Config SetEndomorphism(ECEndomorphism endomorphism)
+            {
+                this.endomorphism = endomorphism;
+                return this;
+            }
+
             public Config SetMultiplier(ECMultiplier multiplier)
             {
                 this.multiplier = multiplier;
@@ -65,6 +74,7 @@ namespace Org.BouncyCastle.Math.EC
                 }
 
                 c.m_coord = coord;
+                c.m_endomorphism = endomorphism;
                 c.m_multiplier = multiplier;
 
                 return c;
@@ -76,6 +86,7 @@ namespace Org.BouncyCastle.Math.EC
         protected BigInteger m_order, m_cofactor;
 
         protected int m_coord = COORD_AFFINE;
+        protected ECEndomorphism m_endomorphism = null;
         protected ECMultiplier m_multiplier = null;
 
         protected ECCurve(IFiniteField field)
@@ -88,7 +99,7 @@ namespace Org.BouncyCastle.Math.EC
 
         public virtual Config Configure()
         {
-            return new Config(this, this.m_coord, this.m_multiplier);
+            return new Config(this, this.m_coord, this.m_endomorphism, this.m_multiplier);
         }
 
         public virtual ECPoint CreatePoint(BigInteger x, BigInteger y)
@@ -110,6 +121,12 @@ namespace Org.BouncyCastle.Math.EC
 
         protected virtual ECMultiplier CreateDefaultMultiplier()
         {
+            GlvEndomorphism glvEndomorphism = m_endomorphism as GlvEndomorphism;
+            if (glvEndomorphism != null)
+            {
+                return new GlvMultiplier(this, glvEndomorphism);
+            }
+
             return new WNafL2RMultiplier();
         }
 
@@ -296,6 +313,11 @@ namespace Org.BouncyCastle.Math.EC
 
         protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1);
 
+        public virtual ECEndomorphism GetEndomorphism()
+        {
+            return m_endomorphism;
+        }
+
         /**
          * Sets the default <code>ECMultiplier</code>, unless already set. 
          */
diff --git a/crypto/src/math/ec/ECPointMap.cs b/crypto/src/math/ec/ECPointMap.cs
new file mode 100644
index 000000000..e78c80065
--- /dev/null
+++ b/crypto/src/math/ec/ECPointMap.cs
@@ -0,0 +1,9 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC
+{
+    public interface ECPointMap
+    {
+        ECPoint Map(ECPoint p);
+    }
+}
diff --git a/crypto/src/math/ec/ScaleXPointMap.cs b/crypto/src/math/ec/ScaleXPointMap.cs
new file mode 100644
index 000000000..f8a363b24
--- /dev/null
+++ b/crypto/src/math/ec/ScaleXPointMap.cs
@@ -0,0 +1,20 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC
+{
+    public class ScaleXPointMap
+        : ECPointMap
+    {
+        protected readonly ECFieldElement scale;
+
+        public ScaleXPointMap(ECFieldElement scale)
+        {
+            this.scale = scale;
+        }
+
+        public virtual ECPoint Map(ECPoint p)
+        {
+            return p.ScaleX(scale);
+        }
+    }
+}
diff --git a/crypto/src/math/ec/ScaleYPointMap.cs b/crypto/src/math/ec/ScaleYPointMap.cs
new file mode 100644
index 000000000..1c4795b70
--- /dev/null
+++ b/crypto/src/math/ec/ScaleYPointMap.cs
@@ -0,0 +1,20 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC
+{
+    public class ScaleYPointMap
+        : ECPointMap
+    {
+        protected readonly ECFieldElement scale;
+
+        public ScaleYPointMap(ECFieldElement scale)
+        {
+            this.scale = scale;
+        }
+
+        public virtual ECPoint Map(ECPoint p)
+        {
+            return p.ScaleY(scale);
+        }
+    }
+}
diff --git a/crypto/src/math/ec/endo/ECEndomorphism.cs b/crypto/src/math/ec/endo/ECEndomorphism.cs
new file mode 100644
index 000000000..dfb321368
--- /dev/null
+++ b/crypto/src/math/ec/endo/ECEndomorphism.cs
@@ -0,0 +1,11 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+    public interface ECEndomorphism
+    {
+        ECPointMap PointMap { get; }
+
+        bool HasEfficientPointMap { get; }
+    }
+}
diff --git a/crypto/src/math/ec/endo/GlvEndomorphism.cs b/crypto/src/math/ec/endo/GlvEndomorphism.cs
new file mode 100644
index 000000000..f65bdd613
--- /dev/null
+++ b/crypto/src/math/ec/endo/GlvEndomorphism.cs
@@ -0,0 +1,10 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+    public interface GlvEndomorphism
+        :   ECEndomorphism
+    {
+        BigInteger[] DecomposeScalar(BigInteger k);
+    }
+}
diff --git a/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs
new file mode 100644
index 000000000..d234d88bf
--- /dev/null
+++ b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs
@@ -0,0 +1,55 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+    public class GlvTypeBEndomorphism
+        :   GlvEndomorphism
+    {
+        protected readonly ECCurve m_curve;
+        protected readonly GlvTypeBParameters m_parameters;
+        protected readonly ECPointMap m_pointMap;
+
+        public GlvTypeBEndomorphism(ECCurve curve, GlvTypeBParameters parameters)
+        {
+            this.m_curve = curve;
+            this.m_parameters = parameters;
+            this.m_pointMap = new ScaleXPointMap(curve.FromBigInteger(parameters.Beta));
+        }
+
+        public virtual BigInteger[] DecomposeScalar(BigInteger k)
+        {
+            int bits = m_parameters.Bits;
+            BigInteger b1 = CalculateB(k, m_parameters.G1, bits);
+            BigInteger b2 = CalculateB(k, m_parameters.G2, bits);
+
+            BigInteger[] v1 = m_parameters.V1, v2 = m_parameters.V2;
+            BigInteger a = k.Subtract((b1.Multiply(v1[0])).Add(b2.Multiply(v2[0])));
+            BigInteger b = (b1.Multiply(v1[1])).Add(b2.Multiply(v2[1])).Negate();
+
+            return new BigInteger[]{ a, b };
+        }
+
+        public virtual ECPointMap PointMap
+        {
+            get { return m_pointMap; }
+        }
+
+        public virtual bool HasEfficientPointMap
+        {
+            get { return true; }
+        }
+
+        protected virtual BigInteger CalculateB(BigInteger k, BigInteger g, int t)
+        {
+            bool negative = (g.SignValue < 0);
+            BigInteger b = k.Multiply(g.Abs());
+            bool extra = b.TestBit(t - 1);
+            b = b.ShiftRight(t);
+            if (extra)
+            {
+                b = b.Add(BigInteger.One);
+            }
+            return negative ? b.Negate() : b;
+        }
+    }
+}
diff --git a/crypto/src/math/ec/endo/GlvTypeBParameters.cs b/crypto/src/math/ec/endo/GlvTypeBParameters.cs
new file mode 100644
index 000000000..f93dfaf2b
--- /dev/null
+++ b/crypto/src/math/ec/endo/GlvTypeBParameters.cs
@@ -0,0 +1,60 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+    public class GlvTypeBParameters
+    {
+        protected readonly BigInteger m_beta;
+        protected readonly BigInteger m_lambda;
+        protected readonly BigInteger[] m_v1, m_v2;
+        protected readonly BigInteger m_g1, m_g2;
+        protected readonly int m_bits;
+
+        public GlvTypeBParameters(BigInteger beta, BigInteger lambda, BigInteger[] v1, BigInteger[] v2,
+            BigInteger g1, BigInteger g2, int bits)
+        {
+            this.m_beta = beta;
+            this.m_lambda = lambda;
+            this.m_v1 = v1;
+            this.m_v2 = v2;
+            this.m_g1 = g1;
+            this.m_g2 = g2;
+            this.m_bits = bits;
+        }
+
+        public virtual BigInteger Beta
+        {
+            get { return m_beta; }
+        }
+
+        public virtual BigInteger Lambda
+        {
+            get { return m_lambda; }
+        }
+
+        public virtual BigInteger[] V1
+        {
+            get { return m_v1; }
+        }
+
+        public virtual BigInteger[] V2
+        {
+            get { return m_v2; }
+        }
+
+        public virtual BigInteger G1
+        {
+            get { return m_g1; }
+        }
+
+        public virtual BigInteger G2
+        {
+            get { return m_g2; }
+        }
+
+        public virtual int Bits
+        {
+            get { return m_bits; }
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 179d6d6eb..98e4f545f 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -268,6 +268,11 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             return wnaf;
         }
 
+        public static WNafPreCompInfo GetWNafPreCompInfo(ECPoint p)
+        {
+            return GetWNafPreCompInfo(p.Curve.GetPreCompInfo(p, PRECOMP_NAME));
+        }
+
         public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo)
         {
             if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo))
@@ -309,6 +314,45 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             return w + 2;
         }
 
+        public static ECPoint MapPointWithPrecomp(ECPoint p, int width, bool includeNegated,
+            ECPointMap pointMap)
+        {
+            ECCurve c = p.Curve;
+            WNafPreCompInfo wnafPreCompP = Precompute(p, width, includeNegated);
+
+            ECPoint q = pointMap.Map(p);
+            WNafPreCompInfo wnafPreCompQ = GetWNafPreCompInfo(c.GetPreCompInfo(q, PRECOMP_NAME));
+
+            ECPoint twiceP = wnafPreCompP.Twice;
+            if (twiceP != null)
+            {
+                ECPoint twiceQ = pointMap.Map(twiceP);
+                wnafPreCompQ.Twice = twiceQ;
+            }
+
+            ECPoint[] preCompP = wnafPreCompP.PreComp;
+            ECPoint[] preCompQ = new ECPoint[preCompP.Length];
+            for (int i = 0; i < preCompP.Length; ++i)
+            {
+                preCompQ[i] = pointMap.Map(preCompP[i]);
+            }
+            wnafPreCompQ.PreComp = preCompQ;
+
+            if (includeNegated)
+            {
+                ECPoint[] preCompNegQ = new ECPoint[preCompQ.Length];
+                for (int i = 0; i < preCompNegQ.Length; ++i)
+                {
+                    preCompNegQ[i] = preCompQ[i].Negate();
+                }
+                wnafPreCompQ.PreCompNeg = preCompNegQ;
+            }
+
+            c.SetPreCompInfo(q, PRECOMP_NAME, wnafPreCompQ);
+
+            return q;
+        }
+
         public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated)
         {
             ECCurve c = p.Curve;
@@ -335,7 +379,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                     ECPoint twiceP = wnafPreCompInfo.Twice;
                     if (twiceP == null)
                     {
-                        twiceP = preComp[0].Twice().Normalize();
+                        twiceP = preComp[0].Twice();
                         wnafPreCompInfo.Twice = twiceP;
                     }