[openssl/openssl] cc2945: OSSL_FN: Add modular multiplicative inverse

  Branch: refs/heads/feature/ossl_fn
  Home:   https://github.com/openssl/openssl
  Commit: cc2945043fcf5cf287a9716fc81897cb2e2caa12
      https://github.com/openssl/openssl/commit/cc2945043fcf5cf287a9716fc81897cb2e2caa12
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-27 (Mon, 27 Jul 2026)

  Changed paths:
    M crypto/err/openssl.txt
    M crypto/fn/build.info
    M crypto/fn/fn_err.c
    A crypto/fn/fn_mod_inv.c
    M include/crypto/fn.h
    M include/crypto/fnerr.h
    M test/fn_api_test.c

  Log Message:
  -----------
  OSSL_FN: Add modular multiplicative inverse

OSSL_FN_mod_inverse() is the OSSL_FN counterpart of the constant-time
bn_mod_inverse_no_branch(): the same extended-Euclidean invariant, the
same A/B/X/Y/D/M working-set rotation, and none of the value-branching
shortcuts.  The no_branch function does not use masked conditional swaps
in this loop (those live in BN_gcd's Bernstein-Yang code), so no
constant-time helpers are needed; what leaks -- iteration count, the
is_one/cmp/sign tests -- matches the BN counterpart exactly.

The branching int_bn_mod_inverse() variant (odd-n <= 2048-bit fast path
and small-D D*X+Y optimizations) is intentionally not included; a
TODO(FIXNUM) notes it may be added later if a use case needs the speed
and can tolerate its leak profile.

OSSL_FN is unsigned, so the int sign bookkeeping stays internal to the
function and the operation returns the non-negative residue.  The
degenerate moduli n == 0 and n == 1 short-circuit to the new
OSSL_FN_R_NO_INVERSE error; every other edge case (a == 0, non-coprime
operands) falls out of the algorithm naturally.

Assisted-by: Pi:z-ai/glm-5.2
Assisted-by: Pi:moonshotai/kimi-k3
Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/1966
Signed-off-by: Richard Levitte <[email protected]>

Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Tomas Mraz <[email protected]>
MergeDate: Fri Jul 31 09:24:02 2026
(Merged from https://github.com/openssl/openssl/pull/31933)


  Commit: 79b5e09d74bf6c57d8018e15da9e9f62b3458120
      https://github.com/openssl/openssl/commit/79b5e09d74bf6c57d8018e15da9e9f62b3458120
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-27 (Mon, 27 Jul 2026)

  Changed paths:
    M test/fntest.c

  Log Message:
  -----------
  OSSL_FN: Add modular-inverse test mirroring bntest

test_mod_inverse in fntest.c mirrors the standalone test_mod_inverse in
bntest.c: the same operands (5193817943 ^-1 mod 3259122431 == 2609653924),
exercised through the OSSL_FN path via bn_acquire_ossl_fn() / bn_release().

The aliasing case diverges from bntest on purpose.  BN_mod_inverse's
binary fast path rejects a result that aliases the modulus (returns NULL),
so bntest asserts NULL there.  The OSSL_FN counterpart follows the
no-branch structure instead, which copies the modulus into a scratch
temporary before the result is written -- and OSSL_FN_div() likewise
captures the denominator before writing the remainder -- so r == n
aliasing succeeds and yields the same inverse.  The test asserts that,
documenting the OSSL_FN-faithful behaviour.

Assisted-by: Pi:z-ai/glm-5.2
Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/1966
Signed-off-by: Richard Levitte <[email protected]>

Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Tomas Mraz <[email protected]>
MergeDate: Fri Jul 31 09:24:04 2026
(Merged from https://github.com/openssl/openssl/pull/31933)


  Commit: 4bd8a62af12729493247d7b9085595cefd135df2
      https://github.com/openssl/openssl/commit/4bd8a62af12729493247d7b9085595cefd135df2
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M test/fntest.c
    M test/recipes/11-test_fn.t

  Log Message:
  -----------
  OSSL_FN: Add mod_inverse stanza tests to fntest

Add a file_modinv() stanza handler to test/fntest.c, exercising
OSSL_FN_mod_inverse() through the BIGNUM/OSSL_FN bridge.  It reuses
the bntest ModInv corpus (test/recipes/10-test_bn_data/bnmodinv.txt),
so 11-test_fn.t now feeds that file to fntest.

The handler mirrors bntest's file_modinv(): a ModInv value of -1 marks
a negative test that expects OSSL_FN_mod_inverse() to fail with
OSSL_FN_R_NO_INVERSE (covering a == 0, non-coprime pairs, and the
degenerate moduli M = 0 and M = 1), while a non-negative ModInv is
checked against the computed inverse and verified by A * inv(A) == 1
(mod M).

OSSL_FN is unsigned, so OSSL_FN_mod_inverse() computes the inverse of
|A|; for negative A the result is adjusted to M - r before the
comparison, matching the sign convention of the corpus.

Assisted-by: Pi:z-ai/glm-5.2

Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Tomas Mraz <[email protected]>
MergeDate: Fri Jul 31 09:32:20 2026
(Merged from https://github.com/openssl/openssl/pull/32027)


  Commit: ea53f98a4ab3c6158fefab43066fba4f814a8ab1
      https://github.com/openssl/openssl/commit/ea53f98a4ab3c6158fefab43066fba4f814a8ab1
  Author: Igor Ustinov <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M crypto/err/openssl.txt
    M crypto/fn/build.info
    M crypto/fn/fn_div.c
    M crypto/fn/fn_err.c
    M crypto/fn/fn_local.h
    A crypto/fn/fn_mont.c
    M include/crypto/fn.h
    M include/crypto/fnerr.h
    M include/crypto/types.h
    M test/fntest.c

  Log Message:
  -----------
  OSSL_FN: Add Montgomery multiplication

Assisted-by: Claude:claude-opus-4-8

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Richard Levitte <[email protected]>
Reviewed-by: Tomas Mraz <[email protected]>
MergeDate: Fri Jul 31 09:36:29 2026
(Merged from https://github.com/openssl/openssl/pull/31072)


  Commit: 09b1978dea833a10cf6683be0385021d2f24a51d
      https://github.com/openssl/openssl/commit/09b1978dea833a10cf6683be0385021d2f24a51d
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M crypto/fn/build.info
    A crypto/fn/fn_exp.c
    M include/crypto/fn.h
    M test/fn_api_test.c

  Log Message:
  -----------
  OSSL_FN: Add OSSL_FN_mod_exp()

Only the simple, non-constant-time sliding-window implementation
OSSL_FN_mod_exp_simple() is added for now.  The dispatcher scaffolds the
Montgomery and reciprocal-based variants (MONT_MUL_MOD / MONT_EXP_WORD /
RECP_MUL_MOD) as #undef'd stubs; the constant-time Montgomery path and the
reciprocal path will be added in follow-up commits.

Assisted-by: Pi:z-ai/glm-5.2
Assisted-by: Pi:moonshotai/kimi-k3
Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/2025
Signed-off-by: Richard Levitte <[email protected]>

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Matt Caswell <[email protected]>
MergeDate: Fri Jul 31 09:38:07 2026
(Merged from https://github.com/openssl/openssl/pull/31962)


  Commit: c792af6d38fbfb9c5fc738546252aeb072639513
      https://github.com/openssl/openssl/commit/c792af6d38fbfb9c5fc738546252aeb072639513
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M test/fntest.c

  Log Message:
  -----------
  OSSL_FN: Add ModExp stanza test in fntest

Assisted-by: Pi:z-ai/glm-5.2
Assisted-by: Pi:moonshotai/kimi-k3
Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/2025
Signed-off-by: Richard Levitte <[email protected]>

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Matt Caswell <[email protected]>
MergeDate: Fri Jul 31 09:38:09 2026
(Merged from https://github.com/openssl/openssl/pull/31962)


  Commit: 23046608037c73f50a583efdb5f39c60d2c87bd5
      https://github.com/openssl/openssl/commit/23046608037c73f50a583efdb5f39c60d2c87bd5
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M crypto/fn/fn_exp.c
    M include/crypto/fn.h
    M test/fn_api_test.c

  Log Message:
  -----------
  OSSL_FN: Add OSSL_FN_mod_exp_mont()

Route odd moduli in OSSL_FN_mod_exp() to a Montgomery sliding-window
path, a faithful port of BN_mod_exp_mont() in crypto/bn/bn_exp.c.  The
fixed-width deviations, the constant-time caveat, the dispatcher
routing, and the OSSL_FN_mod_exp_ctx_size() sizing model are all
documented in the respective function headers.

test_fn and test_fn_api pass on linux-x86_64 and linux-x86; the odd-
modulus cases (the stanza suite and the KAT/alias tests) now exercise
the Montgomery path against the BN_mod_exp oracle.

Assisted-by: Pi:z-ai/glm-5.2
Assisted-by: Pi:moonshotai/kimi-k3
Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/2025
Signed-off-by: Richard Levitte <[email protected]>

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Matt Caswell <[email protected]>
MergeDate: Fri Jul 31 09:38:11 2026
(Merged from https://github.com/openssl/openssl/pull/31962)


  Commit: ed3cf9704fd4a4784282013b4c462ba0ec1c270e
      https://github.com/openssl/openssl/commit/ed3cf9704fd4a4784282013b4c462ba0ec1c270e
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M crypto/fn/build.info
    A crypto/fn/fn_kron.c
    M include/crypto/fn.h
    M test/fn_api_test.c

  Log Message:
  -----------
  OSSL_FN: Add OSSL_FN_kronecker()

The OSSL_FN counterpart of BN_kronecker().  OSSL_FN is unsigned, so
BN_kronecker()'s sign-handling branches are dropped: the B->neg block
goes, and step 4's (A->neg ? ~BN_lsw(A) : BN_lsw(A)) collapses to
lsw(A).  Not constant-time; the leak profile matches the BN counterpart,
which is the reference.

Assisted-by: Pi:z-ai/glm-5.2
Assisted-by: Pi:moonshotai/kimi-k3
Issue: https://github.com/openssl/project/issues/2026
Signed-off-by: Richard Levitte <levitte/openssl.foundation>

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Matt Caswell <[email protected]>
MergeDate: Fri Jul 31 09:39:01 2026
(Merged from https://github.com/openssl/openssl/pull/31963)


  Commit: 0677874b8e9658f455d67583a5d48a6d8c06bb12
      https://github.com/openssl/openssl/commit/0677874b8e9658f455d67583a5d48a6d8c06bb12
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M crypto/err/openssl.txt
    M crypto/fn/build.info
    M crypto/fn/fn_err.c
    A crypto/fn/fn_sqrt.c
    M include/crypto/fn.h
    M include/crypto/fnerr.h
    M test/fn_api_test.c

  Log Message:
  -----------
  OSSL_FN: Add OSSL_FN_mod_sqrt()

The OSSL_FN counterpart of BN_mod_sqrt().  The root is computed and
verified (ret^2 == a mod p, else NOT_A_SQUARE) in a p-wide temporary,
then OSSL_FN_copy_truncate()'d into the caller-sized |ret|, so a
destination narrower than p does not fail the strict copy or mis-report
a non-square when the root's high limb is truncated.

Not constant-time; the leak profile matches the BN counterpart, which
is the reference.

Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/2026
Assisted-by: Pi:z-ai/glm-5.2
Assisted-by: Pi:moonshotai/kimi-k3
Signed-off-by: Richard Levitte <levitte/openssl.foundation>

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Matt Caswell <[email protected]>
MergeDate: Fri Jul 31 09:39:04 2026
(Merged from https://github.com/openssl/openssl/pull/31963)


  Commit: 7c3c77807023bbf1aef20150dfccce58785e6a30
      https://github.com/openssl/openssl/commit/7c3c77807023bbf1aef20150dfccce58785e6a30
  Author: Richard Levitte <[email protected]>
  Date:   2026-07-31 (Fri, 31 Jul 2026)

  Changed paths:
    M test/fntest.c

  Log Message:
  -----------
  OSSL_FN: Add ModSqrt stanza test in fntest

Mirrors file_modsqrt() in test/bntest.c.  Both square roots are
accepted for positive cases (ret and p - ret), since a square root has
two roots.

The operand a is reduced into [0, p) with BN_nnmod() at the boundary
before being handed to OSSL_FN_mod_sqrt(): BN_mod_sqrt() does that
reduction internally, but OSSL_FN_mod_sqrt() is unsigned and sees only
the magnitude, so feeding a raw negative a (e.g. a = -5, p = 7, which
reduces to 2) would present the wrong residue.

Related-to: doc/designs/fixed-size-large-numbers.md
Issue: https://github.com/openssl/project/issues/2026
Assisted-by: Pi:z-ai/glm-5.2
Signed-off-by: Richard Levitte <levitte/openssl.foundation>

Reviewed-by: Jakub Zelenka <[email protected]>
Reviewed-by: Igor Ustinov <[email protected]>
Reviewed-by: Matt Caswell <[email protected]>
MergeDate: Fri Jul 31 09:39:06 2026
(Merged from https://github.com/openssl/openssl/pull/31963)


Compare: https://github.com/openssl/openssl/compare/ff4f86bece81...7c3c77807023

To unsubscribe from these emails, change your notification settings at https://github.com/openssl/openssl/settings/notifications

-- 
You received this message because you are subscribed to the Google Groups "openssl-commits" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/a/openssl.org/d/msgid/openssl-commits/openssl/openssl/push/refs/heads/feature/ossl_fn/ff4f86-7c3c77%40github.com.