diff options
| -rw-r--r-- | crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs | 89 |
1 files changed, 87 insertions, 2 deletions
diff --git a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs index cd9426769..123efd2ab 100644 --- a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs @@ -10,6 +10,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec { public static readonly BigInteger Q = SecP224K1Curve.q; + // Calculated as BigInteger.Two.ModPow(Q.ShiftRight(2), Q) + private static readonly uint[] PRECOMP_POW2 = new uint[]{ 0x33bfd202, 0xdcfad133, 0x2287624a, 0xc3811ba8, + 0xa85558fc, 0x1eaef5d7, 0x8edf154c }; + protected internal readonly uint[] x; public SecP224K1FieldElement(BigInteger x) @@ -125,8 +129,89 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec */ public override ECFieldElement Sqrt() { - ECFieldElement root = new FpFieldElement(Q, ToBigInteger()).Sqrt(); - return root == null ? null : new SecP224K1FieldElement(root.ToBigInteger()); + /* + * Q == 8m + 5, so we use Pocklington's method for this case. + * + * 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} + * + * 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] + */ + + uint[] x1 = this.x; + if (Nat224.IsZero(x1) || Nat224.IsOne(x1)) + return this; + + uint[] x2 = Nat224.Create(); + SecP224K1Field.Square(x1, x2); + SecP224K1Field.Multiply(x2, x1, x2); + uint[] x3 = x2; + SecP224K1Field.Square(x2, x3); + SecP224K1Field.Multiply(x3, x1, x3); + uint[] x4 = Nat224.Create(); + SecP224K1Field.Square(x3, x4); + SecP224K1Field.Multiply(x4, x1, x4); + uint[] x8 = Nat224.Create(); + SecP224K1Field.SquareN(x4, 4, x8); + SecP224K1Field.Multiply(x8, x4, x8); + uint[] x11 = Nat224.Create(); + SecP224K1Field.SquareN(x8, 3, x11); + SecP224K1Field.Multiply(x11, x3, x11); + uint[] x19 = x11; + SecP224K1Field.SquareN(x11, 8, x19); + SecP224K1Field.Multiply(x19, x8, x19); + uint[] x23 = x8; + SecP224K1Field.SquareN(x19, 4, x23); + SecP224K1Field.Multiply(x23, x4, x23); + uint[] x42 = x4; + SecP224K1Field.SquareN(x23, 19, x42); + SecP224K1Field.Multiply(x42, x19, x42); + uint[] x84 = Nat224.Create(); + SecP224K1Field.SquareN(x42, 42, x84); + SecP224K1Field.Multiply(x84, x42, x84); + uint[] x107 = x42; + SecP224K1Field.SquareN(x84, 23, x107); + SecP224K1Field.Multiply(x107, x23, x107); + uint[] x191 = x23; + SecP224K1Field.SquareN(x107, 84, x191); + SecP224K1Field.Multiply(x191, x84, x191); + + uint[] t1 = x191; + SecP224K1Field.SquareN(t1, 20, t1); + SecP224K1Field.Multiply(t1, x19, t1); + SecP224K1Field.SquareN(t1, 3, t1); + SecP224K1Field.Multiply(t1, x1, t1); + SecP224K1Field.SquareN(t1, 2, t1); + SecP224K1Field.Multiply(t1, x1, t1); + SecP224K1Field.SquareN(t1, 4, t1); + SecP224K1Field.Multiply(t1, x3, t1); + SecP224K1Field.Square(t1, t1); + + uint[] t2 = x84; + SecP224K1Field.Square(t1, t2); + + if (Arrays.AreEqual(x1, t2)) + { + return new SecP224K1FieldElement(t1); + } + + /* + * If the first guess is incorrect, we multiply by a precomputed power of 2 to get the second guess, + * which is ((4x)^(m + 1))/2 mod Q + */ + SecP224K1Field.Multiply(t1, PRECOMP_POW2, t1); + + SecP224K1Field.Square(t1, t2); + + if (Arrays.AreEqual(x1, t2)) + { + return new SecP224K1FieldElement(t1); + } + + return null; } public override bool Equals(object obj) |