Re: mpn_sec_powm
ni...@lysator.liu.se (Niels Möller) writes: Given the current implementation, it's natural. But we could document that it is required that any left over bits in the top limb must be zero. Would that be better? My take on this is that asking users to keep that zero isn't a requirement which is hard or unnatural to meet. On the other hand, I could envision problems with some future implementation if there are non-zero bits to ignore. I don't have a strong opinion. You're both a user and an implementator, so perhaps you have a better picture. Torbjörn ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_sec_powm
Torbjorn Granlund t...@gmplib.org writes: The exponent size argument docs implies that bits in the leading limb beyond the bit count argument are to be ignored. I am not sure that is a wise promise. Given the current implementation, it's natural. But we could document that it is required that any left over bits in the top limb must be zero. Would that be better? Please use something else than ebits, since that sounds like the arguments contains bits with individual meaning. IIRC enb would follow conventions used elsewhere in the manual. Ok, then I should switch to enb both in the docs and the code. /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_sec_powm
Torbjorn Granlund t...@gmplib.org writes: Please use something else than ebits, since that sounds like the arguments contains bits with individual meaning. IIRC enb would follow conventions used elsewhere in the manual. Naming is hard ;-) The docs for mpn_sec_invert use nbcnt (I guess that's your choice). Docs for mpf_urandomb use nbits. Other mp_bitcnt_t arguments in the manual give little guidance, names like n, op, starting_bit, bit_index, prec, bit, m2exp. So enb here is as good as any. /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_sec_powm
ni...@lysator.liu.se (Niels Möller) writes:
Maybe one problem is that to make a fair comparison between window
sizes k and k+1, the exponent bit size should be divisible by both k and
k+1.
I'm testing the below patch. Output from four consecutive runs:
#define POWM_SEC_TABLE 1,29,203,839,1409
#define POWM_SEC_TABLE 1,11,203,399,899
#define POWM_SEC_TABLE 1,5,203,579,1289
#define POWM_SEC_TABLE 1,17,203,839,1409
At least the middle value is consistent ;-) It means that we should
increase the window size from 3 to 4 bits when enb 203. I.e.,
benchmarking was done at 204 = 17*12 bits.
Increasing the window size here saves 17 modular multiplications (on
four limbs) and table lookups (out of 68), at the cost of 8 additional
multiplies in the precomputation, and each of the remaining 51 table
lookups getting twice as expensive. Which sounds more or less sane to
me.
/Niels
--- a/tune/tuneup.c Tue Feb 11 22:26:02 2014 +0100
+++ b/tune/tuneup.c Tue Feb 11 22:27:40 2014 +0100
@@ -1868,7 +1868,7 @@ tune_powm_sec (void)
mp_size_t n;
int k, i;
mp_size_t itch;
- mp_bitcnt_t nbits, nbits_next, possible_nbits_cutoff;
+ mp_bitcnt_t nbits, possible_nbits_cutoff;
const int n_max = 3000 / GMP_NUMB_BITS;
const int n_measurements = 5;
mp_ptr rp, bp, ep, mp, tp;
@@ -1914,7 +1914,10 @@ tune_powm_sec (void)
/* For nbits == 1, we should always use k == 1, so no need to tune
that. Starting with nbits == 2 also ensure that nbits always is
larger than the windowsize k+1. */
- for (nbits = 2; nbits = n_max * GMP_NUMB_BITS; )
+ for (nbits = 2;
+ nbits = n_max * GMP_NUMB_BITS k 10;
+ /* Increment, and round upwards to a multiple of k(k+1) */
+ nbits = k*(k+1)*(1+nbits/(k*(k+1
{
n = (nbits - 1) / GMP_NUMB_BITS + 1;
@@ -1972,9 +1975,6 @@ tune_powm_sec (void)
}
else
possible_nbits_cutoff = 0;
-
- nbits_next = nbits * 65 / 64;
- nbits = nbits_next + (nbits_next == nbits);
}
printf (\n);
TMP_FREE;
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_sec_powm
ni...@lysator.liu.se (Niels Möller) writes: Torbjorn Granlund t...@gmplib.org writes: Please use something else than ebits, since that sounds like the arguments contains bits with individual meaning. IIRC enb would follow conventions used elsewhere in the manual. Naming is hard ;-) The docs for mpn_sec_invert use nbcnt (I guess that's your choice). Docs for mpf_urandomb use nbits. Other mp_bitcnt_t arguments in the manual give little guidance, names like n, op, starting_bit, bit_index, prec, bit, m2exp. So enb here is as good as any. Some variance is surely motivated depending on semantics, but I'mafrad that there is a lot of variance which is not motivated. An analysis of variable names used in the manual, following by a naming cleanup, that would be good. Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_sec_powm
ni...@lysator.liu.se (Niels Möller) writes:
After some discussion with Torbjörn, I intend to change mpn_sec_powm to
take the exponent size argument in bits, rather than limbs (because the
current code may leak high bit of the exponent, which can cause serious
problems for some applications, e.g., dsa signatures).
Any comments on the below patch?
Regards,
/Niels
diff -Nrc2 gmp.133eee634d4a/doc/gmp.texi gmp/doc/gmp.texi
*** gmp.133eee634d4a/doc/gmp.texi Mon Feb 10 22:12:32 2014
--- gmp/doc/gmp.texiMon Feb 10 22:12:32 2014
***
*** 5744,5761
! @deftypefun void mpn_sec_powm (mp_limb_t *@var{rp}, const mp_limb_t
*@var{bp}, mp_size_t @var{bn}, const mp_limb_t *@var{ep}, mp_size_t @var{en},
const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_limb_t *@var{tp})
! @deftypefunx mp_size_t mpn_sec_powm_itch (mp_size_t @var{bn}, mp_size_t
@var{en}, size_t @var{n})
Set @var{R} to @m{B^E \bmod @var{M}, (@var{B} raised to @var{E}) modulo
@var{M}}, where @var{R} = @{@var{rp},@var{n}@}, @var{M} =
@{@var{mp},@var{n}@},
! and @var{E} = @{@var{ep},@var{en}@}.
! It is required that @math{@var{B} 0}, that @math{@var{E} 0} specifically
! with @m{@var{ep}[@var{en}-1] @neq 0, @var{ep}[@var{en}-1] != 0}, and that
! @math{@var{M} 0} is odd.
No overlapping between @var{R} and the input operands is allowed.
This function requires scratch space of @code{mpn_sec_powm_itch(@var{bn},
! @var{en}, @var{n})} limbs to be passed in the @var{tp} parameter. The scratch
space requirements are guaranteed to increase monotonously in the operand
sizes.
--- 5744,5759
! @deftypefun void mpn_sec_powm (mp_limb_t *@var{rp}, const mp_limb_t
*@var{bp}, mp_size_t @var{bn}, const mp_limb_t *@var{ep}, mp_bitcnt_t
@var{ebits}, const mp_limb_t *@var{mp}, mp_size_t @var{n}, mp_limb_t *@var{tp})
! @deftypefunx mp_size_t mpn_sec_powm_itch (mp_size_t @var{bn}, mp_bitcnt_t
@var{ebits}, size_t @var{n})
Set @var{R} to @m{B^E \bmod @var{M}, (@var{B} raised to @var{E}) modulo
@var{M}}, where @var{R} = @{@var{rp},@var{n}@}, @var{M} =
@{@var{mp},@var{n}@},
! and @var{E} consists of the least @var{ebits} in the area pointed to by
@var{ep}.
! It is required that @math{@var{B} 0}, and that @math{@var{M} 0} is odd.
No overlapping between @var{R} and the input operands is allowed.
This function requires scratch space of @code{mpn_sec_powm_itch(@var{bn},
! @var{ebits}, @var{n})} limbs to be passed in the @var{tp} parameter. The
scratch
space requirements are guaranteed to increase monotonously in the operand
sizes.
diff -Nrc2 gmp.133eee634d4a/gmp-h.in gmp/gmp-h.in
*** gmp.133eee634d4a/gmp-h.in Mon Feb 10 22:12:32 2014
--- gmp/gmp-h.inMon Feb 10 22:12:32 2014
***
*** 1660,1666
#define mpn_sec_powm __MPN(sec_powm)
! __GMP_DECLSPEC void mpn_sec_powm (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr,
mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sec_powm_itch __MPN(sec_powm_itch)
! __GMP_DECLSPEC mp_size_t mpn_sec_powm_itch (mp_size_t, mp_size_t, mp_size_t)
__GMP_ATTRIBUTE_PURE;
#define mpn_sec_tabselect __MPN(sec_tabselect)
--- 1660,1666
#define mpn_sec_powm __MPN(sec_powm)
! __GMP_DECLSPEC void mpn_sec_powm (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr,
mp_bitcnt_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sec_powm_itch __MPN(sec_powm_itch)
! __GMP_DECLSPEC mp_size_t mpn_sec_powm_itch (mp_size_t, mp_bitcnt_t,
mp_size_t) __GMP_ATTRIBUTE_PURE;
#define mpn_sec_tabselect __MPN(sec_tabselect)
diff -Nrc2 gmp.133eee634d4a/mpn/generic/sec_powm.c gmp/mpn/generic/sec_powm.c
*** gmp.133eee634d4a/mpn/generic/sec_powm.c Mon Feb 10 22:12:32 2014
--- gmp/mpn/generic/sec_powm.c Mon Feb 10 22:12:32 2014
***
*** 257,265
void
mpn_sec_powm (mp_ptr rp, mp_srcptr bp, mp_size_t bn,
! mp_srcptr ep, mp_size_t en,
mp_srcptr mp, mp_size_t n, mp_ptr tp)
{
mp_limb_t ip[2], *mip;
- mp_bitcnt_t ebi;
int windowsize, this_windowsize;
mp_limb_t expbits;
--- 257,264
void
mpn_sec_powm (mp_ptr rp, mp_srcptr bp, mp_size_t bn,
! mp_srcptr ep, mp_bitcnt_t ebi,
mp_srcptr mp, mp_size_t n, mp_ptr tp)
{
mp_limb_t ip[2], *mip;
int windowsize, this_windowsize;
mp_limb_t expbits;
***
*** 268,272
int cnd;
! ASSERT (en 0 ep[en - 1] != 0);
ASSERT (n = 1 ((mp[0] 1) != 0));
/* The code works for bn = 0, but the defined scratch space is 2 limbs
--- 267,271
int cnd;
! ASSERT (ebi 0);
ASSERT (n = 1 ((mp[0] 1) != 0));
/* The code works for bn = 0, but the defined scratch space is 2 limbs
***
*** 274,279
ASSERT (bn = 1);
- MPN_SIZEINBASE_2EXP(ebi, ep, en, 1);
-
windowsize = win_size (ebi);
--- 273,276
***
*** 416,420
mp_size_t
! mpn_sec_powm_itch (mp_size_t bn, mp_size_t en, mp_size_t n)
{
int windowsize;
--- 413,417
