diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-03-04 13:32:06 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-03-04 13:32:06 +0400 |
commit | fb5f285cd2c0511de5244615cd7fcdf3f9d6452b (patch) | |
tree | fb3228a9df58c97d9a6392a46c41504aa946b73b /core/src/main/java/org/bouncycastle | |
parent | c01119978016d48c6fbf48f83ae853014a92efdf (diff) |
Fix infinite loop issue when there is no sqrt
Add test case to check that sqrt returns null for non-squares
Diffstat (limited to 'core/src/main/java/org/bouncycastle')
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java | 85 |
1 files changed, 56 insertions, 29 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java index 74ebc047..90e03de3 100644 --- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java +++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java @@ -140,39 +140,19 @@ public class SecP224R1FieldElement extends ECFieldElement int[] r = Mod.random(SecP224R1Field.P); int[] t = Nat224.create(); - for (;;) + if (!isSquare(c)) { - int[] d1 = Nat224.create(); - Nat224.copy(r, d1); - int[] e1 = Nat224.create(); - e1[0] = 1; - int[] f1 = Nat224.create(); - RP(nc, d1, e1, f1, t); - - int[] d0 = Nat224.create(); - int[] e0 = Nat224.create(); - - for (int k = 1; k < 96; ++k) - { - Nat224.copy(d1, d0); - Nat224.copy(e1, e0); - - RS(d1, e1, f1, t); - - if (Nat224.isZero(d1)) - { - Mod.invert(SecP224R1Field.P, e0, f1); - SecP224R1Field.multiply(f1, d0, f1); - - SecP224R1Field.square(f1, d1); - - return Nat224.eq(c, d1) ? new SecP224R1FieldElement(f1) : null; - } - } + return null; + } - // Avoid any possible infinite loop due to a bad random number generator + while (!trySqrt(nc, r, t)) + { SecP224R1Field.addOne(r, r); } + + SecP224R1Field.square(t, r); + + return Nat224.eq(c, r) ? new SecP224R1FieldElement(t) : null; } public boolean equals(Object other) @@ -196,6 +176,23 @@ public class SecP224R1FieldElement extends ECFieldElement return Q.hashCode() ^ Arrays.hashCode(x, 0, 7); } + private static boolean isSquare(int[] x) + { + int[] t1 = Nat224.create(); + int[] t2 = Nat224.create(); + Nat224.copy(x, t1); + + for (int i = 0; i < 7; ++i) + { + Nat224.copy(t1, t2); + SecP224R1Field.squareN(t1, 1 << i, t1); + SecP224R1Field.multiply(t1, t2, t1); + } + + SecP224R1Field.squareN(t1, 95, t1); + return Nat224.isOne(t1); + } + private static void RM(int[] nc, int[] d0, int[] e0, int[] d1, int[] e1, int[] f1, int[] t) { SecP224R1Field.multiply(e1, e0, t); @@ -242,4 +239,34 @@ public class SecP224R1FieldElement extends ECFieldElement int c = Nat.shiftUpBits(7, f, 2, 0); SecP224R1Field.reduce32(c, f); } + + private static boolean trySqrt(int[] nc, int[] r, int[] t) + { + int[] d1 = Nat224.create(); + Nat224.copy(r, d1); + int[] e1 = Nat224.create(); + e1[0] = 1; + int[] f1 = Nat224.create(); + RP(nc, d1, e1, f1, t); + + int[] d0 = Nat224.create(); + int[] e0 = Nat224.create(); + + for (int k = 1; k < 96; ++k) + { + Nat224.copy(d1, d0); + Nat224.copy(e1, e0); + + RS(d1, e1, f1, t); + + if (Nat224.isZero(d1)) + { + Mod.invert(SecP224R1Field.P, e0, t); + SecP224R1Field.multiply(t, d0, t); + return true; + } + } + + return false; + } } |