23 files changed, 355 insertions, 204 deletions

diff --git a/ChangeLog b/ChangeLog
index a187e4f3..8016fa5c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,47 @@
+2010-03-24  Niels Möller  <nisse@lysator.liu.se>
+
+	* rsa-keygen.c (rsa_generate_keypair): Ensure that bit size of e
+	is less than bit size of n, and check for the unlikely case p = q.
+
+	* rsa.h (RSA_MINIMUM_N_OCTETS, RSA_MINIMUM_N_BITS): Reduced, to
+	correspond to pkcs#1 encryption of single byte messagees.
+
+	* pgp-encode.c (pgp_put_rsa_sha1_signature): Check return value
+	from rsa_sha1_sign.
+	* rsa-compat.c (R_SignFinal): Likewise.
+
+	* rsa-md5-sign.c (rsa_md5_sign): Check and propagate return value
+	from pkcs1_rsa_md5_encode.
+	(rsa_md5_sign_digest): Check and propagate return value from
+	pkcs1_rsa_md5_encode_digest.
+	* rsa-md5-verify.c (rsa_md5_verify): Check return value from
+	pkcs1_rsa_md5_encode.
+	(rsa_md5_verify_digest): Check return value from
+	pkcs1_rsa_md5_encode_digest.
+	* rsa-sha1-sign.c: Analogous changes.
+	* rsa-sha1-verify.c: Analogous changes.
+	* rsa-sha256-sign.c: Analogous changes.
+	* rsa-sha256-verify.c: Analogous changes.
+	* rsa-sha512-sign.c: Analogous changes.
+	* rsa-sha512-verify.c: Analogous changes.
+
+	* pkcs1-rsa-md5.c (pkcs1_rsa_md5_encode)
+	(pkcs1_rsa_md5_encode_digest): Added return value. Check and
+	propagate return value from pkcs1_signature_prefix.
+	* pkcs1-rsa-sha256.c (pkcs1_rsa_sha256_encode)
+	(pkcs1_rsa_sha256_encode_digest): Likewise.
+	* pkcs1-rsa-sha1.c (pkcs1_rsa_sha1_encode)
+	(pkcs1_rsa_sha1_encode_digest): Likewise.
+	* pkcs1-rsa-sha512.c (pkcs1_rsa_sha512_encode)
+	(pkcs1_rsa_sha512_encode_digest): Likewise.
+
+	* pkcs1.c (pkcs1_signature_prefix): Interface change, take both
+	the total size and digest size as arguments, and return a status
+	code to say if the size was large enough.
+
+	* testsuite/Makefile.in: Added hogweed dependency for the test
+	programs.
+
 2010-03-23  Niels Möller  <nisse@lysator.liu.se>
 
 	* testsuite/rsa-test.c (test_main): Test signing with sha512.
diff --git a/NEWS b/NEWS
index bfa37d78..96851b17 100644
--- a/NEWS
+++ b/NEWS
@@ -1,3 +1,8 @@
+NEWS for the 2.5 release
+
+	This release breaks source and binary compatibility for the
+	RSA-related functions.
+	
 NEWS for the 2.0 release
 
 	This release breaks binary compatibility by splitting the
diff --git a/examples/rsa-sign.c b/examples/rsa-sign.c
index 3a97b26c..c4807618 100644
--- a/examples/rsa-sign.c
+++ b/examples/rsa-sign.c
@@ -65,7 +65,11 @@ main(int argc, char **argv)
     }
 
   mpz_init(s);
