diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-30 12:14:43 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-30 12:14:43 +0400 |
commit | c5a1e01ba241e8eeca3537793e8b1ac56a642ffe (patch) | |
tree | bbedfcd34b77195fe03cadd6f1faa1a41f235268 /core/src/main/java/org/bouncycastle/math | |
parent | ad319cc8d6b105655b2f28de86b22f6e53619b26 (diff) |
Take advantage of special prime modulus to optimize sqrt
Diffstat (limited to 'core/src/main/java/org/bouncycastle/math')
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java | 63 | ||||
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java | 38 |
2 files changed, 97 insertions, 4 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java index 57828917..0a874767 100644 --- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java +++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java @@ -128,8 +128,67 @@ public class SecP256K1FieldElement extends ECFieldElement */ public ECFieldElement sqrt() { - ECFieldElement root = new ECFieldElement.Fp(Q, toBigInteger()).sqrt(); - return root == null ? null : new SecP256K1FieldElement(root.toBigInteger()); + /* + * Raise this element to the exponent 2^254 - 2^30 - 2^7 - 2^6 - 2^5 - 2^4 - 2^2 + * + * Breaking up the exponent's binary representation into "repunits", we get: + * { 223 1s } { 1 0s } { 22 1s } { 4 0s } { 2 1s } { 2 0s} + * + * Therefore we need an addition chain containing 2, 22, 223 (the lengths of the repunits) + * We use: 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] + */ + + int[] x1 = this.x; + if (Nat256.isZero(x1) || Nat256.isOne(x1)) + { + return this; + } + + int[] x2 = Nat256.create(); + SecP256K1Field.square(x1, x2); + SecP256K1Field.multiply(x2, x1, x2); + int[] x3 = Nat256.create(); + SecP256K1Field.square(x2, x3); + SecP256K1Field.multiply(x3, x1, x3); + int[] x6 = Nat256.create(); + SecP256K1Field.squareN(x3, 3, x6); + SecP256K1Field.multiply(x6, x3, x6); + int[] x9 = x6; + SecP256K1Field.squareN(x6, 3, x9); + SecP256K1Field.multiply(x9, x3, x9); + int[] x11 = x9; + SecP256K1Field.squareN(x9, 2, x11); + SecP256K1Field.multiply(x11, x2, x11); + int[] x22 = Nat256.create(); + SecP256K1Field.squareN(x11, 11, x22); + SecP256K1Field.multiply(x22, x11, x22); + int[] x44 = x11; + SecP256K1Field.squareN(x22, 22, x44); + SecP256K1Field.multiply(x44, x22, x44); + int[] x88 = Nat256.create(); + SecP256K1Field.squareN(x44, 44, x88); + SecP256K1Field.multiply(x88, x44, x88); + int[] x176 = Nat256.create(); + SecP256K1Field.squareN(x88, 88, x176); + SecP256K1Field.multiply(x176, x88, x176); + int[] x220 = x88; + SecP256K1Field.squareN(x176, 44, x220); + SecP256K1Field.multiply(x220, x44, x220); + int[] x223 = x44; + SecP256K1Field.squareN(x220, 3, x223); + SecP256K1Field.multiply(x223, x3, x223); + + int[] t1 = x223; + SecP256K1Field.squareN(t1, 23, t1); + SecP256K1Field.multiply(t1, x22, t1); + SecP256K1Field.squareN(t1, 6, t1); + SecP256K1Field.multiply(t1, x2, t1); + SecP256K1Field.squareN(t1, 2, t1); + + int[] t2 = x2; + SecP256K1Field.square(t1, t2); + + return Arrays.areEqual(x1, t2) ? new SecP256K1FieldElement(t1) : null; } public boolean equals(Object other) diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java index 03895cfb..f9eaff0e 100644 --- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java +++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java @@ -129,8 +129,42 @@ public class SecP256R1FieldElement extends ECFieldElement */ public ECFieldElement sqrt() { - ECFieldElement root = new ECFieldElement.Fp(Q, toBigInteger()).sqrt(); - return root == null ? null : new SecP256R1FieldElement(root.toBigInteger()); + // Raise this element to the exponent 2^254 - 2^222 + 2^190 + 2^94 + + int[] x1 = this.x; + if (Nat256.isZero(x1) || Nat256.isOne(x1)) + { + return this; + } + + int[] t1 = Nat256.create(); + int[] t2 = Nat256.create(); + + SecP256R1Field.square(x1, t1); + SecP256R1Field.multiply(t1, x1, t1); + + SecP256R1Field.squareN(t1, 2, t2); + SecP256R1Field.multiply(t2, t1, t2); + + SecP256R1Field.squareN(t2, 4, t1); + SecP256R1Field.multiply(t1, t2, t1); + + SecP256R1Field.squareN(t1, 8, t2); + SecP256R1Field.multiply(t2, t1, t2); + + SecP256R1Field.squareN(t2, 16, t1); + SecP256R1Field.multiply(t1, t2, t1); + + SecP256R1Field.squareN(t1, 32, t1); + SecP256R1Field.multiply(t1, x1, t1); + + SecP256R1Field.squareN(t1, 96, t1); + SecP256R1Field.multiply(t1, x1, t1); + + SecP256R1Field.squareN(t1, 94, t1); + SecP256R1Field.square(t1, t2); + + return Arrays.areEqual(x1, t2) ? new SecP256R1FieldElement(t1) : null; } public boolean equals(Object other) |