bignum_core: Add mbedtls_mpi_core_gcd_modinv_odd()
This is a direct translation of sict_mi2() from
https://github.com/mpg/cryptohack/blob/main/ct-pres.py
which was presented in the book club's special session.
This commit only includes two test cases which is very little. Most of
the test cases will be generated by Python modules that belong to the
framework. However we can't have the framework generate those before we
have the corresponding test function in the consuming branches. So,
extended tests are coming as a 2nd step, after the test function has
been merged.
(The test cases in .misc should stay, as they can be convenient when
working on the test function.)
Signed-off-by: Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com>
diff --git a/library/bignum_core.h b/library/bignum_core.h
index 264ee63..29e05cd 100644
--- a/library/bignum_core.h
+++ b/library/bignum_core.h
@@ -822,4 +822,38 @@
mbedtls_mpi_uint mm,
mbedtls_mpi_uint *T);
+/** Compute GCD(A, N) and optionally the inverse of A mod N if it exists.
+ *
+ * Requires N to be odd, and 0 <= A <= N.
+ *
+ * None of the parameters may alias or overlap another.
+ *
+ * \param[out] G The GCD of \p A and \p N.
+ * Must have the same number of limbs as \p N.
+ * \param[out] I The inverse of \p A modulo \p N if it exists (that is,
+ * if \p G above is 1 on exit); indeterminate otherwise.
+ * This must either be NULL (to only compute the GCD),
+ * or have the same number of limbs as \p N.
+ * \param[in] A The 1st operand of GCD and number to invert.
+ * This value must be less than or equal to \p N.
+ * \param A_limbs The number of limbs of \p A.
+ * Must be less than or equal to \p N_limbs.
+ * \param[in] N The 2nd operand of GCD and modulus for inversion.
+ * Must be odd or the results are indeterminate.
+ * \param N_limbs The number of limbs of \p N.
+ * \param[in,out] T Temporary storage of size at least 5 * N_limbs limbs,
+ * or 4 * N_limbs if \p I is NULL (GCD only).
+ * Its initial content is unused and
+ * its final content is indeterminate.
+ * It must not alias or otherwise overlap any of the
+ * other parameters.
+ */
+void mbedtls_mpi_core_gcd_modinv_odd(mbedtls_mpi_uint *G,
+ mbedtls_mpi_uint *I,
+ const mbedtls_mpi_uint *A,
+ size_t A_limbs,
+ const mbedtls_mpi_uint *N,
+ size_t N_limbs,
+ mbedtls_mpi_uint *T);
+
#endif /* MBEDTLS_BIGNUM_CORE_H */