EC updates from bc-java

- use half-trace when possible (odd m) for decompression/validation
- provide field-specific half-trace methods for custom curves
- clarify the logic of point-order testing for binary curves
- expand test cases for invalid points

24 files changed, 553 insertions, 34 deletions

diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index 997f0bbea..36f30d7c0 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -249,7 +249,7 @@ namespace Org.BouncyCastle.Math
             return (nBits + BitsPerByte - 1) / BitsPerByte;
         }
 
-        internal static BigInteger Arbitrary(int sizeInBits)
+        public static BigInteger Arbitrary(int sizeInBits)
         {
             return new BigInteger(sizeInBits, RandomSource);
         }
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index 993b69149..5b9b39c10 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -862,12 +862,29 @@ namespace Org.BouncyCastle.Math.EC
          */
         internal ECFieldElement SolveQuadraticEquation(ECFieldElement beta)
         {
+            AbstractF2mFieldElement betaF2m = (AbstractF2mFieldElement)beta;
+
+            bool fastTrace = betaF2m.HasFastTrace;
+            if (fastTrace && 0 != betaF2m.Trace())
+                return null;
+
+            int m = FieldSize;
+
+            // For odd m, use the half-trace 
+            if (0 != (m & 1))
+            {
+                ECFieldElement r = betaF2m.HalfTrace();
+                if (fastTrace || r.Square().Add(r).Add(beta).IsZero)
+                    return r;
+
+                return null;
+            }
+
             if (beta.IsZero)
                 return beta;
 
             ECFieldElement gamma, z, zeroElement = FromBigInteger(BigInteger.Zero);
 
-            int m = FieldSize;
             do
             {
                 ECFieldElement t = FromBigInteger(BigInteger.Arbitrary(m));
diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs
index 350e8c6d4..ef10dbf90 100644
--- a/crypto/src/math/ec/ECFieldElement.cs
+++ b/crypto/src/math/ec/ECFieldElement.cs
@@ -550,32 +550,63 @@ namespace Org.BouncyCastle.Math.EC
             if ((m & 1) == 0)
                 throw new InvalidOperationException("Half-trace only defined for odd m");
 
-            ECFieldElement fe = this;
-            ECFieldElement ht = fe;
-            for (int i = 2; i < m; i += 2)
+            //ECFieldElement ht = this;
+            //for (int i = 1; i < m; i += 2)
+            //{
+            //    ht = ht.SquarePow(2).Add(this);
+            //}
+
+            int n = (m + 1) >> 1;
+            int k = 31 - Integers.NumberOfLeadingZeros(n);
+            int nk = 1;
+
+            ECFieldElement ht = this;
+            while (k > 0)
             {
-                fe = fe.SquarePow(2);
-                ht = ht.Add(fe);
+                ht = ht.SquarePow(nk << 1).Add(ht);
+                nk = n >> --k;
+                if (0 != (nk & 1))
+                {
+                    ht = ht.SquarePow(2).Add(this);
+                }
             }
 
             return ht;
         }
 
+        public virtual bool HasFastTrace
+        {
+            get { return false; }
+        }
+
         public virtual int Trace()
         {
             int m = FieldSize;
-            ECFieldElement fe = this;
-            ECFieldElement tr = fe;
-            for (int i = 1; i < m; ++i)
+
+            //ECFieldElement tr = this;
+            //for (int i = 1; i < m; ++i)
+            //{
+            //    tr = tr.Square().Add(this);
+            //}
+
+            int k = 31 - Integers.NumberOfLeadingZeros(m);
+            int mk = 1;
+
+            ECFieldElement tr = this;
+            while (k > 0)
             {
-                fe = fe.Square();
-                tr = tr.Add(fe);
+                tr = tr.SquarePow(mk).Add(tr);
+                mk = m >> --k;
+                if (0 != (mk & 1))
+                {
+                    tr = tr.Square().Add(this);
+                }
             }
+
             if (tr.IsZero)
                 return 0;
             if (tr.IsOne)
                 return 1;
-
             throw new InvalidOperationException("Internal error in trace calculation");
         }
     }
diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs
index 2acc9f5c0..425424e32 100644
--- a/crypto/src/math/ec/ECPoint.cs
+++ b/crypto/src/math/ec/ECPoint.cs
@@ -1421,34 +1421,44 @@ namespace Org.BouncyCastle.Math.EC
             if (BigInteger.Two.Equals(cofactor))
             {
                 /*
-                 *  Check that the trace of (X + A) is 0, then there exists a solution to L^2 + L = X + A,
-                 *  and so a halving is possible, so this point is the double of another.  
+                 * Check that 0 == Tr(X + A); then there exists a solution to L^2 + L = X + A, and
+                 * so a halving is possible, so this point is the double of another.
+                 * 
+                 * Note: Tr(A) == 1 for cofactor 2 curves.
                  */
                 ECPoint N = this.Normalize();
                 ECFieldElement X = N.AffineXCoord;
-                ECFieldElement rhs = X.Add(curve.A);
-                return ((AbstractF2mFieldElement)rhs).Trace() == 0;
+                return 0 != ((AbstractF2mFieldElement)X).Trace();
             }
             if (BigInteger.ValueOf(4).Equals(cofactor))
             {
                 /*
                  * Solve L^2 + L = X + A to find the half of this point, if it exists (fail if not).
-                 * Generate both possibilities for the square of the half-point's x-coordinate (w),
-                 * and check if Tr(w + A) == 0 for at least one; then a second halving is possible
-                 * (see comments for cofactor 2 above), so this point is four times another.
                  * 
-                 * Note: Tr(x^2) == Tr(x). 
+                 * Note: Tr(A) == 0 for cofactor 4 curves.
                  */
                 ECPoint N = this.Normalize();
                 ECFieldElement X = N.AffineXCoord;
-                ECFieldElement lambda = ((AbstractF2mCurve)curve).SolveQuadraticEquation(X.Add(curve.A));
-                if (lambda == null)
+                ECFieldElement L = ((AbstractF2mCurve)curve).SolveQuadraticEquation(X.Add(curve.A));
+                if (null == L)
                     return false;
 
-                ECFieldElement w = X.Multiply(lambda).Add(N.AffineYCoord);
-                ECFieldElement t = w.Add(curve.A);
-                return ((AbstractF2mFieldElement)t).Trace() == 0
-                    || ((AbstractF2mFieldElement)(t.Add(X))).Trace() == 0;
+                /*
+                 * A solution exists, therefore 0 == Tr(X + A) == Tr(X).
+                 */
+                ECFieldElement Y = N.AffineYCoord;
+                ECFieldElement T = X.Multiply(L).Add(Y);
+
+                /*
+                 * Either T or (T + X) is the square of a half-point's x coordinate (hx). In either
+                 * case, the half-point can be halved again when 0 == Tr(hx + A).
+                 * 
+                 * Note: Tr(hx + A) == Tr(hx) == Tr(hx^2) == Tr(T) == Tr(T + X)
+                 *
+                 * Check that 0 == Tr(T); then there exists a solution to L^2 + L = hx + A, and so a
+                 * second halving is possible and this point is four times some other.
+                 */
+                return 0 == ((AbstractF2mFieldElement)T).Trace();
             }
 
             return base.SatisfiesOrder();
