From d7471d1d3bbb8b2ed454cb2e2ae15a7d178f2770 Mon Sep 17 00:00:00 2001 From: Jack Lloyd <lloyd@randombit.net> Date: Fri, 29 Jan 2016 14:35:30 -0500 Subject: 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. --- src/lib/math/numbertheory/ressol.cpp | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'src/lib/math/numbertheory/ressol.cpp') 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); -- cgit v1.2.3