[Gmp-commit] /home/hgfiles/gmp: 2 new changesets

mercurial at gmplib.org mercurial at gmplib.org
Sat Dec 5 18:29:38 CET 2009


details:   /home/hgfiles/gmp/rev/58690dc0c4c4
changeset: 12982:58690dc0c4c4
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sat Dec 05 18:22:11 2009 +0100
description:
Clear some comments.

details:   /home/hgfiles/gmp/rev/7a9625bbefa6
changeset: 12983:7a9625bbefa6
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sat Dec 05 18:29:22 2009 +0100
description:
Finalise mpn_powm_sec interface.

diffstat:

 ChangeLog                |    6 ++
 mpn/generic/powm.c       |   15 ++---
 mpn/generic/powm_sec.c   |  124 ++++++++++++++++++++++++++++++++--------
 mpn/generic/redc_1_sec.c |   45 +++++++++++++++
 4 files changed, 155 insertions(+), 35 deletions(-)

diffs (293 lines):

diff -r 796d317b1c72 -r 7a9625bbefa6 ChangeLog
--- a/ChangeLog	Sat Dec 05 14:53:46 2009 +0100
+++ b/ChangeLog	Sat Dec 05 18:29:22 2009 +0100
@@ -1,5 +1,11 @@
 2009-12-05  Torbjorn Granlund  <tege at gmplib.org>
 
+	* mpn/generic/redc_1_sec.c: New file.
+	* mpn/generic/powm_sec.c: Use redc_1_sec.  Use dummy full subtract
+	instead of mpn_cmp since the latter leaks to the side channel.
+	(mpn_local_sqr_n): New function, with associated macros.
+	(mpn_powm_sec): Use mpn_local_sqr_n.
+
 	* configure.in (HAVE_NATIVE): Add missing functions, then sort.
 
 2009-12-04  Torbjorn Granlund  <tege at gmplib.org>
diff -r 796d317b1c72 -r 7a9625bbefa6 mpn/generic/powm.c
--- a/mpn/generic/powm.c	Sat Dec 05 14:53:46 2009 +0100
+++ b/mpn/generic/powm.c	Sat Dec 05 18:29:22 2009 +0100
@@ -29,14 +29,11 @@
 
   1. W <- U
 
-  2. While W^2 < M (and there are more bits in E)
-       W <- power left-to-right base-2 without reduction
+  2. T <- (B^n * U) mod M                Convert to REDC form
 
-  3. T <- (B^n * U) mod M                Convert to REDC form
+  3. Compute table U^1, U^3, U^5... of E-dependent size
 
-  4. Compute power table of E-dependent size
-
-  5. While there are more bits in E
+  4. While there are more bits in E
        W <- power left-to-right base-k
 
 
@@ -50,7 +47,7 @@
 
    * Choose window size without looping.  (Superoptimize or think(tm).)
 
-   * How do we handle small bases?
+   * Handle small bases with initial, reduction-free exponentiation.
 
    * Call new division functions, not mpn_tdiv_qr.
 
@@ -66,8 +63,8 @@
    * When U (the base) is small, we should start the exponentiation with plain
      operations, then convert that partial result to REDC form.
 
-   * But when U is just one limb, should be treated without the k-ary tricks.
-     We should keep a factor of B^n in W, but use U' = BU as base.  After
+   * When U is just one limb, should it be handled without the k-ary tricks?
+     We could keep a factor of B^n in W, but use U' = BU as base.  After
      multiplying by this (pseudo two-limb) number, we need to multiply by 1/B
      mod M.
 */