-  rsa_sha1_sign(&key, &hash, s);
+  if (!rsa_sha1_sign(&key, &hash, s))
+    {
+      werror("RSA key too small\n");
+      return 0;
+    }
 
   if (!mpz_out_str(stdout, 16, s))
     {
diff --git a/pgp-encode.c b/pgp-encode.c
index 5cb9529a..0ac46d21 100644
--- a/pgp-encode.c
+++ b/pgp-encode.c
@@ -294,9 +294,8 @@ pgp_put_rsa_sha1_signature(struct nettle_buffer *buffer,
     }
     
   mpz_init(s);
-  rsa_sha1_sign(key, hash, s);
-
-  if (!pgp_put_mpi(buffer, s))
+  if (!(rsa_sha1_sign(key, hash, s)
+	&& pgp_put_mpi(buffer, s)))
     {
       mpz_clear(s);
       return 0;
diff --git a/pkcs1-rsa-md5.c b/pkcs1-rsa-md5.c
index 1b9af157..eff25fa4 100644
--- a/pkcs1-rsa-md5.c
+++ b/pkcs1-rsa-md5.c
@@ -61,32 +61,40 @@ md5_prefix[] =
       /* Here comes the raw hash value */
 };
 
-void
-pkcs1_rsa_md5_encode(mpz_t m, unsigned length, struct md5_ctx *hash)
+int
+pkcs1_rsa_md5_encode(mpz_t m, unsigned size, struct md5_ctx *hash)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= MD5_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - MD5_DIGEST_SIZE, em,
-			 sizeof(md5_prefix),
-			 md5_prefix);
-  
-  md5_digest(hash, MD5_DIGEST_SIZE, em + length - MD5_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(md5_prefix),
+			     md5_prefix,
+			     MD5_DIGEST_SIZE))
+    {
+      md5_digest(hash, MD5_DIGEST_SIZE, em + size - MD5_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
 
-void
-pkcs1_rsa_md5_encode_digest(mpz_t m, unsigned length, const uint8_t *digest)
+int
+pkcs1_rsa_md5_encode_digest(mpz_t m, unsigned size, const uint8_t *digest)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= MD5_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - MD5_DIGEST_SIZE, em,
-			 sizeof(md5_prefix),
-			 md5_prefix);
-
-  memcpy(em + length - MD5_DIGEST_SIZE, digest, MD5_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(md5_prefix),
+			     md5_prefix,
+			     MD5_DIGEST_SIZE))
+    {
+      memcpy(em + size - MD5_DIGEST_SIZE, digest, MD5_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
diff --git a/pkcs1-rsa-sha1.c b/pkcs1-rsa-sha1.c
index b13be63c..85395bd4 100644
--- a/pkcs1-rsa-sha1.c
+++ b/pkcs1-rsa-sha1.c
@@ -61,32 +61,40 @@ sha1_prefix[] =
       /* Here comes the raw hash value */
 };
 
-void
-pkcs1_rsa_sha1_encode(mpz_t m, unsigned length, struct sha1_ctx *hash)
+int
+pkcs1_rsa_sha1_encode(mpz_t m, unsigned size, struct sha1_ctx *hash)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= SHA1_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - SHA1_DIGEST_SIZE, em,
-			 sizeof(sha1_prefix),
-			 sha1_prefix);
-  
-  sha1_digest(hash, SHA1_DIGEST_SIZE, em + length - SHA1_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(sha1_prefix),
+			     sha1_prefix,
+			     SHA1_DIGEST_SIZE))
+    {
+      sha1_digest(hash, SHA1_DIGEST_SIZE, em + size - SHA1_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
 
-void
-pkcs1_rsa_sha1_encode_digest(mpz_t m, unsigned length, const uint8_t *digest)
+int
+pkcs1_rsa_sha1_encode_digest(mpz_t m, unsigned size, const uint8_t *digest)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= SHA1_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - SHA1_DIGEST_SIZE, em,
-			 sizeof(sha1_prefix),
-			 sha1_prefix);
-
-  memcpy(em + length - SHA1_DIGEST_SIZE, digest, SHA1_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(sha1_prefix),
+			     sha1_prefix,
+			     SHA1_DIGEST_SIZE))
+    {
+      memcpy(em + size - SHA1_DIGEST_SIZE, digest, SHA1_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
diff --git a/pkcs1-rsa-sha256.c b/pkcs1-rsa-sha256.c
index 82c169a5..363f7847 100644
--- a/pkcs1-rsa-sha256.c
+++ b/pkcs1-rsa-sha256.c
@@ -59,32 +59,40 @@ sha256_prefix[] =
       /* Here comes the raw hash value */
 };
 
-void
-pkcs1_rsa_sha256_encode(mpz_t m, unsigned length, struct sha256_ctx *hash)
+int
+pkcs1_rsa_sha256_encode(mpz_t m, unsigned size, struct sha256_ctx *hash)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= SHA256_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - SHA256_DIGEST_SIZE, em,
-			 sizeof(sha256_prefix),
-			 sha256_prefix);
-  
-  sha256_digest(hash, SHA256_DIGEST_SIZE, em + length - SHA256_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(sha256_prefix),
+			     sha256_prefix,
+			     SHA256_DIGEST_SIZE))
+    {
+      sha256_digest(hash, SHA256_DIGEST_SIZE, em + size - SHA256_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;	
 }
 
-void
-pkcs1_rsa_sha256_encode_digest(mpz_t m, unsigned length, const uint8_t *digest)
+int
+pkcs1_rsa_sha256_encode_digest(mpz_t m, unsigned size, const uint8_t *digest)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= SHA256_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - SHA256_DIGEST_SIZE, em,
-			 sizeof(sha256_prefix),
-			 sha256_prefix);
-
-  memcpy(em + length - SHA256_DIGEST_SIZE, digest, SHA256_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(sha256_prefix),
+			     sha256_prefix,
+			     SHA256_DIGEST_SIZE))
+    {
+      memcpy(em + size - SHA256_DIGEST_SIZE, digest, SHA256_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
diff --git a/pkcs1-rsa-sha512.c b/pkcs1-rsa-sha512.c
index 1e446667..8eb4377b 100644
--- a/pkcs1-rsa-sha512.c
+++ b/pkcs1-rsa-sha512.c
@@ -59,32 +59,41 @@ sha512_prefix[] =
       /* Here comes the raw hash value, 64 octets */
 };
 
-void
-pkcs1_rsa_sha512_encode(mpz_t m, unsigned length, struct sha512_ctx *hash)
+int
+pkcs1_rsa_sha512_encode(mpz_t m, unsigned size, struct sha512_ctx *hash)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= SHA512_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - SHA512_DIGEST_SIZE, em,
-			 sizeof(sha512_prefix),
-			 sha512_prefix);
-  
-  sha512_digest(hash, SHA512_DIGEST_SIZE, em + length - SHA512_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(sha512_prefix),
+			     sha512_prefix,
+			     SHA512_DIGEST_SIZE))
+    {
+      sha512_digest(hash, SHA512_DIGEST_SIZE,
+		    em + size - SHA512_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
 
-void
-pkcs1_rsa_sha512_encode_digest(mpz_t m, unsigned length, const uint8_t *digest)
+int
+pkcs1_rsa_sha512_encode_digest(mpz_t m, unsigned size, const uint8_t *digest)
 {
   TMP_DECL(em, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
-  TMP_ALLOC(em, length);
+  TMP_ALLOC(em, size);
 
-  assert(length >= SHA512_DIGEST_SIZE);
-  pkcs1_signature_prefix(length - SHA512_DIGEST_SIZE, em,
-			 sizeof(sha512_prefix),
-			 sha512_prefix);
-
-  memcpy(em + length - SHA512_DIGEST_SIZE, digest, SHA512_DIGEST_SIZE);
-  nettle_mpz_set_str_256_u(m, length, em);
+  if (pkcs1_signature_prefix(size, em,
+			     sizeof(sha512_prefix),
+			     sha512_prefix,
+			     SHA512_DIGEST_SIZE))
+    {
+      memcpy(em + size - SHA512_DIGEST_SIZE, digest, SHA512_DIGEST_SIZE);
+      nettle_mpz_set_str_256_u(m, size, em);
+      return 1;
+    }
+  else
+    return 0;
 }
diff --git a/pkcs1.c b/pkcs1.c
index 1a0fa9dd..786ee63c 100644
--- a/pkcs1.c
+++ b/pkcs1.c
@@ -34,24 +34,31 @@
 
 /* Formats the PKCS#1 padding, of the form
  *
- *   0x01 0xff ... 0xff 0x00 id
+ *   0x01 0xff ... 0xff 0x00 id ...digest...
  *
- * where the 0xff ... 0xff part consists of at least 8 octets.
+ * where the 0xff ... 0xff part consists of at least 8 octets. The 
+ * total size should be one less than the octet size of n.
  */
-void
-pkcs1_signature_prefix(unsigned length,
+int
+pkcs1_signature_prefix(unsigned size,
 		       uint8_t *buffer,
-		       unsigned id_length,
-		       const uint8_t *id)
+		       unsigned id_size,
+		       const uint8_t *id,
+		       unsigned digest_size)
 {
-  assert(length >= id_length);
-  length -= id_length;
-  memcpy(buffer + length, id, id_length);
+  unsigned j;
+  
+  if (size < 10 + id_size + digest_size)
+    return 0;
 
-  assert(length);
-  buffer[--length] = 0;
+  j = size - digest_size - id_size;
 
-  assert(length >= 9);
-  memset(buffer + 1, 0xff, length - 1);
+  memcpy (buffer + j, id, id_size);
   buffer[0] = 1;
+  buffer[--j] = 0;
+
+  assert(j >= 9);
+  memset(buffer + 1, 0xff, j - 1);
+
+  return 1;
 }
diff --git a/pkcs1.h b/pkcs1.h
index 575570b4..a2d00eee 100644
--- a/pkcs1.h
+++ b/pkcs1.h
@@ -49,34 +49,35 @@ struct sha1_ctx;
 struct sha256_ctx;
 struct sha512_ctx;
 
-void
-pkcs1_signature_prefix(unsigned length,
+int
+pkcs1_signature_prefix(unsigned size,
 		       uint8_t *buffer,
-		       unsigned id_length,
-		       const uint8_t *id);
+		       unsigned id_size,
+		       const uint8_t *id,
+		       unsigned digest_size);
 
-void
+int
 pkcs1_rsa_md5_encode(mpz_t m, unsigned length, struct md5_ctx *hash);
 
-void
+int
 pkcs1_rsa_md5_encode_digest(mpz_t m, unsigned length, const uint8_t *digest);
 
-void
+int
 pkcs1_rsa_sha1_encode(mpz_t m, unsigned length, struct sha1_ctx *hash);
 
-void
+int
 pkcs1_rsa_sha1_encode_digest(mpz_t m, unsigned length, const uint8_t *digest);
 
-void
+int
 pkcs1_rsa_sha256_encode(mpz_t m, unsigned length, struct sha256_ctx *hash);
 
-void
+int
 pkcs1_rsa_sha256_encode_digest(mpz_t m, unsigned length, const uint8_t *digest);
 
-void
+int
 pkcs1_rsa_sha512_encode(mpz_t m, unsigned length, struct sha512_ctx *hash);
 
-void
+int
 pkcs1_rsa_sha512_encode_digest(mpz_t m, unsigned length, const uint8_t *digest);
 
 #ifdef __cplusplus
diff --git a/rsa-compat.c b/rsa-compat.c
index 7106acea..8eef1852 100644
--- a/rsa-compat.c
+++ b/rsa-compat.c
@@ -81,14 +81,17 @@ R_SignFinal(R_SIGNATURE_CTX *ctx,
       mpz_t s;
       mpz_init(s);
 
-      rsa_md5_sign(&k, &ctx->hash, s);
-      nettle_mpz_get_str_256(k.size, signature, s);
+      if (rsa_md5_sign(&k, &ctx->hash, s))
+	{
+	  nettle_mpz_get_str_256(k.size, signature, s);
+	  *length = k.size;
 
-      mpz_clear(s);
-
-      *length = k.size;
+	  res = RE_SUCCESS;
+	}
+      else
+	res = RE_PRIVATE_KEY;
 
-      res = RE_SUCCESS;
+      mpz_clear(s);
     }
   else
     res = RE_PRIVATE_KEY;
diff --git a/rsa-md5-sign.c b/rsa-md5-sign.c
index 2d26eeba..166cba7a 100644
--- a/rsa-md5-sign.c
+++ b/rsa-md5-sign.c
@@ -34,26 +34,40 @@
 #include "bignum.h"
 #include "pkcs1.h"
 
-void
+int
 rsa_md5_sign(const struct rsa_private_key *key,
              struct md5_ctx *hash,
              mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
 
-  pkcs1_rsa_md5_encode(s, key->size - 1, hash);
-
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_md5_encode(s, key->size - 1, hash))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }
 }
 
-void
+int
 rsa_md5_sign_digest(const struct rsa_private_key *key,
 		    const uint8_t *digest,
 		    mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
-
-  pkcs1_rsa_md5_encode_digest(s, key->size - 1, digest);
+  assert(key->size > 0);
 
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_md5_encode_digest(s, key->size - 1, digest))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }  
 }
