Add several mpn_sec functions to public interface.

8 files changed, 273 insertions, 31 deletions

diff --git a/ChangeLog b/ChangeLog
index b18b3d78a..e79738731 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2013-12-28  Torbjorn Granlund  <tege@gmplib.org>
+
+	* gmp-h.in (mpn_sec_mul, mpn_sec_mul_itch): New declarations.
+	* gmp-h.in (mpn_sec_sqr, mpn_sec_sqr_itch): Likewise.
+	* mpn/generic/sec_mul.c: New file.
+	* mpn/generic/sec_sqr.c: New file.
+
+	* gmp-h.in (mpn_sec_powm, mpn_sec_powm_itch): New declarations.
+	* gmp-h.in (mpn_sec_div_qr, mpn_sec_div_qr_itch): Likewise.
+	* gmp-h.in (mpn_sec_div_r, mpn_sec_div_r_itch): Likewise.
+	* gmp-impl: Remove declarations of above functions.
+
+	* configure.ac (gmp_mpn_functions): Add sec_mul and sec_sqr.
+
 2013-12-26 Marco Bodrato <bodrato@mail.dm.unipi.it>
 
 	* Update many file's encoding to UTF-8.
@@ -4688,7 +4702,7 @@
 2011-05-03  David Harvey  <dmharvey@cims.nyu.edu>
 
 	* configure.in: make invert_limb_table work correctly with
-	--disable-assembly (from Niels Moller)
+	--disable-assembly (from Niels Möller)
 
 2011-05-02  Marc Glisse  <marc.glisse@inria.fr>
 
diff --git a/configure.ac b/configure.ac
index 552328da4..b2c872c27 100644
--- a/configure.ac
+++ b/configure.ac
@@ -2831,7 +2831,7 @@ gmp_mpn_functions="$extra_functions					   \
   mu_bdiv_q mu_bdiv_qr							   \
   bdiv_q bdiv_qr broot brootinv bsqrt bsqrtinv				   \
   divexact bdiv_dbm1c redc_1 redc_2 redc_n powm powlo sec_powm		   \
-  sec_div_qr sec_div_r sec_pi1_div_qr sec_pi1_div_r			   \
+  sec_mul sec_sqr sec_div_qr sec_div_r sec_pi1_div_qr sec_pi1_div_r	   \
   trialdiv remove							   \
   and_n andn_n nand_n ior_n iorn_n nior_n xor_n xnor_n			   \
   copyi copyd zero sec_tabselect					   \
diff --git a/doc/gmp.texi b/doc/gmp.texi
index f9e7055b3..38616df45 100644
--- a/doc/gmp.texi
+++ b/doc/gmp.texi
@@ -3412,7 +3412,7 @@ If an inverse doesn't exist then a divide by zero is raised.
 @end deftypefun
 
 @deftypefun void mpz_powm_sec (mpz_t @var{rop}, const mpz_t @var{base}, const mpz_t @var{exp}, const mpz_t @var{mod})
-Set @var{rop} to @m{base^{exp} \bmod mod, (@var{base} raised to @var{exp})
+Set @var{rop} to @m{base^{exp} \bmod @var{mod}, (@var{base} raised to @var{exp})
 modulo @var{mod}}.
 
 It is required that @math{@var{exp} > 0} and that @var{mod} is odd.
@@ -5656,19 +5656,141 @@ Copy from @{@var{s1p}, @var{n}@} to @{@var{rp}, @var{n}@}, decreasingly.
 Zero @{@var{rp}, @var{n}@}.
 @end deftypefun
 
-@deftypefun void mpn_cnd_add_n (mp_limb_t @var{cnd}, mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n})
-@deftypefunx void mpn_cnd_sub_n (mp_limb_t @var{cnd}, mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n})
-These functions do conditional addition and subtraction, and are intended for
-cryptographic applications where resilience to side-channel attacks is
-desired. If @var{cnd} is non-zero, they produce the same result as a regular
-@code{mpn_add_n} or @code{mpn_sub_n}, and if @var{cnd} is zero, they copy
-@{@var{s1p},@var{n}@} to the result area and return zero. The functions are
-designed to have timing and memory access patterns depending only on size and
-location of the data areas, but independent of the condition @var{cnd}. Like
-for @code{mpn_add_n} and @code{mpn_sub_n}, on most machines, the timing will
-also be independent of the actual limb values.
+@sp 1
+@section Low-level functions for cryptography
+@cindex Low-level functions for cryptography
+@cindex Cryptography functions, low-level
+
+The functions prefixed with @code{mpn_sec_} and @code{mpn_cnd} are designed to
+perform the exact same low-level operations 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.  These functions are intended for cryptographic purposes, where
+resilience to side-channel attacks is desired.
+
+These functions are less efficient than their ``leaky'' counterparts; their
+performance for operands of the sizes typically used for cryptographic
+applications is between 15% and 100% worse.  For larger operands, these
+functions might be inadequate, since they rely on asymptotically elementary
+algorithms.
+
+These functions do not make any explicit allocations.  Those of these functions
+that need scratch space accept a scratch space operand.  This convention allows
+callers to keep sensitive data in designated memory areas.  Note however that
+compilers may choose to spill scalar values used within these functions to
+their stack frame and that such scalars may contain sensitive data.
+
+@deftypefun mp_limb_t mpn_cnd_add_n (mp_limb_t @var{cnd}, mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n})
+@deftypefunx mp_limb_t mpn_cnd_sub_n (mp_limb_t @var{cnd}, mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n})
+These functions do conditional addition and subtraction.  If @var{cnd} is
+non-zero, they produce the same result as a regular @code{mpn_add_n} or
+@code{mpn_sub_n}, and if @var{cnd} is zero, they copy @{@var{s1p},@var{n}@} to
+the result area and return zero.  The functions are designed to have timing and
+memory access patterns depending only on size and location of the data areas,
+but independent of the condition @var{cnd}.  Like for @code{mpn_add_n} and
+@code{mpn_sub_n}, on most machines, the timing will also be independent of the
+actual limb values.
+@end deftypefun
+
+@deftypefun void mpn_sec_mul (mp_ptr @var{rp}, mp_srcptr @var{ap}, mp_size_t @var{an}, mp_srcptr @var{bp}, mp_size_t @var{bn}, mp_ptr @var{tp})
+@deftypefunx mp_size_t mpn_sec_mul_itch (mp_size_t @var{an}, mp_size_t @var{bn})
+Set @var{R} to @math{A @times B}, where @var{A} = @{@var{ap},@var{an}@},
+@var{B} = @{@var{bp},@var{bn}@}, and @var{R} =
+@{@var{rp},@math{@var{an}+@var{bn}}@}.
+
+It is required that @math{@var{an} @ge @var{bn} > 0}.
+
+No overlapping between @var{R} and the input operands is allowed.  For
+@math{@var{A} = @var{B}}, use @code{mpn_sec_sqr} for optimal performance.
+
+This function requires scratch space of @code{mpn_sec_mul_itch(@var{an},
+@var{bn})} limbs to be passed in the @var{tp} parameter.  The scratch space
+requirements are guaranteed to increase monotonously in the operand sizes.
 @end deftypefun
 
+
+@deftypefun void mpn_sec_sqr (mp_ptr @var{rp}, mp_srcptr @var{ap}, mp_size_t @var{an}, mp_ptr @var{tp})
+@deftypefunx mp_size_t mpn_sec_sqr_itch (mp_size_t @var{an})
+Set @var{R} to @math{A^2}, where @var{A} = @{@var{ap},@var{an}@}, and @var{R} =
+@{@var{rp},@math{2@var{an}}@}.
+
+It is required that @math{@var{an} > 0}.
+
+No overlapping between @var{R} and the input operands is allowed.
+
+This function requires scratch space of @code{mpn_sec_sqr_itch(@var{an})} limbs
+to be passed in the @var{tp} parameter.  The scratch space requirements are
+guaranteed to increase monotonously in the operand size.
+@end deftypefun
+
+
+@deftypefun void mpn_sec_powm (mp_ptr @var{rp}, mp_srcptr @var{bp}, mp_size_t @var{bn}, mp_srcptr @var{ep}, mp_size_t @var{en},  mp_srcptr @var{mp}, mp_size_t @var{n}, mp_ptr @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.
+@end deftypefun
+
+@deftypefun void mpn_sec_tabselect (mp_ptr @var{rp}, mp_srcptr @var{tab}, mp_size_t @var{n}, mp_size_t @var{nents}, mp_size_t @var{which})
+Select entry @var{which} from table @var{tab}, which has @var{nents} entries, each @var{n}
+limbs.  Store the selected entry at @var{rp}.
+
+This function reads the entire table to avoid side-channel information leaks.
+@end deftypefun
+
+@deftypefun void mpn_sec_div_qr (mp_ptr @var{qp}, mp_ptr @var{np}, mp_size_t @var{nn}, mp_srcptr @var{dp}, mp_size_t @var{dn}, mp_ptr @var{tp})
+@deftypefunx mp_size_t mpn_sec_div_qr_itch (mp_size_t @var{nn}, mp_size_t @var{dn})
+@strong{This function's interface is preliminary.}
+
+Set @var{Q} to @m{\lfloor @var{N} / @var{D}\rfloor, the truncated quotient
+@var{N} / @var{D}} and @var{R} to @m{@var{N} \bmod @var{D}, @var{N} modulo
+@var{D}}, where @var{N} = @{@var{np},@var{nn}@}, @var{D} =
+@{@var{dp},@var{dn}@}, @var{Q} = @{@var{qp},@var{nn-dn+1}@}, and @var{R} =
+@{@var{np},@var{dn}@}.
+
+It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that
+@m{@var{dp}[@var{dn}-1] @neq 0, @var{dp}[@var{dn}-1] != 0}.  This does not
+imply that @math{@var{N} @ge @var{D}} since @var{N} might be zero-padded.
+
+Note the overlapping between @var{N} and @var{R}.  No other operand overlapping
+is allowed.  The entire space occupied by @var{N} is overwritten.
+
+This function requires scratch space of @code{mpn_sec_div_qr_itch(@var{nn},
+@var{dn})} limbs to be passed in the @var{tp} parameter.
+@end deftypefun
+
+@deftypefun void mpn_sec_div_r (mp_ptr @var{np}, mp_size_t @var{nn}, mp_srcptr @var{dp}, mp_size_t @var{dn}, mp_ptr @var{tp})
+@deftypefunx mp_size_t mpn_sec_div_r_itch (mp_size_t @var{nn}, mp_size_t @var{dn})
+@strong{This function's interface is preliminary.}
+
+Set @var{R} to @m{@var{N} \bmod @var{D}, @var{N} modulo @var{D}}, where @var{N}
+= @{@var{np},@var{nn}@}, @var{D} = @{@var{dp},@var{dn}@}, and @var{R} =
+@{@var{np},@var{dn}@}.
+
+It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that
+@m{@var{dp}[@var{dn}-1] @neq 0, @var{dp}[@var{dn}-1] != 0}.  This does not
+imply that @math{@var{N} @ge @var{D}} since @var{N} might be zero-padded.
+
+Note the overlapping between @var{N} and @var{R}.  No other operand overlapping
+is allowed.  The entire space occupied by @var{N} is overwritten.
+
+This function requires scratch space of @code{mpn_sec_div_r_itch(@var{nn},
+@var{dn})} limbs to be passed in the @var{tp} parameter.
+@end deftypefun
+
+
+
 @sp 1
 @section Nails
 @cindex Nails
diff --git a/gmp-h.in b/gmp-h.in
index 27053995c..ee5d71d88 100644
--- a/gmp-h.in
+++ b/gmp-h.in
@@ -1626,6 +1626,34 @@ __GMP_DECLSPEC mp_limb_t mpn_cnd_add_n (mp_limb_t, mp_ptr, mp_srcptr, mp_srcptr,
 #define mpn_cnd_sub_n __MPN(cnd_sub_n)
 __GMP_DECLSPEC mp_limb_t mpn_cnd_sub_n (mp_limb_t, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
 
+#define mpn_sec_mul __MPN(sec_mul)
+__GMP_DECLSPEC void mpn_sec_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+#define mpn_sec_mul_itch __MPN(sec_mul_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_mul_itch (mp_size_t, mp_size_t);
+
+#define mpn_sec_sqr __MPN(sec_sqr)
+__GMP_DECLSPEC void mpn_sec_sqr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);
+#define mpn_sec_sqr_itch __MPN(sec_sqr_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_sqr_itch (mp_size_t);
+
+#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);
+
+#define mpn_sec_tabselect __MPN(sec_tabselect)
+__GMP_DECLSPEC void mpn_sec_tabselect (volatile mp_limb_t *, volatile mp_limb_t *, mp_size_t, mp_size_t, mp_size_t);
+
+#define mpn_sec_div_qr __MPN(sec_div_qr)
+__GMP_DECLSPEC void mpn_sec_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+#define mpn_sec_div_qr_itch __MPN(sec_div_qr_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_div_qr_itch (mp_size_t, mp_size_t);
+#define mpn_sec_div_r __MPN(sec_div_r)
+__GMP_DECLSPEC void mpn_sec_div_r (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+#define mpn_sec_div_r_itch __MPN(sec_div_r_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_div_r_itch (mp_size_t, mp_size_t);
+
+
 /**************** mpz inlines ****************/
 
 /* The following are provided as inlines where possible, but always exist as
diff --git a/gmp-impl.h b/gmp-impl.h
index 465f0acc8..b59b35514 100644
--- a/gmp-impl.h
+++ b/gmp-impl.h
@@ -1551,19 +1551,9 @@ __GMP_DECLSPEC mp_limb_t mpn_bdiv_dbm1c (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t
 __GMP_DECLSPEC void      mpn_powm (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
 #define   mpn_powlo __MPN(powlo)
 __GMP_DECLSPEC void      mpn_powlo (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
-#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);
-#define   mpn_sec_tabselect __MPN(sec_tabselect)
-__GMP_DECLSPEC void      mpn_sec_tabselect (volatile mp_limb_t *, volatile mp_limb_t *, mp_size_t, mp_size_t, mp_size_t);
-
-#define mpn_sec_div_qr __MPN(sec_div_qr)
-__GMP_DECLSPEC void mpn_sec_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+
 #define mpn_sec_pi1_div_qr __MPN(sec_pi1_div_qr)
 __GMP_DECLSPEC mp_limb_t mpn_sec_pi1_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);
-#define mpn_sec_div_r __MPN(sec_div_r)
-__GMP_DECLSPEC void mpn_sec_div_r (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
 #define mpn_sec_pi1_div_r __MPN(sec_pi1_div_r)
 __GMP_DECLSPEC void mpn_sec_pi1_div_r (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);
 
diff --git a/mpn/generic/sec_div.c b/mpn/generic/sec_div.c
index 283b873b1..753fb083d 100644
--- a/mpn/generic/sec_div.c
+++ b/mpn/generic/sec_div.c
@@ -2,7 +2,7 @@
    V.  Side-channel silent under the assumption that the used instructions are
    side-channel silent.
 
-   Contributed to the GNU project by Torbjorn Granlund.
+   Contributed to the GNU project by Torbjörn Granlund.
 
    THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES.  IT IS ONLY
    SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
@@ -30,18 +30,31 @@ with the GNU MP Library.  If not, see https://www.gnu.org/licenses/.  */
 #include "longlong.h"
 
 #if OPERATION_sec_div_qr
+#define FNAME mpn_sec_div_qr
+#define FNAME_itch mpn_sec_div_qr_itch
+#define Q(q) q,
+#endif
+#if OPERATION_sec_div_r
+#define FNAME mpn_sec_div_r
+#define FNAME_itch mpn_sec_div_r_itch
+#define Q(q)
+#endif
+
+mp_size_t
+FNAME_itch (mp_size_t nn, mp_size_t dn)
+{
+#if OPERATION_sec_div_qr
 /* Needs (nn + dn + 1) + mpn_sec_pi1_div_qr's needs of (2nn' - dn + 1) for a
    total of 3nn + 4 limbs at tp.  Note that mpn_sec_pi1_div_qr's nn is one
    greater than ours, therefore +4 and not just +2.  */
-#define FNAME mpn_sec_div_qr
-#define Q(q) q,
+  return 3 * nn + 4;
 #endif
 #if OPERATION_sec_div_r
 /* Needs (nn + dn + 1) + mpn_sec_pi1_div_r's needs of (dn + 1) for a total of
    nn + 2dn + 2 limbs at tp.  */
-#define FNAME mpn_sec_div_r
-#define Q(q)
+  return nn + 2 * dn + 2;
 #endif
+}
 
 void
 FNAME (Q(mp_ptr qp)
@@ -74,7 +87,7 @@ FNAME (Q(mp_ptr qp)
     }
   else
     {
-      /* FIXME: Consider copying np->np2 here, adding a 0-limb at the top.
+      /* FIXME: Consider copying np => np2 here, adding a 0-limb at the top.
 	 That would simplify the underlying pi1 function, since then it could
 	 assume nn > dn.  */
       dp2 = (mp_ptr) dp;
diff --git a/mpn/generic/sec_mul.c b/mpn/generic/sec_mul.c
new file mode 100644
index 000000000..6540bb0d9
--- /dev/null
+++ b/mpn/generic/sec_mul.c
@@ -0,0 +1,38 @@
+/* mpn_sec_mul.
+
+   Contributed to the GNU project by Torbjörn Granlund.
+
+Copyright 2013 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 https://www.gnu.org/licenses/.  */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+void
+mpn_sec_mul (mp_ptr rp,
+	     mp_srcptr ap, mp_size_t an,
+	     mp_srcptr bp, mp_size_t bn,
+	     mp_ptr tp)
+{
+  mpn_mul_basecase (rp, ap, an, bp, bn);
+}
+
+mp_size_t
+mpn_sec_mul_itch (mp_size_t an, mp_size_t bn)
+{
+  return 0;
+}
diff --git a/mpn/generic/sec_sqr.c b/mpn/generic/sec_sqr.c
new file mode 100644
index 000000000..b0e645a11
--- /dev/null
+++ b/mpn/generic/sec_sqr.c
@@ -0,0 +1,37 @@
+/* mpn_sec_sqr.
+
+   Contributed to the GNU project by Torbjörn Granlund.
+
+Copyright 2013 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 https://www.gnu.org/licenses/.  */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+void
+mpn_sec_sqr (mp_ptr rp,
+	     mp_srcptr ap, mp_size_t an,
+	     mp_ptr tp)
+{
+  mpn_sqr_basecase (rp, ap, an);
+}
+
+mp_size_t
+mpn_sec_sqr_itch (mp_size_t an)
+{
+  return 0;
+}