diff options
Diffstat (limited to 'crypto/src')
34 files changed, 2042 insertions, 116 deletions
diff --git a/crypto/src/asn1/x9/X9ECParametersHolder.cs b/crypto/src/asn1/x9/X9ECParametersHolder.cs index f0a320094..e802b738c 100644 --- a/crypto/src/asn1/x9/X9ECParametersHolder.cs +++ b/crypto/src/asn1/x9/X9ECParametersHolder.cs @@ -10,15 +10,15 @@ namespace Org.BouncyCastle.Asn1.X9 { lock (this) { - if (parameters == null) - { - parameters = CreateParameters(); - } + if (parameters == null) + { + parameters = CreateParameters(); + } return parameters; } } - } + } protected abstract X9ECParameters CreateParameters(); } diff --git a/crypto/src/bcpg/BcpgInputStream.cs b/crypto/src/bcpg/BcpgInputStream.cs index 3c69fbdf5..2e08cd090 100644 --- a/crypto/src/bcpg/BcpgInputStream.cs +++ b/crypto/src/bcpg/BcpgInputStream.cs @@ -105,19 +105,15 @@ namespace Org.BouncyCastle.Bcpg next = true; } - if (nextB >= 0) + if (nextB < 0) + return (PacketTag)nextB; + + int maskB = nextB & 0x3f; + if ((nextB & 0x40) == 0) // old { - if ((nextB & 0x40) != 0) // new - { - return (PacketTag)(nextB & 0x3f); - } - else // old - { - return (PacketTag)((nextB & 0x3f) >> 2); - } + maskB >>= 2; } - - return (PacketTag) nextB; + return (PacketTag)maskB; } public Packet ReadPacket() diff --git a/crypto/src/cms/SignerInformation.cs b/crypto/src/cms/SignerInformation.cs index 20af29a50..581286a3f 100644 --- a/crypto/src/cms/SignerInformation.cs +++ b/crypto/src/cms/SignerInformation.cs @@ -345,9 +345,12 @@ namespace Org.BouncyCastle.Cms // if (sigParams != null) // throw new CmsException("unrecognised signature parameters provided"); - string signatureName = digestName + "with" + Helper.GetEncryptionAlgName(this.EncryptionAlgOid); + string signatureName = digestName + "with" + Helper.GetEncryptionAlgName(this.EncryptionAlgOid); - sig = Helper.GetSignatureInstance(signatureName); + sig = Helper.GetSignatureInstance(signatureName); + + //sig = Helper.GetSignatureInstance(this.EncryptionAlgOid); + //sig = SignerUtilities.GetSigner(sigAlgOid); } try diff --git a/crypto/src/crypto/ec/CustomNamedCurves.cs b/crypto/src/crypto/ec/CustomNamedCurves.cs index 9b7935523..0f13b4571 100644 --- a/crypto/src/crypto/ec/CustomNamedCurves.cs +++ b/crypto/src/crypto/ec/CustomNamedCurves.cs @@ -516,6 +516,48 @@ namespace Org.BouncyCastle.Crypto.EC }; /* + * sect193r1 + */ + internal class SecT193R1Holder + : X9ECParametersHolder + { + private SecT193R1Holder() { } + + internal static readonly X9ECParametersHolder Instance = new SecT193R1Holder(); + + protected override X9ECParameters CreateParameters() + { + byte[] S = Hex.Decode("103FAEC74D696E676875615175777FC5B191EF30"); + ECCurve curve = ConfigureCurve(new SecT193R1Curve()); + ECPoint G = curve.DecodePoint(Hex.Decode("04" + + "01F481BC5F0FF84A74AD6CDF6FDEF4BF6179625372D8C0C5E1" + + "0025E399F2903712CCF3EA9E3A1AD17FB0B3201B6AF7CE1B05")); + return new X9ECParameters(curve, G, curve.Order, curve.Cofactor, S); + } + }; + + /* + * sect193r2 + */ + internal class SecT193R2Holder + : X9ECParametersHolder + { + private SecT193R2Holder() { } + + internal static readonly X9ECParametersHolder Instance = new SecT193R2Holder(); + + protected override X9ECParameters CreateParameters() + { + byte[] S = Hex.Decode("10B7B4D696E676875615175137C8A16FD0DA2211"); + ECCurve curve = ConfigureCurve(new SecT193R2Curve()); + ECPoint G = curve.DecodePoint(Hex.Decode("04" + + "00D9B67D192E0367C803F39E1A7E82CA14A651350AAE617E8F" + + "01CE94335607C304AC29E7DEFBD9CA01F596F927224CDECF6C")); + return new X9ECParameters(curve, G, curve.Order, curve.Cofactor, S); + } + }; + + /* * sect233k1 */ internal class SecT233K1Holder @@ -766,6 +808,8 @@ namespace Org.BouncyCastle.Crypto.EC DefineCurveWithOid("sect163k1", SecObjectIdentifiers.SecT163k1, SecT163K1Holder.Instance); DefineCurveWithOid("sect163r1", SecObjectIdentifiers.SecT163r1, SecT163R1Holder.Instance); DefineCurveWithOid("sect163r2", SecObjectIdentifiers.SecT163r2, SecT163R2Holder.Instance); + DefineCurveWithOid("sect193r1", SecObjectIdentifiers.SecT193r1, SecT193R1Holder.Instance); + DefineCurveWithOid("sect193r2", SecObjectIdentifiers.SecT193r2, SecT193R2Holder.Instance); DefineCurveWithOid("sect233k1", SecObjectIdentifiers.SecT233k1, SecT233K1Holder.Instance); DefineCurveWithOid("sect233r1", SecObjectIdentifiers.SecT233r1, SecT233R1Holder.Instance); DefineCurveWithOid("sect239k1", SecObjectIdentifiers.SecT239k1, SecT239K1Holder.Instance); diff --git a/crypto/src/crypto/engines/AesEngine.cs b/crypto/src/crypto/engines/AesEngine.cs index 9d7f76c05..164c43ee9 100644 --- a/crypto/src/crypto/engines/AesEngine.cs +++ b/crypto/src/crypto/engines/AesEngine.cs @@ -237,12 +237,22 @@ namespace Org.BouncyCastle.Crypto.Engines private const uint m1 = 0x80808080; private const uint m2 = 0x7f7f7f7f; private const uint m3 = 0x0000001b; + private const uint m4 = 0xC0C0C0C0; + private const uint m5 = 0x3f3f3f3f; private static uint FFmulX(uint x) { return ((x & m2) << 1) ^ (((x & m1) >> 7) * m3); } + private static uint FFmulX2(uint x) + { + uint t0 = (x & m5) << 2; + uint t1 = (x & m4); + t1 ^= (t1 >> 1); + return t0 ^ (t1 >> 2) ^ (t1 >> 5); + } + /* The following defines provide alternative definitions of FFmulX that might give improved performance if a fast 32-bit multiply is not available. @@ -255,12 +265,13 @@ namespace Org.BouncyCastle.Crypto.Engines private static uint Inv_Mcol(uint x) { - uint f2 = FFmulX(x); - uint f4 = FFmulX(f2); - uint f8 = FFmulX(f4); - uint f9 = x ^ f8; - - return f2 ^ f4 ^ f8 ^ Shift(f2 ^ f9, 8) ^ Shift(f4 ^ f9, 16) ^ Shift(f9, 24); + uint t0, t1; + t0 = x; + t1 = t0 ^ Shift(t0, 8); + t0 ^= FFmulX(t1); + t1 ^= FFmulX2(t0); + t0 ^= t1 ^ Shift(t1, 16); + return t0; } private static uint SubWord(uint x) diff --git a/crypto/src/crypto/engines/AesFastEngine.cs b/crypto/src/crypto/engines/AesFastEngine.cs index a1b544568..38ce1a946 100644 --- a/crypto/src/crypto/engines/AesFastEngine.cs +++ b/crypto/src/crypto/engines/AesFastEngine.cs @@ -573,12 +573,22 @@ namespace Org.BouncyCastle.Crypto.Engines private const uint m1 = 0x80808080; private const uint m2 = 0x7f7f7f7f; private const uint m3 = 0x0000001b; + private const uint m4 = 0xC0C0C0C0; + private const uint m5 = 0x3f3f3f3f; private static uint FFmulX(uint x) { return ((x & m2) << 1) ^ (((x & m1) >> 7) * m3); } + private static uint FFmulX2(uint x) + { + uint t0 = (x & m5) << 2; + uint t1 = (x & m4); + t1 ^= (t1 >> 1); + return t0 ^ (t1 >> 2) ^ (t1 >> 5); + } + /* The following defines provide alternative definitions of FFmulX that might give improved performance if a fast 32-bit multiply is not available. @@ -591,12 +601,13 @@ namespace Org.BouncyCastle.Crypto.Engines private static uint Inv_Mcol(uint x) { - uint f2 = FFmulX(x); - uint f4 = FFmulX(f2); - uint f8 = FFmulX(f4); - uint f9 = x ^ f8; - - return f2 ^ f4 ^ f8 ^ Shift(f2 ^ f9, 8) ^ Shift(f4 ^ f9, 16) ^ Shift(f9, 24); + uint t0, t1; + t0 = x; + t1 = t0 ^ Shift(t0, 8); + t0 ^= FFmulX(t1); + t1 ^= FFmulX2(t0); + t0 ^= t1 ^ Shift(t1, 16); + return t0; } private static uint SubWord(uint x) diff --git a/crypto/src/crypto/engines/AesLightEngine.cs b/crypto/src/crypto/engines/AesLightEngine.cs index a6b9e3bd4..a42b34971 100644 --- a/crypto/src/crypto/engines/AesLightEngine.cs +++ b/crypto/src/crypto/engines/AesLightEngine.cs @@ -126,12 +126,22 @@ namespace Org.BouncyCastle.Crypto.Engines private const uint m1 = 0x80808080; private const uint m2 = 0x7f7f7f7f; private const uint m3 = 0x0000001b; + private const uint m4 = 0xC0C0C0C0; + private const uint m5 = 0x3f3f3f3f; private static uint FFmulX(uint x) { return ((x & m2) << 1) ^ (((x & m1) >> 7) * m3); } + private static uint FFmulX2(uint x) + { + uint t0 = (x & m5) << 2; + uint t1 = (x & m4); + t1 ^= (t1 >> 1); + return t0 ^ (t1 >> 2) ^ (t1 >> 5); + } + /* The following defines provide alternative definitions of FFmulX that might give improved performance if a fast 32-bit multiply is not available. @@ -144,18 +154,21 @@ namespace Org.BouncyCastle.Crypto.Engines private static uint Mcol(uint x) { - uint f2 = FFmulX(x); - return f2 ^ Shift(x ^ f2, 8) ^ Shift(x, 16) ^ Shift(x, 24); + uint t0, t1; + t0 = Shift(x, 8); + t1 = x ^ t0; + return Shift(t1, 16) ^ t0 ^ FFmulX(t1); } private static uint Inv_Mcol(uint x) { - uint f2 = FFmulX(x); - uint f4 = FFmulX(f2); - uint f8 = FFmulX(f4); - uint f9 = x ^ f8; - - return f2 ^ f4 ^ f8 ^ Shift(f2 ^ f9, 8) ^ Shift(f4 ^ f9, 16) ^ Shift(f9, 24); + uint t0, t1; + t0 = x; + t1 = t0 ^ Shift(t0, 8); + t0 ^= FFmulX(t1); + t1 ^= FFmulX2(t0); + t0 ^= t1 ^ Shift(t1, 16); + return t0; } private static uint SubWord(uint x) diff --git a/crypto/src/crypto/modes/gcm/GcmUtilities.cs b/crypto/src/crypto/modes/gcm/GcmUtilities.cs index de41d88f4..d8ab2ca73 100644 --- a/crypto/src/crypto/modes/gcm/GcmUtilities.cs +++ b/crypto/src/crypto/modes/gcm/GcmUtilities.cs @@ -46,6 +46,13 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm return tmp; } + internal static ulong[] OneAsUlongs() + { + ulong[] tmp = new ulong[2]; + tmp[0] = 1UL << 63; + return tmp; + } + internal static byte[] AsBytes(uint[] x) { return Pack.UInt32_To_BE(x); @@ -56,6 +63,18 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm Pack.UInt32_To_BE(x, z, 0); } + internal static byte[] AsBytes(ulong[] x) + { + byte[] z = new byte[16]; + Pack.UInt64_To_BE(x, z, 0); + return z; + } + + internal static void AsBytes(ulong[] x, byte[] z) + { + Pack.UInt64_To_BE(x, z, 0); + } + internal static uint[] AsUints(byte[] bs) { uint[] output = new uint[4]; @@ -68,6 +87,18 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm Pack.BE_To_UInt32(bs, 0, output); } + internal static ulong[] AsUlongs(byte[] x) + { + ulong[] z = new ulong[2]; + Pack.BE_To_UInt64(x, 0, z); + return z; + } + + public static void AsUlongs(byte[] x, ulong[] z) + { + Pack.BE_To_UInt64(x, 0, z); + } + internal static void Multiply(byte[] x, byte[] y) { uint[] t1 = GcmUtilities.AsUints(x); @@ -80,7 +111,7 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm { uint r00 = x[0], r01 = x[1], r02 = x[2], r03 = x[3]; uint r10 = 0, r11 = 0, r12 = 0, r13 = 0; - + for (int i = 0; i < 4; ++i) { int bits = (int)y[i]; @@ -93,9 +124,9 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm r13 ^= (r03 & m1); uint m2 = (uint)((int)(r03 << 31) >> 8); - r03 = (r03 >> 1) | (r02 << 63); - r02 = (r02 >> 1) | (r01 << 63); - r01 = (r01 >> 1) | (r00 << 63); + r03 = (r03 >> 1) | (r02 << 31); + r02 = (r02 >> 1) | (r01 << 31); + r01 = (r01 >> 1) | (r00 << 31); r00 = (r00 >> 1) ^ (m2 & E1); } } @@ -119,7 +150,7 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm r10 ^= (r00 & m1); r11 ^= (r01 & m1); - ulong m2 = (r01 << 63) >> 8; + ulong m2 = (ulong)((long)(r01 << 63) >> 8); r01 = (r01 >> 1) | (r00 << 63); r00 = (r00 >> 1) ^ (m2 & E1L); } @@ -272,5 +303,17 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm z[2] = x[2] ^ y[2]; z[3] = x[3] ^ y[3]; } + + internal static void Xor(ulong[] x, ulong[] y) + { + x[0] ^= y[0]; + x[1] ^= y[1]; + } + + internal static void Xor(ulong[] x, ulong[] y, ulong[] z) + { + z[0] = x[0] ^ y[0]; + z[1] = x[1] ^ y[1]; + } } } diff --git a/crypto/src/crypto/parameters/DHParameters.cs b/crypto/src/crypto/parameters/DHParameters.cs index a0544e73b..4258df5c5 100644 --- a/crypto/src/crypto/parameters/DHParameters.cs +++ b/crypto/src/crypto/parameters/DHParameters.cs @@ -91,6 +91,7 @@ namespace Org.BouncyCastle.Crypto.Parameters throw new ArgumentException("m value must be < bitlength of p", "m"); if (l != 0) { + // TODO Check this against the Java version, which has 'l > p.BitLength' here if (l >= p.BitLength) throw new ArgumentException("when l value specified, it must be less than bitlength(p)", "l"); if (l < m) diff --git a/crypto/src/crypto/util/Pack.cs b/crypto/src/crypto/util/Pack.cs index 087cb7cea..dc00ab450 100644 --- a/crypto/src/crypto/util/Pack.cs +++ b/crypto/src/crypto/util/Pack.cs @@ -117,6 +117,22 @@ namespace Org.BouncyCastle.Crypto.Utilities UInt32_To_BE((uint)(n), bs, off + 4); } + internal static byte[] UInt64_To_BE(ulong[] ns) + { + byte[] bs = new byte[8 * ns.Length]; + UInt64_To_BE(ns, bs, 0); + return bs; + } + + internal static void UInt64_To_BE(ulong[] ns, byte[] bs, int off) + { + for (int i = 0; i < ns.Length; ++i) + { + UInt64_To_BE(ns[i], bs, off); + off += 8; + } + } + internal static ulong BE_To_UInt64(byte[] bs) { uint hi = BE_To_UInt32(bs); @@ -131,6 +147,15 @@ namespace Org.BouncyCastle.Crypto.Utilities return ((ulong)hi << 32) | (ulong)lo; } + internal static void BE_To_UInt64(byte[] bs, int off, ulong[] ns) + { + for (int i = 0; i < ns.Length; ++i) + { + ns[i] = BE_To_UInt64(bs, off); + off += 8; + } + } + internal static void UInt16_To_LE(ushort n, byte[] bs) { bs[0] = (byte)(n); diff --git a/crypto/src/math/ec/custom/sec/SecT113Field.cs b/crypto/src/math/ec/custom/sec/SecT113Field.cs index dbb645e6f..640c6e787 100644 --- a/crypto/src/math/ec/custom/sec/SecT113Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT113Field.cs @@ -37,6 +37,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat128.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion + + ulong[] t0 = Nat128.Create64(); + ulong[] t1 = Nat128.Create64(); + + Square(x, t0); + Multiply(t0, x, t0); + Square(t0, t0); + Multiply(t0, x, t0); + SquareN(t0, 3, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 7, t0); + Multiply(t0, t1, t0); + SquareN(t0, 14, t1); + Multiply(t1, t0, t1); + SquareN(t1, 28, t0); + Multiply(t0, t1, t0); + SquareN(t0, 56, t1); + Multiply(t1, t0, t1); + Square(t1, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat128.CreateExt64(); diff --git a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs index e3a923f62..f217e28cb 100644 --- a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT113FieldElement( - AbstractF2mCurve.Inverse(113, new int[]{ 9 }, ToBigInteger())); + ulong[] z = Nat128.Create64(); + SecT113Field.Invert(x, z); + return new SecT113FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT131Field.cs b/crypto/src/math/ec/custom/sec/SecT131Field.cs index df75dfcd7..47f97078c 100644 --- a/crypto/src/math/ec/custom/sec/SecT131Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT131Field.cs @@ -40,6 +40,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat192.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion + + ulong[] t0 = Nat192.Create64(); + ulong[] t1 = Nat192.Create64(); + + Square(x, t0); + Multiply(t0, x, t0); + SquareN(t0, 2, t1); + Multiply(t1, t0, t1); + SquareN(t1, 4, t0); + Multiply(t0, t1, t0); + SquareN(t0, 8, t1); + Multiply(t1, t0, t1); + SquareN(t1, 16, t0); + Multiply(t0, t1, t0); + SquareN(t0, 32, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 65, t0); + Multiply(t0, t1, t0); + Square(t0, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat192.CreateExt64(); @@ -231,7 +260,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 45 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -247,7 +276,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 33; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6 diff --git a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs index 65aaf01ba..0ea00ea07 100644 --- a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT131FieldElement( - AbstractF2mCurve.Inverse(131, new int[] { 2, 3, 8 }, ToBigInteger())); + ulong[] z = Nat192.Create64(); + SecT131Field.Invert(x, z); + return new SecT131FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT163Field.cs b/crypto/src/math/ec/custom/sec/SecT163Field.cs index 2a775e20d..f921a5bc7 100644 --- a/crypto/src/math/ec/custom/sec/SecT163Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT163Field.cs @@ -41,6 +41,47 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat192.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion with bases { 2, 3 } + + ulong[] t0 = Nat192.Create64(); + ulong[] t1 = Nat192.Create64(); + + Square(x, t0); + + // 3 | 162 + SquareN(t0, 1, t1); + Multiply(t0, t1, t0); + SquareN(t1, 1, t1); + Multiply(t0, t1, t0); + + // 3 | 54 + SquareN(t0, 3, t1); + Multiply(t0, t1, t0); + SquareN(t1, 3, t1); + Multiply(t0, t1, t0); + + // 3 | 18 + SquareN(t0, 9, t1); + Multiply(t0, t1, t0); + SquareN(t1, 9, t1); + Multiply(t0, t1, t0); + + // 3 | 6 + SquareN(t0, 27, t1); + Multiply(t0, t1, t0); + SquareN(t1, 27, t1); + Multiply(t0, t1, t0); + + // 2 | 2 + SquareN(t0, 81, t1); + Multiply(t0, t1, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat192.CreateExt64(); @@ -230,7 +271,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 56 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -244,7 +285,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 47; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6; diff --git a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs index 3ab383a1d..c7a0b5639 100644 --- a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT163FieldElement( - AbstractF2mCurve.Inverse(163, new int[] { 3, 6, 7 }, ToBigInteger())); + ulong[] z = Nat192.Create64(); + SecT163Field.Invert(x, z); + return new SecT163FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT193Field.cs b/crypto/src/math/ec/custom/sec/SecT193Field.cs new file mode 100644 index 000000000..5154f1e0a --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs @@ -0,0 +1,282 @@ +using System; +using System.Diagnostics; + +using Org.BouncyCastle.Math.Raw; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193Field + { + private const ulong M01 = 1UL; + private const ulong M49 = ulong.MaxValue >> 15; + + public static void Add(ulong[] x, ulong[] y, ulong[] z) + { + z[0] = x[0] ^ y[0]; + z[1] = x[1] ^ y[1]; + z[2] = x[2] ^ y[2]; + z[3] = x[3] ^ y[3]; + } + + public static void AddExt(ulong[] xx, ulong[] yy, ulong[] zz) + { + zz[0] = xx[0] ^ yy[0]; + zz[1] = xx[1] ^ yy[1]; + zz[2] = xx[2] ^ yy[2]; + zz[3] = xx[3] ^ yy[3]; + zz[4] = xx[4] ^ yy[4]; + zz[5] = xx[5] ^ yy[5]; + zz[6] = xx[6] ^ yy[6]; + } + + public static void AddOne(ulong[] x, ulong[] z) + { + z[0] = x[0] ^ 1UL; + z[1] = x[1]; + z[2] = x[2]; + z[3] = x[3]; + } + + public static ulong[] FromBigInteger(BigInteger x) + { + ulong[] z = Nat256.FromBigInteger64(x); + Reduce63(z, 0); + return z; + } + + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat256.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion with bases { 2, 3 } + + ulong[] t0 = Nat256.Create64(); + ulong[] t1 = Nat256.Create64(); + + Square(x, t0); + + // 3 | 192 + SquareN(t0, 1, t1); + Multiply(t0, t1, t0); + SquareN(t1, 1, t1); + Multiply(t0, t1, t0); + + // 2 | 64 + SquareN(t0, 3, t1); + Multiply(t0, t1, t0); + + // 2 | 32 + SquareN(t0, 6, t1); + Multiply(t0, t1, t0); + + // 2 | 16 + SquareN(t0, 12, t1); + Multiply(t0, t1, t0); + + // 2 | 8 + SquareN(t0, 24, t1); + Multiply(t0, t1, t0); + + // 2 | 4 + SquareN(t0, 48, t1); + Multiply(t0, t1, t0); + + // 2 | 2 + SquareN(t0, 96, t1); + Multiply(t0, t1, z); + } + + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) + { + ulong[] tt = Nat256.CreateExt64(); + ImplMultiply(x, y, tt); + Reduce(tt, z); + } + + public static void MultiplyAddToExt(ulong[] x, ulong[] y, ulong[] zz) + { + ulong[] tt = Nat256.CreateExt64(); + ImplMultiply(x, y, tt); + AddExt(zz, tt, zz); + } + + public static void Reduce(ulong[] xx, ulong[] z) + { + ulong x0 = xx[0], x1 = xx[1], x2 = xx[2], x3 = xx[3], x4 = xx[4], x5 = xx[5], x6 = xx[6]; + + x2 ^= (x6 << 63); + x3 ^= (x6 >> 1) ^ (x6 << 14); + x4 ^= (x6 >> 50); + + x1 ^= (x5 << 63); + x2 ^= (x5 >> 1) ^ (x5 << 14); + x3 ^= (x5 >> 50); + + x0 ^= (x4 << 63); + x1 ^= (x4 >> 1) ^ (x4 << 14); + x2 ^= (x4 >> 50); + + ulong t = x3 >> 1; + z[0] = x0 ^ t ^ (t << 15); + z[1] = x1 ^ (t >> 49); + z[2] = x2; + z[3] = x3 & M01; + } + + public static void Reduce63(ulong[] z, int zOff) + { + ulong z3 = z[zOff + 3], t = z3 >> 1; + z[zOff ] ^= t ^ (t << 15); + z[zOff + 1] ^= (t >> 49); + z[zOff + 3] = z3 & M01; + } + + public static void Square(ulong[] x, ulong[] z) + { + ulong[] tt = Nat256.CreateExt64(); + ImplSquare(x, tt); + Reduce(tt, z); + } + + public static void SquareAddToExt(ulong[] x, ulong[] zz) + { + ulong[] tt = Nat256.CreateExt64(); + ImplSquare(x, tt); + AddExt(zz, tt, zz); + } + + public static void SquareN(ulong[] x, int n, ulong[] z) + { + Debug.Assert(n > 0); + + ulong[] tt = Nat256.CreateExt64(); + ImplSquare(x, tt); + Reduce(tt, z); + + while (--n > 0) + { + ImplSquare(z, tt); + Reduce(tt, z); + } + } + + protected static void ImplCompactExt(ulong[] zz) + { + ulong z0 = zz[0], z1 = zz[1], z2 = zz[2], z3 = zz[3], z4 = zz[4], z5 = zz[5], z6 = zz[6], z7 = zz[7]; + zz[0] = z0 ^ (z1 << 49); + zz[1] = (z1 >> 15) ^ (z2 << 34); + zz[2] = (z2 >> 30) ^ (z3 << 19); + zz[3] = (z3 >> 45) ^ (z4 << 4) + ^ (z5 << 53); + zz[4] = (z4 >> 60) ^ (z6 << 38) + ^ (z5 >> 11); + zz[5] = (z6 >> 26) ^ (z7 << 23); + zz[6] = (z7 >> 41); + zz[7] = 0; + } + + protected static void ImplExpand(ulong[] x, ulong[] z) + { + ulong x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3]; + z[0] = x0 & M49; + z[1] = ((x0 >> 49) ^ (x1 << 15)) & M49; + z[2] = ((x1 >> 34) ^ (x2 << 30)) & M49; + z[3] = ((x2 >> 19) ^ (x3 << 45)); + } + + protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) + { + /* + * "Two-level seven-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. + */ + + ulong[] f = new ulong[4], g = new ulong[4]; + ImplExpand(x, f); + ImplExpand(y, g); + + ImplMulwAcc(f[0], g[0], zz, 0); + ImplMulwAcc(f[1], g[1], zz, 1); + ImplMulwAcc(f[2], g[2], zz, 2); + ImplMulwAcc(f[3], g[3], zz, 3); + + // U *= (1 - t^n) + for (int i = 5; i > 0; --i) + { + zz[i] ^= zz[i - 1]; + } + + ImplMulwAcc(f[0] ^ f[1], g[0] ^ g[1], zz, 1); + ImplMulwAcc(f[2] ^ f[3], g[2] ^ g[3], zz, 3); + + // V *= (1 - t^2n) + for (int i = 7; i > 1; --i) + { + zz[i] ^= zz[i - 2]; + } + + // Double-length recursion + { + ulong c0 = f[0] ^ f[2], c1 = f[1] ^ f[3]; + ulong d0 = g[0] ^ g[2], d1 = g[1] ^ g[3]; + ImplMulwAcc(c0 ^ c1, d0 ^ d1, zz, 3); + ulong[] t = new ulong[3]; + ImplMulwAcc(c0, d0, t, 0); + ImplMulwAcc(c1, d1, t, 1); + ulong t0 = t[0], t1 = t[1], t2 = t[2]; + zz[2] ^= t0; + zz[3] ^= t0 ^ t1; + zz[4] ^= t2 ^ t1; + zz[5] ^= t2; + } + + ImplCompactExt(zz); + } + + protected static void ImplMulwAcc(ulong x, ulong y, ulong[] z, int zOff) + { + Debug.Assert(x >> 49 == 0); + Debug.Assert(y >> 49 == 0); + + ulong[] u = new ulong[8]; + //u[0] = 0; + u[1] = y; + u[2] = u[1] << 1; + u[3] = u[2] ^ y; + u[4] = u[2] << 1; + u[5] = u[4] ^ y; + u[6] = u[3] << 1; + u[7] = u[6] ^ y; + + uint j = (uint)x; + ulong g, h = 0, l = u[j & 7] + ^ (u[(j >> 3) & 7] << 3); + int k = 36; + do + { + j = (uint)(x >> k); + g = u[j & 7] + ^ u[(j >> 3) & 7] << 3 + ^ u[(j >> 6) & 7] << 6 + ^ u[(j >> 9) & 7] << 9 + ^ u[(j >> 12) & 7] << 12; + l ^= (g << k); + h ^= (g >> -k); + } + while ((k -= 15) > 0); + + Debug.Assert(h >> 33 == 0); + + z[zOff ] ^= l & M49; + z[zOff + 1] ^= (l >> 49) ^ (h << 15); + } + + protected static void ImplSquare(ulong[] x, ulong[] zz) + { + Interleave.Expand64To128(x[0], zz, 0); + Interleave.Expand64To128(x[1], zz, 2); + Interleave.Expand64To128(x[2], zz, 4); + zz[6] = (x[3] & M01); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs new file mode 100644 index 000000000..eba4d10e6 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs @@ -0,0 +1,214 @@ +using System; + +using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193FieldElement + : ECFieldElement + { + protected readonly ulong[] x; + + public SecT193FieldElement(BigInteger x) + { + if (x == null || x.SignValue < 0 || x.BitLength > 193) + throw new ArgumentException("value invalid for SecT193FieldElement", "x"); + + this.x = SecT193Field.FromBigInteger(x); + } + + public SecT193FieldElement() + { + this.x = Nat256.Create64(); + } + + protected internal SecT193FieldElement(ulong[] x) + { + this.x = x; + } + + public override bool IsOne + { + get { return Nat256.IsOne64(x); } + } + + public override bool IsZero + { + get { return Nat256.IsZero64(x); } + } + + public override bool TestBitZero() + { + return (x[0] & 1UL) != 0UL; + } + + public override BigInteger ToBigInteger() + { + return Nat256.ToBigInteger64(x); + } + + public override string FieldName + { + get { return "SecT193Field"; } + } + + public override int FieldSize + { + get { return 193; } + } + + public override ECFieldElement Add(ECFieldElement b) + { + ulong[] z = Nat256.Create64(); + SecT193Field.Add(x, ((SecT193FieldElement)b).x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement AddOne() + { + ulong[] z = Nat256.Create64(); + SecT193Field.AddOne(x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Subtract(ECFieldElement b) + { + // Addition and Subtraction are the same in F2m + return Add(b); + } + + public override ECFieldElement Multiply(ECFieldElement b) + { + ulong[] z = Nat256.Create64(); + SecT193Field.Multiply(x, ((SecT193FieldElement)b).x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement MultiplyMinusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y) + { + return MultiplyPlusProduct(b, x, y); + } + + public override ECFieldElement MultiplyPlusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y) + { + ulong[] ax = this.x, bx = ((SecT193FieldElement)b).x; + ulong[] xx = ((SecT193FieldElement)x).x, yx = ((SecT193FieldElement)y).x; + + ulong[] tt = Nat256.CreateExt64(); + SecT193Field.MultiplyAddToExt(ax, bx, tt); + SecT193Field.MultiplyAddToExt(xx, yx, tt); + + ulong[] z = Nat256.Create64(); + SecT193Field.Reduce(tt, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Divide(ECFieldElement b) + { + return Multiply(b.Invert()); + } + + public override ECFieldElement Negate() + { + return this; + } + + public override ECFieldElement Square() + { + ulong[] z = Nat256.Create64(); + SecT193Field.Square(x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement SquareMinusProduct(ECFieldElement x, ECFieldElement y) + { + return SquarePlusProduct(x, y); + } + + public override ECFieldElement SquarePlusProduct(ECFieldElement x, ECFieldElement y) + { + ulong[] ax = this.x; + ulong[] xx = ((SecT193FieldElement)x).x, yx = ((SecT193FieldElement)y).x; + + ulong[] tt = Nat256.CreateExt64(); + SecT193Field.SquareAddToExt(ax, tt); + SecT193Field.MultiplyAddToExt(xx, yx, tt); + + ulong[] z = Nat256.Create64(); + SecT193Field.Reduce(tt, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement SquarePow(int pow) + { + if (pow < 1) + return this; + + ulong[] z = Nat256.Create64(); + SecT193Field.SquareN(x, pow, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Invert() + { + ulong[] z = Nat256.Create64(); + SecT193Field.Invert(x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Sqrt() + { + return SquarePow(M - 1); + } + + public virtual int Representation + { + get { return F2mFieldElement.Tpb; } + } + + public virtual int M + { + get { return 193; } + } + + public virtual int K1 + { + get { return 15; } + } + + public virtual int K2 + { + get { return 0; } + } + + public virtual int K3 + { + get { return 0; } + } + + public override bool Equals(object obj) + { + return Equals(obj as SecT193FieldElement); + } + + public override bool Equals(ECFieldElement other) + { + return Equals(other as SecT193FieldElement); + } + + public virtual bool Equals(SecT193FieldElement other) + { + if (this == other) + return true; + if (null == other) + return false; + return Nat256.Eq64(x, other.x); + } + + public override int GetHashCode() + { + return 1930015 ^ Arrays.GetHashCode(x, 0, 4); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs new file mode 100644 index 000000000..802954b01 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs @@ -0,0 +1,190 @@ +using System; + +using Org.BouncyCastle.Utilities.Encoders; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R1Curve + : AbstractF2mCurve + { + private const int SecT193R1_DEFAULT_COORDS = COORD_LAMBDA_PROJECTIVE; + + protected readonly SecT193R1Point m_infinity; + + public SecT193R1Curve() + : base(193, 15, 0, 0) + { + this.m_infinity = new SecT193R1Point(this, null, null); + + this.m_a = FromBigInteger(new BigInteger(1, Hex.Decode("0017858FEB7A98975169E171F77B4087DE098AC8A911DF7B01"))); + this.m_b = FromBigInteger(new BigInteger(1, Hex.Decode("00FDFB49BFE6C3A89FACADAA7A1E5BBC7CC1C2E5D831478814"))); + this.m_order = new BigInteger(1, Hex.Decode("01000000000000000000000000C7F34A778F443ACC920EBA49")); + this.m_cofactor = BigInteger.Two; + + this.m_coord = SecT193R1_DEFAULT_COORDS; + } + + protected override ECCurve CloneCurve() + { + return new SecT193R1Curve(); + } + + public override bool SupportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_LAMBDA_PROJECTIVE: + return true; + default: + return false; + } + } + + public override ECPoint Infinity + { + get { return m_infinity; } + } + + public override int FieldSize + { + get { return 193; } + } + + public override ECFieldElement FromBigInteger(BigInteger x) + { + return new SecT193FieldElement(x); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) + { + return new SecT193R1Point(this, x, y, withCompression); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + { + return new SecT193R1Point(this, x, y, zs, withCompression); + } + + public override bool IsKoblitz + { + get { return false; } + } + + /** + * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2). + * + * @param yTilde + * ~yp, an indication bit for the decompression of yp. + * @param X1 + * The field element xp. + * @return the decompressed point. + */ + protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) + { + ECFieldElement x = FromBigInteger(X1), y = null; + if (x.IsZero) + { + y = B.Sqrt(); + } + else + { + ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x); + ECFieldElement z = SolveQuadraticEquation(beta); + if (z != null) + { + if (z.TestBitZero() != (yTilde == 1)) + { + z = z.AddOne(); + } + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + y = z.Add(x); + break; + } + default: + { + y = z.Multiply(x); + break; + } + } + } + } + + if (y == null) + throw new ArgumentException("Invalid point compression"); + + return this.CreateRawPoint(x, y, true); + } + + /** + * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 + * D.1.6) The other solution is <code>z + 1</code>. + * + * @param beta + * The value to solve the quadratic equation for. + * @return the solution for <code>z<sup>2</sup> + z = beta</code> or + * <code>null</code> if no solution exists. + */ + private ECFieldElement SolveQuadraticEquation(ECFieldElement beta) + { + if (beta.IsZero) + { + return beta; + } + + ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero); + + ECFieldElement z = null; + ECFieldElement gamma = null; + + Random rand = new Random(); + do + { + ECFieldElement t = FromBigInteger(new BigInteger(193, rand)); + z = zeroElement; + ECFieldElement w = beta; + for (int i = 1; i < 193; i++) + { + ECFieldElement w2 = w.Square(); + z = z.Square().Add(w2.Multiply(t)); + w = w2.Add(beta); + } + if (!w.IsZero) + return null; + gamma = z.Square().Add(z); + } + while (gamma.IsZero); + + return z; + } + + public virtual int M + { + get { return 193; } + } + + public virtual bool IsTrinomial + { + get { return true; } + } + + public virtual int K1 + { + get { return 15; } + } + + public virtual int K2 + { + get { return 0; } + } + + public virtual int K3 + { + get { return 0; } + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R1Point.cs b/crypto/src/math/ec/custom/sec/SecT193R1Point.cs new file mode 100644 index 000000000..062fce9d4 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R1Point.cs @@ -0,0 +1,283 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R1Point + : AbstractF2mPoint + { + /** + * @deprecated Use ECCurve.createPoint to construct points + */ + public SecT193R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + : this(curve, x, y, false) + { + } + + /** + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(bool)} + */ + public SecT193R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) + : base(curve, x, y, withCompression) + { + if ((x == null) != (y == null)) + throw new ArgumentException("Exactly one of the field elements is null"); + } + + internal SecT193R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + : base(curve, x, y, zs, withCompression) + { + } + + protected override ECPoint Detach() + { + return new SecT193R1Point(null, AffineXCoord, AffineYCoord); + } + + public override ECFieldElement YCoord + { + get + { + ECFieldElement X = RawXCoord, L = RawYCoord; + + if (this.IsInfinity || X.IsZero) + return L; + + // Y is actually Lambda (X + Y/X) here; convert to affine value on the fly + ECFieldElement Y = L.Add(X).Multiply(X); + + ECFieldElement Z = RawZCoords[0]; + if (!Z.IsOne) + { + Y = Y.Divide(Z); + } + + return Y; + } + } + + protected internal override bool CompressionYTilde + { + get + { + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return false; + + ECFieldElement Y = this.RawYCoord; + + // Y is actually Lambda (X + Y/X) here + return Y.TestBitZero() != X.TestBitZero(); + } + } + + public override ECPoint Add(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return this; + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + ECFieldElement X2 = b.RawXCoord; + + if (X1.IsZero) + { + if (X2.IsZero) + return curve.Infinity; + + return b.Add(this); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord, Z2 = b.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement U2 = X2, S2 = L2; + if (!Z1IsOne) + { + U2 = U2.Multiply(Z1); + S2 = S2.Multiply(Z1); + } + + bool Z2IsOne = Z2.IsOne; + ECFieldElement U1 = X1, S1 = L1; + if (!Z2IsOne) + { + U1 = U1.Multiply(Z2); + S1 = S1.Multiply(Z2); + } + + ECFieldElement A = S1.Add(S2); + ECFieldElement B = U1.Add(U2); + + if (B.IsZero) + { + if (A.IsZero) + return Twice(); + + return curve.Infinity; + } + + ECFieldElement X3, L3, Z3; + if (X2.IsZero) + { + // TODO This can probably be optimized quite a bit + ECPoint p = this.Normalize(); + X1 = p.XCoord; + ECFieldElement Y1 = p.YCoord; + + ECFieldElement Y2 = L2; + ECFieldElement L = Y1.Add(Y2).Divide(X1); + + X3 = L.Square().Add(L).Add(X1).Add(curve.A); + if (X3.IsZero) + { + return new SecT193R1Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement Y3 = L.Multiply(X1.Add(X3)).Add(X3).Add(Y1); + L3 = Y3.Divide(X3).Add(X3); + Z3 = curve.FromBigInteger(BigInteger.One); + } + else + { + B = B.Square(); + + ECFieldElement AU1 = A.Multiply(U1); + ECFieldElement AU2 = A.Multiply(U2); + + X3 = AU1.Multiply(AU2); + if (X3.IsZero) + { + return new SecT193R1Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement ABZ2 = A.Multiply(B); + if (!Z2IsOne) + { + ABZ2 = ABZ2.Multiply(Z2); + } + + L3 = AU2.Add(B).SquarePlusProduct(ABZ2, L1.Add(Z1)); + + Z3 = ABZ2; + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + } + + return new SecT193R1Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Twice() + { + if (this.IsInfinity) + { + return this; + } + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return curve.Infinity; + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement L1Z1 = Z1IsOne ? L1 : L1.Multiply(Z1); + ECFieldElement Z1Sq = Z1IsOne ? Z1 : Z1.Square(); + ECFieldElement a = curve.A; + ECFieldElement aZ1Sq = Z1IsOne ? a : a.Multiply(Z1Sq); + ECFieldElement T = L1.Square().Add(L1Z1).Add(aZ1Sq); + if (T.IsZero) + { + return new SecT193R1Point(curve, T, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = T.Square(); + ECFieldElement Z3 = Z1IsOne ? T : T.Multiply(Z1Sq); + + ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); + ECFieldElement L3 = X1Z1.SquarePlusProduct(T, L1Z1).Add(X3).Add(Z3); + + return new SecT193R1Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint TwicePlus(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return Twice(); + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return b; + } + + ECFieldElement X2 = b.RawXCoord, Z2 = b.RawZCoords[0]; + if (X2.IsZero || !Z2.IsOne) + { + return Twice().Add(b); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord; + + ECFieldElement X1Sq = X1.Square(); + ECFieldElement L1Sq = L1.Square(); + ECFieldElement Z1Sq = Z1.Square(); + ECFieldElement L1Z1 = L1.Multiply(Z1); + + ECFieldElement T = curve.A.Multiply(Z1Sq).Add(L1Sq).Add(L1Z1); + ECFieldElement L2plus1 = L2.AddOne(); + ECFieldElement A = curve.A.Add(L2plus1).Multiply(Z1Sq).Add(L1Sq).MultiplyPlusProduct(T, X1Sq, Z1Sq); + ECFieldElement X2Z1Sq = X2.Multiply(Z1Sq); + ECFieldElement B = X2Z1Sq.Add(T).Square(); + + if (B.IsZero) + { + if (A.IsZero) + return b.Twice(); + + return curve.Infinity; + } + + if (A.IsZero) + { + return new SecT193R1Point(curve, A, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = A.Square().Multiply(X2Z1Sq); + ECFieldElement Z3 = A.Multiply(B).Multiply(Z1Sq); + ECFieldElement L3 = A.Add(B).Square().MultiplyPlusProduct(T, L2plus1, Z3); + + return new SecT193R1Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Negate() + { + if (this.IsInfinity) + return this; + + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return this; + + // L is actually Lambda (X + Y/X) here + ECFieldElement L = this.RawYCoord, Z = this.RawZCoords[0]; + return new SecT193R1Point(Curve, X, L.Add(Z), new ECFieldElement[] { Z }, IsCompressed); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs new file mode 100644 index 000000000..b5345730c --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs @@ -0,0 +1,190 @@ +using System; + +using Org.BouncyCastle.Utilities.Encoders; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R2Curve + : AbstractF2mCurve + { + private const int SecT193R2_DEFAULT_COORDS = COORD_LAMBDA_PROJECTIVE; + + protected readonly SecT193R2Point m_infinity; + + public SecT193R2Curve() + : base(193, 15, 0, 0) + { + this.m_infinity = new SecT193R2Point(this, null, null); + + this.m_a = FromBigInteger(new BigInteger(1, Hex.Decode("0163F35A5137C2CE3EA6ED8667190B0BC43ECD69977702709B"))); + this.m_b = FromBigInteger(new BigInteger(1, Hex.Decode("00C9BB9E8927D4D64C377E2AB2856A5B16E3EFB7F61D4316AE"))); + this.m_order = new BigInteger(1, Hex.Decode("010000000000000000000000015AAB561B005413CCD4EE99D5")); + this.m_cofactor = BigInteger.Two; + + this.m_coord = SecT193R2_DEFAULT_COORDS; + } + + protected override ECCurve CloneCurve() + { + return new SecT193R2Curve(); + } + + public override bool SupportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_LAMBDA_PROJECTIVE: + return true; + default: + return false; + } + } + + public override ECPoint Infinity + { + get { return m_infinity; } + } + + public override int FieldSize + { + get { return 193; } + } + + public override ECFieldElement FromBigInteger(BigInteger x) + { + return new SecT193FieldElement(x); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) + { + return new SecT193R2Point(this, x, y, withCompression); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + { + return new SecT193R2Point(this, x, y, zs, withCompression); + } + + public override bool IsKoblitz + { + get { return false; } + } + + /** + * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2). + * + * @param yTilde + * ~yp, an indication bit for the decompression of yp. + * @param X1 + * The field element xp. + * @return the decompressed point. + */ + protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) + { + ECFieldElement x = FromBigInteger(X1), y = null; + if (x.IsZero) + { + y = B.Sqrt(); + } + else + { + ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x); + ECFieldElement z = SolveQuadraticEquation(beta); + if (z != null) + { + if (z.TestBitZero() != (yTilde == 1)) + { + z = z.AddOne(); + } + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + y = z.Add(x); + break; + } + default: + { + y = z.Multiply(x); + break; + } + } + } + } + + if (y == null) + throw new ArgumentException("Invalid point compression"); + + return this.CreateRawPoint(x, y, true); + } + + /** + * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 + * D.1.6) The other solution is <code>z + 1</code>. + * + * @param beta + * The value to solve the quadratic equation for. + * @return the solution for <code>z<sup>2</sup> + z = beta</code> or + * <code>null</code> if no solution exists. + */ + private ECFieldElement SolveQuadraticEquation(ECFieldElement beta) + { + if (beta.IsZero) + { + return beta; + } + + ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero); + + ECFieldElement z = null; + ECFieldElement gamma = null; + + Random rand = new Random(); + do + { + ECFieldElement t = FromBigInteger(new BigInteger(193, rand)); + z = zeroElement; + ECFieldElement w = beta; + for (int i = 1; i < 193; i++) + { + ECFieldElement w2 = w.Square(); + z = z.Square().Add(w2.Multiply(t)); + w = w2.Add(beta); + } + if (!w.IsZero) + return null; + gamma = z.Square().Add(z); + } + while (gamma.IsZero); + + return z; + } + + public virtual int M + { + get { return 193; } + } + + public virtual bool IsTrinomial + { + get { return true; } + } + + public virtual int K1 + { + get { return 15; } + } + + public virtual int K2 + { + get { return 0; } + } + + public virtual int K3 + { + get { return 0; } + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R2Point.cs b/crypto/src/math/ec/custom/sec/SecT193R2Point.cs new file mode 100644 index 000000000..18d89e316 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R2Point.cs @@ -0,0 +1,283 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R2Point + : AbstractF2mPoint + { + /** + * @deprecated Use ECCurve.createPoint to construct points + */ + public SecT193R2Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + : this(curve, x, y, false) + { + } + + /** + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(bool)} + */ + public SecT193R2Point(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) + : base(curve, x, y, withCompression) + { + if ((x == null) != (y == null)) + throw new ArgumentException("Exactly one of the field elements is null"); + } + + internal SecT193R2Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + : base(curve, x, y, zs, withCompression) + { + } + + protected override ECPoint Detach() + { + return new SecT193R2Point(null, AffineXCoord, AffineYCoord); + } + + public override ECFieldElement YCoord + { + get + { + ECFieldElement X = RawXCoord, L = RawYCoord; + + if (this.IsInfinity || X.IsZero) + return L; + + // Y is actually Lambda (X + Y/X) here; convert to affine value on the fly + ECFieldElement Y = L.Add(X).Multiply(X); + + ECFieldElement Z = RawZCoords[0]; + if (!Z.IsOne) + { + Y = Y.Divide(Z); + } + + return Y; + } + } + + protected internal override bool CompressionYTilde + { + get + { + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return false; + + ECFieldElement Y = this.RawYCoord; + + // Y is actually Lambda (X + Y/X) here + return Y.TestBitZero() != X.TestBitZero(); + } + } + + public override ECPoint Add(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return this; + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + ECFieldElement X2 = b.RawXCoord; + + if (X1.IsZero) + { + if (X2.IsZero) + return curve.Infinity; + + return b.Add(this); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord, Z2 = b.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement U2 = X2, S2 = L2; + if (!Z1IsOne) + { + U2 = U2.Multiply(Z1); + S2 = S2.Multiply(Z1); + } + + bool Z2IsOne = Z2.IsOne; + ECFieldElement U1 = X1, S1 = L1; + if (!Z2IsOne) + { + U1 = U1.Multiply(Z2); + S1 = S1.Multiply(Z2); + } + + ECFieldElement A = S1.Add(S2); + ECFieldElement B = U1.Add(U2); + + if (B.IsZero) + { + if (A.IsZero) + return Twice(); + + return curve.Infinity; + } + + ECFieldElement X3, L3, Z3; + if (X2.IsZero) + { + // TODO This can probably be optimized quite a bit + ECPoint p = this.Normalize(); + X1 = p.XCoord; + ECFieldElement Y1 = p.YCoord; + + ECFieldElement Y2 = L2; + ECFieldElement L = Y1.Add(Y2).Divide(X1); + + X3 = L.Square().Add(L).Add(X1).Add(curve.A); + if (X3.IsZero) + { + return new SecT193R2Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement Y3 = L.Multiply(X1.Add(X3)).Add(X3).Add(Y1); + L3 = Y3.Divide(X3).Add(X3); + Z3 = curve.FromBigInteger(BigInteger.One); + } + else + { + B = B.Square(); + + ECFieldElement AU1 = A.Multiply(U1); + ECFieldElement AU2 = A.Multiply(U2); + + X3 = AU1.Multiply(AU2); + if (X3.IsZero) + { + return new SecT193R2Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement ABZ2 = A.Multiply(B); + if (!Z2IsOne) + { + ABZ2 = ABZ2.Multiply(Z2); + } + + L3 = AU2.Add(B).SquarePlusProduct(ABZ2, L1.Add(Z1)); + + Z3 = ABZ2; + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + } + + return new SecT193R2Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Twice() + { + if (this.IsInfinity) + { + return this; + } + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return curve.Infinity; + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement L1Z1 = Z1IsOne ? L1 : L1.Multiply(Z1); + ECFieldElement Z1Sq = Z1IsOne ? Z1 : Z1.Square(); + ECFieldElement a = curve.A; + ECFieldElement aZ1Sq = Z1IsOne ? a : a.Multiply(Z1Sq); + ECFieldElement T = L1.Square().Add(L1Z1).Add(aZ1Sq); + if (T.IsZero) + { + return new SecT193R2Point(curve, T, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = T.Square(); + ECFieldElement Z3 = Z1IsOne ? T : T.Multiply(Z1Sq); + + ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); + ECFieldElement L3 = X1Z1.SquarePlusProduct(T, L1Z1).Add(X3).Add(Z3); + + return new SecT193R2Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint TwicePlus(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return Twice(); + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return b; + } + + ECFieldElement X2 = b.RawXCoord, Z2 = b.RawZCoords[0]; + if (X2.IsZero || !Z2.IsOne) + { + return Twice().Add(b); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord; + + ECFieldElement X1Sq = X1.Square(); + ECFieldElement L1Sq = L1.Square(); + ECFieldElement Z1Sq = Z1.Square(); + ECFieldElement L1Z1 = L1.Multiply(Z1); + + ECFieldElement T = curve.A.Multiply(Z1Sq).Add(L1Sq).Add(L1Z1); + ECFieldElement L2plus1 = L2.AddOne(); + ECFieldElement A = curve.A.Add(L2plus1).Multiply(Z1Sq).Add(L1Sq).MultiplyPlusProduct(T, X1Sq, Z1Sq); + ECFieldElement X2Z1Sq = X2.Multiply(Z1Sq); + ECFieldElement B = X2Z1Sq.Add(T).Square(); + + if (B.IsZero) + { + if (A.IsZero) + return b.Twice(); + + return curve.Infinity; + } + + if (A.IsZero) + { + return new SecT193R2Point(curve, A, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = A.Square().Multiply(X2Z1Sq); + ECFieldElement Z3 = A.Multiply(B).Multiply(Z1Sq); + ECFieldElement L3 = A.Add(B).Square().MultiplyPlusProduct(T, L2plus1, Z3); + + return new SecT193R2Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Negate() + { + if (this.IsInfinity) + return this; + + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return this; + + // L is actually Lambda (X + Y/X) here + ECFieldElement L = this.RawYCoord, Z = this.RawZCoords[0]; + return new SecT193R2Point(Curve, X, L.Add(Z), new ECFieldElement[] { Z }, IsCompressed); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs index 165fadbf3..a2f73fd5d 100644 --- a/crypto/src/math/ec/custom/sec/SecT233Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT233Field.cs @@ -45,6 +45,39 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat256.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion + + ulong[] t0 = Nat256.Create64(); + ulong[] t1 = Nat256.Create64(); + + Square(x, t0); + Multiply(t0, x, t0); + Square(t0, t0); + Multiply(t0, x, t0); + SquareN(t0, 3, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 7, t0); + Multiply(t0, t1, t0); + SquareN(t0, 14, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 29, t0); + Multiply(t0, t1, t0); + SquareN(t0, 58, t1); + Multiply(t1, t0, t1); + SquareN(t1, 116, t0); + Multiply(t0, t1, t0); + Square(t0, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat256.CreateExt64(); @@ -200,7 +233,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 59 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -215,7 +248,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 54; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3; l ^= (g << k); diff --git a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs index 60b204604..a9041efde 100644 --- a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT233FieldElement( - AbstractF2mCurve.Inverse(233, new int[] { 74 }, ToBigInteger())); + ulong[] z = Nat256.Create64(); + SecT233Field.Invert(x, z); + return new SecT233FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT239Field.cs b/crypto/src/math/ec/custom/sec/SecT239Field.cs index 1e0824af9..6b8ad696f 100644 --- a/crypto/src/math/ec/custom/sec/SecT239Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT239Field.cs @@ -45,6 +45,43 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat256.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion + + ulong[] t0 = Nat256.Create64(); + ulong[] t1 = Nat256.Create64(); + + Square(x, t0); + Multiply(t0, x, t0); + Square(t0, t0); + Multiply(t0, x, t0); + SquareN(t0, 3, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 7, t0); + Multiply(t0, t1, t0); + SquareN(t0, 14, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 29, t0); + Multiply(t0, t1, t0); + Square(t0, t0); + Multiply(t0, x, t0); + SquareN(t0, 59, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 119, t0); + Multiply(t0, t1, t0); + Square(t0, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat256.CreateExt64(); @@ -204,7 +241,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 60 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -219,7 +256,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 54; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3; l ^= (g << k); diff --git a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs index e7bfffd1f..de074c55f 100644 --- a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT239FieldElement( - AbstractF2mCurve.Inverse(239, new int[] { 158 }, ToBigInteger())); + ulong[] z = Nat256.Create64(); + SecT239Field.Invert(x, z); + return new SecT239FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT283Field.cs b/crypto/src/math/ec/custom/sec/SecT283Field.cs index 9afb27461..903ea02ff 100644 --- a/crypto/src/math/ec/custom/sec/SecT283Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT283Field.cs @@ -48,6 +48,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat320.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion + + ulong[] t0 = Nat320.Create64(); + ulong[] t1 = Nat320.Create64(); + + Square(x, t0); + Multiply(t0, x, t0); + SquareN(t0, 2, t1); + Multiply(t1, t0, t1); + SquareN(t1, 4, t0); + Multiply(t0, t1, t0); + SquareN(t0, 8, t1); + Multiply(t1, t0, t1); + Square(t1, t1); + Multiply(t1, x, t1); + SquareN(t1, 17, t0); + Multiply(t0, t1, t0); + Square(t0, t0); + Multiply(t0, x, t0); + SquareN(t0, 35, t1); + Multiply(t1, t0, t1); + SquareN(t1, 70, t0); + Multiply(t0, t1, t0); + Square(t0, t0); + Multiply(t0, x, t0); + SquareN(t0, 141, t1); + Multiply(t1, t0, t1); + Square(t1, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat320.CreateExt64(); @@ -292,7 +327,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 57 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -306,7 +341,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 48; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6; diff --git a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs index 9181b8685..e02108f73 100644 --- a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT283FieldElement( - AbstractF2mCurve.Inverse(283, new int[] { 5, 7, 12 }, ToBigInteger())); + ulong[] z = Nat320.Create64(); + SecT283Field.Invert(x, z); + return new SecT283FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT409Field.cs b/crypto/src/math/ec/custom/sec/SecT409Field.cs index d71f5b5f9..84eada96e 100644 --- a/crypto/src/math/ec/custom/sec/SecT409Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT409Field.cs @@ -47,6 +47,57 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat448.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion with bases { 2, 3 } + + ulong[] t0 = Nat448.Create64(); + ulong[] t1 = Nat448.Create64(); + ulong[] t2 = Nat448.Create64(); + + Square(x, t0); + + // 3 | 408 + SquareN(t0, 1, t1); + Multiply(t0, t1, t0); + SquareN(t1, 1, t1); + Multiply(t0, t1, t0); + + // 2 | 136 + SquareN(t0, 3, t1); + Multiply(t0, t1, t0); + + // 2 | 68 + SquareN(t0, 6, t1); + Multiply(t0, t1, t0); + + // 2 | 34 + SquareN(t0, 12, t1); + Multiply(t0, t1, t2); + + // ! {2,3} | 17 + SquareN(t2, 24, t0); + SquareN(t0, 24, t1); + Multiply(t0, t1, t0); + + // 2 | 8 + SquareN(t0, 48, t1); + Multiply(t0, t1, t0); + + // 2 | 4 + SquareN(t0, 96, t1); + Multiply(t0, t1, t0); + + // 2 | 2 + SquareN(t0, 192, t1); + Multiply(t0, t1, t0); + + Multiply(t0, t2, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat448.CreateExt64(); @@ -196,7 +247,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 59 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; diff --git a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs index b60ceafee..581ea73df 100644 --- a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT409FieldElement( - AbstractF2mCurve.Inverse(409, new int[] { 87 }, ToBigInteger())); + ulong[] z = Nat448.Create64(); + SecT409Field.Invert(x, z); + return new SecT409FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT571Field.cs b/crypto/src/math/ec/custom/sec/SecT571Field.cs index 0711ee4aa..fc84e336b 100644 --- a/crypto/src/math/ec/custom/sec/SecT571Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT571Field.cs @@ -59,6 +59,57 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return z; } + public static void Invert(ulong[] x, ulong[] z) + { + if (Nat576.IsZero64(x)) + throw new InvalidOperationException(); + + // Itoh-Tsujii inversion with bases { 2, 3, 5 } + + ulong[] t0 = Nat576.Create64(); + ulong[] t1 = Nat576.Create64(); + ulong[] t2 = Nat576.Create64(); + + Square(x, t2); + + // 5 | 570 + Square(t2, t0); + Square(t0, t1); + Multiply(t0, t1, t0); + SquareN(t0, 2, t1); + Multiply(t0, t1, t0); + Multiply(t0, t2, t0); + + // 3 | 114 + SquareN(t0, 5, t1); + Multiply(t0, t1, t0); + SquareN(t1, 5, t1); + Multiply(t0, t1, t0); + + // 2 | 38 + SquareN(t0, 15, t1); + Multiply(t0, t1, t2); + + // ! {2,3,5} | 19 + SquareN(t2, 30, t0); + SquareN(t0, 30, t1); + Multiply(t0, t1, t0); + + // 3 | 9 + SquareN(t0, 60, t1); + Multiply(t0, t1, t0); + SquareN(t1, 60, t1); + Multiply(t0, t1, t0); + + // 3 | 3 + SquareN(t0, 180, t1); + Multiply(t0, t1, t0); + SquareN(t1, 180, t1); + Multiply(t0, t1, t0); + + Multiply(t0, t2, z); + } + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat576.CreateExt64(); @@ -199,7 +250,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMulwAcc(ulong[] xs, ulong y, ulong[] z, int zOff) { ulong[] u = new ulong[32]; - // u[0] = 0; + //u[0] = 0; u[1] = y; for (int i = 2; i < 32; i += 2) { diff --git a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs index a26e1e336..5d5458412 100644 --- a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT571FieldElement( - AbstractF2mCurve.Inverse(571, new int[] { 2, 5, 10 }, ToBigInteger())); + ulong[] z = Nat576.Create64(); + SecT571Field.Invert(x, z); + return new SecT571FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/raw/Interleave.cs b/crypto/src/math/raw/Interleave.cs index 9755c9d6f..a45ee1e08 100644 --- a/crypto/src/math/raw/Interleave.cs +++ b/crypto/src/math/raw/Interleave.cs @@ -4,67 +4,92 @@ namespace Org.BouncyCastle.Math.Raw { internal abstract class Interleave { + private const ulong M32 = 0x55555555UL; + private const ulong M64 = 0x5555555555555555UL; + /* * This expands 8 bit indices into 16 bit contents (high bit 14), by inserting 0s between bits. * In a binary field, this operation is the same as squaring an 8 bit number. */ - private static readonly ushort[] INTERLEAVE2_TABLE = new ushort[] - { - 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, - 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, - 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, - 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, - 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, - 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, - 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, - 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, - 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, - 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, - 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, - 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, - 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, - 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, - 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, - 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, - 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, - 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, - 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, - 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, - 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, - 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, - 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, - 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, - 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, - 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, - 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, - 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, - 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, - 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, - 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, - 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 - }; + //private static readonly ushort[] INTERLEAVE2_TABLE = new ushort[] + //{ + // 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, + // 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, + // 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, + // 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, + // 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, + // 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, + // 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, + // 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, + // 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, + // 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, + // 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, + // 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, + // 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, + // 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, + // 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, + // 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, + // 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, + // 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, + // 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, + // 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, + // 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, + // 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, + // 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, + // 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, + // 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, + // 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, + // 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, + // 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, + // 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, + // 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, + // 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, + // 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 + //}; internal static uint Expand8to16(uint x) { - return INTERLEAVE2_TABLE[x & 0xFF]; + x &= 0xFFU; + x = (x | (x << 4)) & 0x0F0FU; + x = (x | (x << 2)) & 0x3333U; + x = (x | (x << 1)) & 0x5555U; + return x; } internal static uint Expand16to32(uint x) { - return (uint)(INTERLEAVE2_TABLE[x & 0xFF] | INTERLEAVE2_TABLE[(x >> 8) & 0xFF] << 16); + x &= 0xFFFFU; + x = (x | (x << 8)) & 0x00FF00FFU; + x = (x | (x << 4)) & 0x0F0F0F0FU; + x = (x | (x << 2)) & 0x33333333U; + x = (x | (x << 1)) & 0x55555555U; + return x; } internal static ulong Expand32to64(uint x) { - uint r00 = (uint)(INTERLEAVE2_TABLE[x & 0xFF] | INTERLEAVE2_TABLE[(x >> 8) & 0xFF] << 16); - uint r32 = (uint)(INTERLEAVE2_TABLE[(x >> 16) & 0xFF] | INTERLEAVE2_TABLE[x >> 24] << 16); - return (ulong)r32 << 32 | (ulong)r00; + // "shuffle" low half to even bits and high half to odd bits + uint t; + t = (x ^ (x >> 8)) & 0x0000FF00U; x ^= (t ^ (t << 8)); + t = (x ^ (x >> 4)) & 0x00F000F0U; x ^= (t ^ (t << 4)); + t = (x ^ (x >> 2)) & 0x0C0C0C0CU; x ^= (t ^ (t << 2)); + t = (x ^ (x >> 1)) & 0x22222222U; x ^= (t ^ (t << 1)); + + return ((x >> 1) & M32) << 32 | (x & M32); } internal static void Expand64To128(ulong x, ulong[] z, int zOff) { - z[zOff ] = Expand32to64((uint)x); - z[zOff + 1] = Expand32to64((uint)(x >> 32)); + // "shuffle" low half to even bits and high half to odd bits + ulong t; + t = (x ^ (x >> 16)) & 0x00000000FFFF0000UL; x ^= (t ^ (t << 16)); + t = (x ^ (x >> 8)) & 0x0000FF000000FF00UL; x ^= (t ^ (t << 8)); + t = (x ^ (x >> 4)) & 0x00F000F000F000F0UL; x ^= (t ^ (t << 4)); + t = (x ^ (x >> 2)) & 0x0C0C0C0C0C0C0C0CUL; x ^= (t ^ (t << 2)); + t = (x ^ (x >> 1)) & 0x2222222222222222UL; x ^= (t ^ (t << 1)); + + z[zOff ] = (x ) & M64; + z[zOff + 1] = (x >> 1) & M64; } } } diff --git a/crypto/src/pkix/PkixCertPathChecker.cs b/crypto/src/pkix/PkixCertPathChecker.cs index f22738d89..da7e82b46 100644 --- a/crypto/src/pkix/PkixCertPathChecker.cs +++ b/crypto/src/pkix/PkixCertPathChecker.cs @@ -1,5 +1,3 @@ -using System; -using System.Collections; using Org.BouncyCastle.Utilities.Collections; using Org.BouncyCastle.X509; @@ -82,7 +80,7 @@ namespace Org.BouncyCastle.Pkix * @exception CertPathValidatorException * if the specified certificate does not pass the check */ - public abstract void Check(X509Certificate cert, ICollection unresolvedCritExts); + public abstract void Check(X509Certificate cert, ISet unresolvedCritExts); //throws CertPathValidatorException; /** |