commit cdfd1c9c7d35309d43b0ccc122b96ee0d861b7b4
author Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com> Fri Aug 08 09:21:23 2025 +0200
committer Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com> Mon Aug 11 09:35:28 2025 +0200
tree b743558d58c65b8e6f38e181da49d85150556047
parent 00076b4907f67c3e6eb60ab89994fa5125319296

bignum: use CT modinv when N is odd

Signed-off-by: Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com>

library/bignum.c

diff --git a/library/bignum.c b/library/bignum.c
index 4f7ca16..617a7ab 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1969,6 +1969,35 @@
 }
 
 /*
+ * Modular inverse: X = A^-1 mod N with N odd (and A any range)
+ */
+static int mbedtls_mpi_inv_mod_odd(mbedtls_mpi *X,
+                                   const mbedtls_mpi *A,
+                                   const mbedtls_mpi *N)
+{
+    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+    mbedtls_mpi T, G;
+
+    mbedtls_mpi_init(&T);
+    mbedtls_mpi_init(&G);
+
+    MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&T, A, N));
+    MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(&G, &T, &T, N));
+    if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
+        ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
+        goto cleanup;
+    }
+
+    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &T));
+
+cleanup:
+    mbedtls_mpi_free(&T);
+    mbedtls_mpi_free(&G);
+
+    return ret;
+}
+
+/*
  * Modular inverse: X = A^-1 mod N  (HAC 14.61 / 14.64)
  */
 int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
@@ -1980,6 +2009,10 @@
         return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
     }
 
+    if (mbedtls_mpi_get_bit(N, 0) == 1) {
+        return mbedtls_mpi_inv_mod_odd(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);