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.

2 files changed, 31 insertions, 0 deletions

diff --git a/src/tests/data/bigint.vec b/src/tests/data/bigint.vec
index bba83deb6..2445c8de4 100644
--- a/src/tests/data/bigint.vec
+++ b/src/tests/data/bigint.vec
@@ -2580,3 +2580,16 @@ IsPrime = 0
 Value = 0x53251
 IsPrime = 0
 
+[RESSOL]
+Input = 5
+Modulus = 11
+Output = 4
+
+Input = 5
+Modulus = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
+Output = 5128001483797946816458955548662741861156429216952843873274631897232136999791540518339021539968609345897897688700798659762992302941280478805021587896033442584
+
+# Input and composite modulus which would previously cause a (nearly) infinite loop
+Input = 4
+Modulus = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057149
+Output = -1
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index e63be6333..33db242aa 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -278,6 +278,24 @@ class BigInt_KAT_Tests : public Text_Based_Test
 
             result.test_eq("value", Botan::is_prime(value, Test::rng()), v_is_prime);
             }
+         else if(algo == "RESSOL")
+            {
+            const Botan::BigInt a = get_req_bn(vars, "Input");
+            const Botan::BigInt p = get_req_bn(vars, "Modulus");
+            const Botan::BigInt exp = get_req_bn(vars, "Output");
+
+            const Botan::BigInt a_sqrt = Botan::ressol(a, p);
+
+            result.test_eq("result", a_sqrt, exp);
+
+            if(a_sqrt > 1)
+               {
+               const Botan::BigInt a_sqrt2 = (a_sqrt*a_sqrt) % p;
+               result.test_eq("square correct", a_sqrt2, a);
+               }
+
+            return result;
+            }
          else
             {
             result.test_failure("Unknown BigInt algorithm " + algo);