diff options
Diffstat (limited to 'crypto/src/math/ec')
18 files changed, 159 insertions, 739 deletions
diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs index ef10dbf90..ed530b6b7 100644 --- a/crypto/src/math/ec/ECFieldElement.cs +++ b/crypto/src/math/ec/ECFieldElement.cs @@ -1,7 +1,6 @@ using System; using System.Diagnostics; -using Org.BouncyCastle.Math.Raw; using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Math.EC @@ -434,13 +433,7 @@ namespace Org.BouncyCastle.Math.EC protected virtual BigInteger ModInverse(BigInteger x) { - int bits = FieldSize; - int len = (bits + 31) >> 5; - uint[] p = Nat.FromBigInteger(bits, q); - uint[] n = Nat.FromBigInteger(bits, x); - uint[] z = Nat.Create(len); - Mod.Invert(p, n, z); - return Nat.ToBigInteger(len, z); + return BigIntegers.ModOddInverse(q, x); } protected virtual BigInteger ModMult(BigInteger x1, BigInteger x2) diff --git a/crypto/src/math/ec/custom/djb/Curve25519Field.cs b/crypto/src/math/ec/custom/djb/Curve25519Field.cs index 4e4cfbaa5..0006acd94 100644 --- a/crypto/src/math/ec/custom/djb/Curve25519Field.cs +++ b/crypto/src/math/ec/custom/djb/Curve25519Field.cs @@ -70,56 +70,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Djb public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^255 - 21 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 250 1s } { 1 0s } { 1 1s } { 1 0s } { 2 1s } - * - * Therefore we need an addition chain containing 1, 2, 250 (the lengths of the repunits) - * We use: [1], [2], 3, 5, 10, 15, 25, 50, 75, 125, [250] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat256.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat256.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x5 = x3; - SquareN(x3, 2, x5); - Multiply(x5, x2, x5); - uint[] x10 = Nat256.Create(); - SquareN(x5, 5, x10); - Multiply(x10, x5, x10); - uint[] x15 = Nat256.Create(); - SquareN(x10, 5, x15); - Multiply(x15, x5, x15); - uint[] x25 = x5; - SquareN(x15, 10, x25); - Multiply(x25, x10, x25); - uint[] x50 = x10; - SquareN(x25, 25, x50); - Multiply(x50, x25, x50); - uint[] x75 = x15; - SquareN(x50, 25, x75); - Multiply(x75, x25, x75); - uint[] x125 = x25; - SquareN(x75, 50, x125); - Multiply(x125, x50, x125); - uint[] x250 = x50; - SquareN(x125, 125, x250); - Multiply(x250, x125, x250); - - uint[] t = x250; - SquareN(t, 2, t); - Multiply(t, x1, t); - SquareN(t, 3, t); - Multiply(t, x2, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs b/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs index 55596b844..38743189a 100644 --- a/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs +++ b/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs @@ -57,60 +57,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^256 - 2^224 - 2^96 + 2^64 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 31 1s } { 1 0s } { 128 1s } { 32 0s } { 62 1s } { 1 0s } { 1 1s } - * - * We use an addition chain for the beginning: [1], 2, [4], 6, 12, 24, 30, [31] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat256.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x4 = Nat256.Create(); - SquareN(x2, 2, x4); - Multiply(x4, x2, x4); - uint[] x6 = Nat256.Create(); - SquareN(x4, 2, x6); - Multiply(x6, x2, x6); - uint[] x12 = x2; - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x24 = Nat256.Create(); - SquareN(x12, 12, x24); - Multiply(x24, x12, x24); - uint[] x30 = x12; - SquareN(x24, 6, x30); - Multiply(x30, x6, x30); - uint[] x31 = x6; - Square(x30, x31); - Multiply(x31, x1, x31); - - uint[] t = x24; - SquareN(x31, 32, t); - Multiply(t, x31, t); - SquareN(t, 31, t); - Multiply(t, x31, t); - SquareN(t, 31, t); - Multiply(t, x31, t); - SquareN(t, 31, t); - Multiply(t, x31, t); - SquareN(t, 4, t); - Multiply(t, x4, t); - SquareN(t, 63, t); - Multiply(t, x31, t); - SquareN(t, 31, t); - Multiply(t, x31, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static void Half(uint[] x, uint[] z) diff --git a/crypto/src/math/ec/custom/sec/SecP128R1Field.cs b/crypto/src/math/ec/custom/sec/SecP128R1Field.cs index 23ea361a0..03a07f79b 100644 --- a/crypto/src/math/ec/custom/sec/SecP128R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP128R1Field.cs @@ -70,51 +70,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^128 - 2^97 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 30 1s } { 1 0s } { 95 1s } { 1 0s } { 1 1s } - * - * We use an addition chain for the beginning: [1], 2, 3, [5], 10, 20, [30] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat128.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat128.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x5 = x3; - SquareN(x3, 2, x5); - Multiply(x5, x2, x5); - uint[] x10 = x2; - SquareN(x5, 5, x10); - Multiply(x10, x5, x10); - uint[] x20 = Nat128.Create(); - SquareN(x10, 10, x20); - Multiply(x20, x10, x20); - uint[] x30 = x20; - SquareN(x20, 10, x30); - Multiply(x30, x10, x30); - - uint[] t = x10; - SquareN(x30, 31, t); - Multiply(t, x30, t); - SquareN(t, 30, t); - Multiply(t, x30, t); - SquareN(t, 30, t); - Multiply(t, x30, t); - SquareN(t, 5, t); - Multiply(t, x5, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP160R1Field.cs b/crypto/src/math/ec/custom/sec/SecP160R1Field.cs index 139cd80d6..31c957301 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R1Field.cs @@ -74,58 +74,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^160 - 2^31 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 128 1s } { 1 0s } { 29 1s } { 1 0s } { 1 1s } - * - * Therefore we need an addition chain containing 1, 29, 128 (the lengths of the repunits) - * We use: [1], 2, 3, 6, 12, 24, 27, [29], 32, 64, [128] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat160.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat160.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat160.Create(); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x12 = Nat160.Create(); - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x24 = x6; - SquareN(x12, 12, x24); - Multiply(x24, x12, x24); - uint[] x27 = x12; - SquareN(x24, 3, x27); - Multiply(x27, x3, x27); - uint[] x29 = x24; - SquareN(x27, 2, x29); - Multiply(x29, x2, x29); - uint[] x32 = x2; - SquareN(x29, 3, x32); - Multiply(x32, x3, x32); - uint[] x64 = x3; - SquareN(x32, 32, x64); - Multiply(x64, x32, x64); - uint[] x128 = x27; - SquareN(x64, 64, x128); - Multiply(x128, x64, x128); - - uint[] t = x128; - SquareN(t, 30, t); - Multiply(t, x29, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP160R2Field.cs b/crypto/src/math/ec/custom/sec/SecP160R2Field.cs index bc36d9de1..55f02e438 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R2Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R2Field.cs @@ -74,70 +74,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^160 - 2^32 - 2^14 - 2^12 - 2^9 - 2^8 - 2^7 - 2^3 - 2^2 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 127 1s } { 1 0s } { 17 1s } "010110001110001" - * - * Therefore we need an addition chain containing 1, 2, 3, 17, 127 (the lengths of the repunits) - * We use: 1, 2, 3, 6, 12, 15, [17], 34, 68, 102, 119, 125, [127] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat160.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat160.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat160.Create(); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x12 = Nat160.Create(); - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x15 = x12; - SquareN(x12, 3, x15); - Multiply(x15, x3, x15); - uint[] x17 = x15; - SquareN(x15, 2, x17); - Multiply(x17, x2, x17); - uint[] x34 = Nat160.Create(); - SquareN(x17, 17, x34); - Multiply(x34, x17, x34); - uint[] x68 = Nat160.Create(); - SquareN(x34, 34, x68); - Multiply(x68, x34, x68); - uint[] x102 = x68; - SquareN(x68, 34, x102); - Multiply(x102, x34, x102); - uint[] x119 = x34; - SquareN(x102, 17, x119); - Multiply(x119, x17, x119); - uint[] x125 = x102; - SquareN(x119, 6, x125); - Multiply(x125, x6, x125); - uint[] x127 = x6; - SquareN(x125, 2, x127); - Multiply(x127, x2, x127); - - uint[] t = x127; - SquareN(t, 18, t); - Multiply(t, x17, t); - SquareN(t, 2, t); - Multiply(t, x1, t); - SquareN(t, 3, t); - Multiply(t, x2, t); - SquareN(t, 6, t); - Multiply(t, x3, t); - SquareN(t, 4, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs index 30d53f7dc..23bd732bd 100644 --- a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs @@ -75,67 +75,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^192 - 2^32 - 2^12 - 2^8 - 2^7 - 2^6 - 2^3 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 159 1s } { 1 0s } { 19 1s } { 1 0s } { 3 1s } "000110101" - * - * Therefore we need an addition chain containing 1, 2, 3, 19, 159 (the lengths of the repunits) - * We use: [1], [2], [3], 6, 12, 18, [19], 38, 76, 152, 158, [159] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat192.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat192.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat192.Create(); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x12 = Nat192.Create(); - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x18 = x12; - SquareN(x12, 6, x18); - Multiply(x18, x6, x18); - uint[] x19 = x18; - Square(x18, x19); - Multiply(x19, x1, x19); - uint[] x38 = Nat192.Create(); - SquareN(x19, 19, x38); - Multiply(x38, x19, x38); - uint[] x76 = Nat192.Create(); - SquareN(x38, 38, x76); - Multiply(x76, x38, x76); - uint[] x152 = x38; - SquareN(x76, 76, x152); - Multiply(x152, x76, x152); - uint[] x158 = x76; - SquareN(x152, 6, x158); - Multiply(x158, x6, x158); - uint[] x159 = x6; - Square(x158, x159); - Multiply(x159, x1, x159); - - uint[] t = x159; - SquareN(t, 20, t); - Multiply(t, x19, t); - SquareN(t, 4, t); - Multiply(t, x3, t); - SquareN(t, 5, t); - Multiply(t, x2, t); - SquareN(t, 2, t); - Multiply(t, x1, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs index 2061d1359..a4fb4bb76 100644 --- a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs @@ -74,58 +74,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^192 - 2^64 - 1 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 127 1s } { 1 0s } { 62 1s } { 1 0s } { 1 1s } - * - * Therefore we need an addition chain containing 1, 62, 127 (the lengths of the repunits) - * We use: [1], 2, 3, 6, 12, 24, 30, 32, [62], 65, [127] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat192.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat192.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat192.Create(); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x12 = Nat192.Create(); - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x24 = Nat192.Create(); - SquareN(x12, 12, x24); - Multiply(x24, x12, x24); - uint[] x30 = x12; - SquareN(x24, 6, x30); - Multiply(x30, x6, x30); - uint[] x32 = x6; - SquareN(x30, 2, x32); - Multiply(x32, x2, x32); - uint[] x62 = x2; - SquareN(x32, 30, x62); - Multiply(x62, x30, x62); - uint[] x65 = x24; - SquareN(x62, 3, x65); - Multiply(x65, x3, x65); - uint[] x127 = x3; - SquareN(x65, 62, x127); - Multiply(x127, x62, x127); - - uint[] t = x127; - SquareN(t, 63, t); - Multiply(t, x62, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs index d20ac63f3..5d4237708 100644 --- a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs @@ -76,67 +76,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^224 - 2^32 - 2^12 - 2^11 - 2^9 - 2^7 - 2^4 - 5 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 191 1s } { 1 0s } { 19 1s } "0010101101011" - * - * Therefore we need an addition chain containing 1, 2, 19, 191 (the lengths of the repunits) - * We use: [1], [2], 4, 5, 9, 10, [19], 38, 76, 152, 190 [191] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat224.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x4 = Nat224.Create(); - SquareN(x2, 2, x4); - Multiply(x4, x2, x4); - uint[] x5 = Nat224.Create(); - Square(x4, x5); - Multiply(x5, x1, x5); - uint[] x9 = x5; - SquareN(x5, 4, x9); - Multiply(x9, x4, x9); - uint[] x10 = x4; - Square(x9, x10); - Multiply(x10, x1, x10); - uint[] x19 = x10; - SquareN(x10, 9, x19); - Multiply(x19, x9, x19); - uint[] x38 = x9; - SquareN(x19, 19, x38); - Multiply(x38, x19, x38); - uint[] x76 = Nat224.Create(); - SquareN(x38, 38, x76); - Multiply(x76, x38, x76); - uint[] x152 = Nat224.Create(); - SquareN(x76, 76, x152); - Multiply(x152, x76, x152); - uint[] x190 = x76; - SquareN(x152, 38, x190); - Multiply(x190, x38, x190); - uint[] x191 = x38; - Square(x190, x191); - Multiply(x191, x1, x191); - - uint[] t = x191; - SquareN(t, 20, t); - Multiply(t, x19, t); - SquareN(t, 3, t); - Multiply(t, x1, t); - SquareN(t, 2, t); - Multiply(t, x1, t); - SquareN(t, 3, t); - Multiply(t, x2, t); - SquareN(t, 2, t); - Multiply(t, x1, t); - SquareN(t, 3, t); - Multiply(t, x2, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs index 06d451c2b..dde291d5e 100644 --- a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs @@ -75,54 +75,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^224 - 2^96 - 1 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 127 1s } { 1 0s } { 96 1s } - * - * Therefore we need an addition chain containing 96, 127 (the lengths of the repunits) - * We use: 1, 2, 3, 6, 12, 24, 48, [96], 120, 126, [127] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat224.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = x2; - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat224.Create(); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x12 = x3; - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x24 = Nat224.Create(); - SquareN(x12, 12, x24); - Multiply(x24, x12, x24); - uint[] x48 = x12; - SquareN(x24, 24, x48); - Multiply(x48, x24, x48); - uint[] x96 = Nat224.Create(); - SquareN(x48, 48, x96); - Multiply(x96, x48, x96); - uint[] x120 = x48; - SquareN(x96, 24, x120); - Multiply(x120, x24, x120); - uint[] x126 = x24; - SquareN(x120, 6, x126); - Multiply(x126, x6, x126); - uint[] x127 = x6; - Square(x126, x127); - Multiply(x127, x1, x127); - - uint[] t = x127; - SquareN(t, 97, t); - Multiply(t, x96, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs index 2193c94e6..acdb1f362 100644 --- a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs @@ -76,65 +76,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 223 1s } { 1 0s } { 22 1s } { 4 0s } { 1 1s } { 1 0s } { 2 1s } { 1 0s } { 1 1s } - * - * Therefore we need an addition chain containing 1, 2, 22, 223 (the lengths of the repunits) - * We use: [1], [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat256.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat256.Create(); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat256.Create(); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x9 = x6; - SquareN(x6, 3, x9); - Multiply(x9, x3, x9); - uint[] x11 = x9; - SquareN(x9, 2, x11); - Multiply(x11, x2, x11); - uint[] x22 = Nat256.Create(); - SquareN(x11, 11, x22); - Multiply(x22, x11, x22); - uint[] x44 = x11; - SquareN(x22, 22, x44); - Multiply(x44, x22, x44); - uint[] x88 = Nat256.Create(); - SquareN(x44, 44, x88); - Multiply(x88, x44, x88); - uint[] x176 = Nat256.Create(); - SquareN(x88, 88, x176); - Multiply(x176, x88, x176); - uint[] x220 = x88; - SquareN(x176, 44, x220); - Multiply(x220, x44, x220); - uint[] x223 = x44; - SquareN(x220, 3, x223); - Multiply(x223, x3, x223); - - uint[] t = x223; - SquareN(t, 23, t); - Multiply(t, x22, t); - SquareN(t, 5, t); - Multiply(t, x1, t); - SquareN(t, 3, t); - Multiply(t, x2, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs index eadc7ee58..668efc895 100644 --- a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs @@ -70,60 +70,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^256 - 2^224 + 2^192 + 2^96 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 32 1s } { 31 0s } { 1 1s } { 96 0s } { 94 1s } { 1 0s } { 1 1s } - * - * Therefore we need an addition chain containing 1, 32, 94 (the lengths of the repunits) - * We use: [1], 2, 4, 8, 16, [32], 64, 80, 88, 92, [94] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat256.Create(); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x4 = Nat256.Create(); - SquareN(x2, 2, x4); - Multiply(x4, x2, x4); - uint[] x8 = Nat256.Create(); - SquareN(x4, 4, x8); - Multiply(x8, x4, x8); - uint[] x16 = Nat256.Create(); - SquareN(x8, 8, x16); - Multiply(x16, x8, x16); - uint[] x32 = Nat256.Create(); - SquareN(x16, 16, x32); - Multiply(x32, x16, x32); - uint[] x64 = Nat256.Create(); - SquareN(x32, 32, x64); - Multiply(x64, x32, x64); - uint[] x80 = x64; - SquareN(x64, 16, x80); - Multiply(x80, x16, x80); - uint[] x88 = x16; - SquareN(x80, 8, x88); - Multiply(x88, x8, x88); - uint[] x92 = x8; - SquareN(x88, 4, x92); - Multiply(x92, x4, x92); - uint[] x94 = x4; - SquareN(x92, 2, x94); - Multiply(x94, x2, x94); - - uint[] t = x32; - SquareN(t, 32, t); - Multiply(t, x1, t); - SquareN(t, 190, t); - Multiply(t, x94, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs index 9b20db1b0..cddb46895 100644 --- a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs @@ -77,66 +77,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^384 - 2^128 - 2^96 + 2^32 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 255 1s } { 1 0s } { 32 1s } { 64 0s } { 30 1s } { 1 0s } { 1 1s } - * - * Therefore we need an addition chain containing 1, 30, 32, 255 (the lengths of the repunits) - * We use: [1], 2, 3, 6, 12, 24, [30], [32], 62, 124, 248, 254, [255] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat.Create(12); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x3 = Nat.Create(12); - Square(x2, x3); - Multiply(x3, x1, x3); - uint[] x6 = Nat.Create(12); - SquareN(x3, 3, x6); - Multiply(x6, x3, x6); - uint[] x12 = x3; - SquareN(x6, 6, x12); - Multiply(x12, x6, x12); - uint[] x24 = Nat.Create(12); - SquareN(x12, 12, x24); - Multiply(x24, x12, x24); - uint[] x30 = x12; - SquareN(x24, 6, x30); - Multiply(x30, x6, x30); - uint[] x32 = x24; - SquareN(x30, 2, x32); - Multiply(x32, x2, x32); - uint[] x62 = x2; - SquareN(x32, 30, x62); - Multiply(x62, x30, x62); - uint[] x124 = Nat.Create(12); - SquareN(x62, 62, x124); - Multiply(x124, x62, x124); - uint[] x248 = x62; - SquareN(x124, 124, x248); - Multiply(x248, x124, x248); - uint[] x254 = x124; - SquareN(x248, 6, x254); - Multiply(x254, x6, x254); - uint[] x255 = x6; - Square(x254, x255); - Multiply(x255, x1, x255); - - uint[] t = x255; - SquareN(t, 33, t); - Multiply(t, x32, t); - SquareN(t, 94, t); - Multiply(t, x30, t); - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/custom/sec/SecP521R1Field.cs b/crypto/src/math/ec/custom/sec/SecP521R1Field.cs index 10b98fc21..0f1922f36 100644 --- a/crypto/src/math/ec/custom/sec/SecP521R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP521R1Field.cs @@ -56,62 +56,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Inv(uint[] x, uint[] z) { - /* - * Raise this element to the exponent 2^521 - 3 - * - * Breaking up the exponent's binary representation into "repunits", we get: - * { 519 1s } { 1 0s } { 1 1s } - * - * Therefore we need an addition chain containing 1, 519 (the lengths of the repunits) - * We use: [1], 2, 4, 8, 16, 32, 64, 128, 256, 512, 516, 518, [519] - */ - - if (0 != IsZero(x)) - throw new ArgumentException("cannot be 0", "x"); - - uint[] x1 = x; - uint[] x2 = Nat.Create(17); - Square(x1, x2); - Multiply(x2, x1, x2); - uint[] x4 = Nat.Create(17); - SquareN(x2, 2, x4); - Multiply(x4, x2, x4); - uint[] x8 = Nat.Create(17); - SquareN(x4, 4, x8); - Multiply(x8, x4, x8); - uint[] x16 = Nat.Create(17); - SquareN(x8, 8, x16); - Multiply(x16, x8, x16); - uint[] x32 = x8; - SquareN(x16, 16, x32); - Multiply(x32, x16, x32); - uint[] x64 = x16; - SquareN(x32, 32, x64); - Multiply(x64, x32, x64); - uint[] x128 = x32; - SquareN(x64, 64, x128); - Multiply(x128, x64, x128); - uint[] x256 = x64; - SquareN(x128, 128, x256); - Multiply(x256, x128, x256); - uint[] x512 = x128; - SquareN(x256, 256, x512); - Multiply(x512, x256, x512); - uint[] x516 = x256; - SquareN(x512, 4, x516); - Multiply(x516, x4, x516); - uint[] x518 = x4; - SquareN(x516, 2, x518); - Multiply(x518, x2, x518); - uint[] x519 = x2; - Square(x518, x519); - Multiply(x519, x1, x519); - - uint[] t = x519; - SquareN(t, 2, t); - - // NOTE that x1 and z could be the same array - Multiply(x1, t, z); + Mod.CheckedModOddInverse(P, x, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/rfc7748/X25519Field.cs b/crypto/src/math/ec/rfc7748/X25519Field.cs index 6843e274a..ffede563b 100644 --- a/crypto/src/math/ec/rfc7748/X25519Field.cs +++ b/crypto/src/math/ec/rfc7748/X25519Field.cs @@ -1,6 +1,8 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Math.Raw; + namespace Org.BouncyCastle.Math.EC.Rfc7748 { public abstract class X25519Field @@ -11,6 +13,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 private const int M25 = 0x01FFFFFF; private const int M26 = 0x03FFFFFF; + private static readonly uint[] P32 = new uint[]{ 0xFFFFFFEDU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, + 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0x7FFFFFFFU }; private static readonly int[] RootNegOne = { 0x020EA0B0, 0x0386C9D2, 0x00478C4E, 0x0035697F, 0x005E8630, 0x01FBD7A7, 0x0340264F, 0x01F0B2B4, 0x00027E0E, 0x00570649 }; @@ -128,6 +132,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 } } + [CLSCompliantAttribute(false)] + public static void Decode(uint[] x, int xOff, int[] z) + { + Decode128(x, xOff, z, 0); + Decode128(x, xOff + 4, z, 5); + z[9] &= M24; + } + public static void Decode(byte[] x, int xOff, int[] z) { Decode128(x, xOff, z, 0); @@ -135,6 +147,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[9] &= M24; } + private static void Decode128(uint[] x, int xOff, int[] z, int zOff) + { + uint t0 = x[xOff + 0], t1 = x[xOff + 1], t2 = x[xOff + 2], t3 = x[xOff + 3]; + + z[zOff + 0] = (int)t0 & M26; + z[zOff + 1] = (int)((t1 << 6) | (t0 >> 26)) & M26; + z[zOff + 2] = (int)((t2 << 12) | (t1 >> 20)) & M25; + z[zOff + 3] = (int)((t3 << 19) | (t2 >> 13)) & M26; + z[zOff + 4] = (int)(t3 >> 7); + } + private static void Decode128(byte[] bs, int off, int[] z, int zOff) { uint t0 = Decode32(bs, off + 0); @@ -158,12 +181,30 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return n; } + [CLSCompliantAttribute(false)] + public static void Encode(int[] x, uint[] z, int zOff) + { + Encode128(x, 0, z, zOff); + Encode128(x, 5, z, zOff + 4); + } + public static void Encode(int[] x, byte[] z, int zOff) { Encode128(x, 0, z, zOff); Encode128(x, 5, z, zOff + 16); } + private static void Encode128(int[] x, int xOff, uint[] z, int zOff) + { + uint x0 = (uint)x[xOff + 0], x1 = (uint)x[xOff + 1], x2 = (uint)x[xOff + 2], x3 = (uint)x[xOff + 3], + x4 = (uint)x[xOff + 4]; + + z[zOff + 0] = x0 | (x1 << 26); + z[zOff + 1] = (x1 >> 6) | (x2 << 20); + z[zOff + 2] = (x2 >> 12) | (x3 << 13); + z[zOff + 3] = (x3 >> 19) | (x4 << 7); + } + private static void Encode128(int[] x, int xOff, byte[] bs, int off) { uint x0 = (uint)x[xOff + 0], x1 = (uint)x[xOff + 1], x2 = (uint)x[xOff + 2]; @@ -185,15 +226,36 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 public static void Inv(int[] x, int[] z) { - // z = x^(p-2) = x^7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEB - // (250 1s) (1 0s) (1 1s) (1 0s) (2 1s) - // Addition chain: [1] [2] 3 5 10 15 25 50 75 125 [250] + //int[] x2 = Create(); + //int[] t = Create(); + //PowPm5d8(x, x2, t); + //Sqr(t, 3, t); + //Mul(t, x2, z); - int[] x2 = Create(); int[] t = Create(); - PowPm5d8(x, x2, t); - Sqr(t, 3, t); - Mul(t, x2, z); + uint[] u = new uint[8]; + + Copy(x, 0, t, 0); + Normalize(t); + Encode(t, u, 0); + + Mod.ModOddInverse(P32, u, u); + + Decode(u, 0, z); + } + + public static void InvVar(int[] x, int[] z) + { + int[] t = Create(); + uint[] u = new uint[8]; + + Copy(x, 0, t, 0); + Normalize(t); + Encode(t, u, 0); + + Mod.ModOddInverseVar(P32, u, u); + + Decode(u, 0, z); } public static int IsZero(int[] x) diff --git a/crypto/src/math/ec/rfc7748/X448Field.cs b/crypto/src/math/ec/rfc7748/X448Field.cs index 240518cde..4d3be5cda 100644 --- a/crypto/src/math/ec/rfc7748/X448Field.cs +++ b/crypto/src/math/ec/rfc7748/X448Field.cs @@ -1,6 +1,8 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Math.Raw; + namespace Org.BouncyCastle.Math.EC.Rfc7748 { [CLSCompliantAttribute(false)] @@ -10,6 +12,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 private const uint M28 = 0x0FFFFFFFU; + private static readonly uint[] P32 = new uint[]{ 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, + 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFEU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, + 0xFFFFFFFFU, 0xFFFFFFFFU }; + protected X448Field() {} public static void Add(uint[] x, uint[] y, uint[] z) @@ -129,6 +135,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 } } + public static void Decode(uint[] x, int xOff, uint[] z) + { + Decode224(x, xOff, z, 0); + Decode224(x, xOff + 7, z, 8); + } + public static void Decode(byte[] x, int xOff, uint[] z) { Decode56(x, xOff, z, 0); @@ -141,6 +153,21 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Decode56(x, xOff + 49, z, 14); } + private static void Decode224(uint[] x, int xOff, uint[] z, int zOff) + { + uint x0 = x[xOff + 0], x1 = x[xOff + 1], x2 = x[xOff + 2], x3 = x[xOff + 3]; + uint x4 = x[xOff + 4], x5 = x[xOff + 5], x6 = x[xOff + 6]; + + z[zOff + 0] = x0 & M28; + z[zOff + 1] = (x0 >> 28 | x1 << 4) & M28; + z[zOff + 2] = (x1 >> 24 | x2 << 8) & M28; + z[zOff + 3] = (x2 >> 20 | x3 << 12) & M28; + z[zOff + 4] = (x3 >> 16 | x4 << 16) & M28; + z[zOff + 5] = (x4 >> 12 | x5 << 20) & M28; + z[zOff + 6] = (x5 >> 8 | x6 << 24) & M28; + z[zOff + 7] = x6 >> 4; + } + private static uint Decode24(byte[] bs, int off) { uint n = bs[off]; @@ -166,6 +193,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[zOff + 1] = (lo >> 28) | (hi << 4); } + public static void Encode(uint[] x, uint[] z, int zOff) + { + Encode224(x, 0, z, zOff); + Encode224(x, 8, z, zOff + 7); + } + public static void Encode(uint[] x, byte[] z, int zOff) { Encode56(x, 0, z, zOff); @@ -178,6 +211,20 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Encode56(x, 14, z, zOff + 49); } + private static void Encode224(uint[] x, int xOff, uint[] z, int zOff) + { + uint x0 = x[xOff + 0], x1 = x[xOff + 1], x2 = x[xOff + 2], x3 = x[xOff + 3]; + uint x4 = x[xOff + 4], x5 = x[xOff + 5], x6 = x[xOff + 6], x7 = x[xOff + 7]; + + z[zOff + 0] = x0 | (x1 << 28); + z[zOff + 1] = (x1 >> 4) | (x2 << 24); + z[zOff + 2] = (x2 >> 8) | (x3 << 20); + z[zOff + 3] = (x3 >> 12) | (x4 << 16); + z[zOff + 4] = (x4 >> 16) | (x5 << 12); + z[zOff + 5] = (x5 >> 20) | (x6 << 8); + z[zOff + 6] = (x6 >> 24) | (x7 << 4); + } + private static void Encode24(uint n, byte[] bs, int off) { bs[ off] = (byte)(n ); @@ -202,14 +249,35 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 public static void Inv(uint[] x, uint[] z) { - // z = x^(p-2) = x^(2^448 - 2^224 - 3) - // (223 1s) (1 0s) (222 1s) (1 0s) (1 1s) - // Addition chain: [1] 2 3 6 9 18 19 37 74 111 [222] [223] + //uint[] t = Create(); + //PowPm3d4(x, t); + //Sqr(t, 2, t); + //Mul(t, x, z); uint[] t = Create(); - PowPm3d4(x, t); - Sqr(t, 2, t); - Mul(t, x, z); + uint[] u = new uint[14]; + + Copy(x, 0, t, 0); + Normalize(t); + Encode(t, u, 0); + + Mod.ModOddInverse(P32, u, u); + + Decode(u, 0, z); + } + + public static void InvVar(uint[] x, uint[] z) + { + uint[] t = Create(); + uint[] u = new uint[14]; + + Copy(x, 0, t, 0); + Normalize(t); + Encode(t, u, 0); + + Mod.ModOddInverseVar(P32, u, u); + + Decode(u, 0, z); } public static int IsZero(uint[] x) diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs index 95ba43472..3a39ae53d 100644 --- a/crypto/src/math/ec/rfc8032/Ed25519.cs +++ b/crypto/src/math/ec/rfc8032/Ed25519.cs @@ -754,7 +754,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 X25519Field.Add(q.z, q.z, x); // TODO[ed25519] Batch inversion - X25519Field.Inv(x, y); + X25519Field.InvVar(x, y); X25519Field.Mul(q.x, y, x); X25519Field.Mul(q.y, y, y); diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs index 12f24c1ff..c1202dc02 100644 --- a/crypto/src/math/ec/rfc8032/Ed448.cs +++ b/crypto/src/math/ec/rfc8032/Ed448.cs @@ -702,7 +702,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { PointExt q = points[i]; // TODO[ed448] Batch inversion - X448Field.Inv(q.z, q.z); + X448Field.InvVar(q.z, q.z); X448Field.Mul(q.x, q.z, q.x); X448Field.Mul(q.y, q.z, q.y); |