bignum: remove dead variable-time inv_mod code
Signed-off-by: Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com>
diff --git a/library/bignum.c b/library/bignum.c
index 137afb0..bd09710 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -2082,13 +2082,12 @@
}
/*
- * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
+ * Modular inverse: X = A^-1 mod N
+ *
+ * Wrapper around mbedtls_mpi_gcd_modinv_odd() that lifts its limitations.
*/
int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
{
- int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
- mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
-
if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
}
@@ -2101,80 +2100,8 @@
return mbedtls_mpi_inv_mod_even(X, A, N);
}
- mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TU); mbedtls_mpi_init(&U1); mbedtls_mpi_init(&U2);
- mbedtls_mpi_init(&G); mbedtls_mpi_init(&TB); mbedtls_mpi_init(&TV);
- mbedtls_mpi_init(&V1); mbedtls_mpi_init(&V2);
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N));
-
- if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
- ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
- goto cleanup;
- }
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N));
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA));
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N));
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N));
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0));
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0));
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1));
-
- do {
- while ((TU.p[0] & 1) == 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1));
-
- if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB));
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA));
- }
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1));
- }
-
- while ((TV.p[0] & 1) == 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1));
-
- if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB));
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA));
- }
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1));
- }
-
- if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV));
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2));
- } else {
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU));
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2));
- }
- } while (mbedtls_mpi_cmp_int(&TU, 0) != 0);
-
- while (mbedtls_mpi_cmp_int(&V1, 0) < 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N));
- }
-
- while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N));
- }
-
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1));
-
-cleanup:
-
- mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2);
- mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV);
- mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2);
-
- return ret;
+ /* If A and N are both even, 2 divides they GCD, so no inverse. */
+ return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
}
#if defined(MBEDTLS_GENPRIME)