From f52f59b2023546700efd3637d655333184114b7b Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Wed, 5 Mar 2014 23:09:04 +0700 Subject: Improved reduction --- crypto/src/math/ec/custom/sec/SecP192R1Field.cs | 24 +++++++++- crypto/src/math/ec/custom/sec/SecP224R1Field.cs | 46 +++++++++++++----- crypto/src/math/ec/custom/sec/SecP256R1Field.cs | 62 +++++++++++-------------- crypto/src/math/ec/custom/sec/SecP384R1Field.cs | 32 ++++++------- 4 files changed, 101 insertions(+), 63 deletions(-) (limited to 'crypto/src/math/ec/custom') diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs index add8dd410..078ef94f8 100644 --- a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs @@ -127,7 +127,29 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Reduce32(uint x, uint[] z) { - if ((x != 0 && (Nat.AddWordTo(6, x, z) + Nat.AddWordAt(6, x, z, 2) != 0)) + long cc = 0; + + if (x != 0) + { + long xx06 = x; + + cc += (long)z[0] + xx06; + z[0] = (uint)cc; + cc >>= 32; + if (cc != 0) + { + cc += (long)z[1]; + z[1] = (uint)cc; + cc >>= 32; + } + cc += (long)z[2] + xx06; + z[2] = (uint)cc; + cc >>= 32; + + Debug.Assert(cc == 0 || cc == 1); + } + + if ((cc != 0 && Nat.IncAt(6, z, 3) != 0) || (z[5] == P5 && Nat192.Gte(z, P))) { AddPInvTo(z); diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs index 9b29ff3d1..712d6a46d 100644 --- a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs @@ -95,8 +95,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec long t1 = xx08 + xx12; long t2 = xx09 + xx13; + const long n = 1; + long cc = 0; - cc += (long)xx[0] - t0; + cc += (long)xx[0] - t0 + n; z[0] = (uint)cc; cc >>= 32; cc += (long)xx[1] - t1; @@ -105,7 +107,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)xx[2] - t2; z[2] = (uint)cc; cc >>= 32; - cc += (long)xx[3] + t0 - xx10; + cc += (long)xx[3] + t0 - xx10 - n; z[3] = (uint)cc; cc >>= 32; cc += (long)xx[4] + t1 - xx11; @@ -117,21 +119,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)xx[6] + xx10 - xx13; z[6] = (uint)cc; cc >>= 32; + cc += n; - int c = (int)cc; - if (c >= 0) - { - Reduce32((uint)c, z); - } - else - { - SubPInvFrom(z); - } + Debug.Assert(cc >= 0); + + Reduce32((uint)cc, z); } public static void Reduce32(uint x, uint[] z) { - if ((x != 0 && (Nat.SubWordFrom(7, x, z) + Nat.AddWordAt(7, x, z, 3) != 0)) + long cc = 0; + + if (x != 0) + { + long xx07 = x; + + cc += (long)z[0] - xx07; + z[0] = (uint)cc; + cc >>= 32; + if (cc != 0) + { + cc += (long)z[1]; + z[1] = (uint)cc; + cc >>= 32; + cc += (long)z[2]; + z[2] = (uint)cc; + cc >>= 32; + } + cc += (long)z[3] + xx07; + z[3] = (uint)cc; + cc >>= 32; + + Debug.Assert(cc == 0 || cc == 1); + } + + if ((cc != 0 && Nat.IncAt(7, z, 4) != 0) || (z[6] == P6 && Nat224.Gte(z, P))) { AddPInvTo(z); diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs index 383b42a5e..cc2fe4866 100644 --- a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs @@ -11,8 +11,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec internal static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE }; - private static readonly uint[] _2P = new uint[]{ 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000000, - 0x00000002, 0xFFFFFFFE, 0x00000001 }; private const uint P7 = 0xFFFFFFFF; private const uint PExt15 = 0xFFFFFFFE; @@ -98,8 +96,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec long t5 = xx13 + xx14; long t6 = xx14 + xx15; + const long n = 6; + long cc = 0; - cc += (long)xx[0] + t0 - t3 - t5; + cc += (long)xx[0] + t0 - t3 - t5 - n; z[0] = (uint)cc; cc >>= 32; cc += (long)xx[1] + t1 - t4 - t6; @@ -108,7 +108,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)xx[2] + t2 - t5 - xx15; z[2] = (uint)cc; cc >>= 32; - cc += (long)xx[3] + (t3 << 1) + xx13 - xx15 - t0; + cc += (long)xx[3] + (t3 << 1) + xx13 - xx15 - t0 + n; z[3] = (uint)cc; cc >>= 32; cc += (long)xx[4] + (t4 << 1) + xx14 - t1; @@ -117,29 +117,17 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)xx[5] + (t5 << 1) + xx15 - t2; z[5] = (uint)cc; cc >>= 32; - cc += (long)xx[6] + (t6 << 1) + t5 - t0; + cc += (long)xx[6] + (t6 << 1) + t5 - t0 + n; z[6] = (uint)cc; cc >>= 32; - cc += (long)xx[7] + (xx15 << 1) + xx15 + xx08 - t2 - t4; + cc += (long)xx[7] + (xx15 << 1) + xx15 + xx08 - t2 - t4 - n; z[7] = (uint)cc; cc >>= 32; + cc += n; - int c = (int)cc; - if (c >= 0) - { - Reduce32((uint)c, z); - } - else - { - while (c < -1) - { - c += (int)Nat256.AddTo(_2P, z) + 1; - } - while (c < 0) - { - c += (int)Nat256.AddTo(P, z); - } - } + Debug.Assert(cc >= 0); + + Reduce32((uint)cc, z); } public static void Reduce32(uint x, uint[] z) @@ -153,21 +141,27 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)z[0] + xx08; z[0] = (uint)cc; cc >>= 32; - cc += (long)z[1]; - z[1] = (uint)cc; - cc >>= 32; - cc += (long)z[2]; - z[2] = (uint)cc; - cc >>= 32; + if (cc != 0) + { + cc += (long)z[1]; + z[1] = (uint)cc; + cc >>= 32; + cc += (long)z[2]; + z[2] = (uint)cc; + cc >>= 32; + } cc += (long)z[3] - xx08; z[3] = (uint)cc; cc >>= 32; - cc += (long)z[4]; - z[4] = (uint)cc; - cc >>= 32; - cc += (long)z[5]; - z[5] = (uint)cc; - cc >>= 32; + if (cc != 0) + { + cc += (long)z[4]; + z[4] = (uint)cc; + cc >>= 32; + cc += (long)z[5]; + z[5] = (uint)cc; + cc >>= 32; + } cc += (long)z[6] - xx08; z[6] = (uint)cc; cc >>= 32; diff --git a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs index 039c18af8..dc531f4de 100644 --- a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs @@ -95,20 +95,22 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec long xx16 = xx[16], xx17 = xx[17], xx18 = xx[18], xx19 = xx[19]; long xx20 = xx[20], xx21 = xx[21], xx22 = xx[22], xx23 = xx[23]; + const long n = 1; + long cc = 0; - cc += (long)xx[0] + xx12 + xx20 + xx21 - xx23; + cc += (long)xx[0] + xx12 + xx20 + xx21 - xx23 - n; z[0] = (uint)cc; cc >>= 32; - cc += (long)xx[1] + xx13 + xx22 + xx23 - xx12 - xx20; + cc += (long)xx[1] + xx13 + xx22 + xx23 - xx12 - xx20 + n; z[1] = (uint)cc; cc >>= 32; cc += (long)xx[2] + xx14 + xx23 - xx13 - xx21; z[2] = (uint)cc; cc >>= 32; - cc += (long)xx[3] + xx12 + xx15 + xx20 + xx21 - xx14 - xx22 - xx23; + cc += (long)xx[3] + xx12 + xx15 + xx20 + xx21 - xx14 - xx22 - xx23 - n; z[3] = (uint)cc; cc >>= 32; - cc += (long)xx[4] + xx12 + xx13 + xx16 + xx20 + ((xx21 - xx23) << 1) + xx22 - xx15; + cc += (long)xx[4] + xx12 + xx13 + xx16 + xx20 + ((xx21 - xx23) << 1) + xx22 - xx15 - n; z[4] = (uint)cc; cc >>= 32; cc += (long)xx[5] + xx13 + xx14 + xx17 + xx21 + (xx22 << 1) + xx23 - xx16; @@ -132,16 +134,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)xx[11] + xx19 + xx20 + xx23 - xx22; z[11] = (uint)cc; cc >>= 32; + cc += n; - int c = (int)cc; - if (c >= 0) - { - Reduce32((uint)c, z); - } - else - { - SubPInvFrom(z); - } + Debug.Assert(cc >= 0); + + Reduce32((uint)cc, z); } public static void Reduce32(uint x, uint[] z) @@ -158,9 +155,12 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec cc += (long)z[1] - xx12; z[1] = (uint)cc; cc >>= 32; - cc += (long)z[2]; - z[2] = (uint)cc; - cc >>= 32; + if (cc != 0) + { + cc += (long)z[2]; + z[2] = (uint)cc; + cc >>= 32; + } cc += (long)z[3] + xx12; z[3] = (uint)cc; cc >>= 32; -- cgit 1.4.1