bignum: add mpi wrapper for gcd_modinv
Signed-off-by: Felix Conway <felix.conway@arm.com>
diff --git a/library/bignum.c b/library/bignum.c
index 4244909..a942359 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1743,6 +1743,66 @@
return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR);
}
+/* Constant-time GCD and/or modinv with odd modulus and A <= N */
+int mbedtls_mpi_gcd_modinv_odd(mbedtls_mpi *G,
+ mbedtls_mpi *I,
+ const mbedtls_mpi *A,
+ const mbedtls_mpi *N)
+{
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+ mbedtls_mpi local_g;
+ mbedtls_mpi_uint *T = NULL;
+ const size_t T_factor = I != NULL ? 5 : 4;
+
+ /* Check requirements on A and N */
+ if (mbedtls_mpi_cmp_int(A, 0) < 0 ||
+ mbedtls_mpi_cmp_mpi(A, N) > 0 ||
+ mbedtls_mpi_get_bit(N, 0) != 1 ||
+ (I != NULL && mbedtls_mpi_cmp_int(N, 1) == 0)) {
+ return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+ }
+
+ /* Check aliasing requirements */
+ if (A == N || (I != NULL && (I == N || G == N))) {
+ return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+ }
+
+ mbedtls_mpi_init(&local_g);
+
+ if (G == NULL) {
+ G = &local_g;
+ }
+
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(G, N->n));
+ G->s = 1;
+ if (I != NULL) {
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(I, N->n));
+ I->s = 1;
+ }
+
+ T = mbedtls_calloc(sizeof(mbedtls_mpi_uint) * N->n, T_factor);
+ if (T == NULL) {
+ ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
+ goto cleanup;
+ }
+
+ mbedtls_mpi_uint *Ip = I != NULL ? I->p : NULL;
+ size_t An = A->n <= N->n ? A->n : N->n;
+ mbedtls_mpi_core_gcd_modinv_odd(G->p, Ip, A->p, An, N->p, N->n, T);
+
+ if (G->n > N->n) {
+ memset(G->p + N->n, 0, ciL * (G->n - N->n));
+ }
+ if (I != NULL && I->n > N->n) {
+ memset(I->p + N->n, 0, ciL * (I->n - N->n));
+ }
+
+cleanup:
+ mbedtls_mpi_free(&local_g);
+ mbedtls_free(T);
+ return ret;
+}
+
/*
* Greatest common divisor: G = gcd(A, B) (HAC 14.54)
*/
diff --git a/library/bignum_internal.h b/library/bignum_internal.h
index aceaf55..e5657f5 100644
--- a/library/bignum_internal.h
+++ b/library/bignum_internal.h
@@ -47,4 +47,30 @@
const mbedtls_mpi *E, const mbedtls_mpi *N,
mbedtls_mpi *prec_RR);
+/**
+ * \brief Compute GCD(A, N) and/or A^-1 mod N if it exists,
+ * in constant time.
+ *
+ * \warning Requires N to be odd, and 0 <= A <= N.
+ *
+ * \note G and I must not alias each other but may alias A or N.
+ *
+ * \param[out] G The GCD of \p A and \p N.
+ * This may be NULL, to only compute I.
+ * \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 may be NULL, to only compute G.
+ * \param[in] A The 1st operand of GCD and number to invert.
+ * This value must be less than or equal to \p N.
+ * \param[in] N The 2nd operand of GCD and modulus for inversion.
+ * Must be odd or the results are indeterminate.
+ *
+ * \return \c 0 if successful.
+ * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed.
+ */
+int mbedtls_mpi_gcd_modinv_odd(mbedtls_mpi *G,
+ mbedtls_mpi *I,
+ const mbedtls_mpi *A,
+ const mbedtls_mpi *N);
+
#endif /* bignum_internal.h */