[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