Merge branch 'release-3.4-fixes' into master

28 files changed, 1636 insertions, 70 deletions

diff --git a/ChangeLog b/ChangeLog
index 4d14dd84..fd487df1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,140 @@
+2018-12-26  Niels Möller  <nisse@lysator.liu.se>
+
+	* tools/nettle-pbkdf2.c: Add #define _GNU_SOURCE, needed for
+	strdup with gcc -std=c89.
+	* testsuite/ed25519-test.c: Add #define _GNU_SOURCE, needed for
+	getline with gcc -std=c89.
+
+	* rsa-sign-tr.c (sec_equal): Fix accidental use of C99 for loop.
+	Reported by Andreas Gustafsson.
+	* testsuite/rsa-sec-decrypt-test.c (test_main): Likewise.
+
+2018-12-04  Niels Möller  <nisse@lysator.liu.se>
+
+	* Released nettle-3.4.1.
+
+2018-11-28  Niels Möller  <nisse@lysator.liu.se>
+
+	* configure.ac: Update GMP check. Check for the function
+	mpn_sec_div_r, available since GMP-6.0.0.
+
+	* testsuite/rsa-encrypt-test.c (test_main): Fix allocation of
+	decrypted storage. Update test of rsa_decrypt, to allow clobbering
+	of all of the passed in message area.
+
+	* pkcs1-decrypt.c (pkcs1_decrypt): Rewrite as a wrapper around
+	_pkcs1_sec_decrypt_variable. Improves side-channel silence of the
+	only caller, rsa_decrypt.
+
+	* Makefile.in (DISTFILES): Add rsa-internal.h, needed for make
+	dist. Patch from Simo Sorce.
+
+	* rsa-internal.h: Add include of rsa.h.
+
+2018-11-27  Niels Möller  <nisse@lysator.liu.se>
+
+	* rsa-sec-compute-root.c (sec_mul, sec_mod_mul, sec_powm): New
+	local helper functions, with their own itch functions.
+	(_rsa_sec_compute_root_itch, _rsa_sec_compute_root): Rewrote to
+	use helpers, for clarity.
+
+2018-11-26  Niels Möller  <nisse@lysator.liu.se>
+
+	* testsuite/rsa-compute-root-test.c (generate_keypair): Simplify
+	selection of psize and qsize, and fix so that qsize is used.
+	(test_main): Add outer loop, to test with more than one key.
+	Deallocate storage before exiting.
+
+2018-11-25  Niels Möller  <nisse@lysator.liu.se>
+
+	* testsuite/rsa-compute-root-test.c: Renamed, from ...
+	* testsuite/rsa-sec-compute-root-test.c: ... old name.
+
+	* rsa.h (rsa_sec_compute_root_tr): Deleted declaration, moved to ...
+	* rsa-internal.h (_rsa_sec_compute_root_tr): ... new location.
+	* rsa-sign-tr.c (_rsa_sec_compute_root_tr): Renamed, from...
+	(rsa_sec_compute_root_tr): ... old name. Updated callers.
+	(cnd_mpn_zero): Use a volatile-declared mask variable.
+
+	* testsuite/testutils.c (mpz_urandomb) [NETTLE_USE_MINI_GMP]: Fix
+	masking of most significant bits.
+
+	* rsa-decrypt-tr.c (rsa_decrypt_tr): Use
+	NETTLE_OCTET_SIZE_TO_LIMB_SIZE.
+
+	* testsuite/rsa-sec-decrypt-test.c (rsa_decrypt_for_test): Tweak
+	valgrind marking, and document potential leakage of lowest and
+	highest bits of p and q.
+
+	* rsa-sec-compute-root.c (_rsa_sec_compute_root): Avoid calls to
+	mpz_sizeinbase, since that potentially leaks most significant bits
+	of private key parameters a and b.
+
+	* testsuite/pkcs1-sec-decrypt-test.c (pkcs1_decrypt_for_test): Fix
+	valgrind marking of return value.
+
+	Merged below changes from Simo Sorce, to make RSA private key
+	operations side-channel silent.
+
+2018-11-08  Simo Sorce  <simo@redhat.com>
+
+	* rsa-sign.c (rsa_compute_root) [!NETTLE_USE_MINI_GMP]: Use
+	_rsa_sec_compute_root.
+
+	* testsuite/rsa-sec-compute-root-test.c: Add more tests for new
+	side-channel silent functions.
+
+	* rsa-sign.c (rsa_private_key_prepare): Check that qn + cn >= pn,
+	since that is required for one of the GMP calls in
+	_rsa_sec_compute_root.
+
+	* rsa-decrypt-tr.c: Switch to use side-channel silent functions.
+
+	* pkcs1-sec-decrypt.c (_pkcs1_sec_decrypt_variable): New private
+	function. Variable size version for backwards compatibility.
+
+	* testsuite/rsa-sec-decrypt-test.c: Adds more tests.
+
+	* rsa-sec-decrypt.c (rsa_sec_decrypt): New function.
+	Fixed length side-channel silent version of rsa-decrypt.
+	* testsuite/rsa-encrypt-test.c: add tests for the new fucntion.
+
+	* testsuite/pkcs1-sec-decrypt-test.c: Adds tests for
+	_pkcs1_sec_decrypt.
+
+	* gmp-glue.c (mpn_get_base256): New function.
+
+	* pkcs1-sec-decrypt.c (_pkcs1_sec_decrypt): New private function.
+	Fixed length side-channel silent version of pkcs1-decrypt.
+
+	* cnd-memcpy.c (cnd_memcpy): New function.
+	* memops.h: Declare it.
+	* testsuite/cnd-memcpy-test.c: New test case.
+
+	* rsa-sign-tr.c (rsa_sec_compute_root_tr): New function that uses
+	_rsa_sec_compute_root, as well as side-channel silent RSA
+	blinding.
+	(rsa_compute_root_tr) Rewritten as a wrapper around
+	rsa_sec_compute_root_tr.
+	(rsa_sec_blind, rsa_sec_unblind, sec_equal, rsa_sec_check_root)
+	(cnd_mpn_zero): New helper functions.
+	(rsa_sec_compute_root_tr) [NETTLE_USE_MINI_GMP]: Defined as a not
+	side-channel silent wrapper around rsa_compute_root_tr, and the
+	latter function left unchanged.
+
+	* rsa-sec-compute-root.c (_rsa_sec_compute_root_itch)
+	(_rsa_sec_compute_root): New file, new private functions.
+	Side-channel silent version of rsa_compute_root.
+	* rsa-internal.h: New header file with declarations.
+
+	* gmp-glue.h (NETTLE_OCTET_SIZE_TO_LIMB_SIZE): New macro.
+
+2018-11-24  Niels Möller  <nisse@lysator.liu.se>
+
+	* configure.ac: Bump package version to 3.4.1.
+	(LIBNETTLE_MINOR): Bump library version to 6.5.
+	(LIBHOGWEED_MINOR): Bump library version to 4.5.
+
 2018-11-17  Niels Möller  <nisse@lysator.liu.se>
 
 	* examples/hogweed-benchmark.c (bench_rsa_verify)
diff --git a/Makefile.in b/Makefile.in
index d4fa628a..c7db0aed 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -89,6 +89,7 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c \
 		 camellia256-meta.c \
 		 cast128.c cast128-meta.c cbc.c \
 		 ccm.c ccm-aes128.c ccm-aes192.c ccm-aes256.c cfb.c \
+		 cnd-memcpy.c \
 		 chacha-crypt.c chacha-core-internal.c \
 		 chacha-poly1305.c chacha-poly1305-meta.c \
 		 chacha-set-key.c chacha-set-nonce.c \
@@ -141,10 +142,12 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  bignum.c bignum-random.c bignum-random-prime.c \
 		  sexp2bignum.c \
 		  pkcs1.c pkcs1-encrypt.c pkcs1-decrypt.c \
+		  pkcs1-sec-decrypt.c \
 		  pkcs1-rsa-digest.c pkcs1-rsa-md5.c pkcs1-rsa-sha1.c \
 		  pkcs1-rsa-sha256.c pkcs1-rsa-sha512.c \
 		  pss.c pss-mgf1.c \
 		  rsa.c rsa-sign.c rsa-sign-tr.c rsa-verify.c \
+		  rsa-sec-compute-root.c \
 		  rsa-pkcs1-sign.c rsa-pkcs1-sign-tr.c rsa-pkcs1-verify.c \
 		  rsa-md5-sign.c rsa-md5-sign-tr.c rsa-md5-verify.c \
 		  rsa-sha1-sign.c rsa-sha1-sign-tr.c rsa-sha1-verify.c \
@@ -152,7 +155,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  rsa-sha512-sign.c rsa-sha512-sign-tr.c rsa-sha512-verify.c \
 		  rsa-pss-sha256-sign-tr.c rsa-pss-sha256-verify.c \
 		  rsa-pss-sha512-sign-tr.c rsa-pss-sha512-verify.c \
-		  rsa-encrypt.c rsa-decrypt.c rsa-decrypt-tr.c \
+		  rsa-encrypt.c rsa-decrypt.c \
+		  rsa-sec-decrypt.c rsa-decrypt-tr.c \
 		  rsa-keygen.c rsa-blind.c \
 		  rsa2sexp.c sexp2rsa.c \
 		  dsa.c dsa-compat.c dsa-compat-keygen.c dsa-gen-params.c \
diff --git a/NEWS b/NEWS
index e1091920..b0a0dda4 100644
--- a/NEWS
+++ b/NEWS
@@ -8,11 +8,6 @@ NEWS for the Nettle 3.5 release
 	  assumptions accidentally made in GnuTLS, up to and including
 	  version 3.6.1.
 