diff -r 796d317b1c72 -r 7a9625bbefa6 mpn/generic/powm_sec.c
--- a/mpn/generic/powm_sec.c	Sat Dec 05 14:53:46 2009 +0100
+++ b/mpn/generic/powm_sec.c	Sat Dec 05 18:29:22 2009 +0100
@@ -1,4 +1,5 @@
-/* mpn_powm_sec -- Compute R = U^E mod M.  Safe variant, not leaking time info.
+/* mpn_powm_sec -- Compute R = U^E mod M.  Sacure variant, side-channel silent
+   under the assupmtion that the multiply instruction is side channel silent.
 
 Copyright 2007, 2008, 2009 Free Software Foundation, Inc.
 
@@ -19,19 +20,14 @@
 
 
 /*
-  BASIC ALGORITHM, Compute b^e mod n, where n is odd.
+  BASIC ALGORITHM, Compute U^E mod M, where M < B^n is odd.
 
-  1. w <- b
+  1. T <- (B^n * U) mod M                Convert to REDC form
 
-  2. While w^2 < n (and there are more bits in e)
-       w <- power left-to-right base-2 without reduction
+  2. Compute table U^0, U^1, U^2... of E-dependent size
 
-  3. t <- (B^n * b) / n                Convert to REDC form
-
-  4. Compute power table of e-dependent size
-
-  5. While there are more bits in e
-       w <- power left-to-right base-k with reduction
+  3. While there are more bits in E
+       W <- power left-to-right base-k
 
 
   TODO:
@@ -44,15 +40,7 @@
 
    * Choose window size without looping.  (Superoptimize or think(tm).)
 
-   * Make it sub-quadratic.
-
    * Call new division functions, not mpn_tdiv_qr.
-
-   * Is redc obsolete with improved SB division?
-
-   * Consider special code for one-limb M.
-
-   * Handle even M (in mpz_powm_sec) with two modexps and CRT.
 */
 
 #include "gmp.h"
@@ -62,6 +50,89 @@
 #define WANT_CACHE_SECURITY 1
 
 
+/* Define our own mpn squaring function.  We do this since we cannot use a
+   native mpn_sqr_basecase over TUNE_SQR_TOOM2_MAX, or a non-native one over
+   SQR_TOOM2_THRESHOLD.  This is so because of fixed size stack allocations
+   made inside mpn_sqr_basecase.  */
+
+#if HAVE_NATIVE_mpn_sqr_diagonal
+#define MPN_SQR_DIAGONAL(rp, up, n)					\
+  mpn_sqr_diagonal (rp, up, n)
+#else
+#define MPN_SQR_DIAGONAL(rp, up, n)					\
+  do {									\
+    mp_size_t _i;							\
+    for (_i = 0; _i < (n); _i++)					\
+      {									\
+	mp_limb_t ul, lpl;						\
+	ul = (up)[_i];							\
+	umul_ppmm ((rp)[2 * _i + 1], lpl, ul, ul << GMP_NAIL_BITS);	\
+	(rp)[2 * _i] = lpl >> GMP_NAIL_BITS;				\
+      }									\
+  } while (0)
+#endif
+
+#if HAVE_NATIVE_mpn_sqr_basecase
+#define BASECASE_LIMIT TUNE_SQR_TOOM2_MAX
+#else
+#define BASECASE_LIMIT SQR_TOOM2_THRESHOLD
+#endif
+
+static void
+mpn_local_sqr_n (mp_ptr rp, mp_srcptr up, mp_size_t n)
+{
+  mp_size_t i;
+
+  ASSERT (n >= 1);
+  ASSERT (! MPN_OVERLAP_P (rp, 2*n, up, n));
+
+  if (n < BASECASE_LIMIT)
+    {
+      mpn_sqr_basecase (rp, up, n);
+      return;
+    }
+
+  {
+    mp_limb_t ul, lpl;
+    ul = up[0];
+    umul_ppmm (rp[1], lpl, ul, ul << GMP_NAIL_BITS);
+    rp[0] = lpl >> GMP_NAIL_BITS;
+  }
+  if (n > 1)
+    {
+      mp_ptr tp;
+      mp_limb_t cy;
+      TMP_DECL;
+      TMP_MARK;
+
+      tp = TMP_ALLOC_LIMBS (2 * n);
+
+      cy = mpn_mul_1 (tp, up + 1, n - 1, up[0]);
+      tp[n - 1] = cy;
+      for (i = 2; i < n; i++)
+	{
+	  mp_limb_t cy;
+	  cy = mpn_addmul_1 (tp + 2 * i - 2, up + i, n - i, up[i - 1]);
+	  tp[n + i - 2] = cy;
+	}
+      MPN_SQR_DIAGONAL (rp + 2, up + 1, n - 1);
+
+      {
+	mp_limb_t cy;
+#if HAVE_NATIVE_mpn_addlsh1_n
+	cy = mpn_addlsh1_n (rp + 1, rp + 1, tp, 2 * n - 2);
+#else
+	cy = mpn_lshift (tp, tp, 2 * n - 2, 1);
+	cy += mpn_add_n (rp + 1, rp + 1, tp, 2 * n - 2);
+#endif
+	rp[2 * n - 1] += cy;
+      }
+
+      TMP_FREE;
+    }
+}
+
+
 #define getbit(p,bi) \
   ((p[(bi - 1) / GMP_LIMB_BITS] >> (bi - 1) % GMP_LIMB_BITS) & 1)
 
