mpn_sec_powm
Niels Möller
nisse at lysator.liu.se
Mon Feb 10 21:15:24 UTC 2014
nisse at 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.texi Mon 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}, at var{n}@}, @var{M} = @{@var{mp}, at var{n}@},
! and @var{E} = @{@var{ep}, at 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}, at var{n}@}, @var{M} = @{@var{mp}, at 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.in Mon 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 ----
mp_size_t
! mpn_sec_powm_itch (mp_size_t bn, mp_bitcnt_t eb, mp_size_t n)
{
int windowsize;
***************
*** 426,430 ****
mpn_sqr_basecase. We assume 4n always for now.) */
! windowsize = win_size (en * GMP_NUMB_BITS); /* slight over-estimate of exp */
/* The 2n term is due to pp[0] and pp[1] at the time of the 2nd redcify call,
--- 423,427 ----
mpn_sqr_basecase. We assume 4n always for now.) */
! windowsize = win_size (eb);
/* The 2n term is due to pp[0] and pp[1] at the time of the 2nd redcify call,
diff -Nrc2 gmp.133eee634d4a/mpz/powm_sec.c gmp/mpz/powm_sec.c
*** gmp.133eee634d4a/mpz/powm_sec.c Mon Feb 10 22:12:32 2014
--- gmp/mpz/powm_sec.c Mon Feb 10 22:12:32 2014
***************
*** 77,81 ****
TMP_MARK;
! tp = TMP_ALLOC_LIMBS (n + mpn_sec_powm_itch (bn, en, n));
rp = tp; tp += n;
--- 77,81 ----
TMP_MARK;
! tp = TMP_ALLOC_LIMBS (n + mpn_sec_powm_itch (bn, en * GMP_NUMB_BITS, n));
rp = tp; tp += n;
***************
*** 84,88 ****
ep = PTR(e);
! mpn_sec_powm (rp, bp, bn, ep, en, mp, n, tp);
rn = n;
--- 84,88 ----
ep = PTR(e);
! mpn_sec_powm (rp, bp, bn, ep, en * GMP_NUMB_BITS, mp, n, tp);
rn = n;
diff -Nrc2 gmp.133eee634d4a/tune/tuneup.c gmp/tune/tuneup.c
*** gmp.133eee634d4a/tune/tuneup.c Mon Feb 10 22:12:32 2014
--- gmp/tune/tuneup.c Mon Feb 10 22:12:32 2014
***************
*** 1882,1886 ****
winsize = 10; /* the itch function needs this */
! itch = mpn_sec_powm_itch (n_max, n_max, n_max);
rp = TMP_ALLOC_LIMBS (n_max);
--- 1882,1886 ----
winsize = 10; /* the itch function needs this */
! itch = mpn_sec_powm_itch (n_max, n_max * GMP_NUMB_BITS, n_max);
rp = TMP_ALLOC_LIMBS (n_max);
***************
*** 1924,1937 ****
ep[i] = ~CNST_LIMB(0);
- /* Truncate E to be exactly nbits large. */
- if (nbits % GMP_NUMB_BITS != 0)
- mpn_rshift (ep, ep, n, GMP_NUMB_BITS - nbits % GMP_NUMB_BITS);
- ep[n - 1] |= CNST_LIMB(1) << (nbits - 1) % GMP_NUMB_BITS;
-
winsize = k;
for (i = 0; i < n_measurements; i++)
{
speed_starttime ();
! mpn_sec_powm (rp, bp, n, ep, n, mp, n, tp);
ttab[i] = speed_endtime ();
}
--- 1924,1932 ----
ep[i] = ~CNST_LIMB(0);
winsize = k;
for (i = 0; i < n_measurements; i++)
{
speed_starttime ();
! mpn_sec_powm (rp, bp, n, ep, nbits, mp, n, tp);
ttab[i] = speed_endtime ();
}
***************
*** 1943,1947 ****
{
speed_starttime ();
! mpn_sec_powm (rp, bp, n, ep, n, mp, n, tp);
ttab[i] = speed_endtime ();
}
--- 1938,1942 ----
{
speed_starttime ();
! mpn_sec_powm (rp, bp, n, ep, nbits, mp, n, tp);
ttab[i] = speed_endtime ();
}
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list