diff --git a/rsa-md5-verify.c b/rsa-md5-verify.c
index 0f232b4b..f8931c76 100644
--- a/rsa-md5-verify.c
+++ b/rsa-md5-verify.c
@@ -42,11 +42,11 @@ rsa_md5_verify(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
-  
-  pkcs1_rsa_md5_encode(m, key->size - 1, hash);
-  res = _rsa_verify(key, m, s);
+
+  res = (pkcs1_rsa_md5_encode(m, key->size - 1, hash)
+	 && _rsa_verify(key, m, s));
 
   mpz_clear(m);
 
@@ -61,12 +61,11 @@ rsa_md5_verify_digest(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
-  
+  assert(key->size > 0);
   mpz_init(m);
   
-  pkcs1_rsa_md5_encode_digest(m, key->size - 1, digest);
-  res = _rsa_verify(key, m, s);
+  res = (pkcs1_rsa_md5_encode_digest(m, key->size - 1, digest)
+	 && _rsa_verify(key, m, s));
 
   mpz_clear(m);
 
diff --git a/rsa-sha1-sign.c b/rsa-sha1-sign.c
index 90338af8..f120c7b0 100644
--- a/rsa-sha1-sign.c
+++ b/rsa-sha1-sign.c
@@ -34,26 +34,40 @@
 #include "bignum.h"
 #include "pkcs1.h"
 
-void
+int
 rsa_sha1_sign(const struct rsa_private_key *key,
               struct sha1_ctx *hash,
               mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
 
-  pkcs1_rsa_sha1_encode(s, key->size - 1, hash);
-
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_sha1_encode(s, key->size - 1, hash))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }
 }
 
