diff options
Diffstat (limited to 'crypto/src/math/ec/custom')
| -rw-r--r-- | crypto/src/math/ec/custom/djb/Curve25519Field.cs | 51 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/gm/SM2P256V1Field.cs | 55 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP128R1Field.cs | 46 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP160R1Field.cs | 53 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP160R2Field.cs | 65 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP192K1Field.cs | 62 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP192R1Field.cs | 53 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP224K1Field.cs | 62 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP224R1Field.cs | 49 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP256K1Field.cs | 60 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP256R1Field.cs | 55 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP384R1Field.cs | 61 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP521R1Field.cs | 57 |
13 files changed, 13 insertions, 716 deletions
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) |