[PATCH] MPI helper of table lookup, Least Leak Intended

[NIIBE Yutaka]

Hello,

This change introduces a function _gcry_mpih_table_lookup.  The idea is
accessing the whole table entries (so that cache timing won't possible)
and select the value by ct_limb_select.

Your suggestions/comments for the implementation and/or for the suitable
name for the function are welcome.

For the use case of the function, please have a look at gniibe/t7490
branch of libgcrypt:

    https://dev.gnupg.org/source/libgcrypt/browse/gniibe%252Ft7490/

diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
index ffe8140a..decaadd8 100644
--- a/mpi/mpi-internal.h
+++ b/mpi/mpi-internal.h
@@ -272,6 +275,7 @@ mpi_limb_t _gcry_mpih_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
 
 DEFINE_CT_TYPE_GEN_MASK(limb, mpi_limb_t)
 DEFINE_CT_TYPE_GEN_INV_MASK(limb, mpi_limb_t)
+DEFINE_CT_TYPE_SELECT_FUNC(limb, mpi_limb_t)
 
 static inline int
 mpih_limb_is_zero (mpi_limb_t a)
@@ -301,6 +305,8 @@ void _gcry_mpih_swap_cond (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t usize,
                            unsigned long op_enable);
 void _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up,
                           mpi_size_t usize, unsigned long op_enable);
+void _gcry_mpih_table_lookup (mpi_ptr_t rp, const mpi_limb_t *table,
+                              mpi_size_t n, mpi_size_t nents, mpi_size_t idx);
 mpi_ptr_t _gcry_mpih_mod_lli (mpi_ptr_t vp, mpi_size_t vsize,
                               mpi_ptr_t up, mpi_size_t usize);
 int _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize, unsigned long v);
diff --git a/mpi/mpih-const-time.c b/mpi/mpih-const-time.c
index 9c2cd6a9..78c66da5 100644
--- a/mpi/mpih-const-time.c
+++ b/mpi/mpih-const-time.c
@@ -1,5 +1,5 @@
 /* mpih-const-time.c  -  Constant-time MPI helper functions
- *      Copyright (C) 2020  g10 Code GmbH
+ *      Copyright (C) 2020, 2025  g10 Code GmbH
  *
  * This file is part of Libgcrypt.
  *
@@ -183,6 +183,28 @@ _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
 }
 
 
+/*
+ *  Lookup an MPI value from TABLE at IDX, and put into RP.
+ *  The size of the MPI value is N limbs.
+ *  TABLE has NENTS entries.
+ */
+void
+_gcry_mpih_table_lookup (mpi_ptr_t rp, const mpi_limb_t *table,
+                         mpi_size_t n, mpi_size_t nents, mpi_size_t idx)
+{
+  mpi_size_t i, k;
+  const mpi_limb_t *tp = table;
+
+  for (k = 0; k < nents; k++)
+    {
+      unsigned long idx_neq_k = ct_is_not_zero (idx ^ k);
+      for (i = 0; i < n; i++)
+        rp[i] = ct_limb_select (rp[i], tp[i], idx_neq_k);
+      tp += n;
+    }
+}
+
+
 /*
  * Allocating memory for W,
  * compute W = V % U, then return W
--