-void
+int
 rsa_sha1_sign_digest(const struct rsa_private_key *key,
 		     const uint8_t *digest,
 		     mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
-
-  pkcs1_rsa_sha1_encode_digest(s, key->size - 1, digest);
+  assert(key->size > 0);
 
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_sha1_encode_digest(s, key->size - 1, digest))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }
 }
diff --git a/rsa-sha1-verify.c b/rsa-sha1-verify.c
index 2f6b57b4..71ed8484 100644
--- a/rsa-sha1-verify.c
+++ b/rsa-sha1-verify.c
@@ -42,11 +42,11 @@ rsa_sha1_verify(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
   
-  pkcs1_rsa_sha1_encode(m, key->size - 1, hash);
-  res = _rsa_verify(key, m, s);
+  res = (pkcs1_rsa_sha1_encode(m, key->size - 1, hash)
+	 && _rsa_verify(key, m, s));
   
   mpz_clear(m);
 
@@ -61,11 +61,11 @@ rsa_sha1_verify_digest(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
   
-  pkcs1_rsa_sha1_encode_digest(m, key->size - 1, digest);
-  res = _rsa_verify(key, m, s);
+  res = (pkcs1_rsa_sha1_encode_digest(m, key->size - 1, digest)
+	 && _rsa_verify(key, m, s));
   
   mpz_clear(m);
 
diff --git a/rsa-sha256-sign.c b/rsa-sha256-sign.c
index cf146061..5f3cf7c2 100644
--- a/rsa-sha256-sign.c
+++ b/rsa-sha256-sign.c
@@ -34,26 +34,40 @@
 #include "bignum.h"
 #include "pkcs1.h"
 
-void
+int
 rsa_sha256_sign(const struct rsa_private_key *key,
 		struct sha256_ctx *hash,
 		mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
 
-  pkcs1_rsa_sha256_encode(s, key->size - 1, hash);
-
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_sha256_encode(s, key->size - 1, hash))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }  
 }
 
