diff options
32 files changed, 1075 insertions, 97 deletions
diff --git a/crypto/src/math/ec/custom/djb/Curve25519.cs b/crypto/src/math/ec/custom/djb/Curve25519.cs index f9a1b450c..2566af030 100644 --- a/crypto/src/math/ec/custom/djb/Curve25519.cs +++ b/crypto/src/math/ec/custom/djb/Curve25519.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Djb @@ -93,6 +94,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Djb return new Curve25519LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat256.Create(); + Curve25519Field.Random(r, x); + return new Curve25519FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat256.Create(); + Curve25519Field.RandomMult(r, x); + return new Curve25519FieldElement(x); + } + private class Curve25519LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/djb/Curve25519Field.cs b/crypto/src/math/ec/custom/djb/Curve25519Field.cs index 837821e1a..4e4cfbaa5 100644 --- a/crypto/src/math/ec/custom/djb/Curve25519Field.cs +++ b/crypto/src/math/ec/custom/djb/Curve25519Field.cs @@ -1,15 +1,17 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Djb { internal class Curve25519Field { - // 2^255 - 2^4 - 2^1 - 1 - internal static readonly uint[] P = new uint[]{ 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0x7FFFFFFF }; + // 2^255 - 19 + internal static readonly uint[] P = new uint[]{ 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0x7FFFFFFF }; private const uint P7 = 0x7FFFFFFF; private static readonly uint[] PExt = new uint[]{ 0x00000169, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, @@ -66,6 +68,71 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 8; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat256.CreateExt(); @@ -84,9 +151,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Djb public static void Negate(uint[] x, uint[] z) { - if (Nat256.IsZero(x)) + if (0 != IsZero(x)) { - Nat256.Zero(z); + Nat256.Sub(P, P, z); } else { @@ -94,6 +161,27 @@ namespace Org.BouncyCastle.Math.EC.Custom.Djb } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[8 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 8); + z[7] &= P7; + } + while (0 == Nat.LessThan(8, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { Debug.Assert(xx[15] >> 30 == 0); diff --git a/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs b/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs index 5d82df547..a5509841d 100644 --- a/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs +++ b/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs @@ -96,7 +96,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Djb { //return Multiply(b.Invert()); uint[] z = Nat256.Create(); - Mod.Invert(Curve25519Field.P, ((Curve25519FieldElement)b).x, z); + Curve25519Field.Inv(((Curve25519FieldElement)b).x, z); Curve25519Field.Multiply(z, x, z); return new Curve25519FieldElement(z); } @@ -119,7 +119,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Djb { //return new Curve25519FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat256.Create(); - Mod.Invert(Curve25519Field.P, x, z); + Curve25519Field.Inv(x, z); return new Curve25519FieldElement(z); } diff --git a/crypto/src/math/ec/custom/gm/SM2P256V1Curve.cs b/crypto/src/math/ec/custom/gm/SM2P256V1Curve.cs index 3135cbb06..805245c45 100644 --- a/crypto/src/math/ec/custom/gm/SM2P256V1Curve.cs +++ b/crypto/src/math/ec/custom/gm/SM2P256V1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.GM @@ -92,6 +93,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM return new SM2P256V1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat256.Create(); + SM2P256V1Field.Random(r, x); + return new SM2P256V1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat256.Create(); + SM2P256V1Field.RandomMult(r, x); + return new SM2P256V1FieldElement(x); + } + private class SM2P256V1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs b/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs index b1d232347..55596b844 100644 --- a/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs +++ b/crypto/src/math/ec/custom/gm/SM2P256V1Field.cs @@ -1,20 +1,22 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.GM { internal class SM2P256V1Field { // 2^256 - 2^224 - 2^96 + 2^64 - 1 - internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0xFFFFFFFE }; - internal static readonly uint[] PExt = new uint[]{ 00000001, 0x00000000, 0xFFFFFFFE, 0x00000001, 0x00000001, + internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE }; + private static readonly uint[] PExt = new uint[]{ 00000001, 0x00000000, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0xFFFFFFFE, 0xFFFFFFFD, 0x00000003, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFE }; - internal const uint P7 = 0xFFFFFFFE; - internal const uint PExt15 = 0xFFFFFFFE; + private const uint P7 = 0xFFFFFFFE; + private const uint PExt15 = 0xFFFFFFFE; public static void Add(uint[] x, uint[] y, uint[] z) { @@ -53,6 +55,64 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM return z; } + 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); + } + public static void Half(uint[] x, uint[] z) { if ((x[0] & 1) == 0) @@ -66,6 +126,17 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM } } + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 8; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat256.CreateExt(); @@ -84,9 +155,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM public static void Negate(uint[] x, uint[] z) { - if (Nat256.IsZero(x)) + if (0 != IsZero(x)) { - Nat256.Zero(z); + Nat256.Sub(P, P, z); } else { @@ -94,6 +165,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[8 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 8); + } + while (0 == Nat.LessThan(8, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { long xx08 = xx[8], xx09 = xx[9], xx10 = xx[10], xx11 = xx[11]; diff --git a/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs b/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs index a9331eb52..25cb24932 100644 --- a/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs +++ b/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs @@ -94,7 +94,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM { //return Multiply(b.Invert()); uint[] z = Nat256.Create(); - Mod.Invert(SM2P256V1Field.P, ((SM2P256V1FieldElement)b).x, z); + SM2P256V1Field.Inv(((SM2P256V1FieldElement)b).x, z); SM2P256V1Field.Multiply(z, x, z); return new SM2P256V1FieldElement(z); } @@ -117,7 +117,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM { //return new SM2P256V1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat256.Create(); - Mod.Invert(SM2P256V1Field.P, x, z); + SM2P256V1Field.Inv(x, z); return new SM2P256V1FieldElement(z); } @@ -131,7 +131,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM * Raise this element to the exponent 2^254 - 2^222 - 2^94 + 2^62 * * Breaking up the exponent's binary representation into "repunits", we get: - * { 31 1s } { 1 0s } { 128 1s } { 31 0s } { 1 1s } { 62 0s} + * { 31 1s } { 1 0s } { 128 1s } { 31 0s } { 1 1s } { 62 0s } * * We use an addition chain for the beginning: [1], 2, 3, 6, 12, [24], 30, [31] */ diff --git a/crypto/src/math/ec/custom/sec/SecP128R1Curve.cs b/crypto/src/math/ec/custom/sec/SecP128R1Curve.cs index e92aca75b..b4a150ca0 100644 --- a/crypto/src/math/ec/custom/sec/SecP128R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP128R1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -93,6 +94,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP128R1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat128.Create(); + SecP128R1Field.Random(r, x); + return new SecP128R1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat128.Create(); + SecP128R1Field.RandomMult(r, x); + return new SecP128R1FieldElement(x); + } + private class SecP128R1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP128R1Field.cs b/crypto/src/math/ec/custom/sec/SecP128R1Field.cs index cf91c7e5d..23ea361a0 100644 --- a/crypto/src/math/ec/custom/sec/SecP128R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP128R1Field.cs @@ -1,15 +1,17 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP128R1Field { // 2^128 - 2^97 - 1 - internal static readonly uint[] P = new uint[] { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFD }; - internal static readonly uint[] PExt = new uint[] { 0x00000001, 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFE, + internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFD }; + private static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFE, 0xFFFFFFFF, 0x00000003, 0xFFFFFFFC }; private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFB, 0x00000001, 0x00000000, 0xFFFFFFFC, 0x00000003 }; @@ -66,6 +68,66 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 4; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat128.CreateExt(); @@ -84,9 +146,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat128.IsZero(x)) + if (0 != IsZero(x)) { - Nat128.Zero(z); + Nat128.Sub(P, P, z); } else { @@ -94,6 +156,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[4 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 4); + } + while (0 == Nat.LessThan(4, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { ulong x0 = xx[0], x1 = xx[1], x2 = xx[2], x3 = xx[3]; diff --git a/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs index 8ddabe9a7..e9235c2f3 100644 --- a/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs @@ -94,7 +94,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // return multiply(b.invert()); uint[] z = Nat128.Create(); - Mod.Invert(SecP128R1Field.P, ((SecP128R1FieldElement)b).x, z); + SecP128R1Field.Inv(((SecP128R1FieldElement)b).x, z); SecP128R1Field.Multiply(z, x, z); return new SecP128R1FieldElement(z); } @@ -117,7 +117,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // return new SecP128R1FieldElement(toBigInteger().modInverse(Q)); uint[] z = Nat128.Create(); - Mod.Invert(SecP128R1Field.P, x, z); + SecP128R1Field.Inv(x, z); return new SecP128R1FieldElement(z); } diff --git a/crypto/src/math/ec/custom/sec/SecP160K1Curve.cs b/crypto/src/math/ec/custom/sec/SecP160K1Curve.cs index fbc928ab7..c2c78e464 100644 --- a/crypto/src/math/ec/custom/sec/SecP160K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP160K1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -90,6 +91,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP160K1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat160.Create(); + SecP160R2Field.Random(r, x); + return new SecP160R2FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat160.Create(); + SecP160R2Field.RandomMult(r, x); + return new SecP160R2FieldElement(x); + } + private class SecP160K1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP160R1Curve.cs b/crypto/src/math/ec/custom/sec/SecP160R1Curve.cs index 39855c549..8ae519ad3 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -93,6 +94,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP160R1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat160.Create(); + SecP160R1Field.Random(r, x); + return new SecP160R1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat160.Create(); + SecP160R1Field.RandomMult(r, x); + return new SecP160R1FieldElement(x); + } + private class SecP160R1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP160R1Field.cs b/crypto/src/math/ec/custom/sec/SecP160R1Field.cs index 6a5a2ef64..139cd80d6 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R1Field.cs @@ -1,15 +1,17 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP160R1Field { // 2^160 - 2^31 - 1 - internal static readonly uint[] P = new uint[] { 0x7FFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}; - internal static readonly uint[] PExt = new uint[] { 0x00000001, 0x40000001, 0x00000000, 0x00000000, 0x00000000, + internal static readonly uint[] P = new uint[]{ 0x7FFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static readonly uint[] PExt = new uint[]{ 0x00000001, 0x40000001, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0xBFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000001 }; @@ -70,6 +72,73 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 5; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat160.CreateExt(); @@ -91,9 +160,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat160.IsZero(x)) + if (0 != IsZero(x)) { - Nat160.Zero(z); + Nat160.Sub(P, P, z); } else { @@ -101,6 +170,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[5 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 5); + } + while (0 == Nat.LessThan(5, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { ulong x5 = xx[5], x6 = xx[6], x7 = xx[7], x8 = xx[8], x9 = xx[9]; diff --git a/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs index eade0b8e9..4876fafa9 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs @@ -94,7 +94,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // return multiply(b.invert()); uint[] z = Nat160.Create(); - Mod.Invert(SecP160R1Field.P, ((SecP160R1FieldElement)b).x, z); + SecP160R1Field.Inv(((SecP160R1FieldElement)b).x, z); SecP160R1Field.Multiply(z, x, z); return new SecP160R1FieldElement(z); } @@ -117,7 +117,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // return new SecP160R1FieldElement(ToBigInteger().modInverse(Q)); uint[] z = Nat160.Create(); - Mod.Invert(SecP160R1Field.P, x, z); + SecP160R1Field.Inv(x, z); return new SecP160R1FieldElement(z); } diff --git a/crypto/src/math/ec/custom/sec/SecP160R2Curve.cs b/crypto/src/math/ec/custom/sec/SecP160R2Curve.cs index c8ac2e0ab..49c3fa331 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R2Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R2Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -93,6 +94,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP160R2LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat160.Create(); + SecP160R2Field.Random(r, x); + return new SecP160R2FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat160.Create(); + SecP160R2Field.RandomMult(r, x); + return new SecP160R2FieldElement(x); + } + private class SecP160R2LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP160R2Field.cs b/crypto/src/math/ec/custom/sec/SecP160R2Field.cs index 1bef32eea..bc36d9de1 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R2Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R2Field.cs @@ -1,7 +1,9 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { @@ -9,10 +11,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // 2^160 - 2^32 - 2^14 - 2^12 - 2^9 - 2^8 - 2^7 - 2^3 - 2^2 - 1 internal static readonly uint[] P = new uint[]{ 0xFFFFAC73, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - internal static readonly uint[] PExt = new uint[]{ 0x1B44BBA9, 0x0000A71A, 0x00000001, 0x00000000, 0x00000000, + private static readonly uint[] PExt = new uint[]{ 0x1B44BBA9, 0x0000A71A, 0x00000001, 0x00000000, 0x00000000, 0xFFFF58E6, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xE4BB4457, 0xFFFF58E5, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, - 0x0000A719, 0x00000002 }; + private static readonly uint[] PExtInv = new uint[]{ 0xE4BB4457, 0xFFFF58E5, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0x0000A719, 0x00000002 }; private const uint P4 = 0xFFFFFFFF; private const uint PExt9 = 0xFFFFFFFF; private const uint PInv33 = 0x538D; @@ -70,6 +72,85 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 5; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat160.CreateExt(); @@ -91,9 +172,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat160.IsZero(x)) + if (0 != IsZero(x)) { - Nat160.Zero(z); + Nat160.Sub(P, P, z); } else { @@ -101,6 +182,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[5 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 5); + } + while (0 == Nat.LessThan(5, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { ulong cc = Nat160.Mul33Add(PInv33, xx, 5, xx, 0, z, 0); diff --git a/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs index b67fc44f0..795fe3b2e 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs @@ -94,7 +94,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // return Multiply(b.invert()); uint[] z = Nat160.Create(); - Mod.Invert(SecP160R2Field.P, ((SecP160R2FieldElement)b).x, z); + SecP160R2Field.Inv(((SecP160R2FieldElement)b).x, z); SecP160R2Field.Multiply(z, x, z); return new SecP160R2FieldElement(z); } @@ -117,7 +117,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { // return new SecP160R2FieldElement(ToBigInteger().modInverse(Q)); uint[] z = Nat160.Create(); - Mod.Invert(SecP160R2Field.P, x, z); + SecP160R2Field.Inv(x, z); return new SecP160R2FieldElement(z); } diff --git a/crypto/src/math/ec/custom/sec/SecP192K1Curve.cs b/crypto/src/math/ec/custom/sec/SecP192K1Curve.cs index 6f1069af9..b9fb08e56 100644 --- a/crypto/src/math/ec/custom/sec/SecP192K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP192K1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -90,6 +91,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP192K1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat192.Create(); + SecP192K1Field.Random(r, x); + return new SecP192K1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat192.Create(); + SecP192K1Field.RandomMult(r, x); + return new SecP192K1FieldElement(x); + } + private class SecP192K1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs index a00360360..30d53f7dc 100644 --- a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs @@ -1,18 +1,21 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP192K1Field { // 2^192 - 2^32 - 2^12 - 2^8 - 2^7 - 2^6 - 2^3 - 1 - internal static readonly uint[] P = new uint[]{ 0xFFFFEE37, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - internal static readonly uint[] PExt = new uint[]{ 0x013C4FD1, 0x00002392, 0x00000001, 0x00000000, 0x00000000, + internal static readonly uint[] P = new uint[]{ 0xFFFFEE37, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF }; + private static readonly uint[] PExt = new uint[]{ 0x013C4FD1, 0x00002392, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0xFFFFDC6E, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xFEC3B02F, 0xFFFFDC6D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0x00002391, 0x00000002 }; + private static readonly uint[] PExtInv = new uint[]{ 0xFEC3B02F, 0xFFFFDC6D, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0x00002391, 0x00000002 }; private const uint P5 = 0xFFFFFFFF; private const uint PExt11 = 0xFFFFFFFF; private const uint PInv33 = 0x11C9; @@ -70,6 +73,82 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 6; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat192.CreateExt(); @@ -91,9 +170,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat192.IsZero(x)) + if (0 != IsZero(x)) { - Nat192.Zero(z); + Nat192.Sub(P, P, z); } else { @@ -101,6 +180,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[6 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 6); + } + while (0 == Nat.LessThan(6, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { ulong cc = Nat192.Mul33Add(PInv33, xx, 6, xx, 0, z, 0); diff --git a/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs index 7d5beaed8..c933ffc8d 100644 --- a/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs @@ -95,7 +95,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return Multiply(b.Invert()); uint[] z = Nat192.Create(); - Mod.Invert(SecP192K1Field.P, ((SecP192K1FieldElement)b).x, z); + SecP192K1Field.Inv(((SecP192K1FieldElement)b).x, z); SecP192K1Field.Multiply(z, x, z); return new SecP192K1FieldElement(z); } @@ -118,7 +118,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return new SecP192K1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat192.Create(); - Mod.Invert(SecP192K1Field.P, x, z); + SecP192K1Field.Inv(x, z); return new SecP192K1FieldElement(z); } @@ -132,7 +132,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec * Raise this element to the exponent 2^190 - 2^30 - 2^10 - 2^6 - 2^5 - 2^4 - 2^1 * * Breaking up the exponent's binary representation into "repunits", we get: - * { 159 1s } { 1 0s } { 19 1s } { 1 0s } { 3 1s } { 3 0s} { 3 1s } { 1 0s } + * { 159 1s } { 1 0s } { 19 1s } { 1 0s } { 3 1s } { 3 0s } { 3 1s } { 1 0s } * * Therefore we need an addition chain containing 3, 19, 159 (the lengths of the repunits) * We use: 1, 2, [3], 6, 8, 16, [19], 35, 70, 140, [159] diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Curve.cs b/crypto/src/math/ec/custom/sec/SecP192R1Curve.cs index 249542449..465768514 100644 --- a/crypto/src/math/ec/custom/sec/SecP192R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP192R1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -93,6 +94,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP192R1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat192.Create(); + SecP192R1Field.Random(r, x); + return new SecP192R1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat192.Create(); + SecP192R1Field.RandomMult(r, x); + return new SecP192R1FieldElement(x); + } + private class SecP192R1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs index 096c2b51f..2061d1359 100644 --- a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs @@ -1,18 +1,21 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP192R1Field { // 2^192 - 2^64 - 1 - internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - internal static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, + internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF }; + private static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFE, - 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000002 }; + private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, + 0xFFFFFFFE, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000002 }; private const uint P5 = 0xFFFFFFFF; private const uint PExt11 = 0xFFFFFFFF; @@ -69,6 +72,73 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 6; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat192.CreateExt(); @@ -90,9 +160,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat192.IsZero(x)) + if (0 != IsZero(x)) { - Nat192.Zero(z); + Nat192.Sub(P, P, z); } else { @@ -100,6 +170,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[6 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 6); + } + while (0 == Nat.LessThan(6, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { ulong xx06 = xx[6], xx07 = xx[7], xx08 = xx[8]; diff --git a/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs index d197cb698..e61c2251b 100644 --- a/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs @@ -94,7 +94,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return Multiply(b.Invert()); uint[] z = Nat192.Create(); - Mod.Invert(SecP192R1Field.P, ((SecP192R1FieldElement)b).x, z); + SecP192R1Field.Inv(((SecP192R1FieldElement)b).x, z); SecP192R1Field.Multiply(z, x, z); return new SecP192R1FieldElement(z); } @@ -117,7 +117,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return new SecP192R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat192.Create(); - Mod.Invert(SecP192R1Field.P, x, z); + SecP192R1Field.Inv(x, z); return new SecP192R1FieldElement(z); } diff --git a/crypto/src/math/ec/custom/sec/SecP224K1Curve.cs b/crypto/src/math/ec/custom/sec/SecP224K1Curve.cs index 7f45b14f6..dc5cd6c0b 100644 --- a/crypto/src/math/ec/custom/sec/SecP224K1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP224K1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -90,6 +91,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP224K1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat224.Create(); + SecP224K1Field.Random(r, x); + return new SecP224K1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat224.Create(); + SecP224K1Field.RandomMult(r, x); + return new SecP224K1FieldElement(x); + } + private class SecP224K1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs index 98cf777a5..d20ac63f3 100644 --- a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs @@ -1,19 +1,22 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP224K1Field { // 2^224 - 2^32 - 2^12 - 2^11 - 2^9 - 2^7 - 2^4 - 2 - 1 - internal static readonly uint[] P = new uint[]{ 0xFFFFE56D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF }; - internal static readonly uint[] PExt = new uint[]{ 0x02C23069, 0x00003526, 0x00000001, 0x00000000, 0x00000000, - 0x00000000, 0x00000000, 0xFFFFCADA, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xFD3DCF97, 0xFFFFCAD9, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0xFFFFFFFF, 0x00003525, 0x00000002 }; + internal static readonly uint[] P = new uint[]{ 0xFFFFE56D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF }; + private static readonly uint[] PExt = new uint[]{ 0x02C23069, 0x00003526, 0x00000001, 0x00000000, 0x00000000, + 0x00000000, 0x00000000, 0xFFFFCADA, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF + }; + private static readonly uint[] PExtInv = new uint[]{ 0xFD3DCF97, 0xFFFFCAD9, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00003525, 0x00000002 }; private const uint P6 = 0xFFFFFFFF; private const uint PExt13 = 0xFFFFFFFF; private const uint PInv33 = 0x1A93; @@ -71,6 +74,82 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 7; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat224.CreateExt(); @@ -92,9 +171,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat224.IsZero(x)) + if (0 != IsZero(x)) { - Nat224.Zero(z); + Nat224.Sub(P, P, z); } else { @@ -102,6 +181,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[7 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 7); + } + while (0 == Nat.LessThan(7, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { ulong cc = Nat224.Mul33Add(PInv33, xx, 7, xx, 0, z, 0); diff --git a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs index 422b8294a..eb740419f 100644 --- a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs @@ -99,7 +99,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return Multiply(b.Invert()); uint[] z = Nat224.Create(); - Mod.Invert(SecP224K1Field.P, ((SecP224K1FieldElement)b).x, z); + SecP224K1Field.Inv(((SecP224K1FieldElement)b).x, z); SecP224K1Field.Multiply(z, x, z); return new SecP224K1FieldElement(z); } @@ -122,7 +122,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return new SecP224K1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat224.Create(); - Mod.Invert(SecP224K1Field.P, x, z); + SecP224K1Field.Inv(x, z); return new SecP224K1FieldElement(z); } @@ -138,7 +138,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec * First, raise this element to the exponent 2^221 - 2^29 - 2^9 - 2^8 - 2^6 - 2^4 - 2^1 (i.e. m + 1) * * Breaking up the exponent's binary representation into "repunits", we get: - * { 191 1s } { 1 0s } { 19 1s } { 2 0s } { 1 1s } { 1 0s} { 1 1s } { 1 0s} { 3 1s } { 1 0s} + * { 191 1s } { 1 0s } { 19 1s } { 2 0s } { 1 1s } { 1 0s } { 1 1s } { 1 0s } { 3 1s } { 1 0s } * * Therefore we need an addition chain containing 1, 3, 19, 191 (the lengths of the repunits) * We use: [1], 2, [3], 4, 8, 11, [19], 23, 42, 84, 107, [191] diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Curve.cs b/crypto/src/math/ec/custom/sec/SecP224R1Curve.cs index 1f75dc1db..8e79316d8 100644 --- a/crypto/src/math/ec/custom/sec/SecP224R1Curve.cs +++ b/crypto/src/math/ec/custom/sec/SecP224R1Curve.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities.Encoders; namespace Org.BouncyCastle.Math.EC.Custom.Sec @@ -93,6 +94,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return new SecP224R1LookupTable(this, table, len); } + public override ECFieldElement RandomFieldElement(SecureRandom r) + { + uint[] x = Nat224.Create(); + SecP224R1Field.Random(r, x); + return new SecP224R1FieldElement(x); + } + + public override ECFieldElement RandomFieldElementMult(SecureRandom r) + { + uint[] x = Nat224.Create(); + SecP224R1Field.RandomMult(r, x); + return new SecP224R1FieldElement(x); + } + private class SecP224R1LookupTable : AbstractECLookupTable { diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs index 4f5c3bbda..06d451c2b 100644 --- a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs @@ -1,18 +1,22 @@ using System; using System.Diagnostics; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP224R1Field { // 2^224 - 2^96 + 1 - internal static readonly uint[] P = new uint[] { 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - internal static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, - 0xFFFFFFFF, 0x00000000, 0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, - 0x00000000, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001 }; + internal static readonly uint[] P = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF }; + private static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0x00000000, 0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF + }; + private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, + 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001 }; private const uint P6 = 0xFFFFFFFF; private const uint PExt13 = 0xFFFFFFFF; @@ -69,6 +73,69 @@ 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); + } + + public static int IsZero(uint[] x) + { + uint d = 0; + for (int i = 0; i < 7; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return ((int)d - 1) >> 31; + } + public static void Multiply(uint[] x, uint[] y, uint[] z) { uint[] tt = Nat224.CreateExt(); @@ -90,9 +157,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Negate(uint[] x, uint[] z) { - if (Nat224.IsZero(x)) + if (0 != IsZero(x)) { - Nat224.Zero(z); + Nat224.Sub(P, P, z); } else { @@ -100,6 +167,26 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec } } + public static void Random(SecureRandom r, uint[] z) + { + byte[] bb = new byte[7 * 4]; + do + { + r.NextBytes(bb); + Pack.LE_To_UInt32(bb, 0, z, 0, 7); + } + while (0 == Nat.LessThan(7, z, P)); + } + + public static void RandomMult(SecureRandom r, uint[] z) + { + do + { + Random(r, z); + } + while (0 != IsZero(z)); + } + public static void Reduce(uint[] xx, uint[] z) { long xx10 = xx[10], xx11 = xx[11], xx12 = xx[12], xx13 = xx[13]; diff --git a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs index e44b4f7b7..bb60edaf6 100644 --- a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs @@ -94,7 +94,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return Multiply(b.Invert()); uint[] z = Nat224.Create(); - Mod.Invert(SecP224R1Field.P, ((SecP224R1FieldElement)b).x, z); + SecP224R1Field.Inv(((SecP224R1FieldElement)b).x, z); SecP224R1Field.Multiply(z, x, z); return new SecP224R1FieldElement(z); } @@ -117,7 +117,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { //return new SecP224R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat224.Create(); - Mod.Invert(SecP224R1Field.P, x, z); + SecP224R1Field.Inv(x, z); return new SecP224R1FieldElement(z); } @@ -259,7 +259,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec if (Nat224.IsZero(d1)) { - Mod.Invert(SecP224R1Field.P, e0, t); + SecP224R1Field.Inv(e0, t); SecP224R1Field.Multiply(t, d0, t); return true; } diff --git a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs index 1f11c9c78..2193c94e6 100644 --- a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs @@ -10,13 +10,13 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec internal class SecP256K1Field { // 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 - private static readonly uint[] P = new uint[]{ 0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0xFFFFFFFF }; + internal static readonly uint[] P = new uint[]{ 0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; private static readonly uint[] PExt = new uint[]{ 0x000E90A1, 0x000007A2, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFF85E, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xFFF16F5F, 0xFFFFF85D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x000007A1, 0x00000002 }; + private static readonly uint[] PExtInv = new uint[]{ 0xFFF16F5F, 0xFFFFF85D, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x000007A1, 0x00000002 }; private const uint P7 = 0xFFFFFFFF; private const uint PExt15 = 0xFFFFFFFF; private const uint PInv33 = 0x3D1; diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs index 0b4918820..eadc7ee58 100644 --- a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs @@ -10,8 +10,8 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec internal class SecP256R1Field { // 2^256 - 2^224 + 2^192 + 2^96 - 1 - private static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000000, 0x00000000, - 0x00000001, 0xFFFFFFFF }; + internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000000, + 0x00000000, 0x00000001, 0xFFFFFFFF }; private static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE }; @@ -74,7 +74,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec * 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} + * { 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] diff --git a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs index f15678497..9b20db1b0 100644 --- a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs @@ -9,15 +9,16 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecP384R1Field { - // 2^384 - 2^128 - 2^96 + 2^32 - 1 - private static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, - 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExt = new uint[]{ 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE, - 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFE, 0x00000001, 0x00000000, - 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; - private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0x00000001, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0x00000001, - 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0xFFFFFFFE, 0xFFFFFFFF, - 0x00000001, 0x00000002 }; + // 2^384 - 2^128 - 2^96 + 2^32 - 1 + internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static readonly uint[] PExt = new uint[]{ 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, + 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFE, 0x00000001, + 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF }; + private static readonly uint[] PExtInv = new uint[]{ 0xFFFFFFFF, 0x00000001, 0xFFFFFFFF, 0xFFFFFFFD, + 0xFFFFFFFF, 0x00000001, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, + 0xFFFFFFFE, 0xFFFFFFFF, 0x00000001, 0x00000002 }; private const uint P11 = 0xFFFFFFFF; private const uint PExt23 = 0xFFFFFFFF; @@ -80,7 +81,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec * 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} + * { 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] diff --git a/crypto/src/math/ec/custom/sec/SecP521R1Field.cs b/crypto/src/math/ec/custom/sec/SecP521R1Field.cs index ec81cf021..10b98fc21 100644 --- a/crypto/src/math/ec/custom/sec/SecP521R1Field.cs +++ b/crypto/src/math/ec/custom/sec/SecP521R1Field.cs @@ -10,9 +10,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec internal class SecP521R1Field { // 2^521 - 1 - private static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, - 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x1FF }; - private const int P16 = 0x1FF; + internal static readonly uint[] P = new uint[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0x1FF }; + private const uint P16 = 0x1FFU; public static void Add(uint[] x, uint[] y, uint[] z) { @@ -59,7 +60,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec * 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} + * { 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] @@ -150,7 +151,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { r.NextBytes(bb); Pack.LE_To_UInt32(bb, 0, z, 0, 17); - z[16] &= 0x000001FFU; + z[16] &= P16; } while (0 == Nat.LessThan(17, z, P)); } @@ -218,7 +219,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec if (c < 0) { c += Nat.Dec(16, z); - c &= P16; + c &= (int)P16; } z[16] = (uint)c; } |