bn: procduce correct sign for result of BN_mod()

There is a problem that appears when calling BN_div(a, c, a, b) with negative b.
In this case, the sign of the remainder c is incorrect.  The problem only
occurs if the dividend and the quotient are the same BIGNUM.

Fixes #15982

Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/15991)

1 files changed, 75 insertions, 2 deletions

diff --git a/test/bntest.c b/test/bntest.c
index 5bbef1f543..86fa163c6e 100644
--- a/test/bntest.c
+++ b/test/bntest.c
@@ -308,6 +308,75 @@ static int test_div_recip(void)
     return st;
 }
 
+static struct {
+    int n, divisor, result, remainder;
+} signed_mod_tests[] = {
+    {  10,   3,   3,   1 },
+    { -10,   3,  -3,  -1 },
+    {  10,  -3,  -3,   1 },
+    { -10,  -3,   3,  -1 },
+};
+
+static BIGNUM *set_signed_bn(int value)
+{
+    BIGNUM *bn = BN_new();
+
+    if (bn == NULL)
+        return NULL;
+    if (!BN_set_word(bn, value < 0 ? -value : value)) {
+        BN_free(bn);
+        return NULL;
+    }
+    BN_set_negative(bn, value < 0);
+    return bn;
+}
+
+static int test_signed_mod_replace_ab(int n)
+{
+    BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
+    int st = 0;
+
+    if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))
+            || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))
+            || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))
+            || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))
+        goto err;
+
+    if (TEST_true(BN_div(a, b, a, b, ctx))
+            && TEST_BN_eq(a, c)
+            && TEST_BN_eq(b, d))
+        st = 1;
+ err:
+    BN_free(a);
+    BN_free(b);
+    BN_free(c);
+    BN_free(d);
+    return st;
+}
+
+static int test_signed_mod_replace_ba(int n)
+{
+    BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
+    int st = 0;
+
+    if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))
+            || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))
+            || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))
+            || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))
+        goto err;
+
+    if (TEST_true(BN_div(b, a, a, b, ctx))
+            && TEST_BN_eq(b, c)
+            && TEST_BN_eq(a, d))
+        st = 1;
+ err:
+    BN_free(a);
+    BN_free(b);
+    BN_free(c);
+    BN_free(d);
+    return st;
+}
+
 static int test_mod(void)
 {
     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
@@ -329,8 +398,10 @@ static int test_mod(void)
         BN_set_negative(b, rand_neg());
         if (!(TEST_true(BN_mod(c, a, b, ctx))
                 && TEST_true(BN_div(d, e, a, b, ctx))
-                && TEST_true(BN_sub(e, e, c))
-                && TEST_BN_eq_zero(e)))
+                && TEST_BN_eq(e, c)
+                && TEST_true(BN_mul(c, d, b, ctx))
+                && TEST_true(BN_add(d, c, e))
+                && TEST_BN_eq(d, a)))
             goto err;
     }
     st = 1;
@@ -2875,6 +2946,8 @@ int setup_tests(void)
     if (n == 0) {
         ADD_TEST(test_sub);
         ADD_TEST(test_div_recip);
+        ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests));
+        ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests));
         ADD_TEST(test_mod);
         ADD_TEST(test_modexp_mont5);
         ADD_TEST(test_kronecker);