-void
+int
 rsa_sha256_sign_digest(const struct rsa_private_key *key,
 		       const uint8_t *digest,
 		       mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
-
-  pkcs1_rsa_sha256_encode_digest(s, key->size - 1, digest);
+  assert(key->size > 0);
 
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_sha256_encode_digest(s, key->size - 1, digest))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }  
 }
diff --git a/rsa-sha256-verify.c b/rsa-sha256-verify.c
index aba5fefb..ef3f1e31 100644
--- a/rsa-sha256-verify.c
+++ b/rsa-sha256-verify.c
@@ -42,11 +42,11 @@ rsa_sha256_verify(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
-  
-  pkcs1_rsa_sha256_encode(m, key->size - 1, hash);
-  res = _rsa_verify(key, m, s);
+
+  res = (pkcs1_rsa_sha256_encode(m, key->size - 1, hash)
+	 &&_rsa_verify(key, m, s));
   
   mpz_clear(m);
 
@@ -61,11 +61,11 @@ rsa_sha256_verify_digest(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
   
-  pkcs1_rsa_sha256_encode_digest(m, key->size - 1, digest);
-  res = _rsa_verify(key, m, s);
+  res = (pkcs1_rsa_sha256_encode_digest(m, key->size - 1, digest)
+	 && _rsa_verify(key, m, s));
   
   mpz_clear(m);
 
diff --git a/rsa-sha512-sign.c b/rsa-sha512-sign.c
index 2d0981d8..fa14487d 100644
--- a/rsa-sha512-sign.c
+++ b/rsa-sha512-sign.c
@@ -34,26 +34,40 @@
 #include "bignum.h"
 #include "pkcs1.h"
 
-void
+int
 rsa_sha512_sign(const struct rsa_private_key *key,
 		struct sha512_ctx *hash,
 		mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
 
-  pkcs1_rsa_sha512_encode(s, key->size - 1, hash);
-
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_sha512_encode(s, key->size - 1, hash))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }  
 }
 