-	Bug fixes:
-
-	* Fix bug in pkcs1-conv, missing break statements in the
-	  parsing of PEM input files.
-
 	New features:
 
 	* Support for CFB8 (Cipher Feedback Mode, processing a single
@@ -55,6 +50,81 @@ NEWS for the Nettle 3.5 release
 	  gcmdata are no longer built by default. Makefile
 	  improvements contributed by Jay Foad.
 
+NEWS for the Nettle 3.4.1 release
+
+	This release fixes a few bugs, and makes the RSA private key
+	operations side channel silent. The RSA improvements are
+	contributed by Simo Sorce and Red Hat, and include one new
+	public function, rsa_sec_decrypt, see below.
+
+	All functions using RSA private keys are now side-channel
+	silent, meaning that they try hard to avoid any branches or
+	memory accesses depending on secret data. This applies both to
+	the bignum calculations, which now use GMP's mpn_sec_* family
+	of functions, and the processing of PKCS#1 padding needed for
+	RSA decryption.
+
+	Nettle's ECC functions were already side-channel silent, while
+	the DSA functions still aren't. There's also one caveat
+	regarding the improved RSA functions: due to small table
+	lookups in relevant mpn_sec_* functions in GMP-6.1.2, the
+	lowest and highest few bits of the secret factors p and q may
+	still leak. I'm not aware of any attacks on RSA where knowing
+	a few bits of the factors makes a significant difference. This
+	leak will likely be plugged in later GMP versions.
+
+	Changes in behavior:
+
+	* The functions rsa_decrypt and rsa_decrypt_tr may now clobber
+	  all of the provided message buffer, independent of the
+	  actual message length. They are side-channel silent, in that
+	  branches and memory accesses don't depend on the validity or
+	  length of the message. Side-channel leakage from the
+	  caller's use of length and return value may still provide an
+	  oracle useable for a Bleichenbacher-style chosen ciphertext
+	  attack. Which is why the new function rsa_sec_decrypt is
+	  recommended.
+
+	New features:
+
+	* A new function rsa_sec_decrypt. It differs from
+	  rsa_decrypt_tr in that the length of the decrypted message
+	  is given a priori, and PKCS#1 padding indicating a different
+	  length is treated as an error. For applications that may be
+	  subject to chosen ciphertext attacks, it is recommended to
+	  initialize the message area with random data, call this
+	  function, and ignore the return value. This applies in
+	  particular to RSA-based key exchange in the TLS protocol.
+
+	Bug fixes:
+
+	* Fix bug in pkcs1-conv, missing break statements in the
+	  parsing of PEM input files.
+
+	* Fix link error on the pss-mgf1-test test, affecting builds
+	  without public key support.
+
+	Performance regression:
+
+	* All RSA private key operations employing RSA blinding, i.e.,
+	  rsa_decrypt_tr, rsa_*_sign_tr, the new rsa_sec_decrypt, and
+	  rsa_compute_root_tr, are significantly slower. This is
+	  because (i) RSA blinding now use side-channel silent
+	  operations, (ii) blinding includes a modular inversion, and
+	  (iii) side-channel silent modular inversion, implemented as
+	  mpn_sec_invert, is very expensive. A 60% slowdown for
+	  2048-bit RSA keys have been measured.
+
+	Miscellaneous:
+
+	* Building the public key support of nettle now requires GMP
+	  version 6.0 or later (unless --enable-mini-gmp is used).
+
+	The shared library names are libnettle.so.6.5 and
+	libhogweed.so.4.5, with sonames still libnettle.so.6 and
+	libhogweed.so.4. It is intended to be fully binary compatible
+	with nettle-3.1.
+
 NEWS for the Nettle 3.4 release
 
 	This release fixes bugs and adds a few new features. It also
@@ -178,7 +248,7 @@ NEWS for the Nettle 3.3 release
 	This release fixes a couple of bugs, and improves resistance
 	to side-channel attacks on RSA and DSA private key operations.
 
-	Changes in behavoir:
+	Changes in behavior:
 
 	* Invalid private RSA keys, with an even modulo, are now
 	  rejected by rsa_private_key_prepare. (Earlier versions
diff --git a/cnd-memcpy.c b/cnd-memcpy.c
new file mode 100644
index 00000000..4aaee78b
--- /dev/null
+++ b/cnd-memcpy.c
@@ -0,0 +1,55 @@
+/* cnd-memcpy.c
+
+   Copyright (C) 2018 Niels Möller
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * 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.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle 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
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "memops.h"
+
+void
+cnd_memcpy(int cnd, volatile void *dst, const volatile void *src, size_t n)
+{
+  const volatile unsigned char *sp = src;
+  volatile unsigned char *dp = dst;
+  volatile unsigned char c;
+  volatile unsigned char m;
+  size_t i;
+
+  m = -(unsigned char) cnd;
+
+  for (i = 0; i < n; i++)
+    {
+      c = (sp[i] & m);
+      c |= (dp[i] & ~m);
+      dp[i] = c;
+    }
+}
diff --git a/configure.ac b/configure.ac
index a3460853..455463d7 100644
--- a/configure.ac
+++ b/configure.ac
@@ -2,7 +2,7 @@ dnl -*- mode: shell-script; sh-indentation: 2; -*-
 
 dnl Process this file with autoconf to produce a configure script.
 
-AC_INIT([nettle], [3.4], [nettle-bugs@lists.lysator.liu.se])
+AC_INIT([nettle], [3.4.1], [nettle-bugs@lists.lysator.liu.se])
 AC_PREREQ(2.61)
 AC_CONFIG_SRCDIR([arcfour.c])
 # Needed to stop autoconf from looking for files in parent directories.
@@ -11,10 +11,10 @@ AC_CONFIG_AUX_DIR([.])
 AC_CONFIG_HEADER([config.h])
 
 LIBNETTLE_MAJOR=6
-LIBNETTLE_MINOR=4
+LIBNETTLE_MINOR=5
 
 LIBHOGWEED_MAJOR=4
-LIBHOGWEED_MINOR=4
+LIBHOGWEED_MINOR=5
 
 dnl Note double square brackets, for extra m4 quoting.
 MAJOR_VERSION=`echo $PACKAGE_VERSION | sed 's/^\([[^.]]*\)\..*/\1/'`
@@ -260,9 +260,9 @@ fi
 # Checks for libraries
 if test "x$enable_public_key" = "xyes" ; then
   if test "x$enable_mini_gmp" = "xno" ; then
-    AC_CHECK_LIB(gmp, __gmpz_powm_sec,,
+    AC_CHECK_LIB(gmp, __gmpn_sec_div_r,,
         [AC_MSG_WARN(
-    [GNU MP not found, or too old. GMP-5.0 or later is needed, see http://gmplib.org/.
+    [GNU MP not found, or too old. GMP-6.0 or later is needed, see https://gmplib.org/.
     Support for public key algorithms will be unavailable.])]
         enable_public_key=no)
 
diff --git a/gmp-glue.c b/gmp-glue.c
index c44332df..805b50c4 100644
--- a/gmp-glue.c
+++ b/gmp-glue.c
@@ -247,6 +247,37 @@ mpn_set_base256_le (mp_limb_t *rp, mp_size_t rn,
 }
 
 void
+mpn_get_base256 (uint8_t *rp, size_t rn,
+		 const mp_limb_t *xp, mp_size_t xn)
+{
+  unsigned bits;
+  mp_limb_t in;
+  for (bits = in = 0; xn > 0 && rn > 0; )
+    {
+      if (bits >= 8)
+	{
+	  rp[--rn] = in;
+	  in >>= 8;
+	  bits -= 8;
+	}
+      else
+	{
+	  uint8_t old = in;
+	  in = *xp++;
+	  xn--;
+	  rp[--rn] = old | (in << bits);
+	  in >>= (8 - bits);
+	  bits += GMP_NUMB_BITS - 8;
+	}
+    }
+  while (rn > 0)
+    {
+      rp[--rn] = in;
+      in >>= 8;
+    }
+}
+
+void
 mpn_get_base256_le (uint8_t *rp, size_t rn,
 		    const mp_limb_t *xp, mp_size_t xn)
 {
diff --git a/gmp-glue.h b/gmp-glue.h
index 648724bc..7f42cc2b 100644
--- a/gmp-glue.h
+++ b/gmp-glue.h
@@ -57,6 +57,7 @@
 #define mpz_set_n _nettle_mpz_set_n
 #define mpn_set_base256 _nettle_mpn_set_base256
 #define mpn_set_base256_le _nettle_mpn_set_base256_le
+#define mpn_get_base256 _nettle_mpn_get_base256
 #define mpn_get_base256_le _nettle_mpn_get_base256_le
 #define gmp_alloc_limbs _nettle_gmp_alloc_limbs
 #define gmp_free_limbs _nettle_gmp_free_limbs
@@ -81,6 +82,9 @@
 # define cnd_sub_n(cnd, rp, ap, n) mpn_submul_1 ((rp), (ap), (n), (cnd) != 0)
 #endif
 
+#define NETTLE_OCTET_SIZE_TO_LIMB_SIZE(n) \
+  (((n) * 8 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
+
 /* Some functions for interfacing between mpz and mpn code. Signs of
    the mpz numbers are generally ignored. */
 
@@ -148,6 +152,10 @@ mpn_set_base256_le (mp_limb_t *rp, mp_size_t rn,
 		    const uint8_t *xp, size_t xn);
 
 void
+mpn_get_base256 (uint8_t *rp, size_t rn,
+	         const mp_limb_t *xp, mp_size_t xn);
+
+void
 mpn_get_base256_le (uint8_t *rp, size_t rn,
 		    const mp_limb_t *xp, mp_size_t xn);
 
diff --git a/memops.h b/memops.h
index 8e40594d..815d5472 100644
--- a/memops.h
+++ b/memops.h
@@ -39,11 +39,17 @@ extern "C" {
 #endif
 
 /* Name mangling */
+#define cnd_memcpy nettle_cnd_memcpy
 #define memeql_sec nettle_memeql_sec
 
 int
 memeql_sec (const void *a, const void *b, size_t n);
 
+/* Side-channel silent conditional memcpy. cnd must be 0 (nop) or 1
+   (copy). */
+void
+cnd_memcpy(int cnd, volatile void *dst, const volatile void *src, size_t n);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/pkcs1-decrypt.c b/pkcs1-decrypt.c
index 7acd2d57..1a02c706 100644
--- a/pkcs1-decrypt.c
+++ b/pkcs1-decrypt.c
@@ -41,6 +41,7 @@
 
 #include "bignum.h"
 #include "gmp-glue.h"
+#include "rsa-internal.h"
 
 int
 pkcs1_decrypt (size_t key_size,
@@ -48,49 +49,13 @@ pkcs1_decrypt (size_t key_size,
 	       size_t *length, uint8_t *message)
 {
   TMP_GMP_DECL(em, uint8_t);
-  uint8_t *terminator;
-  size_t padding;
-  size_t message_length;
   int ret;
 
   TMP_GMP_ALLOC(em, key_size);
   nettle_mpz_get_str_256(key_size, em, m);
 
-  /* Check format */
-  if (em[0] || em[1] != 2)
-    {
-      ret = 0;
-      goto cleanup;
-    }
-
-  terminator = memchr(em + 2, 0, key_size - 2);
-
-  if (!terminator)
-    {
-      ret = 0;
-      goto cleanup;
-    }
-  
-  padding = terminator - (em + 2);
-  if (padding < 8)
-    {
-      ret = 0;
-      goto cleanup;
-    }
-
-  message_length = key_size - 3 - padding;
-
-  if (*length < message_length)
-    {
-      ret = 0;
-      goto cleanup;
-    }
-  
-  memcpy(message, terminator + 1, message_length);
-  *length = message_length;
-
-  ret = 1;
-cleanup:
+  ret = _pkcs1_sec_decrypt_variable (length, message, key_size, em);
+
   TMP_GMP_FREE(em);
   return ret;
 }
diff --git a/pkcs1-sec-decrypt.c b/pkcs1-sec-decrypt.c
new file mode 100644
index 00000000..722044b0
--- /dev/null
+++ b/pkcs1-sec-decrypt.c
@@ -0,0 +1,149 @@
+/* pkcs1-sec-decrypt.c
+
+   The RSA publickey algorithm. Side channel resistant PKCS#1 decryption.
+
+   Copyright (C) 2001, 2012 Niels Möller
+   Copyright (C) 2018 Red Hat, Inc.
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * 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.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle 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
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include <string.h>
+
+#include "memops.h"
+
+#include "gmp-glue.h"
+#include "rsa.h"
+#include "rsa-internal.h"
+
+/* Inputs are always cast to uint32_t values. But all values used in this
+ * function should never exceed the maximum value of a uint32_t anyway.
+ * these macros returns 1 on success, 0 on failure */
+#define NOT_EQUAL(a, b) \
+    ((0U - ((uint32_t)(a) ^ (uint32_t)(b))) >> 31)
+#define EQUAL(a, b) \
+    ((((uint32_t)(a) ^ (uint32_t)(b)) - 1U) >> 31)
+#define GREATER_OR_EQUAL(a, b) \
+    (1U - (((uint32_t)(a) - (uint32_t)(b)) >> 31))
+
+int
+_pkcs1_sec_decrypt (size_t length, uint8_t *message,
+                    size_t padded_message_length,
+                    const volatile uint8_t *padded_message)
+{
+  volatile int ok;
+  size_t i, t;
+
+  assert (padded_message_length >= length);
+
+  t = padded_message_length - length - 1;
+
+  /* Check format, padding, message_size */
+  ok = EQUAL(padded_message[0], 0);       /* ok if padded_message[0] == 0 */
+  ok &= EQUAL(padded_message[1], 2);      /* ok if padded_message[1] == 2 */
+  for (i = 2; i < t; i++)      /* check padding has no zeros */
+    {
+      ok &= NOT_EQUAL(padded_message[i], 0);
+    }
+  ok &= EQUAL(padded_message[t], 0);      /* ok if terminator == 0 */
+
+  /* fill destination buffer regardless of outcome */
+  cnd_memcpy(ok, message, padded_message + t + 1, length);
+
+  return ok;
+}
+
+int
+_pkcs1_sec_decrypt_variable(size_t *length, uint8_t *message,
+                            size_t padded_message_length,
+                            const volatile uint8_t *padded_message)
+{
+  volatile int not_found = 1;
+  volatile int ok;
+  volatile size_t offset;
+  size_t buflen, msglen;
+  size_t shift, i;
+
+  /* Check format, padding, message_size */
+  ok = EQUAL(padded_message[0], 0);
+  ok &= EQUAL(padded_message[1], 2);
+
+  /* length is discovered in a side-channel silent way.
+   * not_found goes to 0 when the terminator is found.
+   * offset strts at 3 as it includes the terminator and
+   * the fomat bytes already */
+  offset = 3;
+  for (i = 2; i < padded_message_length; i++)
+    {
+      not_found &= NOT_EQUAL(padded_message[i], 0);
+      offset += not_found;
+    }
+  /* check if we ran out of buffer */
+  ok &= NOT_EQUAL(not_found, 1);
+  /* padding must be >= 11 (2 format bytes + 8 pad bytes min. + terminator) */
+  ok &= GREATER_OR_EQUAL(offset, 11);
+
+  /* offset can vary between 3 and padded_message_length, due to the loop
+   * above, therefore msglen can't underflow */
+  msglen = padded_message_length - offset;
+
+  /* we always fill the whole buffer but only up to
+   * padded_message_length length */
+  buflen = *length;
+  if (buflen > padded_message_length) { /* input independent branch */
+    buflen = padded_message_length;
+  }
+
+  /* if the message length is larger than the buffer we must fail */
+  ok &= GREATER_OR_EQUAL(buflen, msglen);
+
+  /* fill destination buffer fully regardless of outcome. Copies the message
+   * in a memory access independent way. The destination message buffer will
+   * be clobbered past the message length. */
+  shift = padded_message_length - buflen;
+  cnd_memcpy(ok, message, padded_message + shift, buflen);
+  offset -= shift;
+  /* In this loop, the bits of the 'offset' variable are used as shifting
+   * conditions, starting from the least significant bit. The end result is
+   * that the buffer is shifted left exactly 'offset' bytes. */
+  for (shift = 1; shift < buflen; shift <<= 1, offset >>= 1)
+    {
+      /* 'ok' is both a least significant bit mask and a condition */
+      cnd_memcpy(offset & ok, message, message + shift, buflen - shift);
+    }
+
+  /* update length only if we succeeded, otherwise leave unchanged */
+  *length = (msglen & (-(size_t) ok)) + (*length & ((size_t) ok - 1));
+
+  return ok;
+}
diff --git a/rsa-decrypt-tr.c b/rsa-decrypt-tr.c
index e800b71e..1e6ad934 100644
--- a/rsa-decrypt-tr.c
+++ b/rsa-decrypt-tr.c
@@ -36,11 +36,8 @@
 # include "config.h"
 #endif
 
-#include "rsa.h"
 #include "rsa-internal.h"
-
-#include "bignum.h"
-#include "pkcs1.h"
+#include "gmp-glue.h"
 
 int
 rsa_decrypt_tr(const struct rsa_public_key *pub,
@@ -49,14 +46,25 @@ rsa_decrypt_tr(const struct rsa_public_key *pub,
 	       size_t *length, uint8_t *message,
 	       const mpz_t gibberish)
 {
-  mpz_t m;
+  TMP_GMP_DECL (m, mp_limb_t);
+  TMP_GMP_DECL (em, uint8_t);
+  mp_size_t key_limb_size;
   int res;
 
-  mpz_init_set(m, gibberish);
+  key_limb_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);
+
+  TMP_GMP_ALLOC (m, key_limb_size);
+  TMP_GMP_ALLOC (em, key->size);
+
+  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, m,
+				  mpz_limbs_read(gibberish),
+				  mpz_size(gibberish));
+
+  mpn_get_base256 (em, key->size, m, key_limb_size);
 
-  res = (rsa_compute_root_tr (pub, key, random_ctx, random, m, gibberish)
-	 && pkcs1_decrypt (key->size, m, length, message));
+  res &= _pkcs1_sec_decrypt_variable (length, message, key->size, em);
 
-  mpz_clear(m);
+  TMP_GMP_FREE (em);
+  TMP_GMP_FREE (m);
   return res;
 }
diff --git a/rsa-internal.h b/rsa-internal.h
index 5c97eaa1..264c0a6a 100644
--- a/rsa-internal.h
+++ b/rsa-internal.h
@@ -34,13 +34,18 @@
 #ifndef NETTLE_RSA_INTERNAL_H_INCLUDED
 #define NETTLE_RSA_INTERNAL_H_INCLUDED
 
-#include "nettle-types.h"
+#include "rsa.h"
 
 #define _rsa_verify _nettle_rsa_verify
 #define _rsa_verify_recover _nettle_rsa_verify_recover
 #define _rsa_check_size _nettle_rsa_check_size
 #define _rsa_blind _nettle_rsa_blind
 #define _rsa_unblind _nettle_rsa_unblind
+#define _rsa_sec_compute_root_itch _nettle_rsa_sec_compute_root_itch
+#define _rsa_sec_compute_root _nettle_rsa_sec_compute_root
+#define _rsa_sec_compute_root_tr _nettle_rsa_sec_compute_root_tr
+#define _pkcs1_sec_decrypt _nettle_pkcs1_sec_decrypt
+#define _pkcs1_sec_decrypt_variable _nettle_pkcs1_sec_decrypt_variable
 
 /* Internal functions. */
 int
@@ -66,4 +71,32 @@ void
 _rsa_unblind (const struct rsa_public_key *pub, mpz_t c, const mpz_t ri)
   _NETTLE_ATTRIBUTE_DEPRECATED;
 
+/* side-channel silent root computation */
+mp_size_t
+_rsa_sec_compute_root_itch(const struct rsa_private_key *key);
+void
+_rsa_sec_compute_root(const struct rsa_private_key *key,
+                      mp_limb_t *rp, const mp_limb_t *mp,
+                      mp_limb_t *scratch);
+
+/* Safe side-channel silent variant, using RSA blinding, and checking the
+ * result after CRT. */
+int
+_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,
+			 const struct rsa_private_key *key,
+			 void *random_ctx, nettle_random_func *random,
+			 mp_limb_t *x, const mp_limb_t *m, size_t mn);
+
+/* additional resistance to memory access side-channel attacks.
+ * Note: message buffer is returned unchanged on error */
+int
+_pkcs1_sec_decrypt (size_t length, uint8_t *message,
+                    size_t padded_message_length,
+                    const volatile uint8_t *padded_message);
+
+int
+_pkcs1_sec_decrypt_variable(size_t *length, uint8_t *message,
+                            size_t padded_message_length,
+                            const volatile uint8_t *padded_message);
+
 #endif /* NETTLE_RSA_INTERNAL_H_INCLUDED */
diff --git a/rsa-sec-compute-root.c b/rsa-sec-compute-root.c
new file mode 100644
index 00000000..98b6c2a5
--- /dev/null
+++ b/rsa-sec-compute-root.c
@@ -0,0 +1,195 @@
+/* rsa-sec-compute-root.c
+
+   Side-channel silent RSA root computation.
+
+   Copyright (C) 2018 Niels Möller
+   Copyright (C) 2018 Red Hat, Inc
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * 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.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle 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
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "rsa.h"
+#include "rsa-internal.h"
+#include "gmp-glue.h"
+
+#if !NETTLE_USE_MINI_GMP
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+/* Like mpn_sec_mul_itch, monotonously increasing in operand sizes. */
+static mp_size_t
+sec_mul_itch (mp_size_t an, mp_size_t bn)
+{
+  if (an >= bn)
+    return mpn_sec_mul_itch (an, bn);
+  else
+    return mpn_sec_mul_itch (bn, an);
+}
+
+/* Writes an + bn limbs to the rp area */
+static void
+sec_mul (mp_limb_t *rp,
+	 const mp_limb_t *ap, mp_size_t an,
+	 const mp_limb_t *bp, mp_size_t bn, mp_limb_t *scratch)
+{
+  if (an >= bn)
+    mpn_sec_mul (rp, ap, an, bp, bn, scratch);
+  else
+    mpn_sec_mul (rp, bp, bn, ap, an, scratch);
+}
+
+static mp_size_t
+sec_mod_mul_itch (mp_size_t an, mp_size_t bn, mp_size_t mn)
+{
+  mp_size_t mul_itch = sec_mul_itch (an, bn);
+  mp_size_t mod_itch = mpn_sec_div_r_itch (an + bn, mn);
+  return MAX(mul_itch, mod_itch);
+}
+
+/* Sets r <-- a b % m. Needs space for an + bn limbs at rp. It is
+   required than an + bn >= mn. */
+static void
+sec_mod_mul (mp_limb_t *rp,
+	     const mp_limb_t *ap, mp_size_t an,
+	     const mp_limb_t *bp, mp_size_t bn,
+	     const mp_limb_t *mp, mp_size_t mn,
+	     mp_limb_t *scratch)
+{
+  assert (an + bn >= mn);
+  sec_mul (rp, ap, an, bp, bn, scratch);
+  mpn_sec_div_r (rp, an + bn, mp, mn, scratch);
+}
+
+static mp_size_t
+sec_powm_itch (mp_size_t bn, mp_size_t en, mp_size_t mn)
+{
+  mp_size_t mod_itch = bn + mpn_sec_div_r_itch (bn, mn);
+  mp_size_t pow_itch = mn + mpn_sec_powm_itch (mn, en * GMP_NUMB_BITS, mn);
+  return MAX (mod_itch, pow_itch);
+}
+
+/* Sets r <-- b ^ e % m. Performs an initial reduction b mod m, and
+   requires bn >= mn. */
+static void
+sec_powm (mp_limb_t *rp,
+	  const mp_limb_t *bp, mp_size_t bn,
+	  const mp_limb_t *ep, mp_size_t en,
+	  const mp_limb_t *mp, mp_size_t mn, mp_limb_t *scratch)
+{
+  assert (bn >= mn);
+  assert (en <= mn);
+  mpn_copyi (scratch, bp, bn);
+  mpn_sec_div_r (scratch, bn, mp, mn, scratch + bn);
+  mpn_sec_powm (rp, scratch, mn, ep, en * GMP_NUMB_BITS, mp, mn,
+		scratch + mn);
+}
+
+mp_size_t
+_rsa_sec_compute_root_itch (const struct rsa_private_key *key)
+{
+  mp_size_t nn = NETTLE_OCTET_SIZE_TO_LIMB_SIZE (key->size);
+  mp_size_t pn = mpz_size (key->p);
+  mp_size_t qn = mpz_size (key->q);
+  mp_size_t an = mpz_size (key->a);
+  mp_size_t bn = mpz_size (key->b);
+  mp_size_t cn = mpz_size (key->c);
+
+  mp_size_t powm_p_itch = sec_powm_itch (nn, an, pn);
+  mp_size_t powm_q_itch = sec_powm_itch (nn, bn, qn);
+  mp_size_t mod_mul_itch = cn + MAX(pn, qn) 
+    + sec_mod_mul_itch (MAX(pn, qn), cn, pn);
+
+  mp_size_t mul_itch = sec_mul_itch (qn, pn);
+  mp_size_t add_1_itch = mpn_sec_add_1_itch (nn - qn);
+
+  /* pn + qn for the product q * r_mod_p' */
+  mp_size_t itch = pn + qn + MAX (mul_itch, add_1_itch);
+
+  itch = MAX (itch, powm_p_itch);
+  itch = MAX (itch, powm_q_itch);
+  itch = MAX (itch, mod_mul_itch);
+
+  /* pn + qn for the r_mod_p and r_mod_q temporaries. */
+  return pn + qn + itch;
+}
+
+void
+_rsa_sec_compute_root (const struct rsa_private_key *key,
+		       mp_limb_t *rp, const mp_limb_t *mp,
+		       mp_limb_t *scratch)
+{
+  mp_size_t nn = NETTLE_OCTET_SIZE_TO_LIMB_SIZE (key->size);
+
+  /* The common case is pn = qn. This function would be simpler if we
+   * could require that pn >= qn. */
+  const mp_limb_t *pp = mpz_limbs_read (key->p);
+  const mp_limb_t *qp = mpz_limbs_read (key->q);
+
+  mp_size_t pn = mpz_size (key->p);
+  mp_size_t qn = mpz_size (key->q);
+  mp_size_t an = mpz_size (key->a);
+  mp_size_t bn = mpz_size (key->b);
+  mp_size_t cn = mpz_size (key->c);
+
+  mp_limb_t *r_mod_p = scratch;
+  mp_limb_t *r_mod_q = scratch + pn;
+  mp_limb_t *scratch_out = r_mod_q + qn;
+  mp_limb_t cy;
+
+  assert (pn <= nn);
+  assert (qn <= nn);
+  assert (an <= pn);
+  assert (bn <= qn);
+  assert (cn <= pn);
+
+  /* Compute r_mod_p = m^d % p = (m%p)^a % p */
+  sec_powm (r_mod_p, mp, nn, mpz_limbs_read (key->a), an, pp, pn, scratch_out);
+  /* Compute r_mod_q = m^d % q = (m%q)^b % q */
+  sec_powm (r_mod_q, mp, nn, mpz_limbs_read (key->b), bn, qp, qn, scratch_out);
+
+  /* Set r_mod_p' = r_mod_p * c % p - r_mod_q * c % p . */
+  sec_mod_mul (scratch_out, r_mod_p, pn, mpz_limbs_read (key->c), cn, pp, pn,
+	       scratch_out + cn + pn);
+  mpn_copyi (r_mod_p, scratch_out, pn);
+
+  sec_mod_mul (scratch_out, r_mod_q, qn, mpz_limbs_read (key->c), cn, pp, pn,
+	       scratch_out + cn + qn);
+  cy = mpn_sub_n (r_mod_p, r_mod_p, scratch_out, pn);
+  cnd_add_n (cy, r_mod_p, pp, pn);
+
+  /* Finally, compute x = r_mod_q + q r_mod_p' */
+  sec_mul (scratch_out, qp, qn, r_mod_p, pn, scratch_out + pn + qn);
+
+  cy = mpn_add_n (rp, scratch_out, r_mod_q, qn);
+  mpn_sec_add_1 (rp + qn, scratch_out + qn, nn - qn, cy, scratch_out + pn + qn);
+}
+#endif
diff --git a/rsa-sec-decrypt.c b/rsa-sec-decrypt.c
new file mode 100644
index 00000000..e6a4b267
--- /dev/null
+++ b/rsa-sec-decrypt.c
@@ -0,0 +1,72 @@
+/* rsa-sec-decrypt.c
+
+   RSA decryption, using randomized RSA blinding to be more resistant
+   to side-channel attacks like timing attacks or cache based memory
+   access measurements.
+
+   Copyright (C) 2001, 2012 Niels Möller, Nikos Mavrogiannopoulos
+   Copyright (C) 2018 Red Hat, Inc.
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * 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.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle 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
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "rsa.h"
+#include "rsa-internal.h"
+
+#include "gmp-glue.h"
+
+int
+rsa_sec_decrypt(const struct rsa_public_key *pub,
+	        const struct rsa_private_key *key,
+	        void *random_ctx, nettle_random_func *random,
+	        size_t length, uint8_t *message,
+	        const mpz_t gibberish)
+{
+  TMP_GMP_DECL (m, mp_limb_t);
+  TMP_GMP_DECL (em, uint8_t);
+  int res;
+
+  TMP_GMP_ALLOC (m, mpz_size(pub->n));
+  TMP_GMP_ALLOC (em, key->size);
+
+  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, m,
+				  mpz_limbs_read(gibberish),
+				  mpz_size(gibberish));
+
+  mpn_get_base256 (em, key->size, m, mpz_size(pub->n));
+
+  res &= _pkcs1_sec_decrypt (length, message, key->size, em);
+
+  TMP_GMP_FREE (em);
+  TMP_GMP_FREE (m);
+  return res;
+}
+
diff --git a/rsa-sign-tr.c b/rsa-sign-tr.c
index 257a02b4..f824c4ca 100644
--- a/rsa-sign-tr.c
+++ b/rsa-sign-tr.c
@@ -4,6 +4,7 @@
 
    Copyright (C) 2001, 2015 Niels Möller
    Copyright (C) 2012 Nikos Mavrogiannopoulos
+   Copyright (C) 2018 Red Hat Inc.
 
    This file is part of GNU Nettle.
 
@@ -36,9 +37,15 @@
 # include "config.h"
 #endif
 
+#include <assert.h>
+
+#include "gmp-glue.h"
 #include "rsa.h"
 #include "rsa-internal.h"
 
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+#if NETTLE_USE_MINI_GMP
 /* Blinds m, by computing c = m r^e (mod n), for a random r. Also
    returns the inverse (ri), for use by rsa_unblind. */
 static void
@@ -119,3 +126,251 @@ rsa_compute_root_tr(const struct rsa_public_key *pub,
 
   return res;
 }
+
+int
+_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,
+			 const struct rsa_private_key *key,
+			 void *random_ctx, nettle_random_func *random,
+			 mp_limb_t *x, const mp_limb_t *m, size_t mn)
+{
+  mpz_t mz;
+  mpz_t xz;
+  int res;
+
+  mpz_init(mz);
+  mpz_init(xz);
+
+  mpn_copyi(mpz_limbs_write(mz, mn), m, mn);
+  mpz_limbs_finish(mz, mn);
+
+  res = rsa_compute_root_tr(pub, key, random_ctx, random, xz, mz);
+
+  if (res)
+    mpz_limbs_copy(x, xz, mpz_size(pub->n));
+
+  mpz_clear(mz);
+  mpz_clear(xz);
+  return res;
+}
+#else
+/* Blinds m, by computing c = m r^e (mod n), for a random r. Also
+   returns the inverse (ri), for use by rsa_unblind. */
+static void
+rsa_sec_blind (const struct rsa_public_key *pub,
+               void *random_ctx, nettle_random_func *random,
+               mp_limb_t *c, mp_limb_t *ri, const mp_limb_t *m,
+               mp_size_t mn)
+{
+  const mp_limb_t *ep = mpz_limbs_read (pub->e);
+  const mp_limb_t *np = mpz_limbs_read (pub->n);
+  mp_bitcnt_t ebn = mpz_sizeinbase (pub->e, 2);
+  mp_size_t nn = mpz_size (pub->n);
+  size_t itch;
+  size_t i2;
+  mp_limb_t *scratch;
+  TMP_GMP_DECL (tp, mp_limb_t);
+  TMP_GMP_DECL (rp, mp_limb_t);
+  TMP_GMP_DECL (r, uint8_t);
+
+  TMP_GMP_ALLOC (rp, nn);
+  TMP_GMP_ALLOC (r, nn * sizeof(mp_limb_t));
+
+  /* c = m*(r^e) mod n */
+  itch = mpn_sec_powm_itch(nn, ebn, nn);
+  i2 = mpn_sec_mul_itch(nn, mn);
+  itch = MAX(itch, i2);
+  i2 = mpn_sec_div_r_itch(nn + mn, nn);
+  itch = MAX(itch, i2);
+  i2 = mpn_sec_invert_itch(nn);
+  itch = MAX(itch, i2);
+
+  TMP_GMP_ALLOC (tp, nn + mn + itch);
+  scratch = tp + nn + mn;
+
+  /* ri = r^(-1) */
+  do
+    {
+      random(random_ctx, nn * sizeof(mp_limb_t), (uint8_t *)r);
+      mpn_set_base256(rp, nn, r, nn * sizeof(mp_limb_t));
+      mpn_copyi(tp, rp, nn);
+      /* invert r */
+    }
+  while (!mpn_sec_invert (ri, tp, np, nn, 2 * nn * GMP_NUMB_BITS, scratch));
+
+  mpn_sec_powm (c, rp, nn, ep, ebn, np, nn, scratch);
+  /* normally mn == nn, but m can be smaller in some cases */
+  mpn_sec_mul (tp, c, nn, m, mn, scratch);
+  mpn_sec_div_r (tp, nn + mn, np, nn, scratch);
+  mpn_copyi(c, tp, nn);
+
+  TMP_GMP_FREE (r);
+  TMP_GMP_FREE (rp);
+  TMP_GMP_FREE (tp);
+}
+
+/* m = c ri mod n */
+static void
+rsa_sec_unblind (const struct rsa_public_key *pub,
+                 mp_limb_t *x, mp_limb_t *ri, const mp_limb_t *c)
+{
+  const mp_limb_t *np = mpz_limbs_read (pub->n);
+  mp_size_t nn = mpz_size (pub->n);
+
+  size_t itch;
+  size_t i2;
+  mp_limb_t *scratch;
+  TMP_GMP_DECL(tp, mp_limb_t);
+
+  itch = mpn_sec_mul_itch(nn, nn);
+  i2 = mpn_sec_div_r_itch(nn + nn, nn);
+  itch = MAX(itch, i2);
+
+  TMP_GMP_ALLOC (tp, nn + nn + itch);
+  scratch = tp + nn + nn;
+
+  mpn_sec_mul (tp, c, nn, ri, nn, scratch);
+  mpn_sec_div_r (tp, nn + nn, np, nn, scratch);
+  mpn_copyi(x, tp, nn);
+
+  TMP_GMP_FREE (tp);
+}
+
+static int
+sec_equal(const mp_limb_t *a, const mp_limb_t *b, size_t limbs)
+{
+  volatile mp_limb_t z = 0;
+  size_t i;
+
+  for (i = 0; i < limbs; i++)
+    {
+      z |= (a[i] ^ b[i]);
+    }
+
+  /* FIXME: Might compile to a branch instruction on some platforms. */
+  return z == 0;
+}
+
+static int
+rsa_sec_check_root(const struct rsa_public_key *pub,
+                   const mp_limb_t *x, const mp_limb_t *m)
+{
+  mp_size_t nn = mpz_size (pub->n);
+  mp_size_t ebn = mpz_sizeinbase (pub->e, 2);
+  const mp_limb_t *np = mpz_limbs_read (pub->n);
+  const mp_limb_t *ep = mpz_limbs_read (pub->e);
+  int ret;
+
+  mp_size_t itch;
+
+  mp_limb_t *scratch;
+  TMP_GMP_DECL(tp, mp_limb_t);
+
+  itch = mpn_sec_powm_itch (nn, ebn, nn);
+  TMP_GMP_ALLOC (tp, nn + itch);
+  scratch = tp + nn;
+
+  mpn_sec_powm(tp, x, nn, ep, ebn, np, nn, scratch);
+  ret = sec_equal(tp, m, nn);
+
+  TMP_GMP_FREE (tp);
+  return ret;
+}
+
+static void
+cnd_mpn_zero (int cnd, volatile mp_ptr rp, mp_size_t n)
+{
+  volatile mp_limb_t c;
+  volatile mp_limb_t mask = (mp_limb_t) cnd - 1;
+
+  while (--n >= 0)
+    {
+      c = rp[n];
+      c &= mask;
+      rp[n] = c;
+    }
+}
+
+/* Checks for any errors done in the RSA computation. That avoids
+ * attacks which rely on faults on hardware, or even software MPI
+ * implementation.
+ * This version is side-channel silent even in case of error,
+ * the destination buffer is always overwritten */
+int
+_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,
+			 const struct rsa_private_key *key,
+			 void *random_ctx, nettle_random_func *random,
+			 mp_limb_t *x, const mp_limb_t *m, size_t mn)
+{
+  TMP_GMP_DECL (c, mp_limb_t);
+  TMP_GMP_DECL (ri, mp_limb_t);
+  TMP_GMP_DECL (scratch, mp_limb_t);
+  size_t key_limb_size;
+  int ret;
+
+  key_limb_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);
+
+  /* mpz_powm_sec handles only odd moduli. If p, q or n is even, the
+     key is invalid and rejected by rsa_private_key_prepare. However,
+     some applications, notably gnutls, don't use this function, and
+     we don't want an invalid key to lead to a crash down inside
+     mpz_powm_sec. So do an additional check here. */
+  if (mpz_even_p (pub->n) || mpz_even_p (key->p) || mpz_even_p (key->q))
+    {
+      mpn_zero(x, key_limb_size);
+      return 0;
+    }
+
+  assert(mpz_size(pub->n) == key_limb_size);
+  assert(mn <= key_limb_size);
+
+  TMP_GMP_ALLOC (c, key_limb_size);
+  TMP_GMP_ALLOC (ri, key_limb_size);
+  TMP_GMP_ALLOC (scratch, _rsa_sec_compute_root_itch(key));
+
+  rsa_sec_blind (pub, random_ctx, random, x, ri, m, mn);
+
+  _rsa_sec_compute_root(key, c, x, scratch);
+
+  ret = rsa_sec_check_root(pub, c, x);
+
+  rsa_sec_unblind(pub, x, ri, c);
+
+  cnd_mpn_zero(1 - ret, x, key_limb_size);
+
+  TMP_GMP_FREE (scratch);
+  TMP_GMP_FREE (ri);
+  TMP_GMP_FREE (c);
+  return ret;
+}
+
+/* Checks for any errors done in the RSA computation. That avoids
+ * attacks which rely on faults on hardware, or even software MPI
+ * implementation.
+ * This version is maintained for API compatibility reasons. It
+ * is not completely side-channel silent. There are conditionals
+ * in buffer copying both in case of success or error.
+ */
+int
+rsa_compute_root_tr(const struct rsa_public_key *pub,
+		    const struct rsa_private_key *key,
+		    void *random_ctx, nettle_random_func *random,
+		    mpz_t x, const mpz_t m)
+{
+  TMP_GMP_DECL (l, mp_limb_t);
+  int res;
+
+  mp_size_t l_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);
+  TMP_GMP_ALLOC (l, l_size);
+
+  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, l,
+				  mpz_limbs_read(m), mpz_size(m));
+  if (res) {
+    mp_limb_t *xp = mpz_limbs_write (x, l_size);
+    mpn_copyi (xp, l, l_size);
+    mpz_limbs_finish (x, l_size);
+  }
+
+  TMP_GMP_FREE (l);
+  return res;
+}
+#endif
diff --git a/rsa-sign.c b/rsa-sign.c
index a5b6cfab..9a6409a9 100644
--- a/rsa-sign.c
+++ b/rsa-sign.c
@@ -35,10 +35,11 @@
 # include "config.h"
 #endif
 
+#include <assert.h>
+
 #include "rsa.h"
 #include "rsa-internal.h"
-
-#include "bignum.h"
+#include "gmp-glue.h"
 
 void
 rsa_private_key_init(struct rsa_private_key *key)
@@ -70,7 +71,13 @@ int
 rsa_private_key_prepare(struct rsa_private_key *key)
 {
   mpz_t n;
-  
+
+  /* A key is invalid if the sizes of q and c are smaller than
+   * the size of n, we rely on that property in calculations so
+   * fail early if that happens. */
+  if (mpz_size (key->q) + mpz_size (key->c) < mpz_size(key->p))
+    return 0;
+
   /* The size of the product is the sum of the sizes of the factors,
    * or sometimes one less. It's possible but tricky to compute the
    * size without computing the full product. */
@@ -81,10 +88,12 @@ rsa_private_key_prepare(struct rsa_private_key *key)
   key->size = _rsa_check_size(n);
 
   mpz_clear(n);
-  
+
   return (key->size > 0);
 }
 
+#if NETTLE_USE_MINI_GMP
+
 /* Computing an rsa root. */
 void
 rsa_compute_root(const struct rsa_private_key *key,
@@ -143,3 +152,35 @@ rsa_compute_root(const struct rsa_private_key *key,
 
   mpz_clear(xp); mpz_clear(xq);
 }
+
+#else /* !NETTLE_USE_MINI_GMP */
+
+/* Computing an rsa root. */
+void
+rsa_compute_root(const struct rsa_private_key *key,
+		 mpz_t x, const mpz_t m)
+{
+  TMP_GMP_DECL (scratch, mp_limb_t);
+  TMP_GMP_DECL (ml, mp_limb_t);
+  mp_limb_t *xl;
+  size_t key_size;
+
+  key_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);
+  assert(mpz_size (m) <= key_size);
+
+  /* we need a copy because m can be shorter than key_size,
+   * but _rsa_sec_compute_root expect all inputs to be
+   * normalized to a key_size long buffer length */
+  TMP_GMP_ALLOC (ml, key_size);
+  mpz_limbs_copy(ml, m, key_size);
+
+  TMP_GMP_ALLOC (scratch, _rsa_sec_compute_root_itch(key));
+
+  xl = mpz_limbs_write (x, key_size);
+  _rsa_sec_compute_root (key, xl, ml, scratch);
+  mpz_limbs_finish (x, key_size);
+
+  TMP_GMP_FREE (ml);
+  TMP_GMP_FREE (scratch);
+}
+#endif /* !NETTLE_USE_MINI_GMP */
diff --git a/rsa.h b/rsa.h
index 7d66d004..3b10155f 100644
--- a/rsa.h
+++ b/rsa.h
@@ -88,6 +88,7 @@ extern "C" {
 #define rsa_encrypt nettle_rsa_encrypt
 #define rsa_decrypt nettle_rsa_decrypt
 #define rsa_decrypt_tr nettle_rsa_decrypt_tr
+#define rsa_sec_decrypt nettle_rsa_sec_decrypt
 #define rsa_compute_root nettle_rsa_compute_root
 #define rsa_compute_root_tr nettle_rsa_compute_root_tr
 #define rsa_generate_keypair nettle_rsa_generate_keypair
@@ -418,6 +419,15 @@ rsa_decrypt_tr(const struct rsa_public_key *pub,
 	       size_t *length, uint8_t *message,
 	       const mpz_t gibberish);
 
+/* like rsa_decrypt_tr but with additional side-channel resistance.
+ * NOTE: the length of the final message must be known in advance. */
+int
+rsa_sec_decrypt(const struct rsa_public_key *pub,
+	        const struct rsa_private_key *key,
+	        void *random_ctx, nettle_random_func *random,
+	        size_t length, uint8_t *message,
+	        const mpz_t gibberish);
+
 /* Compute x, the e:th root of m. Calling it with x == m is allowed. */
 void
 rsa_compute_root(const struct rsa_private_key *key,
diff --git a/testsuite/.gitignore b/testsuite/.gitignore
index 5db4e789..f98a949a 100644
--- a/testsuite/.gitignore
+++ b/testsuite/.gitignore
@@ -15,6 +15,7 @@
 /cfb-test
 /chacha-poly1305-test
 /chacha-test
+/cnd-memcpy-test
 /ctr-test
 /curve25519-dh-test
 /cxx-test
@@ -58,11 +59,14 @@
 /meta-hash-test
 /pbkdf2-test
 /pkcs1-test
+/pkcs1-sec-decrypt-test
 /poly1305-test
 /pss-mgf1-test
 /pss-test
 /random-prime-test
 /ripemd160-test
+/rsa-sec-decrypt-test
+/rsa-compute-root-test
 /rsa-encrypt-test
 /rsa-keygen-test
 /rsa-pss-sign-tr-test
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index 033d8e0b..f36a1f7f 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -25,6 +25,9 @@ camellia-test$(EXEEXT): camellia-test.$(OBJEXT)
 chacha-test$(EXEEXT): chacha-test.$(OBJEXT)
 	$(LINK) chacha-test.$(OBJEXT) $(TEST_OBJS) -o chacha-test$(EXEEXT)
 
+cnd-memcpy-test$(EXEEXT): cnd-memcpy-test.$(OBJEXT)
+	$(LINK) cnd-memcpy-test.$(OBJEXT) $(TEST_OBJS) -o cnd-memcpy-test$(EXEEXT)
+
 des-test$(EXEEXT): des-test.$(OBJEXT)
 	$(LINK) des-test.$(OBJEXT) $(TEST_OBJS) -o des-test$(EXEEXT)
 
@@ -187,6 +190,9 @@ random-prime-test$(EXEEXT): random-prime-test.$(OBJEXT)
 pkcs1-test$(EXEEXT): pkcs1-test.$(OBJEXT)
 	$(LINK) pkcs1-test.$(OBJEXT) $(TEST_OBJS) -o pkcs1-test$(EXEEXT)
 
+pkcs1-sec-decrypt-test$(EXEEXT): pkcs1-sec-decrypt-test.$(OBJEXT)
+	$(LINK) pkcs1-sec-decrypt-test.$(OBJEXT) $(TEST_OBJS) -o pkcs1-sec-decrypt-test$(EXEEXT)
+
 pss-test$(EXEEXT): pss-test.$(OBJEXT)
 	$(LINK) pss-test.$(OBJEXT) $(TEST_OBJS) -o pss-test$(EXEEXT)
 
@@ -208,6 +214,12 @@ rsa-encrypt-test$(EXEEXT): rsa-encrypt-test.$(OBJEXT)
 rsa-keygen-test$(EXEEXT): rsa-keygen-test.$(OBJEXT)
 	$(LINK) rsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o rsa-keygen-test$(EXEEXT)
 
+rsa-sec-decrypt-test$(EXEEXT): rsa-sec-decrypt-test.$(OBJEXT)
+	$(LINK) rsa-sec-decrypt-test.$(OBJEXT) $(TEST_OBJS) -o rsa-sec-decrypt-test$(EXEEXT)
+
+rsa-compute-root-test$(EXEEXT): rsa-compute-root-test.$(OBJEXT)
+	$(LINK) rsa-compute-root-test.$(OBJEXT) $(TEST_OBJS) -o rsa-compute-root-test$(EXEEXT)
+
 dsa-test$(EXEEXT): dsa-test.$(OBJEXT)
 	$(LINK) dsa-test.$(OBJEXT) $(TEST_OBJS) -o dsa-test$(EXEEXT)
 
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in
index 3ab1d3f0..e2982b66 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -14,6 +14,7 @@ TS_NETTLE_SOURCES = aes-test.c arcfour-test.c arctwo-test.c \
 		    blowfish-test.c cast128-test.c \
 	            base16-test.c base64-test.c \
 		    camellia-test.c chacha-test.c \
+		    cnd-memcpy-test.c \
 		    des-test.c des3-test.c des-compat-test.c \
 		    md2-test.c md4-test.c md5-test.c md5-compat-test.c \
 		    memeql-test.c memxor-test.c gosthash94-test.c \
@@ -36,9 +37,12 @@ TS_NETTLE_SOURCES = aes-test.c arcfour-test.c arctwo-test.c \
 TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
 		     rsa2sexp-test.c sexp2rsa-test.c \
 		     bignum-test.c random-prime-test.c \
-		     pkcs1-test.c pss-test.c rsa-sign-tr-test.c \
+		     pkcs1-test.c pkcs1-sec-decrypt-test.c \
+		     pss-test.c rsa-sign-tr-test.c \
 		     pss-mgf1-test.c rsa-pss-sign-tr-test.c \
 		     rsa-test.c rsa-encrypt-test.c rsa-keygen-test.c \
+		     rsa-sec-decrypt-test.c \
+		     rsa-compute-root-test.c \
 		     dsa-test.c dsa-keygen-test.c \
 		     curve25519-dh-test.c \
 		     ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c \
diff --git a/testsuite/cnd-memcpy-test.c b/testsuite/cnd-memcpy-test.c
new file mode 100644
index 00000000..6e5db341
--- /dev/null
+++ b/testsuite/cnd-memcpy-test.c
@@ -0,0 +1,47 @@
+#include "testutils.h"
+#include "knuth-lfib.h"
+#include "memops.h"
+
+#if HAVE_VALGRIND_MEMCHECK_H
+# include <valgrind/memcheck.h>
+static void
+cnd_memcpy_for_test(int cnd, void *dst, const void *src, size_t n)
+{
+  /* Makes valgrind trigger on any branches depending on the input
+     data. */
+  VALGRIND_MAKE_MEM_UNDEFINED (dst, n);
+  VALGRIND_MAKE_MEM_UNDEFINED (src, n);
+  VALGRIND_MAKE_MEM_UNDEFINED (&cnd, sizeof(cnd));
+
+  cnd_memcpy (cnd, dst, src, n);
+  VALGRIND_MAKE_MEM_DEFINED (src, n);
+  VALGRIND_MAKE_MEM_DEFINED (dst, n);
+}
+#else
+#define cnd_memcpy_for_test cnd_memcpy
+#endif
+
+#define MAX_SIZE 50
+void
+test_main(void)
+{
+  uint8_t src[MAX_SIZE];
+  uint8_t dst[MAX_SIZE];
+  uint8_t res[MAX_SIZE];
+  struct knuth_lfib_ctx random_ctx;
+
+  knuth_lfib_init (&random_ctx, 11);
+
+  size_t size;
+  for (size = 1; size < 50; size++)
+    {
+      knuth_lfib_random (&random_ctx, size, src);
+      knuth_lfib_random (&random_ctx, size, dst);
+      memcpy (res, dst, size);
+      cnd_memcpy_for_test (0, res, src, size);
+
+      ASSERT (memcmp (res, dst, size) == 0);
+      cnd_memcpy_for_test (1, res, src, size);
+      ASSERT (memcmp (res, src, size) == 0);
+    }
+}
diff --git a/testsuite/ed25519-test.c b/testsuite/ed25519-test.c
index 83b6b84e..abcef34e 100644
--- a/testsuite/ed25519-test.c
+++ b/testsuite/ed25519-test.c
@@ -29,6 +29,8 @@
    not, see http://www.gnu.org/licenses/.
 */
 
+#define _GNU_SOURCE
+
 #include "testutils.h"
 
 #include <errno.h>
diff --git a/testsuite/pkcs1-sec-decrypt-test.c b/testsuite/pkcs1-sec-decrypt-test.c
new file mode 100644
index 00000000..9c7b06d5
--- /dev/null
+++ b/testsuite/pkcs1-sec-decrypt-test.c
@@ -0,0 +1,77 @@
+#include "testutils.h"
+
+#include "rsa.h"
+#include "rsa-internal.h"
+
+#if HAVE_VALGRIND_MEMCHECK_H
+# include <valgrind/memcheck.h>
+static int
+pkcs1_decrypt_for_test(size_t msg_len, uint8_t *msg,
+                       size_t pad_len, uint8_t *pad)
+{
+  int ret;
+
+  VALGRIND_MAKE_MEM_UNDEFINED (msg, msg_len);
+  VALGRIND_MAKE_MEM_UNDEFINED (pad, pad_len);
+
+  ret = _pkcs1_sec_decrypt (msg_len, msg, pad_len, pad);
+
+  VALGRIND_MAKE_MEM_DEFINED (msg, msg_len);
+  VALGRIND_MAKE_MEM_DEFINED (pad, pad_len);
+  VALGRIND_MAKE_MEM_DEFINED (&ret, sizeof (ret));
+
+  return ret;
+}
+#else
+#define pkcs1_decrypt_for_test _pkcs1_sec_decrypt
+#endif
+
+void
+test_main(void)
+{
+  uint8_t pad[128];
+  uint8_t buffer[] =
+    "\x00\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10"
+    "\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20"
+    "\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x2f\x30"
+    "\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f\x40"
+    "\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x4e\x4f\x50"
+    "\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b\x5c\x5d\x5e\x5f\x60"
+    "\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x6e\x6f\x70"
+    "\x00\x53\x49\x47\x4e\x45\x44\x20\x4d\x45\x53\x53\x41\x47\x45\x2e";
+  uint8_t message[15];
+
+  memcpy(pad, buffer, 128);
+
+  memset (message, 'A', 15);
+  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 1);
+  ASSERT (memcmp (message, "SIGNED MESSAGE.", 15) == 0);
+
+  /* break format byte 1 */
+  memcpy(pad, buffer, 128);
+  pad[0] = 1;
+  memset (message, 'B', 15);
+  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);
+  ASSERT (memcmp (message, "BBBBBBBBBBBBBBB", 15) == 0);
+
+  /* break format byte 2 */
+  memcpy(pad, buffer, 128);
+  pad[1] = 1;
+  memset (message, 'C', 15);
+  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);
+  ASSERT (memcmp (message, "CCCCCCCCCCCCCCC", 15) == 0);
+
+  /* break padding */
+  memcpy(pad, buffer, 128);
+  pad[24] = 0;
+  memset (message, 'D', 15);
+  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);
+  ASSERT (memcmp (message, "DDDDDDDDDDDDDDD", 15) == 0);
+
+  /* break terminator */
+  memcpy(pad, buffer, 128);
+  pad[112] = 1;
+  memset (message, 'E', 15);
+  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);
+  ASSERT (memcmp (message, "EEEEEEEEEEEEEEE", 15) == 0);
+}
diff --git a/testsuite/rsa-compute-root-test.c b/testsuite/rsa-compute-root-test.c
new file mode 100644
index 00000000..9e3cb7f8
--- /dev/null
+++ b/testsuite/rsa-compute-root-test.c
@@ -0,0 +1,234 @@
+#include "testutils.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <limits.h>
+#include <sys/time.h>
+
+#include "rsa.h"
+
+#define KEY_COUNT 20
+#define COUNT 100
+
+static void
+random_fn (void *ctx, size_t n, uint8_t *dst)
+{
+  gmp_randstate_t *rands = (gmp_randstate_t *)ctx;
+  mpz_t r;
+
+  mpz_init (r);
+  mpz_urandomb (r, *rands, n*8);
+  nettle_mpz_get_str_256 (n, dst, r);
+  mpz_clear (r);
+}
+
+static void
+test_one (gmp_randstate_t *rands, struct rsa_public_key *pub,
+          struct rsa_private_key *key, mpz_t plaintext)
+{
+  mpz_t ciphertext;
+  mpz_t decrypted;
+
+  mpz_init (ciphertext);
+  mpz_init (decrypted);
+
+  mpz_powm (ciphertext, plaintext, pub->e, pub->n);
+  rsa_compute_root_tr (pub, key, rands, random_fn, decrypted, ciphertext);
+  if (mpz_cmp (plaintext, decrypted)) {
+    fprintf (stderr, "rsa_compute_root_tr failed\n");
+
+    fprintf(stderr, "Public key: size=%lu\n n:", pub->size);
+    mpz_out_str (stderr, 10, pub->n);
+    fprintf(stderr, "\n e:");
+    mpz_out_str (stderr, 10, pub->e);
+    fprintf(stderr, "\nPrivate key: size=%lu\n p:", key->size);
+    mpz_out_str (stderr, 10, key->p);
+    fprintf(stderr, "\n q:");
+    mpz_out_str (stderr, 10, key->q);
+    fprintf(stderr, "\n a:");
+    mpz_out_str (stderr, 10, key->a);
+    fprintf(stderr, "\n b:");
+    mpz_out_str (stderr, 10, key->b);
+    fprintf(stderr, "\n c:");
+    mpz_out_str (stderr, 10, key->c);
+    fprintf(stderr, "\n d:");
+    mpz_out_str (stderr, 10, key->d);
+    fprintf(stderr, "\n");
+
+    fprintf (stderr, "plaintext(%lu) = ", mpz_sizeinbase (plaintext, 2));
+    mpz_out_str (stderr, 10, plaintext);
+    fprintf (stderr, "\n");
+    fprintf (stderr, "ciphertext(%lu) = ", mpz_sizeinbase (ciphertext, 2));
+    mpz_out_str (stderr, 10, ciphertext);
+    fprintf (stderr, "\n");
+    fprintf (stderr, "decrypted(%lu) = ", mpz_sizeinbase (decrypted, 2));
+    mpz_out_str (stderr, 10, decrypted);
+    fprintf (stderr, "\n");
+    abort();
+  }
+
+  mpz_clear (ciphertext);
+  mpz_clear (decrypted);
+}
+
+#if !NETTLE_USE_MINI_GMP
+/* We want to generate keypairs that are not "standard" but have more size
+ * variance between q and p.
+ * Function is otherwise the same as standard rsa_generate_keypair()
+ */
+static void
+generate_keypair (gmp_randstate_t rands,
+                  struct rsa_public_key *pub, struct rsa_private_key *key)
+{
+  unsigned long int psize;
+  unsigned long int qsize;
+  mpz_t p1;
+  mpz_t q1;
+  mpz_t phi;
+  mpz_t tmp;
+
+  mpz_init (p1);
+  mpz_init (q1);
+  mpz_init (phi);
+  mpz_init (tmp);
+
+  psize = 100 + gmp_urandomm_ui (rands, 400);
+  qsize = 100 + gmp_urandomm_ui (rands, 400);
+
+  mpz_set_ui (pub->e, 65537);
+
+  for (;;)
+    {
+      for (;;)
+        {
+          mpz_rrandomb (key->p, rands, psize);
+          mpz_nextprime (key->p, key->p);
+          mpz_sub_ui (p1, key->p, 1);
+          mpz_gcd (tmp, pub->e, p1);
+          if (mpz_cmp_ui (tmp, 1) == 0)
+            break;
+        }
+
+      for (;;)
+        {
+          mpz_rrandomb (key->q, rands, qsize);
+          mpz_nextprime (key->q, key->q);
+          mpz_sub_ui (q1, key->q, 1);
+          mpz_gcd (tmp, pub->e, q1);
+          if (mpz_cmp_ui (tmp, 1) == 0)
+            break;
+        }
+
+      if (mpz_invert (key->c, key->q, key->p))
+        break;
+    }
+
+  mpz_mul(phi, p1, q1);
+  assert (mpz_invert(key->d, pub->e, phi));
+
+  mpz_fdiv_r (key->a, key->d, p1);
+  mpz_fdiv_r (key->b, key->d, q1);
+
+  mpz_mul (pub->n, key->p, key->q);
+
+  pub->size = key->size = mpz_size(pub->n) * sizeof(mp_limb_t);
+
+  mpz_clear (tmp);
+  mpz_clear (phi);
+  mpz_clear (q1);
+  mpz_clear (p1);
+}
+#endif
+
+#if !NETTLE_USE_MINI_GMP
+static void
+get_random_seed(mpz_t seed)
+{
+  struct timeval tv;
+  FILE *f;
+  f = fopen ("/dev/urandom", "rb");
+  if (f)
+    {
+      uint8_t buf[8];
+      size_t res;
+
+      setbuf (f, NULL);
+      res = fread (&buf, sizeof(buf), 1, f);
+      fclose(f);
+      if (res == 1)
+	{
+	  nettle_mpz_set_str_256_u (seed, sizeof(buf), buf);
+	  return;
+	}
+      fprintf (stderr, "Read of /dev/urandom failed: %s\n",
+	       strerror (errno));
+    }
+  gettimeofday(&tv, NULL);
+  mpz_set_ui (seed, tv.tv_sec);
+  mpz_mul_ui (seed, seed, 1000000UL);
+  mpz_add_ui (seed, seed, tv.tv_usec);
+}
+#endif /* !NETTLE_USE_MINI_GMP */
+
+void
+test_main (void)
+{
+  const char *nettle_test_seed;
+  gmp_randstate_t rands;
+  struct rsa_public_key pub;
+  struct rsa_private_key key;
+  mpz_t plaintext;
+  unsigned i, j;
+
+  rsa_private_key_init(&key);
+  rsa_public_key_init(&pub);
+  mpz_init (plaintext);
+
+  gmp_randinit_default (rands);
+
+#if !NETTLE_USE_MINI_GMP
+  nettle_test_seed = getenv ("NETTLE_TEST_SEED");
+  if (nettle_test_seed && *nettle_test_seed)
+    {
+      mpz_t seed;
+      mpz_init (seed);
+      if (mpz_set_str (seed, nettle_test_seed, 0) < 0
+	  || mpz_sgn (seed) < 0)
+	die ("Invalid NETTLE_TEST_SEED: %s\n",
+	     nettle_test_seed);
+      if (mpz_sgn (seed) == 0)
+	get_random_seed (seed);
+      fprintf (stderr, "Using NETTLE_TEST_SEED=");
+      mpz_out_str (stderr, 10, seed);
+      fprintf (stderr, "\n");
+
+      gmp_randseed (rands, seed);
+      mpz_clear (seed);
+    }
+#endif
+
+  for (j = 0; j < KEY_COUNT; j++)
+    {
+#if !NETTLE_USE_MINI_GMP
+      generate_keypair(rands, &pub, &key);
+#else
+      rsa_generate_keypair(&pub, &key, &rands, random_fn, NULL, NULL, 512, 16);
+#endif /* !NETTLE_USE_MINI_GMP */
+
+      for (i = 0; i < COUNT; i++)
+	{
+	  mpz_urandomb(plaintext, rands, mpz_sizeinbase(pub.n, 2) - 1);
+	  test_one(&rands, &pub, &key, plaintext);
+	}
+      for (i = 0; i < COUNT; i++)
+	{
+	  mpz_rrandomb(plaintext, rands, mpz_sizeinbase(pub.n, 2) - 1);
+	  test_one(&rands, &pub, &key, plaintext);
+	}
+    }
+  mpz_clear (plaintext);
+  rsa_public_key_clear (&pub);
+  rsa_private_key_clear (&key);
+
+  gmp_randclear (rands);
+}
diff --git a/testsuite/rsa-encrypt-test.c b/testsuite/rsa-encrypt-test.c
index 93053a7f..87525f78 100644
--- a/testsuite/rsa-encrypt-test.c
+++ b/testsuite/rsa-encrypt-test.c
@@ -30,6 +30,8 @@ test_main(void)
 
   if (verbose)
     fprintf(stderr, "msg: `%s', length = %d\n", msg, (int) msg_length);
