From 671252b31dfdbd72fd0fcea2e163e38e5c2fa8fe Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 13 Aug 2015 18:19:24 +0700 Subject: Switch from lookup table to bit twiddling --- crypto/src/math/raw/Interleave.cs | 109 +++++++++++++++++++++++--------------- 1 file changed, 67 insertions(+), 42 deletions(-) (limited to 'crypto/src/math') 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; } } } -- cgit 1.5.1 From dbbd073f7c5081b5e92b1ba685142ea9ff4faeab Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 13 Aug 2015 18:20:55 +0700 Subject: Use Itoh-Tsujii inversion (with extended bases for some cases) --- crypto/src/math/ec/custom/sec/SecT113Field.cs | 29 ++++++++++++ .../src/math/ec/custom/sec/SecT113FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT131Field.cs | 29 ++++++++++++ .../src/math/ec/custom/sec/SecT131FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT163Field.cs | 41 +++++++++++++++++ .../src/math/ec/custom/sec/SecT163FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT193Field.cs | 43 ++++++++++++++++++ .../src/math/ec/custom/sec/SecT193FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT233Field.cs | 33 ++++++++++++++ .../src/math/ec/custom/sec/SecT233FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT239Field.cs | 37 ++++++++++++++++ .../src/math/ec/custom/sec/SecT239FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT283Field.cs | 35 +++++++++++++++ .../src/math/ec/custom/sec/SecT283FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT409Field.cs | 51 ++++++++++++++++++++++ .../src/math/ec/custom/sec/SecT409FieldElement.cs | 5 ++- crypto/src/math/ec/custom/sec/SecT571Field.cs | 51 ++++++++++++++++++++++ .../src/math/ec/custom/sec/SecT571FieldElement.cs | 5 ++- 18 files changed, 376 insertions(+), 18 deletions(-) (limited to 'crypto/src/math') 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 6a1d2a960..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(); 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 165d5b841..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(); 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 index 85db061c3..5154f1e0a 100644 --- a/crypto/src/math/ec/custom/sec/SecT193Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs @@ -44,6 +44,49 @@ 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 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(); diff --git a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs index 995d2ebdd..eba4d10e6 100644 --- a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs @@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - return new SecT193FieldElement( - AbstractF2mCurve.Inverse(193, new int[] { 15 }, ToBigInteger())); + ulong[] z = Nat256.Create64(); + SecT193Field.Invert(x, z); + return new SecT193FieldElement(z); } public override ECFieldElement Sqrt() diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs index b36ffba2e..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(); 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 6dab907dd..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(); 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 435787467..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(); 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 ce6f43f2e..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(); 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 921c841a9..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(); 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() -- cgit 1.5.1 From 00700c43cb02825f64a58f3861c15dab769bf699 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Fri, 14 Aug 2015 19:38:14 +0700 Subject: Add Miller-Rabin methods --- crypto/src/math/Primes.cs | 364 ++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 319 insertions(+), 45 deletions(-) (limited to 'crypto/src/math') diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs index b57977983..55d739f34 100644 --- a/crypto/src/math/Primes.cs +++ b/crypto/src/math/Primes.cs @@ -1,10 +1,14 @@ using System; using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Math { + /** + * Utility methods for generating primes and testing for primality. + */ public static class Primes { private static readonly BigInteger One = BigInteger.One; @@ -12,7 +16,54 @@ namespace Org.BouncyCastle.Math private static readonly BigInteger Three = BigInteger.Three; /** - * Used to return the output from the {@linkplain #generateSTRandomPrime(Digest) Shawe-Taylor Random_Prime Routine} + * Used to return the output from the + * {@linkplain Primes#enhancedMRProbablePrimeTest(BigInteger, SecureRandom, int) Enhanced + * Miller-Rabin Probabilistic Primality Test} + */ + public class MROutput + { + internal static MROutput ProbablyPrime() + { + return new MROutput(false, null); + } + + internal static MROutput ProvablyCompositeWithFactor(BigInteger factor) + { + return new MROutput(true, factor); + } + + internal static MROutput ProvablyCompositeNotPrimePower() + { + return new MROutput(true, null); + } + + private readonly bool mProvablyComposite; + private readonly BigInteger mFactor; + + private MROutput(bool provablyComposite, BigInteger factor) + { + this.mProvablyComposite = provablyComposite; + this.mFactor = factor; + } + + public BigInteger Factor + { + get { return mFactor; } + } + + public bool IsProvablyComposite + { + get { return mProvablyComposite; } + } + + public bool IsNotPrimePower + { + get { return mProvablyComposite && mFactor == null; } + } + } + + /** + * Used to return the output from the {@linkplain Primes#generateSTRandomPrime(Digest, int, byte[]) Shawe-Taylor Random_Prime Routine} */ public class STOutput { @@ -51,11 +102,11 @@ namespace Org.BouncyCastle.Math * @param hash * the {@link Digest} instance to use (as "Hash()"). Cannot be null. * @param length - * the length (in bits) of the prime to be generated. Must be >= 2. + * the length (in bits) of the prime to be generated. Must be at least 2. * @param inputSeed * the seed to be used for the generation of the requested prime. Cannot be null or * empty. - * @returns an {@link STOutput} instance containing the requested prime. + * @return an {@link STOutput} instance containing the requested prime. */ public static STOutput GenerateSTRandomPrime(IDigest hash, int length, byte[] inputSeed) { @@ -71,6 +122,269 @@ namespace Org.BouncyCastle.Math return ImplSTRandomPrime(hash, length, Arrays.Clone(inputSeed)); } + /** + * FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test + * + * Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases. This is an + * alternative to {@link #isMRProbablePrime(BigInteger, SecureRandom, int)} that provides more + * information about a composite candidate, which may be useful when generating or validating + * RSA moduli. + * + * @param candidate + * the {@link BigInteger} instance to test for primality. + * @param random + * the source of randomness to use to choose bases. + * @param iterations + * the number of randomly-chosen bases to perform the test for. + * @return an {@link MROutput} instance that can be further queried for details. + */ + public static MROutput EnhancedMRProbablePrimeTest(BigInteger candidate, SecureRandom random, int iterations) + { + CheckCandidate(candidate, "candidate"); + + if (random == null) + throw new ArgumentNullException("random"); + if (iterations < 1) + throw new ArgumentException("must be > 0", "iterations"); + + if (candidate.BitLength == 2) + return MROutput.ProbablyPrime(); + + if (!candidate.TestBit(0)) + return MROutput.ProvablyCompositeWithFactor(Two); + + BigInteger w = candidate; + BigInteger wSubOne = candidate.Subtract(One); + BigInteger wSubTwo = candidate.Subtract(Two); + + int a = wSubOne.GetLowestSetBit(); + BigInteger m = wSubOne.ShiftRight(a); + + for (int i = 0; i < iterations; ++i) + { + BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random); + BigInteger g = b.Gcd(w); + + if (g.CompareTo(One) > 0) + return MROutput.ProvablyCompositeWithFactor(g); + + BigInteger z = b.ModPow(m, w); + + if (z.Equals(One) || z.Equals(wSubOne)) + continue; + + bool primeToBase = false; + + BigInteger x = z; + for (int j = 1; j < a; ++j) + { + z = z.ModPow(Two, w); + + if (z.Equals(wSubOne)) + { + primeToBase = true; + break; + } + + if (z.Equals(One)) + break; + + x = z; + } + + if (!primeToBase) + { + if (!z.Equals(One)) + { + x = z; + z = z.ModPow(Two, w); + + if (!z.Equals(One)) + { + x = z; + } + } + + g = x.Subtract(One).Gcd(w); + + if (g.CompareTo(One) > 0) + return MROutput.ProvablyCompositeWithFactor(g); + + return MROutput.ProvablyCompositeNotPrimePower(); + } + } + + return MROutput.ProbablyPrime(); + } + + /** + * A fast check for small divisors, up to some implementation-specific limit. + * + * @param candidate + * the {@link BigInteger} instance to test for division by small factors. + * + * @return true if the candidate is found to have any small factors, + * false otherwise. + */ + public static bool HasAnySmallFactors(BigInteger candidate) + { + CheckCandidate(candidate, "candidate"); + + return ImplHasAnySmallFactors(candidate); + } + + /** + * FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test + * + * Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases. + * + * @param candidate + * the {@link BigInteger} instance to test for primality. + * @param random + * the source of randomness to use to choose bases. + * @param iterations + * the number of randomly-chosen bases to perform the test for. + * @return false if any witness to compositeness is found amongst the chosen bases + * (so candidate is definitely NOT prime), or else true + * (indicating primality with some probability dependent on the number of iterations + * that were performed). + */ + public static bool IsMRProbablePrime(BigInteger candidate, SecureRandom random, int iterations) + { + CheckCandidate(candidate, "candidate"); + + if (random == null) + throw new ArgumentException("cannot be null", "random"); + if (iterations < 1) + throw new ArgumentException("must be > 0", "iterations"); + + if (candidate.BitLength == 2) + return true; + if (!candidate.TestBit(0)) + return false; + + BigInteger w = candidate; + BigInteger wSubOne = candidate.Subtract(One); + BigInteger wSubTwo = candidate.Subtract(Two); + + int a = wSubOne.GetLowestSetBit(); + BigInteger m = wSubOne.ShiftRight(a); + + for (int i = 0; i < iterations; ++i) + { + BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random); + + if (!ImplMRProbablePrimeToBase(w, wSubOne, m, a, b)) + return false; + } + + return true; + } + + /** + * FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test (to a fixed base). + * + * Run a single iteration of the Miller-Rabin algorithm against the specified base. + * + * @param candidate + * the {@link BigInteger} instance to test for primality. + * @param baseValue + * the base value to use for this iteration. + * @return false if the specified base is a witness to compositeness (so + * candidate is definitely NOT prime), or else true. + */ + public static bool IsMRProbablePrimeToBase(BigInteger candidate, BigInteger baseValue) + { + CheckCandidate(candidate, "candidate"); + CheckCandidate(baseValue, "baseValue"); + + if (baseValue.CompareTo(candidate.Subtract(One)) >= 0) + throw new ArgumentException("must be < ('candidate' - 1)", "baseValue"); + + if (candidate.BitLength == 2) + return true; + + BigInteger w = candidate; + BigInteger wSubOne = candidate.Subtract(One); + + int a = wSubOne.GetLowestSetBit(); + BigInteger m = wSubOne.ShiftRight(a); + + return ImplMRProbablePrimeToBase(w, wSubOne, m, a, baseValue); + } + + private static void CheckCandidate(BigInteger n, string name) + { + if (n == null || n.SignValue < 1 || n.BitLength < 2) + throw new ArgumentException("must be non-null and >= 2", name); + } + + private static bool ImplHasAnySmallFactors(BigInteger x) + { + /* + * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders. + */ + int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23; + int r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0 + && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0) + { + m = 29 * 31 * 37 * 41 * 43; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0) + { + m = 47 * 53 * 59 * 61 * 67; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0) + { + m = 71 * 73 * 79 * 83; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0) + { + m = 89 * 97 * 101 * 103; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0) + { + m = 107 * 109 * 113 * 127; + r = x.Mod(BigInteger.ValueOf(m)).IntValue; + if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0) + { + return false; + } + } + } + } + } + } + return true; + } + + private static bool ImplMRProbablePrimeToBase(BigInteger w, BigInteger wSubOne, BigInteger m, int a, BigInteger b) + { + BigInteger z = b.ModPow(m, w); + + if (z.Equals(One) || z.Equals(wSubOne)) + return true; + + bool result = false; + + for (int j = 1; j < a; ++j) + { + z = z.ModPow(Two, w); + + if (z.Equals(wSubOne)) + { + result = true; + break; + } + + if (z.Equals(One)) + return false; + } + + return result; + } + private static STOutput ImplSTRandomPrime(IDigest d, int length, byte[] primeSeed) { int dLen = d.GetDigestSize(); @@ -131,7 +445,7 @@ namespace Org.BouncyCastle.Math /* * TODO Since the candidate primes are generated by constant steps ('c0x2'), - * sieving could be used here in place of the 'mightBePrime' approach. + * sieving could be used here in place of the 'HasAnySmallFactors' approach. */ for (;;) { @@ -149,7 +463,7 @@ namespace Org.BouncyCastle.Math * * NOTE: 'primeSeed' is still incremented as if we performed the full check! */ - if (MightBePrime(c)) + if (!ImplHasAnySmallFactors(c)) { BigInteger a = HashGen(d, primeSeed, iterations + 1); a = a.Mod(c.Subtract(Three)).Add(Two); @@ -266,45 +580,5 @@ namespace Org.BouncyCastle.Math } } } - - private static bool MightBePrime(BigInteger x) - { - /* - * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders. - */ - int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23; - int r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0 - && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0) - { - m = 29 * 31 * 37 * 41 * 43; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0) - { - m = 47 * 53 * 59 * 61 * 67; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0) - { - m = 71 * 73 * 79 * 83; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0) - { - m = 89 * 97 * 101 * 103; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0) - { - m = 107 * 109 * 113 * 127; - r = x.Mod(BigInteger.ValueOf(m)).IntValue; - if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0) - { - return true; - } - } - } - } - } - } - return false; - } } } -- cgit 1.5.1 From 17913b62ebcc11a32df5d9207a2daa06205cff01 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Sun, 6 Sep 2015 17:40:54 +0700 Subject: Fix class declaration --- crypto/src/math/Primes.cs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'crypto/src/math') diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs index 55d739f34..420c3cc5a 100644 --- a/crypto/src/math/Primes.cs +++ b/crypto/src/math/Primes.cs @@ -9,7 +9,7 @@ namespace Org.BouncyCastle.Math /** * Utility methods for generating primes and testing for primality. */ - public static class Primes + public abstract class Primes { private static readonly BigInteger One = BigInteger.One; private static readonly BigInteger Two = BigInteger.Two; -- cgit 1.5.1 From 1391032b1062eb16f527223d8b9c56216ed5da86 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Wed, 14 Oct 2015 14:07:03 +0700 Subject: Consolidate all F2m decompression methods into AbstractF2m --- crypto/src/math/ec/ECCurve.cs | 194 ++++++++++++------------ crypto/src/math/ec/custom/sec/SecT113R1Curve.cs | 92 +---------- crypto/src/math/ec/custom/sec/SecT113R2Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT131R1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT131R2Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT163K1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT163R1Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT163R2Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT193R1Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT193R2Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT233K1Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT233R1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT239K1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT283K1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT283R1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT409K1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT409R1Curve.cs | 90 ----------- crypto/src/math/ec/custom/sec/SecT571K1Curve.cs | 92 ----------- crypto/src/math/ec/custom/sec/SecT571R1Curve.cs | 91 ----------- 19 files changed, 96 insertions(+), 1735 deletions(-) (limited to 'crypto/src/math') diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 9fe9e32fd..40b46ce72 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -677,28 +677,110 @@ namespace Org.BouncyCastle.Math.EC switch (this.CoordinateSystem) { - case COORD_LAMBDA_AFFINE: - case COORD_LAMBDA_PROJECTIVE: - { - if (X.IsZero) + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: { - if (!Y.Square().Equals(B)) - throw new ArgumentException(); + if (X.IsZero) + { + if (!Y.Square().Equals(B)) + throw new ArgumentException(); + } + else + { + // Y becomes Lambda (X + Y/X) here + Y = Y.Divide(X).Add(X); + } + break; } - else + default: { - // Y becomes Lambda (X + Y/X) here - Y = Y.Divide(X).Add(X); + break; } - break; } - default: + + return CreateRawPoint(X, Y, withCompression); + } + + protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) + { + ECFieldElement xp = FromBigInteger(X1), yp = null; + if (xp.IsZero) { - break; + yp = B.Sqrt(); } + else + { + ECFieldElement beta = xp.Square().Invert().Multiply(B).Add(A).Add(xp); + ECFieldElement z = SolveQuadradicEquation(beta); + + if (z != null) + { + if (z.TestBitZero() != (yTilde == 1)) + { + z = z.AddOne(); + } + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + yp = z.Add(xp); + break; + } + default: + { + yp = z.Multiply(xp); + break; + } + } + } } - return CreateRawPoint(X, Y, withCompression); + if (yp == null) + throw new ArgumentException("Invalid point compression"); + + return CreateRawPoint(xp, yp, true); + } + + /** + * Solves a quadratic equation z2 + z = beta(X9.62 + * D.1.6) The other solution is z + 1. + * + * @param beta + * The value to solve the qradratic equation for. + * @return the solution for z2 + z = beta or + * null if no solution exists. + */ + private ECFieldElement SolveQuadradicEquation(ECFieldElement beta) + { + if (beta.IsZero) + return beta; + + ECFieldElement gamma, z, zeroElement = FromBigInteger(BigInteger.Zero); + + int m = FieldSize; + Random rand = new Random(); + do + { + ECFieldElement t = FromBigInteger(new BigInteger(m, rand)); + z = zeroElement; + ECFieldElement w = beta; + for (int i = 1; i < m; 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; } /** @@ -994,92 +1076,6 @@ namespace Org.BouncyCastle.Math.EC get { return m_infinity; } } - protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) - { - ECFieldElement xp = FromBigInteger(X1), yp = null; - if (xp.IsZero) - { - yp = m_b.Sqrt(); - } - else - { - ECFieldElement beta = xp.Square().Invert().Multiply(B).Add(A).Add(xp); - ECFieldElement z = SolveQuadradicEquation(beta); - - if (z != null) - { - if (z.TestBitZero() != (yTilde == 1)) - { - z = z.AddOne(); - } - - switch (this.CoordinateSystem) - { - case COORD_LAMBDA_AFFINE: - case COORD_LAMBDA_PROJECTIVE: - { - yp = z.Add(xp); - break; - } - default: - { - yp = z.Multiply(xp); - break; - } - } - } - } - - if (yp == null) - throw new ArgumentException("Invalid point compression"); - - return CreateRawPoint(xp, yp, true); - } - - /** - * Solves a quadratic equation z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the qradratic equation for. - * @return the solution for z2 + z = beta or - * null if no solution exists. - */ - private ECFieldElement SolveQuadradicEquation(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(m, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < m; 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 int M { get { return m; } diff --git a/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs index 04e69e2a8..2705c94aa 100644 --- a/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT113R1Curve.cs @@ -65,101 +65,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecT113R1Point(this, x, y, zs, withCompression); } - public override bool IsKoblitz + 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(113, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 113; 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 113; } diff --git a/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs index a02db6b25..abfd26d5b 100644 --- a/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT113R2Curve.cs @@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(113, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 113; 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 113; } diff --git a/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs index 789e3c0c3..b73964c39 100644 --- a/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT131R1Curve.cs @@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(131, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 131; 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 131; } diff --git a/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs index 2004f84ca..724921c94 100644 --- a/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT131R2Curve.cs @@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(131, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 131; 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 131; } diff --git a/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs index 1cfd09e1c..68ff646ca 100644 --- a/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT163K1Curve.cs @@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec get { return true; } } - /** - * 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(163, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 163; 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 163; } diff --git a/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs index fc18e1094..8ae58ccef 100644 --- a/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT163R1Curve.cs @@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(163, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 163; 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 163; } diff --git a/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs index 9efe11c3e..5a4fa5ad1 100644 --- a/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT163R2Curve.cs @@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(163, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 163; 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 163; } diff --git a/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs index 802954b01..a2cb5a8ac 100644 --- a/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs @@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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; } diff --git a/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs index b5345730c..1c84a3eac 100644 --- a/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs @@ -70,98 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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; } diff --git a/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs index 8768eaa81..72935913d 100644 --- a/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT233K1Curve.cs @@ -76,98 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec get { return true; } } - /** - * 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(233, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 233; 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 233; } diff --git a/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs index 92795b8a7..db6e6e1d4 100644 --- a/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT233R1Curve.cs @@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(233, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 233; 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 233; } diff --git a/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs index 2c73d941f..a499d48b4 100644 --- a/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT239K1Curve.cs @@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec get { return true; } } - /** - * 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(239, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 239; 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 239; } diff --git a/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs index 42414401f..4053287ec 100644 --- a/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT283K1Curve.cs @@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec get { return true; } } - /** - * 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(283, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 283; 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 283; } diff --git a/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs index d8c462eeb..e659675ce 100644 --- a/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT283R1Curve.cs @@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(283, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 283; 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 283; } diff --git a/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs index edfe1a293..4f573553e 100644 --- a/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT409K1Curve.cs @@ -76,96 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec get { return true; } } - /** - * 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(409, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 409; 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 409; } diff --git a/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs index e679094ad..9212fb5d2 100644 --- a/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT409R1Curve.cs @@ -70,96 +70,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(409, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 409; 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 409; } diff --git a/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs b/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs index fb136c967..f5806f09c 100644 --- a/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT571K1Curve.cs @@ -76,98 +76,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec get { return true; } } - /** - * 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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(571, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 571; 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 571; } diff --git a/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs index 05d58863e..082afa5bd 100644 --- a/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecT571R1Curve.cs @@ -74,97 +74,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec 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(); - y = SecT571R1_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 z2 + z = beta(X9.62 - * D.1.6) The other solution is z + 1. - * - * @param beta - * The value to solve the quadratic equation for. - * @return the solution for z2 + z = beta or - * null 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(571, rand)); - z = zeroElement; - ECFieldElement w = beta; - for (int i = 1; i < 571; 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 571; } -- cgit 1.5.1