-void
+int
 rsa_sha512_sign_digest(const struct rsa_private_key *key,
 		       const uint8_t *digest,
 		       mpz_t s)
 {
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
-
-  pkcs1_rsa_sha512_encode_digest(s, key->size - 1, digest);
+  assert(key->size > 0);
 
-  rsa_compute_root(key, s, s);
+  if (pkcs1_rsa_sha512_encode_digest(s, key->size - 1, digest))
+    {
+      rsa_compute_root(key, s, s);
+      return 1;
+    }
+  else
+    {
+      mpz_set_ui(s, 0);
+      return 0;
+    }  
 }
diff --git a/rsa-sha512-verify.c b/rsa-sha512-verify.c
index 1ac24a12..869a8f51 100644
--- a/rsa-sha512-verify.c
+++ b/rsa-sha512-verify.c
@@ -42,11 +42,11 @@ rsa_sha512_verify(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
   
-  pkcs1_rsa_sha512_encode(m, key->size - 1, hash);
-  res = _rsa_verify(key, m, s);
+  res = (pkcs1_rsa_sha512_encode(m, key->size - 1, hash) 
+	 && _rsa_verify(key, m, s));
   
   mpz_clear(m);
 
@@ -61,11 +61,11 @@ rsa_sha512_verify_digest(const struct rsa_public_key *key,
   int res;
   mpz_t m;
 
-  assert(key->size >= RSA_MINIMUM_N_OCTETS);
+  assert(key->size > 0);
   mpz_init(m);
   
-  pkcs1_rsa_sha512_encode_digest(m, key->size - 1, digest);
-  res = _rsa_verify(key, m, s);
+  res = (pkcs1_rsa_sha512_encode_digest(m, key->size - 1, digest)
+	 && _rsa_verify(key, m, s));
   
   mpz_clear(m);
 
diff --git a/rsa.h b/rsa.h
index 9c29587b..2105daa5 100644
--- a/rsa.h
+++ b/rsa.h
@@ -76,15 +76,15 @@ extern "C" {
 #define _rsa_verify _nettle_rsa_verify
 #define _rsa_check_size _nettle_rsa_check_size
 
-/* For PKCS#1 to make sense, the size of the modulo, in octets, must
- * be at least 11 + the length of the DER-encoded Digest Info.
- *
- * And a DigestInfo is 34 octets for md5, 35 octets for sha1, 51
- * octets for sha256, and 83 octetss for sha512. 94 octets is 752
- * bits, and as the upper 7 bits may be zero, the smallest useful size
- * of n is 745 bits. */
-
-#define RSA_MINIMUM_N_OCTETS 94
+  /* This limit is somewhat arbitrary. Technically, the smallest
+     modulo which makes sense at all is 15 = 3*5, phi(15) = 8, size 4
+     bits. But for ridiculously small keys, not all odd e are possible
+     (e.g., for 5 bits, the only possible modulo is 3*7 = 21, phi(21)
+     = 12, and e = 3 don't work). The smallest size that makes sense
+     with pkcs#1, and which allows RSA encryption of one byte
+     messages, is 12 octets, 89 bits. */
+
+#define RSA_MINIMUM_N_OCTETS 12
 #define RSA_MINIMUM_N_BITS (8*RSA_MINIMUM_N_OCTETS - 7)
 
 struct rsa_public_key
@@ -168,7 +168,7 @@ rsa_private_key_prepare(struct rsa_private_key *key);
 
 
 /* PKCS#1 style signatures */
-void
+int
 rsa_md5_sign(const struct rsa_private_key *key,
              struct md5_ctx *hash,
              mpz_t signature);
@@ -179,7 +179,7 @@ rsa_md5_verify(const struct rsa_public_key *key,
                struct md5_ctx *hash,
 	       const mpz_t signature);
 
-void
+int
 rsa_sha1_sign(const struct rsa_private_key *key,
               struct sha1_ctx *hash,
               mpz_t signature);
@@ -189,7 +189,7 @@ rsa_sha1_verify(const struct rsa_public_key *key,
                 struct sha1_ctx *hash,
 		const mpz_t signature);
 
-void
+int
 rsa_sha256_sign(const struct rsa_private_key *key,
 		struct sha256_ctx *hash,
 		mpz_t signature);
@@ -199,7 +199,7 @@ rsa_sha256_verify(const struct rsa_public_key *key,
 		  struct sha256_ctx *hash,
 		  const mpz_t signature);
 
-void
+int
 rsa_sha512_sign(const struct rsa_private_key *key,
 		struct sha512_ctx *hash,
 		mpz_t signature);
@@ -210,7 +210,7 @@ rsa_sha512_verify(const struct rsa_public_key *key,
 		  const mpz_t signature);
 
 /* Variants taking the digest as argument. */
-void
+int
 rsa_md5_sign_digest(const struct rsa_private_key *key,
 		    const uint8_t *digest,
 		    mpz_t s);
@@ -220,7 +220,7 @@ rsa_md5_verify_digest(const struct rsa_public_key *key,
 		      const uint8_t *digest,
 		      const mpz_t signature);
 
-void
+int
 rsa_sha1_sign_digest(const struct rsa_private_key *key,
 		     const uint8_t *digest,
 		     mpz_t s);
@@ -230,7 +230,7 @@ rsa_sha1_verify_digest(const struct rsa_public_key *key,
 		       const uint8_t *digest,
 		       const mpz_t signature);
 
-void
+int
 rsa_sha256_sign_digest(const struct rsa_private_key *key,
 		       const uint8_t *digest,
 		       mpz_t s);
@@ -240,7 +240,7 @@ rsa_sha256_verify_digest(const struct rsa_public_key *key,
 			 const uint8_t *digest,
 			 const mpz_t signature);
 
-void
+int
 rsa_sha512_sign_digest(const struct rsa_private_key *key,
 		       const uint8_t *digest,
 		       mpz_t s);
diff --git a/testsuite/cxx-test.cxx b/testsuite/cxx-test.cxx
index d4cd795f..b5635fbf 100644
--- a/testsuite/cxx-test.cxx
+++ b/testsuite/cxx-test.cxx
@@ -88,7 +88,7 @@ test_main(void)
   /* Create signature */
   md5_update (&md5, 39, reinterpret_cast<const uint8_t *>
 	      ("The magic words are squeamish ossifrage"));
-  rsa_md5_sign (&key, &md5, signature);
+  ASSERT (rsa_md5_sign (&key, &md5, signature));
 
   /* Verify it */
   md5_update (&md5, 39, reinterpret_cast<const uint8_t *>
diff --git a/testsuite/pkcs1-test.c b/testsuite/pkcs1-test.c
index 58aa7b2e..283e742e 100644
--- a/testsuite/pkcs1-test.c
+++ b/testsuite/pkcs1-test.c
@@ -10,7 +10,7 @@ test_main(void)
 			   0xff, 0xff, 0xff, 0xff, 0,    'a',  'b',  'c' };
 
   pkcs1_signature_prefix(sizeof(buffer), buffer,
-			 3, "abc");
+			 3, "abc", 0);
 
   ASSERT(MEMEQ(sizeof(buffer), buffer, expected));
 
diff --git a/testsuite/testutils.c b/testsuite/testutils.c
index 4a316a60..7c9229ff 100644
--- a/testsuite/testutils.c
+++ b/testsuite/testutils.c
@@ -450,9 +450,9 @@ mpz_togglebit (mpz_t x, unsigned long int bit)
 #endif /* HAVE_LIBGMP */
 
 #if WITH_HOGWEED
-#define SIGN(key, hash, msg, signature) do {	\
-  hash##_update(&hash, LDATA(msg));		\
-  rsa_##hash##_sign(key, &hash, signature);	\
+#define SIGN(key, hash, msg, signature) do {		\
+  hash##_update(&hash, LDATA(msg));			\
+  ASSERT(rsa_##hash##_sign(key, &hash, signature));	\
 } while(0)
 
 #define VERIFY(key, hash, msg, signature) (	\