OSSL_FN: Convert the mod_exp_mont base without testing its valuefeature/ossl_fn

OSSL_FN_mod_exp_mont() converted the base with OSSL_FN_to_mont(), which
branches on whether the base is below the modulus.  For the Fermat
inverse the base is the secret, so every constant-time inverse (ECDSA,
DSA and SM2 nonces and keys, projective EC coordinates) branches on a
secret.  For a reduced base the branch always goes the same way, as it
does in BN_mod_exp_mont_consttime(), so this is not a measurable leak,
but it fails ct-validation.

A base no wider than the modulus is below R, so reduce it with
OSSL_FN_mont_reduce() and convert it with OSSL_FN_to_mont_quick().
Wider bases keep the existing path, chosen on the widths alone.  Use
OSSL_FN_to_mont_quick() for the public mont(1) as well.

Add a secret-operand OSSL_FN_mod_inverse_prime() case to test_fn_ct.

Assisted-by: Claude Code:claude-opus-5-5
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Richard Levitte <[email protected]>
Merge-date: Fri Oct  9 07:16:20 2026
Merged-from: https://github.com/openssl/openssl/pull/33108

2 files changed, 81 insertions, 12 deletions

diff --git a/crypto/fn/fn_exp.c b/crypto/fn/fn_exp.c
index 0635640a05b..584f07470c1 100644
--- a/crypto/fn/fn_exp.c
+++ b/crypto/fn/fn_exp.c
@@ -246,15 +246,18 @@ static size_t mod_exp_mont_nested(const OSSL_FN *a, const OSSL_FN *m,
         in_mont = &mont_model;
 
     /*
-     * to_mont / loop mul_mont_quick / from_mont, via their ctx_size
+     * Base conversion / loop mul_mont_quick / from_mont, via their ctx_size
      * companions in fn_mont.c; only one is live at a time, so take the max.
-     * to_mont() performs the initial reduction of a internally (via the
-     * reducing OSSL_FN_mul_mont), so no separate OSSL_FN_mod() frame is
-     * sized.  The fixed-window loop multiplies only already-reduced
-     * Montgomery-domain values, so it uses the non-reducing
+     * A base no wider than m is reduced with OSSL_FN_mont_reduce(), a wider
+     * one by to_mont() (via the reducing OSSL_FN_mul_mont), so no separate
+     * OSSL_FN_mod() frame is sized.  The fixed-window loop multiplies only
+     * already-reduced Montgomery-domain values, so it uses the non-reducing
      * OSSL_FN_mul_mont_quick() and its smaller ctx_size.
      */
-    mont_size = ossl_fn_ctx_max_size(OSSL_FN_to_mont_ctx_size(NULL, a, in_mont),
+    mont_size = a->dsize <= m->dsize
+        ? OSSL_FN_mont_reduce_ctx_size(NULL, a, in_mont)
+        : OSSL_FN_to_mont_ctx_size(NULL, a, in_mont);
+    mont_size = ossl_fn_ctx_max_size(mont_size,
         ossl_fn_ctx_max_size(OSSL_FN_mul_mont_quick_ctx_size(NULL, NULL, NULL, in_mont),
             OSSL_FN_from_mont_ctx_size(NULL, NULL, in_mont)));
 
@@ -668,18 +671,24 @@ int OSSL_FN_mod_exp_mont(OSSL_FN *r, const OSSL_FN *a, const OSSL_FN *p,
         /* ml > 0 is guaranteed, so OSSL_FN_one() cannot fail. */
         if (!ossl_assert(OSSL_FN_one(am)))
             goto err;
-        if (!OSSL_FN_to_mont(tmp, am, mont, ctx))
+        if (!OSSL_FN_to_mont_quick(tmp, am, mont, ctx))
             goto err;
     }
 
     /*
-     * a^1 in Montgomery domain.  to_mont() reduces a modulo m internally
-     * when a is not already reduced, so no separate OSSL_FN_mod() is
-     * needed.  When a == 0 (mod m), mont(a) == 0 and the fixed-window loop
-     * yields 0 for any non-zero exponent.
+     * a^1 in Montgomery domain.  A base no wider than m is below R, so
+     * OSSL_FN_mont_reduce() reduces it without testing its value; a wider
+     * one is left to to_mont(), which reduces it by division.  The choice
+     * depends on the widths alone.  When a == 0 (mod m), mont(a) == 0 and
+     * the fixed-window loop yields 0 for any non-zero exponent.
      */
-    if (!OSSL_FN_to_mont(am, a, mont, ctx))
+    if (a->dsize <= m->dsize) {
+        if (!OSSL_FN_mont_reduce(am, a, mont, ctx)
+            || !OSSL_FN_to_mont_quick(am, am, mont, ctx))
+            goto err;
+    } else if (!OSSL_FN_to_mont(am, a, mont, ctx)) {
         goto err;
+    }
 
     size_t window0, wmask, wvalue;
 
diff --git a/test/fn_ct_test.c b/test/fn_ct_test.c
index 11958ad0563..da486bed0de 100644
--- a/test/fn_ct_test.c
+++ b/test/fn_ct_test.c
@@ -460,11 +460,71 @@ err:
     return ret;
 }
 
+/*
+ * The Fermat inverse a^(m-2) mod m with a secret a, as used for ECDSA, DSA
+ * and SM2 nonces and keys and for projective EC coordinates.
+ */
+static int test_mod_inverse_prime(int idx)
+{
+    size_t mi = idx / OSSL_NELEM(pairs), pi = idx % OSSL_NELEM(pairs);
+    BN_CTX *bnctx = BN_CTX_new();
+    BIGNUM *m = NULL, *a = BN_new(), *e = BN_new();
+    OSSL_FN *fm = NULL, *fa = NULL, *r = NULL;
+    OSSL_FN_MONT_CTX *mont = NULL;
+    OSSL_FN_CTX *ctx = NULL;
+    size_t len = 0, limbs = 0;
+    int ret = 0;
+
+    if (!TEST_ptr(bnctx) || !TEST_ptr(a) || !TEST_ptr(e)
+        || !TEST_true(BN_hex2bn(&m, moduli[mi]))
+        || !TEST_true(set_operand(a, m, pairs[pi].a, bnctx)))
+        goto err;
+    /* Zero has no inverse */
+    if (BN_is_zero(a)) {
+        ret = 1;
+        goto err;
+    }
+
+    len = (size_t)BN_num_bytes(m);
+    limbs = (len + OSSL_FN_BYTES - 1) / OSSL_FN_BYTES;
+    if (!TEST_ptr(fm = fn_from_bn(m, limbs, len))
+        || !TEST_ptr(fa = fn_from_bn(a, limbs, len))
+        || !TEST_ptr(r = OSSL_FN_new_limbs(limbs))
+        || !TEST_ptr(mont = OSSL_FN_MONT_CTX_new(fm))
+        || !TEST_ptr(ctx = OSSL_FN_CTX_new_size(NULL,
+                         OSSL_FN_mod_inverse_prime_ctx_size(r, fa, fm, mont))))
+        goto err;
+
+    fn_secret(fa, limbs);
+
+    if (!TEST_true(OSSL_FN_mod_inverse_prime(r, fa, fm, ctx, mont))
+        || !TEST_ptr(BN_mod_inverse(e, a, m, bnctx))
+        || !check("mod_inverse_prime", r, limbs, e, len))
+        goto err;
+
+    ret = 1;
+err:
+    if (fa != NULL)
+        fn_declassify(fa, limbs);
+    OSSL_FN_CTX_free(ctx);
+    OSSL_FN_MONT_CTX_free(mont);
+    OSSL_FN_free(fm);
+    OSSL_FN_free(fa);
+    OSSL_FN_free(r);
+    BN_free(m);
+    BN_free(a);
+    BN_free(e);
+    BN_CTX_free(bnctx);
+    return ret;
+}
+
 int setup_tests(void)
 {
     ADD_ALL_TESTS(test_quick_ops, (int)(OSSL_NELEM(moduli) * OSSL_NELEM(pairs)));
     ADD_ALL_TESTS(test_mont_ops, (int)(OSSL_NELEM(moduli) * OSSL_NELEM(pairs)));
     ADD_ALL_TESTS(test_mont_reduce, (int)(2 * OSSL_NELEM(moduli)));
     ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(exp_limbs));
+    ADD_ALL_TESTS(test_mod_inverse_prime,
+        (int)(OSSL_NELEM(moduli) * OSSL_NELEM(pairs)));
     return 1;
 }