@@ -132,6 +203,7 @@
   mp_limb_t expbits;
   mp_ptr pp, this_pp;
   long i;
+  int cnd;
   TMP_DECL;
 
   ASSERT (en > 1 || (en == 1 && ep[0] > 1));
@@ -160,7 +232,7 @@
     {
       mpn_mul_basecase (tp, this_pp, n, pp + n, n);
       this_pp += n;
-      mpn_redc_1 (this_pp, tp, mp, n, minv);
+      mpn_redc_1_sec (this_pp, tp, mp, n, minv);
     }
 
   expbits = getbits (ep, ebi, windowsize);
@@ -183,8 +255,8 @@
 
       do
 	{
-	  mpn_sqr_basecase (tp, rp, n);
-	  mpn_redc_1 (rp, tp, mp, n, minv);
+	  mpn_local_sqr_n (tp, rp, n);
+	  mpn_redc_1_sec (rp, tp, mp, n, minv);
 	  this_windowsize--;
 	}
       while (this_windowsize != 0);
@@ -195,14 +267,14 @@
 #else
       mpn_mul_basecase (tp, rp, n, pp + n * expbits, n);
 #endif
-      mpn_redc_1 (rp, tp, mp, n, minv);
+      mpn_redc_1_sec (rp, tp, mp, n, minv);
     }
 
   MPN_COPY (tp, rp, n);
   MPN_ZERO (tp + n, n);
-  mpn_redc_1 (rp, tp, mp, n, minv);
-  if (mpn_cmp (rp, mp, n) >= 0)
-    mpn_sub_n (rp, rp, mp, n);
+  mpn_redc_1_sec (rp, tp, mp, n, minv);
+  cnd = mpn_sub_n (tp, rp, mp, n);	/* we need just retval */
+  mpn_subcnd_n (rp, rp, mp, n, !cnd);
   TMP_FREE;
 }
 
diff -r 796d317b1c72 -r 7a9625bbefa6 mpn/generic/redc_1_sec.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/redc_1_sec.c	Sat Dec 05 18:29:22 2009 +0100
@@ -0,0 +1,45 @@
+/* mpn_redc_1_sec.  Set cp[] <- up[]/R^n mod mp[].  Clobber up[].
+   mp[] is n limbs; up[] is 2n limbs.
+
+   THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE.  IT IS ONLY
+   SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES.
+
+Copyright (C) 2000, 2001, 2002, 2004, 2008, 2009 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+void
+mpn_redc_1_sec (mp_ptr rp, mp_ptr up, mp_srcptr mp, mp_size_t n, mp_limb_t invm)
+{
+  mp_size_t j;
+  mp_limb_t cy;
+
+  ASSERT (n > 0);
+  ASSERT_MPN (up, 2*n);
+
+  for (j = n - 1; j >= 0; j--)
+    {
+      cy = mpn_addmul_1 (up, mp, n, (up[0] * invm) & GMP_NUMB_MASK);
+      ASSERT (up[0] == 0);
+      up[0] = cy;
+      up++;
+    }
+  cy = mpn_add_n (rp, up, up - n, n);
+  mpn_subcnd_n (rp, rp, mp, n, cy);
+}


More information about the gmp-commit mailing list