Make Montgomery reduction available to applications

[jack-fortanix]

Enhancement\Feature Request

Suggested enhancement

Mbedtls already implements Montgomery reduction, but this functionality is not available to applications. I would propose making the functions mpi_montred, mpi_montmul and mpi_montg_init available as public APIs (presumably renamed the match library naming conventions).

Justification - why does the library need this feature?

Applications doing mathematical operations with a single modulus can be greatly sped up (and get better side channel resistance) by using Montgomery multiplication/reduction instead of performing a multiply followed by standard division.

As an example, we have implemented support for decompressing compressed EC points in our application using the Mbedtls API. We would have just contributed a patch to the library, but it seems this feature has already been proposed and rejected in #861.

Other applications that Mbedtls is unlikely to implement directly but that perform many modular multiplications include format preserving encryption, BIP32 key derivation, elliptic curve signature schemes like GOST/ECGDSA/SM2, ... all of which could be aided by making Montgomery operations available. And again the functionality already exists in the library, it just is not available to applications. So there is no cost to code size from this change.

If if would be accepted we would provide a patch.

[Wesmania]

Bumping just to say I have a use case for this :) (sw implementation of an API that has a Montgomery multiplication function)

[gilles-peskine-arm]

@Wesmania This is currently off our radar. However, I see no objection if someone makes a pull request.

Please note that the existing functions are meant for internal use and have constraints on their arguments that they don't verify. So we wouldn't just expose the existing functions. We could expose wrappers that ensure that there's no way to cause a buffer overflow by passing valid bignum objects. These wrappers would need unit tests covering edge cases (e.g. negative numbers, zero, very large values, aliasing).

[gilles-peskine-arm]

#6213 adds an internal interface that performs conversion to and from Montgomery representation. We currently have no plans to build a public interface on top of this.

[gilles-peskine-arm]

Revisiting this in light of the plans for the next major version of Mbed TLS (or rather TF-PSA-Crypto 1.0): we are going to focus on being a crypto library, and there will no longer be a stable API for bignum calculations.

It will remain possible to link applications that call bignum functions, including the ones that perform Montgomery reduction. That interface will be documented, and intended to be secure (if you carefully follow all documented limitations). But we make no promises regarding stability. In particular, a security update may change those functions' interfaces, which is a major reason why we don't want to make it a public API.