Fix (nearly) infinite loop in RESSOL (modular square root).

It first computed the first i for q**(2**i) == 1, then checked that i
was smaller than s. Given a composite modulus (for which the algorithm
does not work), the loop might do a very large amount of work before
returning the failure.

1 files changed, 12 insertions, 8 deletions

diff --git a/src/lib/math/numbertheory/ressol.cpp b/src/lib/math/numbertheory/ressol.cpp
index 834dd94ce..875d054c3 100644
--- a/src/lib/math/numbertheory/ressol.cpp
+++ b/src/lib/math/numbertheory/ressol.cpp
@@ -16,15 +16,17 @@ namespace Botan {
 */
 BigInt ressol(const BigInt& a, const BigInt& p)
    {
-   if(a < 0)
-      throw Invalid_Argument("ressol(): a to solve for must be positive");
-   if(p <= 1)
-      throw Invalid_Argument("ressol(): prime must be > 1");
-
    if(a == 0)
       return 0;
+   else if(a < 0)
+      throw Invalid_Argument("ressol(): a to solve for must be positive");
+
    if(p == 2)
       return a;
+   else if(p <= 1)
+      throw Invalid_Argument("ressol(): prime must be > 1 a");
+   else if(p.is_even())
+      throw Invalid_Argument("ressol(): invalid prime");
 
    if(jacobi(a, p) != 1) // not a quadratic residue
       return -BigInt(1);
@@ -63,10 +65,12 @@ BigInt ressol(const BigInt& a, const BigInt& p)
          {
          q = mod_p.square(q);
          ++i;
-         }
 
-      if(s <= i)
-         return -BigInt(1);
+         if(s >= i)
+            {
+            return -BigInt(1);
+            }
+         }
 
       c = power_mod(c, BigInt::power_of_2(s-i-1), p);
       r = mod_p.multiply(r, c);