Add Montgomery conversion and high level I/O

[yanesca]

Prerequisites: https://github.com/Mbed-TLS/mbedtls/issues/6015, https://github.com/Mbed-TLS/mbedtls/issues/6016

Add Montgomery conversion and high level I/O.

Add missing fields to the mbedtls_mpi_mont_struct and update setup and free to initialise and free these fields: https://github.com/hanno-arm/mbedtls/blob/ecp_prototype/library/bignum_core.h#L86-L87 Extract functions required to do this from the prototype.

Extract low level conversion functions from the prototype: https://github.com/hanno-arm/mbedtls/blob/ecp_prototype/library/bignum_core.c#L963-L978 Adapt naming conventions and add them to bignum_mod_raw.h.

Add I/O functions for mbedtls_mod_residue that take a modulus as a parameter and automatically converts to internal representation as needed based on int_rep field of the modulus.

The task includes making the legacy Bignum functions call the extracted functions where the functionality is duplicated. This is necessary to minimise cost in code size.

Whenever extracting functions from the prototype, there should be separate commits containing the code from the prototype, with the absolute minimum of modifications that make the library compile. (It is Ok if these functions are not called at all at this point.) These commits should have Hanno as the author (git commit --author="Hanno Becker [email protected]")

The prototype is too macro heavy. Most new macros should be expanded/removed or replaced with static functions if possible. (Pre-existing macros should not be touched.) The macro MPI_CORE should expand to mbedtls_mpi_core_ ## func ## instead of mbedtls_mpi_core_ ## func ## _minimal.

All new function implementations should go into bignum_new.c.

This task is done when the following changes are merged on development:

• [x] Missing fields are added to to the mbedtls_mpi_mont_struct
• [x] Setup and free functions are updated to allocate, initialise and free these fields
• [x] Functions for doing these calculations are extracted from the prototype
• [ ] New I/O functions are added for residue
• [ ] New macros are expanded/removed
• [ ] The legacy functions in bignum.c are calling the new functions in library/bignum_core.h wherever possible
• [ ] Extensive unit tests are added for all new functions

[minosgalanakis]

PR 6083 and PR 6095 have been succeffully test-merged with conflicts resovles on 6017_add_Montgomery_conversion_high_lv_IO branch.

Currently the code compiles, and all implemented tests are passing

[tom-cosgrove-arm]

That's great! Note that with the merging of #6070 remove radix from test data I will be rebasing my PR on top of development, so you'll need to re-do the rebase (sorry)

[minosgalanakis]

That is as expected (Also the reason this is for now a branch and not a PR).

This step was neccessary to have a common starting point for implemting the Montgomery conversion and to also ensure there are no dragons when the other two tasks are merged.

[minosgalanakis]

Testing Design

Following the sync design meeting the following items have been agreed with regards to testing for this pr:

For testing we need to test the following methods:

• mbedtls_mpi_set_montgomery_constant_unsafe
• mbedtls_mpi_mod_raw_from_mont_rep
• mbedtls_mpi_mod_raw_to_mont_rep
• mbedtls_mpi_mod_read
• mbedtls_mpi_mod_write

The following methods may need new tests to warranty the succesfull allocation/deallocation/zeorisation of memory:

• mbedtls_mpi_mod_modulus_setup
• mbedtls_mpi_mod_modulus_free

For testing we need to test for:

• 4 and 8 limb sizes, prefferably in different testing routes.
• RR is matching precalculated values.
• That methods fail with invalid input.
• That conversion methods from cannonical to montgomery and montgomery to cannonical are working, by comparing precalculated values with the output.
• That consecutive calls for conversion to and from one form will give consistent outputs.
• Max allowed size is size of mod - 1. We need to test edge cases, and negative testing that if size == mod it will fail.
• Verify that memory is zerod and not accessible during setup - clean cycle.

Because of the high level nature of this PR, most of the math are testing during the Multiplication depedency, and is assumed to be trustworthy.

[yanesca]

Reopening as the PR that automatically closed this is only the first in a series of PRs implementing this.

[yanesca]

Still not done, one more PR to go.