diff options
Diffstat (limited to 'crypto')
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; + } } } |