Repository: randombit/botan (cpp)

Issue:
Special case in ressol() for p == 2 is never reached
The `ressol()` function contains a special case for `p == 2`, so I assume this is a valid input.

But in 55fa3685c5053d66533a7a9e0f08403ffa95b323 the input checks there rearranged so that the `p.is_even()` check is now done at the beginning, which results in an exception being thrown before the special case for `p == 2` is reached.

Pull request description:
Correct the case of ressol modulo 2
Also rename ressol to sqrt_modulo_prime to make the meaning more clear.

Fixes #2962

Patch:
diff --git a/src/fuzzer/ecc_helper.h b/src/fuzzer/ecc_helper.h
index 4df23a572..9d9f881b1 100644
--- a/src/fuzzer/ecc_helper.h
+++ b/src/fuzzer/ecc_helper.h
@@ -33,7 +33,7 @@ Botan::BigInt decompress_point(bool yMod2,
    g += curve_b;
    g = g % curve_p;
 
-   Botan::BigInt z = ressol(g, curve_p);
+   Botan::BigInt z = sqrt_modulo_prime(g, curve_p);
 
    if(z < 0)
       throw Botan::Exception("Could not perform square root");
diff --git a/src/fuzzer/ressol.cpp b/src/fuzzer/ressol.cpp
index 99d48f98b..8b9fc85b4 100644
--- a/src/fuzzer/ressol.cpp
+++ b/src/fuzzer/ressol.cpp
@@ -21,7 +21,7 @@ void fuzz(const uint8_t in[], size_t len)
    try
       {
       const Botan::BigInt a = Botan::BigInt::decode(in, len);
-      Botan::BigInt a_sqrt = Botan::ressol(a, p);
+      Botan::BigInt a_sqrt = Botan::sqrt_modulo_prime(a, p);
 
       if(a_sqrt > 0)
          {
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 726a6d850..a8115951e 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -37,19 +37,16 @@ void sub_abs(BigInt& z, const BigInt& x, const BigInt& y)
 /*
 * Tonelli-Shanks algorithm
 */
-BigInt ressol(const BigInt& a, const BigInt& p)
+BigInt sqrt_modulo_prime(const BigInt& a, const BigInt& p)
    {
-   if(p <= 1 || p.is_even())
-      throw Invalid_Argument("ressol: invalid prime");
-
-   if(a == 0)
-      return BigInt::zero();
-   else if(a < 0)
-      throw Invalid_Argument("ressol: value to solve for must be positive");
-   else if(a >= p)
-      throw Invalid_Argument("ressol: value to solve for must be less than p");
-
-   if(p == 2)
+   if(p <= 1)
+      throw Invalid_Argument("sqrt_modulo_prime: invalid prime");
+   if(a >= p)
+      throw Invalid_Argument("sqrt_modulo_prime: value to solve for must be less than p");
+   if(a < 0)
+      throw Invalid_Argument("sqrt_modulo_prime: value to solve for must be positive");
+
+   if(p == 2 || a <= 1)
       return a;
 
    if(jacobi(a, p) != 1) // not a quadratic residue
@@ -63,6 +60,7 @@ BigInt ressol(const BigInt& a, const BigInt& p)
       return monty_exp_vartime(monty_p, a, ((p+1) >> 2));
       }
 
+   // Otherwise we have to use Shanks-Tonelli
    size_t s = low_zero_bits(p - 1);
    BigInt q = p >> s;
 
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index 92a99418b..eb04ae100 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -88,10 +88,10 @@ BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
 * about its arguments.
 *
 * @param x the input
-* @param p the prime
+* @param p the prime modulus
 * @return y such that (y*y)%p == x, or -1 if no such integer
 */
-BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p);
+BigInt BOTAN_PUBLIC_API(3,0) sqrt_modulo_prime(const BigInt& x, const BigInt& p);
 
 /**
 * @param x an integer
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 0fa46524f..168cede64 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -650,7 +650,7 @@ BigInt decompress_point(bool yMod2,
    g += curve_b;
    g = g % curve_p;
 
-   BigInt z = ressol(g, curve_p);
+   BigInt z = sqrt_modulo_prime(g, curve_p);
 
    if(z < 0)
       throw Decoding_Error("Error during EC point decompression");


Test patch:
diff --git a/src/tests/data/bn/ressol.vec b/src/tests/data/bn/sqrt_modulo_prime.vec
similarity index 96%
rename from src/tests/data/bn/ressol.vec
rename to src/tests/data/bn/sqrt_modulo_prime.vec
index 5ccecaa5c..84fd85fb2 100644
--- a/src/tests/data/bn/ressol.vec
+++ b/src/tests/data/bn/sqrt_modulo_prime.vec
@@ -1,4 +1,12 @@
-[RESSOL]
+[SqrtModuloPrime]
+Input = 0
+Modulus = 2
+Output = 0
+
+Input = 1
+Modulus = 2
+Output = 1
+
 Input = 5
 Modulus = 11
 Output = 4
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 515c7620b..4e76524d0 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -629,22 +629,22 @@ class BigInt_IsSquare_Test final : public Text_Based_Test
 
 BOTAN_REGISTER_TEST("math", "bn_issquare", BigInt_IsSquare_Test);
 
-class BigInt_Ressol_Test final : public Text_Based_Test
+class BigInt_Sqrt_Modulo_Prime_Test final : public Text_Based_Test
    {
    public:
-      BigInt_Ressol_Test() : Text_Based_Test("bn/ressol.vec", "Input,Modulus,Output") {}
+      BigInt_Sqrt_Modulo_Prime_Test() : Text_Based_Test("bn/sqrt_modulo_prime.vec", "Input,Modulus,Output") {}
 
       Test::Result run_one_test(const std::string& /*header*/, const VarMap& vars) override
          {
-         Test::Result result("BigInt Ressol");
+         Test::Result result("BigInt Sqrt Modulo Prime");
 
          const Botan::BigInt a = vars.get_req_bn("Input");
          const Botan::BigInt p = vars.get_req_bn("Modulus");
          const Botan::BigInt exp = vars.get_req_bn("Output");
 
-         const Botan::BigInt a_sqrt = Botan::ressol(a, p);
+         const Botan::BigInt a_sqrt = Botan::sqrt_modulo_prime(a, p);
 
-         result.test_eq("ressol", a_sqrt, exp);
+         result.test_eq("sqrt_modulo_prime", a_sqrt, exp);
 
          if(a_sqrt > 1)
             {
@@ -656,7 +656,7 @@ class BigInt_Ressol_Test final : public Text_Based_Test
          }
    };
 
-BOTAN_REGISTER_TEST("math", "bn_ressol", BigInt_Ressol_Test);
+BOTAN_REGISTER_TEST("math", "bn_sqrt_modulo_prime", BigInt_Sqrt_Modulo_Prime_Test);
 
 class BigInt_InvMod_Test final : public Text_Based_Test
    {
diff --git a/src/tests/test_ec_group.cpp b/src/tests/test_ec_group.cpp
index 5e8d778c8..4b01d058c 100644
--- a/src/tests/test_ec_group.cpp
+++ b/src/tests/test_ec_group.cpp
@@ -92,7 +92,7 @@ Botan::PointGFp create_random_point(Botan::RandomNumberGenerator& rng,
       const Botan::BigInt x3 = mod_p.multiply(x, mod_p.square(x));
       const Botan::BigInt ax = mod_p.multiply(group.get_a(), x);
       const Botan::BigInt y = mod_p.reduce(x3 + ax + group.get_b());
-      const Botan::BigInt sqrt_y = ressol(y, p);
+      const Botan::BigInt sqrt_y = Botan::sqrt_modulo_prime(y, p);
 
       if(sqrt_y > 1)
          {