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.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},@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.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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel