[Gmp-commit] /var/hg/gmp: Add several mpn_sec functions to public interface.
mercurial at gmplib.org
mercurial at gmplib.org
Sat Dec 28 14:53:57 UTC 2013
details: /var/hg/gmp/rev/84112357a017
changeset: 16113:84112357a017
user: Torbjorn Granlund <tege at gmplib.org>
date: Sat Dec 28 15:53:54 2013 +0100
description:
Add several mpn_sec functions to public interface.
diffstat:
ChangeLog | 16 +++++-
configure.ac | 2 +-
doc/gmp.texi | 148 +++++++++++++++++++++++++++++++++++++++++++++----
gmp-h.in | 28 +++++++++
gmp-impl.h | 12 +---
mpn/generic/sec_div.c | 25 ++++++--
mpn/generic/sec_mul.c | 38 ++++++++++++
mpn/generic/sec_sqr.c | 37 ++++++++++++
8 files changed, 274 insertions(+), 32 deletions(-)
diffs (truncated from 409 to 300 lines):
diff -r 9cf589856aa1 -r 84112357a017 ChangeLog
--- a/ChangeLog Sat Dec 28 06:18:54 2013 +0100
+++ b/ChangeLog Sat Dec 28 15:53:54 2013 +0100
@@ -1,3 +1,17 @@
+2013-12-28 Torbjorn Granlund <tege at 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 at mail.dm.unipi.it>
* Update many file's encoding to UTF-8.
@@ -4688,7 +4702,7 @@
2011-05-03 David Harvey <dmharvey at 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 at inria.fr>
diff -r 9cf589856aa1 -r 84112357a017 configure.ac
--- a/configure.ac Sat Dec 28 06:18:54 2013 +0100
+++ b/configure.ac Sat Dec 28 15:53:54 2013 +0100
@@ -2831,7 +2831,7 @@
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 -r 9cf589856aa1 -r 84112357a017 doc/gmp.texi
--- a/doc/gmp.texi Sat Dec 28 06:18:54 2013 +0100
+++ b/doc/gmp.texi Sat Dec 28 15:53:54 2013 +0100
@@ -3412,7 +3412,7 @@
@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,18 +5656,140 @@
Zero @{@var{rp}, @var{n}@}.
@end deftypefun
- at 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})
- at 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
- at code{mpn_add_n} or @code{mpn_sub_n}, and if @var{cnd} is zero, they copy
-@{@var{s1p}, at 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.
- at end deftypefun
+ at sp 1
+ at section Low-level functions for cryptography
+ at cindex Low-level functions for cryptography
+ at 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.
+
+ at 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})
+ at 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
+ at code{mpn_sub_n}, and if @var{cnd} is zero, they copy @{@var{s1p}, at 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
+ at code{mpn_sub_n}, on most machines, the timing will also be independent of the
+actual limb values.
+ at end deftypefun
+
+ at 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})
+ at 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}, at var{an}@},
+ at var{B} = @{@var{bp}, at var{bn}@}, and @var{R} =
+@{@var{rp}, at math{@var{an}+ at 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
+ at 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},
+ at var{bn})} limbs to be passed in the @var{tp} parameter. The scratch space
+requirements are guaranteed to increase monotonously in the operand sizes.
+ at end deftypefun
+
+
+ at deftypefun void mpn_sec_sqr (mp_ptr @var{rp}, mp_srcptr @var{ap}, mp_size_t @var{an}, mp_ptr @var{tp})
+ at 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}, at var{an}@}, and @var{R} =
+@{@var{rp}, at math{2 at 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.
+ at end deftypefun
+
+
+ at 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})
+ at 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
+ at 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
+ at 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},
+ at 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.
+ at end deftypefun
+
+ at 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.
+ at end deftypefun
+
+ at 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})
+ at deftypefunx mp_size_t mpn_sec_div_qr_itch (mp_size_t @var{nn}, mp_size_t @var{dn})
+ at strong{This function's interface is preliminary.}
+
+Set @var{Q} to @m{\lfloor @var{N} / @var{D}\rfloor, the truncated quotient
+ at var{N} / @var{D}} and @var{R} to @m{@var{N} \bmod @var{D}, @var{N} modulo
+ at var{D}}, where @var{N} = @{@var{np}, at var{nn}@}, @var{D} =
+@{@var{dp}, at var{dn}@}, @var{Q} = @{@var{qp}, at var{nn-dn+1}@}, and @var{R} =
+@{@var{np}, at var{dn}@}.
+
+It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that
+ at 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},
+ at var{dn})} limbs to be passed in the @var{tp} parameter.
+ at end deftypefun
+
+ at 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})
+ at deftypefunx mp_size_t mpn_sec_div_r_itch (mp_size_t @var{nn}, mp_size_t @var{dn})
+ at 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}, at var{nn}@}, @var{D} = @{@var{dp}, at var{dn}@}, and @var{R} =
+@{@var{np}, at var{dn}@}.
+
+It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that
+ at 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},
+ at var{dn})} limbs to be passed in the @var{tp} parameter.
+ at end deftypefun
+
+
@sp 1
@section Nails
diff -r 9cf589856aa1 -r 84112357a017 gmp-h.in
--- a/gmp-h.in Sat Dec 28 06:18:54 2013 +0100
+++ b/gmp-h.in Sat Dec 28 15:53:54 2013 +0100
@@ -1626,6 +1626,34 @@
#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 -r 9cf589856aa1 -r 84112357a017 gmp-impl.h
--- a/gmp-impl.h Sat Dec 28 06:18:54 2013 +0100
+++ b/gmp-impl.h Sat Dec 28 15:53:54 2013 +0100
@@ -1551,19 +1551,9 @@
__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 -r 9cf589856aa1 -r 84112357a017 mpn/generic/sec_div.c
--- a/mpn/generic/sec_div.c Sat Dec 28 06:18:54 2013 +0100
+++ b/mpn/generic/sec_div.c Sat Dec 28 15:53:54 2013 +0100
@@ -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 @@
#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
More information about the gmp-commit
mailing list