Bignum: Implement mbedtls_mpi_mod_raw_inv_prime() and tests
Fixes #6023.
Signed-off-by: Tom Cosgrove <tom.cosgrove@arm.com>
diff --git a/library/bignum_mod_raw.c b/library/bignum_mod_raw.c
index 22e56b7..03924d2 100644
--- a/library/bignum_mod_raw.c
+++ b/library/bignum_mod_raw.c
@@ -124,6 +124,34 @@
/* BEGIN MERGE SLOT 3 */
+size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs( size_t AN_limbs )
+{
+ /* mbedtls_mpi_mod_raw_inv_prime() needs a temporary for the exponent,
+ * which will be the same size as the modulus and input (AN_limbs),
+ * and additional space to pass to mbedtls_mpi_core_exp_mod(). */
+ return( AN_limbs +
+ mbedtls_mpi_core_exp_mod_working_limbs( AN_limbs, AN_limbs ) );
+}
+
+void mbedtls_mpi_mod_raw_inv_prime( mbedtls_mpi_uint *X,
+ const mbedtls_mpi_uint *A,
+ const mbedtls_mpi_uint *N,
+ size_t AN_limbs,
+ const mbedtls_mpi_uint *RR,
+ mbedtls_mpi_uint *T )
+{
+ /* Inversion by power: g^|G| = 1 => g^(-1) = g^(|G|-1), and
+ * |G| = N - 1, so we want
+ * g^(|G|-1) = g^(N - 2)
+ */
+ mbedtls_mpi_uint *Nminus2 = T;
+ (void) mbedtls_mpi_core_sub_int( Nminus2, N, 2, AN_limbs );
+
+ mbedtls_mpi_core_exp_mod( X,
+ A, N, AN_limbs, Nminus2, AN_limbs,
+ RR, T + AN_limbs );
+}
+
/* END MERGE SLOT 3 */
/* BEGIN MERGE SLOT 4 */
diff --git a/library/bignum_mod_raw.h b/library/bignum_mod_raw.h
index d7b6dd1..698119e 100644
--- a/library/bignum_mod_raw.h
+++ b/library/bignum_mod_raw.h
@@ -174,6 +174,51 @@
/* BEGIN MERGE SLOT 3 */
+/**
+ * \brief Returns the number of limbs of working memory required for
+ * a call to `mbedtls_mpi_mod_raw_inv_prime()`.
+ *
+ * \param AN_limbs The number of limbs in the input `A` and the modulus `N`
+ * (they must be the same size) that will be given to
+ * `mbedtls_mpi_mod_raw_inv_prime()`.
+ *
+ * \return The number of limbs of working memory required by
+ * `mbedtls_mpi_mod_raw_inv_prime()`.
+ */
+size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs( size_t AN_limbs );
+
+/**
+ * \brief Perform fixed-width modular inversion of a Montgomery-form MPI with
+ * respect to a modulus \p N that must be prime.
+ *
+ * \p X may be aliased to \p A, but not to \p N or \p RR.
+ *
+ * \param[out] X The modular inverse of \p A with respect to \p N.
+ * Will be in Montgomery form.
+ * \param[in] A The number to calculate the modular inverse of.
+ * Must be in Montgomery form. Must not be 0.
+ * \param[in] N The modulus, as a little-endian array of length \p AN_limbs.
+ * Must be prime.
+ * \param AN_limbs The number of limbs in \p A, \p N and \p RR.
+ * \param[in] RR The precomputed residue of 2^{2*biL} modulo N, as a little-
+ * endian array of length \p AN_limbs.
+ * \param[in,out] T Temporary storage of at least the number of limbs returned
+ * by `mbedtls_mpi_mod_raw_inv_prime_working_limbs()`.
+ * Its initial content is unused and its final content is
+ * indeterminate.
+ * It must not alias or otherwise overlap any of the other
+ * parameters.
+ * It is up to the caller to zeroize \p T when it is no
+ * longer needed, and before freeing it if it was dynamically
+ * allocated.
+ */
+void mbedtls_mpi_mod_raw_inv_prime( mbedtls_mpi_uint *X,
+ const mbedtls_mpi_uint *A,
+ const mbedtls_mpi_uint *N,
+ size_t AN_limbs,
+ const mbedtls_mpi_uint *RR,
+ mbedtls_mpi_uint *T );
+
/* END MERGE SLOT 3 */
/* BEGIN MERGE SLOT 4 */