[Gmp-commit] /home/hgfiles/gmp: 6 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Dec 23 05:39:57 CET 2009
details: /home/hgfiles/gmp/rev/930207b06f37
changeset: 13192:930207b06f37
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 23 05:10:52 2009 +0100
description:
(win_size): Start loop from 1.
details: /home/hgfiles/gmp/rev/c95177fe5a94
changeset: 13193:c95177fe5a94
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 23 05:17:39 2009 +0100
description:
Add itch interface, overhaul scratch usage.
details: /home/hgfiles/gmp/rev/445633b9cf4e
changeset: 13194:445633b9cf4e
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 23 05:27:55 2009 +0100
description:
Add some comments.
details: /home/hgfiles/gmp/rev/15b480ba0ada
changeset: 13195:15b480ba0ada
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 23 05:30:08 2009 +0100
description:
Add function mpz_powm_sec.
details: /home/hgfiles/gmp/rev/3aedbb3e1a20
changeset: 13196:3aedbb3e1a20
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 23 05:31:01 2009 +0100
description:
Test mpz_powm_sec.
details: /home/hgfiles/gmp/rev/94bcfa37e666
changeset: 13197:94bcfa37e666
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 23 05:39:48 2009 +0100
description:
Trivial merge.
diffstat:
ChangeLog | 21 +++++++++
Makefile.am | 4 +-
doc/gmp.texi | 13 ++++++
gmp-h.in | 3 +
gmp-impl.h | 2 +
mpn/generic/powm.c | 9 ++-
mpn/generic/powm_sec.c | 51 ++++++++++++++---------
mpn/generic/toom6h_mul.c | 4 +-
mpn/generic/toom_eval_pm2exp.c | 4 +-
mpz/Makefile.am | 2 +-
mpz/powm.c | 2 +
mpz/powm_sec.c | 90 ++++++++++++++++++++++++++++++++++++++++++
tests/mpz/t-powm.c | 25 ++++++++++-
13 files changed, 196 insertions(+), 34 deletions(-)
diffs (truncated from 473 to 300 lines):
diff -r 751e47e8eff1 -r 94bcfa37e666 ChangeLog
--- a/ChangeLog Tue Dec 22 23:05:31 2009 +0100
+++ b/ChangeLog Wed Dec 23 05:39:48 2009 +0100
@@ -1,3 +1,24 @@
+2009-12-23 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpn/generic/toom_eval_pm2exp.c: Assert support for degree 3.
+ * mpn/generic/toom6h_mul.c: Do not use obsolete _itch function any more.
+
+2009-12-23 Torbjorn Granlund <tege at gmplib.org>
+
+ * tests/mpz/t-powm.c: Test mpz_powm_sec.
+
+ * mpz/powm_sec.c: New file.
+ * gmp-h.in: Declare it.
+ * Makefile.am, mpz/Makefile.am: Compile it.
+ * doc/gmp.texi: Document it.
+
+ * mpn/generic/powm_sec.c (mpn_powm_sec_itch): New function.
+ (mpn_powm_sec): Use passed scratch, no local allocation.
+ Allow exp argument = 1.
+ (win_size): Start loop from 1.
+
+ * mpn/generic/powm.c (win_size): Start loop from 1.
+
2009-12-22 Torbjorn Granlund <tege at gmplib.org>
* tests/mpn/t-div.c: New file.
diff -r 751e47e8eff1 -r 94bcfa37e666 Makefile.am
--- a/Makefile.am Tue Dec 22 23:05:31 2009 +0100
+++ b/Makefile.am Wed Dec 23 05:39:48 2009 +0100
@@ -175,8 +175,8 @@
mpz/mul_si$U.lo mpz/mul_ui$U.lo \
mpz/n_pow_ui$U.lo mpz/neg$U.lo mpz/nextprime$U.lo \
mpz/out_raw$U.lo mpz/out_str$U.lo mpz/perfpow$U.lo mpz/perfsqr$U.lo \
- mpz/popcount$U.lo mpz/pow_ui$U.lo mpz/powm$U.lo mpz/powm_ui$U.lo \
- mpz/pprime_p$U.lo mpz/random$U.lo mpz/random2$U.lo \
+ mpz/popcount$U.lo mpz/pow_ui$U.lo mpz/powm$U.lo mpz/powm_sec$U.lo \
+ mpz/powm_ui$U.lo mpz/pprime_p$U.lo mpz/random$U.lo mpz/random2$U.lo \
mpz/realloc$U.lo mpz/realloc2$U.lo mpz/remove$U.lo \
mpz/root$U.lo mpz/rootrem$U.lo mpz/rrandomb$U.lo mpz/scan0$U.lo \
mpz/scan1$U.lo mpz/set$U.lo mpz/set_d$U.lo mpz/set_f$U.lo \
diff -r 751e47e8eff1 -r 94bcfa37e666 doc/gmp.texi
--- a/doc/gmp.texi Tue Dec 22 23:05:31 2009 +0100
+++ b/doc/gmp.texi Wed Dec 23 05:39:48 2009 +0100
@@ -3424,6 +3424,19 @@
If an inverse doesn't exist then a divide by zero is raised.
@end deftypefun
+ at deftypefun void mpz_powm_sec (mpz_t @var{rop}, mpz_t @var{base}, mpz_t @var{exp}, mpz_t @var{mod})
+Set @var{rop} to @m{base^{exp} \bmod mod, (@var{base} raised to @var{exp})
+modulo @var{mod}}.
+
+It is required that @math{@var{exp} > 0} and that @var{mod} is odd.
+
+This function is designed to take the same time and have the same cache access
+patterns for any two same-size arguments, assuming that function arguments are
+placed at the same position and that the machine state is identical upon
+function entry. This function is intended for cryptographic purposes, where
+resilience to side-channel attacks is desired.
+ at end deftypefun
+
@deftypefun void mpz_pow_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp})
@deftypefunx void mpz_ui_pow_ui (mpz_t @var{rop}, unsigned long int @var{base}, unsigned long int @var{exp})
Set @var{rop} to @m{base^{exp}, @var{base} raised to @var{exp}}. The case
diff -r 751e47e8eff1 -r 94bcfa37e666 gmp-h.in
--- a/gmp-h.in Tue Dec 22 23:05:31 2009 +0100
+++ b/gmp-h.in Wed Dec 23 05:39:48 2009 +0100
@@ -1034,6 +1034,9 @@
#define mpz_powm __gmpz_powm
__GMP_DECLSPEC void mpz_powm __GMP_PROTO ((mpz_ptr, mpz_srcptr, mpz_srcptr, mpz_srcptr));
+#define mpz_powm_sec __gmpz_powm_sec
+__GMP_DECLSPEC void mpz_powm_sec __GMP_PROTO ((mpz_ptr, mpz_srcptr, mpz_srcptr, mpz_srcptr));
+
#define mpz_powm_ui __gmpz_powm_ui
__GMP_DECLSPEC void mpz_powm_ui __GMP_PROTO ((mpz_ptr, mpz_srcptr, unsigned long int, mpz_srcptr));
diff -r 751e47e8eff1 -r 94bcfa37e666 gmp-impl.h
--- a/gmp-impl.h Tue Dec 22 23:05:31 2009 +0100
+++ b/gmp-impl.h Wed Dec 23 05:39:48 2009 +0100
@@ -1283,6 +1283,8 @@
__GMP_DECLSPEC void mpn_powlo __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr));
#define mpn_powm_sec __MPN(powm_sec)
__GMP_DECLSPEC void mpn_powm_sec __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
+#define mpn_powm_sec_itch __MPN(powm_sec_itch)
+__GMP_DECLSPEC mp_size_t mpn_powm_sec_itch __GMP_PROTO ((mp_size_t, mp_size_t, mp_size_t));
#define mpn_subcnd_n __MPN(subcnd_n)
__GMP_DECLSPEC mp_limb_t mpn_subcnd_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
#define mpn_tabselect __MPN(tabselect)
diff -r 751e47e8eff1 -r 94bcfa37e666 mpn/generic/powm.c
--- a/mpn/generic/powm.c Tue Dec 22 23:05:31 2009 +0100
+++ b/mpn/generic/powm.c Wed Dec 23 05:39:48 2009 +0100
@@ -43,7 +43,8 @@
That will simplify the code using getbits. (Perhaps make getbits' sibling
getbit then have similar form, for symmetry.)
- * Write an itch function.
+ * Write an itch function. Or perhaps get rid of tp parameter since the huge
+ pp area is allocated locally anyway?
* Choose window size without looping. (Superoptimize or think(tm).)
@@ -108,8 +109,8 @@
win_size (mp_bitcnt_t eb)
{
int k;
- static mp_bitcnt_t x[] = {1,7,25,81,241,673,1793,4609,11521,28161,~(mp_bitcnt_t)0};
- for (k = 0; eb > x[k]; k++)
+ static mp_bitcnt_t x[] = {0,7,25,81,241,673,1793,4609,11521,28161,~(mp_bitcnt_t)0};
+ for (k = 1; eb > x[k]; k++)
;
return k;
}
@@ -134,7 +135,7 @@
/* rp[n-1..0] = bp[bn-1..0] ^ ep[en-1..0] mod mp[n-1..0]
Requires that mp[n-1..0] is odd.
Requires that ep[en-1..0] is > 1.
- Uses scratch space tp[3n..0], i.e., 3n+1 words. */
+ Uses scratch space at tp of MAX(mpn_binvert_itch(n),3n+1) limbs. */
void
mpn_powm (mp_ptr rp, mp_srcptr bp, mp_size_t bn,
mp_srcptr ep, mp_size_t en,
diff -r 751e47e8eff1 -r 94bcfa37e666 mpn/generic/powm_sec.c
--- a/mpn/generic/powm_sec.c Tue Dec 22 23:05:31 2009 +0100
+++ b/mpn/generic/powm_sec.c Wed Dec 23 05:39:48 2009 +0100
@@ -42,7 +42,8 @@
That will simplify the code using getbits. (Perhaps make getbits' sibling
getbit then have similar form, for symmetry.)
- * Write an itch function.
+ * Write an itch function. Or perhaps get rid of tp parameter since the huge
+ pp area is allocated locally anyway?
* Choose window size without looping. (Superoptimize or think(tm).)
@@ -102,7 +103,7 @@
/* Define our own squaring function, which uses mpn_sqr_basecase for its
allowed sizes, but its own code for larger sizes. */
static void
-mpn_local_sqr_n (mp_ptr rp, mp_srcptr up, mp_size_t n)
+mpn_local_sqr_n (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_ptr tp)
{
mp_size_t i;
@@ -123,13 +124,10 @@
}
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++)
@@ -187,22 +185,21 @@
win_size (mp_bitcnt_t eb)
{
int k;
- static mp_bitcnt_t x[] = {1,4,27,100,325,1026,2905,7848,20457,51670,~(mp_bitcnt_t)0};
- for (k = 0; eb > x[k]; k++)
+ static mp_bitcnt_t x[] = {0,4,27,100,325,1026,2905,7848,20457,51670,~(mp_bitcnt_t)0};
+ for (k = 1; eb > x[k]; k++)
;
return k;
}
/* Convert U to REDC form, U_r = B^n * U mod M */
static void
-redcify (mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t n)
+redcify (mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t n, mp_ptr tp)
{
- mp_ptr tp, qp;
+ mp_ptr qp;
TMP_DECL;
TMP_MARK;
- tp = TMP_ALLOC_LIMBS (un + n);
- qp = TMP_ALLOC_LIMBS (un + 1); /* FIXME: Put at tp+? */
+ qp = tp + un + n;
MPN_ZERO (tp, n);
MPN_COPY (tp + n, up, un);
@@ -211,9 +208,9 @@
}
/* rp[n-1..0] = bp[bn-1..0] ^ ep[en-1..0] mod mp[n-1..0]
- Requires that mp[n-1..0] is odd.
+ Requires that mp[n-1..0] is odd. FIXME: is this true?
Requires that ep[en-1..0] is > 1.
- Uses scratch space tp[3n..0], i.e., 3n+1 words. */
+ Uses scratch space at tp of 3n+1 limbs. */
void
mpn_powm_sec (mp_ptr rp, mp_srcptr bp, mp_size_t bn,
mp_srcptr ep, mp_size_t en,
@@ -229,7 +226,7 @@
int cnd;
TMP_DECL;
- ASSERT (en > 1 || (en == 1 && ep[0] > 1));
+ ASSERT (en > 1 || (en == 1 && ep[0] > 0));
ASSERT (n >= 1 && ((mp[0] & 1) != 0));
TMP_MARK;
@@ -242,13 +239,13 @@
binvert_limb (minv, mp[0]);
minv = -minv;
- pp = TMP_ALLOC_LIMBS (n << windowsize);
+ pp = tp + 4 * n;
this_pp = pp;
this_pp[n] = 1;
- redcify (this_pp, this_pp + n, 1, mp, n);
+ redcify (this_pp, this_pp + n, 1, mp, n, tp + 6 * n);
this_pp += n;
- redcify (this_pp, bp, bn, mp, n);
+ redcify (this_pp, bp, bn, mp, n, tp + 6 * n);
/* Precompute powers of b and put them in the temporary area at pp. */
for (i = (1 << windowsize) - 2; i > 0; i--)
@@ -280,7 +277,7 @@
do
{
- mpn_local_sqr_n (tp, rp, n);
+ mpn_local_sqr_n (tp, rp, n, tp + 2 * n);
mpn_redc_1_sec (rp, tp, mp, n, minv);
this_windowsize--;
}
@@ -306,8 +303,8 @@
#if ! HAVE_NATIVE_mpn_tabselect
/* Select entry `which' from table `tab', which has nents entries, each `n'
limbs. Store the selected entry at rp. Reads entire table to avoid
- sideband information leaks. O(n*nents). */
-
+ side-channel information leaks. O(n*nents).
+ FIXME: Move to its own file. */
void
mpn_tabselect (volatile mp_limb_t *rp, volatile mp_limb_t *tab, mp_size_t n,
mp_size_t nents, mp_size_t which)
@@ -327,3 +324,17 @@
}
}
#endif
+
+mp_size_t
+mpn_powm_sec_itch (mp_size_t bn, mp_size_t en, mp_size_t n)
+{
+ int windowsize;
+ mp_size_t redcify_itch, itch;
+
+ windowsize = win_size (en * GMP_NUMB_BITS); /* slight over-estimate of exp */
+ itch = 4 * n + (n << windowsize);
+ redcify_itch = 2 * bn + n + 1;
+ /* The 6n is due to the placement of reduce scratch 6n into the start of the
+ scratch area. */
+ return MAX (itch, redcify_itch + 6 * n);
+}
diff -r 751e47e8eff1 -r 94bcfa37e666 mpn/generic/toom6h_mul.c
--- a/mpn/generic/toom6h_mul.c Tue Dec 22 23:05:31 2009 +0100
+++ b/mpn/generic/toom6h_mul.c Wed Dec 23 05:39:48 2009 +0100
@@ -158,9 +158,9 @@
/* Alloc also 3n+1 limbs for wsi... toom_interpolate_12pts may
need all of them */
/* if (scratch == NULL) */
-/* scratch = TMP_SALLOC_LIMBS(mpn_toom6h_mul_n_itch(n * 6)); */
+/* scratch = TMP_SALLOC_LIMBS(mpn_toom6_sqr_itch(n * 6)); */
ASSERT (12 * n + 6 <= mpn_toom6h_mul_itch(an,bn));
- ASSERT (12 * n + 6 <= mpn_toom6h_mul_n_itch(n * 6));
+ ASSERT (12 * n + 6 <= mpn_toom6_sqr_itch(n * 6));
/********************** evaluation and recursive calls *********************/
/* $\pm1/2$ */
diff -r 751e47e8eff1 -r 94bcfa37e666 mpn/generic/toom_eval_pm2exp.c
--- a/mpn/generic/toom_eval_pm2exp.c Tue Dec 22 23:05:31 2009 +0100
+++ b/mpn/generic/toom_eval_pm2exp.c Wed Dec 23 05:39:48 2009 +0100
@@ -27,7 +27,7 @@
#include "gmp.h"
#include "gmp-impl.h"
-/* Evaluates a polynomial of degree k > 3, in the points +2 and -2. */
+/* Evaluates a polynomial of degree k > 2, in the points +2^shift and -2^shift. */
int
mpn_toom_eval_pm2exp (mp_ptr xp2, mp_ptr xm2, unsigned k,
mp_srcptr xp, mp_size_t n, mp_size_t hn, unsigned shift,
@@ -39,7 +39,7 @@
mp_limb_t cy;
#endif
- ASSERT (k >= 4);
+ ASSERT (k >= 3);
ASSERT (hn > 0);
ASSERT (hn <= n);
diff -r 751e47e8eff1 -r 94bcfa37e666 mpz/Makefile.am
More information about the gmp-commit
mailing list