+
+  ASSERT(msg_length <= key.size);
   
   ASSERT(rsa_encrypt(&pub,
 		     &lfib, (nettle_random_func *) knuth_lfib_random,
@@ -42,7 +44,7 @@ test_main(void)
       mpz_out_str(stderr, 10, gibberish);
     }
   
-  decrypted = xalloc(msg_length + 1);
+  decrypted = xalloc(key.size + 1);
 
   knuth_lfib_random (&lfib, msg_length + 1, decrypted);
   after = decrypted[msg_length];
@@ -56,14 +58,14 @@ test_main(void)
   ASSERT(MEMEQ(msg_length, msg, decrypted));
   ASSERT(decrypted[msg_length] == after);
 
-  knuth_lfib_random (&lfib, msg_length + 1, decrypted);
-  after = decrypted[msg_length];
+  knuth_lfib_random (&lfib, key.size + 1, decrypted);
+  after = decrypted[key.size];
 
   decrypted_length = key.size;
   ASSERT(rsa_decrypt(&key, &decrypted_length, decrypted, gibberish));
   ASSERT(decrypted_length == msg_length);
   ASSERT(MEMEQ(msg_length, msg, decrypted));
-  ASSERT(decrypted[msg_length] == after);
+  ASSERT(decrypted[key.size] == after);
   
   knuth_lfib_random (&lfib, msg_length + 1, decrypted);
   after = decrypted[msg_length];
@@ -76,6 +78,30 @@ test_main(void)
   ASSERT(MEMEQ(msg_length, msg, decrypted));
   ASSERT(decrypted[msg_length] == after);
 
+  /* test side channel resistant variant */
+  knuth_lfib_random (&lfib, msg_length + 1, decrypted);
+  after = decrypted[msg_length];
+  decrypted_length = msg_length;
+
+  ASSERT(rsa_sec_decrypt(&pub, &key,
+                         &lfib, (nettle_random_func *) knuth_lfib_random,
+                         decrypted_length, decrypted, gibberish));
+  ASSERT(MEMEQ(msg_length, msg, decrypted));
+  ASSERT(decrypted[msg_length] == after);
+
+  /* test invalid length to rsa_sec_decrypt */
+  knuth_lfib_random (&lfib, msg_length + 1, decrypted);
+  decrypted_length = msg_length - 1;
+  after = decrypted[decrypted_length] = 'X';
+  decrypted[0] = 'A';
+
+  ASSERT(!rsa_sec_decrypt(&pub, &key,
+                          &lfib, (nettle_random_func *) knuth_lfib_random,
+                          decrypted_length, decrypted, gibberish));
+  ASSERT(decrypted[decrypted_length] == after);
+  ASSERT(decrypted[0] == 'A');
+
+
   /* Test invalid key. */
   mpz_add_ui (key.q, key.q, 2);
   decrypted_length = key.size;
diff --git a/testsuite/rsa-sec-decrypt-test.c b/testsuite/rsa-sec-decrypt-test.c
new file mode 100644
index 00000000..fb0ed3a1
--- /dev/null
+++ b/testsuite/rsa-sec-decrypt-test.c
@@ -0,0 +1,119 @@
+#include "testutils.h"
+
+#include "rsa.h"
+#include "knuth-lfib.h"
+
+#if HAVE_VALGRIND_MEMCHECK_H
+# include <valgrind/memcheck.h>
+
+#define MARK_MPZ_LIMBS_UNDEFINED(parm) \
+  VALGRIND_MAKE_MEM_UNDEFINED (mpz_limbs_read (parm), \
+                               mpz_size (parm) * sizeof (mp_limb_t))
+#define MARK_MPZ_LIMBS_DEFINED(parm) \
+  VALGRIND_MAKE_MEM_DEFINED (mpz_limbs_read (parm), \
+                               mpz_size (parm) * sizeof (mp_limb_t))
+static int
+rsa_decrypt_for_test(const struct rsa_public_key *pub,
+                     const struct rsa_private_key *key,
+                     void *random_ctx, nettle_random_func *random,
+                     size_t length, uint8_t *message,
+                     const mpz_t gibberish)
+{
+  int ret;
+  /* Makes valgrind trigger on any branches depending on the input
+     data. Except that (i) we have to allow rsa_sec_compute_root_tr to
+     check that p and q are odd, (ii) mpn_sec_div_r may leak
+     information about the most significant bits of p and q, due to
+     normalization check and table lookup in invert_limb, and (iii)
+     mpn_sec_powm may leak information about the least significant
+     bits of p and q, due to table lookup in binvert_limb. */
+  VALGRIND_MAKE_MEM_UNDEFINED (message, length);
+  MARK_MPZ_LIMBS_UNDEFINED(gibberish);
+  MARK_MPZ_LIMBS_UNDEFINED(key->a);
+  MARK_MPZ_LIMBS_UNDEFINED(key->b);
+  MARK_MPZ_LIMBS_UNDEFINED(key->c);
+  VALGRIND_MAKE_MEM_UNDEFINED(mpz_limbs_read (key->p) + 1,
+			      (mpz_size (key->p) - 3) * sizeof(mp_limb_t));
+  VALGRIND_MAKE_MEM_UNDEFINED(mpz_limbs_read (key->q) + 1,
+			      (mpz_size (key->q) - 3) * sizeof(mp_limb_t));
+
+  ret = rsa_sec_decrypt (pub, key, random_ctx, random, length, message, gibberish);
+
+  VALGRIND_MAKE_MEM_DEFINED (message, length);
+  VALGRIND_MAKE_MEM_DEFINED (&ret, sizeof(ret));
+  MARK_MPZ_LIMBS_DEFINED(gibberish);
+  MARK_MPZ_LIMBS_DEFINED(key->a);
+  MARK_MPZ_LIMBS_DEFINED(key->b);
+  MARK_MPZ_LIMBS_DEFINED(key->c);
+  MARK_MPZ_LIMBS_DEFINED(key->p);
+  MARK_MPZ_LIMBS_DEFINED(key->q);
+
+  return ret;
+}
+#else
+#define rsa_decrypt_for_test rsa_sec_decrypt
+#endif
+
+#define PAYLOAD_SIZE 50
+void
+test_main(void)
+{
+  struct rsa_public_key pub;
+  struct rsa_private_key key;
+  struct knuth_lfib_ctx random_ctx;
+
+  uint8_t plaintext[PAYLOAD_SIZE];
+  uint8_t decrypted[PAYLOAD_SIZE];
+  uint8_t verifybad[PAYLOAD_SIZE];
+  unsigned n_size = 1024;
+  mpz_t gibberish;
+  mpz_t garbage;
+  size_t size;
+
+  rsa_private_key_init(&key);
+  rsa_public_key_init(&pub);
+  mpz_init(gibberish);
+  mpz_init(garbage);
+
+  knuth_lfib_init (&random_ctx, 19);
+
+  memset(verifybad, 'A', PAYLOAD_SIZE);
+
+  for (size = 1; size < 51; size++)
+    {
+      ASSERT (rsa_generate_keypair(&pub, &key, &random_ctx,
+			           (nettle_random_func *) knuth_lfib_random,
+			           NULL, NULL, n_size, 17));
+
+      /* the next key will be 19 bits larger */
+      n_size += 19;
+
+      knuth_lfib_random (&random_ctx, PAYLOAD_SIZE, plaintext);
+      ASSERT(rsa_encrypt(&pub, &random_ctx,
+                         (nettle_random_func *) knuth_lfib_random,
+                         PAYLOAD_SIZE, plaintext, gibberish));
+
+      /* good decryption */
+      ASSERT (rsa_decrypt_for_test (&pub, &key, &random_ctx,
+                                    (nettle_random_func *) knuth_lfib_random,
+                                    PAYLOAD_SIZE, decrypted, gibberish) == 1);
+      ASSERT (MEMEQ (PAYLOAD_SIZE, plaintext, decrypted));
+
+      /* bad one */
+      memcpy(decrypted, verifybad, PAYLOAD_SIZE);
+      nettle_mpz_random_size(garbage, &random_ctx,
+                             (nettle_random_func *) knuth_lfib_random,
+                             mpz_sizeinbase(gibberish, 2));
+
+      ASSERT (rsa_decrypt_for_test (&pub, &key, &random_ctx,
+                                    (nettle_random_func *) knuth_lfib_random,
+                                    PAYLOAD_SIZE, decrypted, garbage) == 0);
+      ASSERT (MEMEQ (PAYLOAD_SIZE, verifybad, decrypted));
+    }
+
+  rsa_private_key_clear(&key);
+  rsa_public_key_clear(&pub);
+  mpz_clear(gibberish);
+  mpz_clear(garbage);
+}
+
diff --git a/testsuite/testutils.c b/testsuite/testutils.c
index 1812ff4f..337e4c4c 100644
--- a/testsuite/testutils.c
+++ b/testsuite/testutils.c
@@ -1004,7 +1004,7 @@ mpz_urandomb (mpz_t r, struct knuth_lfib_ctx *ctx, mp_bitcnt_t bits)
   uint8_t *buf = xalloc (bytes);
 
   knuth_lfib_random (ctx, bytes, buf);
-  buf[bytes-1] &= 0xff >> (8*bytes - bits);
+  buf[0] &= 0xff >> (8*bytes - bits);
   nettle_mpz_set_str_256_u (r, bytes, buf);
   free (buf);
 }
diff --git a/tools/nettle-pbkdf2.c b/tools/nettle-pbkdf2.c
index 1f0a3015..fe6528d9 100644
--- a/tools/nettle-pbkdf2.c
+++ b/tools/nettle-pbkdf2.c
@@ -31,6 +31,8 @@
    not, see http://www.gnu.org/licenses/.
 */
 
+#define _GNU_SOURCE
+
 #if HAVE_CONFIG_H
 # include "config.h"
 #endif