diff --git a/crypto/src/math/ec/custom/sec/SecT113Field.cs b/crypto/src/math/ec/custom/sec/SecT113Field.cs
index 1c4576062..3c9e0938d 100644
--- a/crypto/src/math/ec/custom/sec/SecT113Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113Field.cs
@@ -30,11 +30,32 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[1] = x[1];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(113, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat128.CreateExt64();
+
+            Nat128.Copy64(x, z);
+            for (int i = 1; i < 113; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat128.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
index bb87b00fc..63de2b88c 100644
--- a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT113FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat128.Create64();
+            SecT113Field.HalfTrace(x, z);
+            return new SecT113FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT113Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT131Field.cs b/crypto/src/math/ec/custom/sec/SecT131Field.cs
index 248b1969e..db703d9e0 100644
--- a/crypto/src/math/ec/custom/sec/SecT131Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131Field.cs
@@ -35,11 +35,33 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[2] = x[2];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(131, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat.Create64(5);
+
+            Nat192.Copy64(x, z);
+            for (int i = 1; i < 131; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat192.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
index f96c7ca39..4884e7152 100644
--- a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT131FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat192.Create64();
+            SecT131Field.HalfTrace(x, z);
+            return new SecT131FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT131Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT163Field.cs b/crypto/src/math/ec/custom/sec/SecT163Field.cs
index bc35ae6e8..b7f60d860 100644
--- a/crypto/src/math/ec/custom/sec/SecT163Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163Field.cs
@@ -36,11 +36,33 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[2] = x[2];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(163, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat192.CreateExt64();
+
+            Nat192.Copy64(x, z);
+            for (int i = 1; i < 163; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat192.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
index 903645999..214a56343 100644
--- a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT163FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat192.Create64();
+            SecT163Field.HalfTrace(x, z);
+            return new SecT163FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT163Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT193Field.cs b/crypto/src/math/ec/custom/sec/SecT193Field.cs
index a186da7b6..3ad9b0af2 100644
--- a/crypto/src/math/ec/custom/sec/SecT193Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs
@@ -37,11 +37,34 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[3] = x[3];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+            z[3] ^= x[3];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(193, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat256.CreateExt64();
+
+            Nat256.Copy64(x, z);
+            for (int i = 1; i < 193; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat256.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
index 9813bcb01..3a3ed09ce 100644
--- a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT193FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat256.Create64();
+            SecT193Field.HalfTrace(x, z);
+            return new SecT193FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT193Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs
index 013e6b8f9..d7916c57d 100644
--- a/crypto/src/math/ec/custom/sec/SecT233Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233Field.cs
@@ -38,11 +38,34 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[3] = x[3];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+            z[3] ^= x[3];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(233, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat256.CreateExt64();
+
+            Nat256.Copy64(x, z);
+            for (int i = 1; i < 233; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat256.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
index fbfe35e13..8aff8c87a 100644
--- a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT233FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat256.Create64();
+            SecT233Field.HalfTrace(x, z);
+            return new SecT233FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT233Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT239Field.cs b/crypto/src/math/ec/custom/sec/SecT239Field.cs
index b0c033fe2..eab929359 100644
--- a/crypto/src/math/ec/custom/sec/SecT239Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239Field.cs
@@ -38,11 +38,34 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[3] = x[3];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+            z[3] ^= x[3];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(239, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat256.CreateExt64();
+
+            Nat256.Copy64(x, z);
+            for (int i = 1; i < 239; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat256.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
index b1b58e89b..9f1bf671c 100644
--- a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT239FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat256.Create64();
+            SecT239Field.HalfTrace(x, z);
+            return new SecT239FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT239Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT283Field.cs b/crypto/src/math/ec/custom/sec/SecT283Field.cs
index ec2ba2cc1..4e2cee0f8 100644
--- a/crypto/src/math/ec/custom/sec/SecT283Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283Field.cs
@@ -43,11 +43,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[4] = x[4];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+            z[3] ^= x[3];
+            z[4] ^= x[4];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(283, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat.Create64(9);
+
+            Nat320.Copy64(x, z);
+            for (int i = 1; i < 283; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat320.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
index c1bb2e30c..6bd720acd 100644
--- a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT283FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat320.Create64();
+            SecT283Field.HalfTrace(x, z);
+            return new SecT283FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT283Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT409Field.cs b/crypto/src/math/ec/custom/sec/SecT409Field.cs
index 7cb9d4529..2e5609542 100644
--- a/crypto/src/math/ec/custom/sec/SecT409Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409Field.cs
@@ -40,11 +40,37 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[6] = x[6];
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            z[0] ^= x[0];
+            z[1] ^= x[1];
+            z[2] ^= x[2];
+            z[3] ^= x[3];
+            z[4] ^= x[4];
+            z[5] ^= x[5];
+            z[6] ^= x[6];
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(409, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat.Create64(13);
+
+            Nat448.Copy64(x, z);
+            for (int i = 1; i < 409; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat448.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
index 68a63312d..a9b08526a 100644
--- a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT409FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat448.Create64();
+            SecT409Field.HalfTrace(x, z);
+            return new SecT409FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT409Field.Trace(x);
diff --git a/crypto/src/math/ec/custom/sec/SecT571Field.cs b/crypto/src/math/ec/custom/sec/SecT571Field.cs
index 5a91985bc..0d9b337fc 100644
--- a/crypto/src/math/ec/custom/sec/SecT571Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571Field.cs
@@ -55,11 +55,34 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        private static void AddTo(ulong[] x, ulong[] z)
+        {
+            for (int i = 0; i < 9; ++i)
+            {
+                z[i] ^= x[i];
+            }
+        }
+
         public static ulong[] FromBigInteger(BigInteger x)
         {
             return Nat.FromBigInteger64(571, x);
         }
 
+        public static void HalfTrace(ulong[] x, ulong[] z)
+        {
+            ulong[] tt = Nat576.CreateExt64();
+
+            Nat576.Copy64(x, z);
+            for (int i = 1; i < 571; i += 2)
+            {
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                ImplSquare(z, tt);
+                Reduce(tt, z);
+                AddTo(x, z);
+            }
+        }
+
         public static void Invert(ulong[] x, ulong[] z)
         {
             if (Nat576.IsZero64(x))
diff --git a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
index c9f3aa5c0..22edfe0a2 100644
--- a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
@@ -150,6 +150,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return new SecT571FieldElement(z);
         }
 
+        public override ECFieldElement HalfTrace()
+        {
+            ulong[] z = Nat576.Create64();
+            SecT571Field.HalfTrace(x, z);
+            return new SecT571FieldElement(z);
+        }
+
+        public override bool HasFastTrace
+        {
+            get { return true; }
+        }
+
         public override int Trace()
         {
             return (int)SecT571Field.Trace(x);
diff --git a/crypto/src/util/Integers.cs b/crypto/src/util/Integers.cs
index e746b0ef4..bd05a053e 100644
--- a/crypto/src/util/Integers.cs
+++ b/crypto/src/util/Integers.cs
@@ -4,6 +4,21 @@ namespace Org.BouncyCastle.Utilities
 {
     public abstract class Integers
     {
+        public static int NumberOfLeadingZeros(int i)
+        {
+            if (i <= 0)
+                return (~i >> (31 - 5)) & (1 << 5);
+
+            uint u = (uint)i;
+            int n = 1;
+            if (0 == (u >> 16)) { n += 16; u <<= 16; }
+            if (0 == (u >> 24)) { n +=  8; u <<=  8; }
+            if (0 == (u >> 28)) { n +=  4; u <<=  4; }
+            if (0 == (u >> 30)) { n +=  2; u <<=  2; }
+            n -= (int)(u >> 31);
+            return n;
+        }
+
         public static int RotateLeft(int i, int distance)
         {
             return (i << distance) ^ (int)((uint)i >> -distance);
diff --git a/crypto/test/src/math/ec/test/ECPointTest.cs b/crypto/test/src/math/ec/test/ECPointTest.cs
index dbd739023..e1a2b8a6a 100644
--- a/crypto/test/src/math/ec/test/ECPointTest.cs
+++ b/crypto/test/src/math/ec/test/ECPointTest.cs
@@ -5,9 +5,11 @@ using NUnit.Framework;
 
 using Org.BouncyCastle.Asn1.X9;
 using Org.BouncyCastle.Crypto.EC;
+using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 using Org.BouncyCastle.Utilities.Collections;
+using Org.BouncyCastle.Utilities.Encoders;
 
 namespace Org.BouncyCastle.Math.EC.Tests
 {
@@ -399,10 +401,15 @@ namespace Org.BouncyCastle.Math.EC.Tests
             ImplTestMultiply(q, n.BitLength);
             ImplTestMultiply(infinity, n.BitLength);
 
+            int logSize = 32 - Integers.NumberOfLeadingZeros(curve.FieldSize - 1);
+            int rounds = System.Math.Max(2, System.Math.Min(10, 32 - 3 * logSize));
+
             ECPoint p = q;
-            for (int i = 0; i < 10; ++i)
+            for (int i = 0; ; )
             {
                 ImplTestEncoding(p);
+                if (++i == rounds)
+                    break;
                 p = p.Twice();
             }
         }
@@ -446,14 +453,42 @@ namespace Org.BouncyCastle.Math.EC.Tests
         {
             Assert.IsTrue(g.IsValid());
 
-            BigInteger h = c.Cofactor;
-            if (h != null && h.CompareTo(BigInteger.One) > 0)
+            if (ECAlgorithms.IsF2mCurve(c))
             {
-                if (ECAlgorithms.IsF2mCurve(c))
+                BigInteger h = c.Cofactor;
+                if (null != h)
                 {
-                    ECPoint order2 = c.CreatePoint(BigInteger.Zero, c.B.Sqrt().ToBigInteger());
-                    ECPoint bad = g.Add(order2);
-                    Assert.IsFalse(bad.IsValid());
+                    if (!h.TestBit(0))
+                    {
+                        ECFieldElement sqrtB = c.B.Sqrt();
+                        ECPoint order2 = c.CreatePoint(BigInteger.Zero, sqrtB.ToBigInteger());
+                        Assert.IsTrue(order2.Twice().IsInfinity);
+                        Assert.IsFalse(order2.IsValid());
+                        ECPoint bad2 = g.Add(order2);
+                        Assert.IsFalse(bad2.IsValid());
+                        ECPoint good2 = bad2.Add(order2);
+                        Assert.IsTrue(good2.IsValid());
+
+                        if (!h.TestBit(1))
+                        {
+                            ECFieldElement L = SolveQuadraticEquation(c, c.A);
+                            Assert.IsNotNull(L);
+                            ECFieldElement T = sqrtB;
+                            ECFieldElement x = T.Sqrt();
+                            ECFieldElement y = T.Add(x.Multiply(L));
+                            ECPoint order4 = c.CreatePoint(x.ToBigInteger(), y.ToBigInteger());
+                            Assert.IsTrue(order4.Twice().Equals(order2));
+                            Assert.IsFalse(order4.IsValid());
+                            ECPoint bad4_1 = g.Add(order4);
+                            Assert.IsFalse(bad4_1.IsValid());
+                            ECPoint bad4_2 = bad4_1.Add(order4);
+                            Assert.IsFalse(bad4_2.IsValid());
+                            ECPoint bad4_3 = bad4_2.Add(order4);
+                            Assert.IsFalse(bad4_3.IsValid());
+                            ECPoint good4 = bad4_3.Add(order4);
+                            Assert.IsTrue(good4.IsValid());
+                        }
+                    }
                 }
             }
         }
@@ -543,6 +578,55 @@ namespace Org.BouncyCastle.Math.EC.Tests
             }
         }
 
+        [Test]
+        public void TestExampleFpB0()
+        {
+            /*
+             * The supersingular curve y^2 = x^3 - 3.x (i.e. with 'B' == 0) from RFC 6508 2.1, with
+             * curve parameters from RFC 6509 Appendix A.
+             */
+            BigInteger p = FromHex(
+                  "997ABB1F0A563FDA65C61198DAD0657A"
+                + "416C0CE19CB48261BE9AE358B3E01A2E"
+                + "F40AAB27E2FC0F1B228730D531A59CB0"
+                + "E791B39FF7C88A19356D27F4A666A6D0"
+                + "E26C6487326B4CD4512AC5CD65681CE1"
+                + "B6AFF4A831852A82A7CF3C521C3C09AA"
+                + "9F94D6AF56971F1FFCE3E82389857DB0"
+                + "80C5DF10AC7ACE87666D807AFEA85FEB");
+            BigInteger a = p.Subtract(BigInteger.ValueOf(3));
+            BigInteger b = BigInteger.Zero;
+            byte[] S = null;
+            BigInteger n = p.Add(BigInteger.One).ShiftRight(2);
+            BigInteger h = BigInteger.ValueOf(4);
+
+            ECCurve curve = ConfigureCurve(new FpCurve(p, a, b, n, h));
+
+            X9ECPoint G = ConfigureBasepoint(curve, "04"
+                // Px
+                + "53FC09EE332C29AD0A7990053ED9B52A"
+                + "2B1A2FD60AEC69C698B2F204B6FF7CBF"
+                + "B5EDB6C0F6CE2308AB10DB9030B09E10"
+                + "43D5F22CDB9DFA55718BD9E7406CE890"
+                + "9760AF765DD5BCCB337C86548B72F2E1"
+                + "A702C3397A60DE74A7C1514DBA66910D"
+                + "D5CFB4CC80728D87EE9163A5B63F73EC"
+                + "80EC46C4967E0979880DC8ABEAE63895"
+                // Py
+                + "0A8249063F6009F1F9F1F0533634A135"
+                + "D3E82016029906963D778D821E141178"
+                + "F5EA69F4654EC2B9E7F7F5E5F0DE55F6"
+                + "6B598CCF9A140B2E416CFF0CA9E032B9"
+                + "70DAE117AD547C6CCAD696B5B7652FE0"
+                + "AC6F1E80164AA989492D979FC5A4D5F2"
+                + "13515AD7E9CB99A980BDAD5AD5BB4636"
+                + "ADB9B5706A67DCDE75573FD71BEF16D7");
+
+            X9ECParameters x9 = new X9ECParameters(curve, G, n, h, S);
+
+            ImplAddSubtractMultiplyTwiceEncodingTestAllCoords(x9);
+        }
+
         private void AssertPointsEqual(string message, ECPoint a, ECPoint b)
         {
             // NOTE: We intentionally test points for equality in both directions
@@ -565,5 +649,52 @@ namespace Org.BouncyCastle.Math.EC.Tests
                 Assert.IsTrue(Arrays.AreEqual(a, b));
             }
         }
+
+        private static X9ECPoint ConfigureBasepoint(ECCurve curve, string encoding)
+        {
+            X9ECPoint G = new X9ECPoint(curve, Hex.Decode(encoding));
+            //WNafUtilities.ConfigureBasepoint(G.Point);
+            return G;
+        }
+
+        private static ECCurve ConfigureCurve(ECCurve curve)
+        {
+            return curve;
+        }
+
+        private static BigInteger FromHex(string hex)
+        {
+            return new BigInteger(1, Hex.Decode(hex));
+        }
+
+        private static ECFieldElement SolveQuadraticEquation(ECCurve c, ECFieldElement rhs)
+        {
+            if (rhs.IsZero)
+                return rhs;
+
+            ECFieldElement gamma, z, zeroElement = c.FromBigInteger(BigInteger.Zero);
+
+            int m = c.FieldSize;
+            do
+            {
+                ECFieldElement t = c.FromBigInteger(BigInteger.Arbitrary(m));
+                z = zeroElement;
+                ECFieldElement w = rhs;
+                for (int i = 1; i < m; i++)
+                {
+                    ECFieldElement w2 = w.Square();
+                    z = z.Square().Add(w2.Multiply(t));
+                    w = w2.Add(rhs);
+                }
+                if (!w.IsZero)
+                {
+                    return null;
+                }
+                gamma = z.Square().Add(z);
+            }
+            while (gamma.IsZero);
+
+            return z;
+        }
     }
 }