Reorganize eddsa, based on patch by Daiki Ueno.

* eddsa-internal.h (struct ecc_eddsa): New struct for eddsa
parameters.
* ed25519-sha512.c (_nettle_ed25519_sha512): New parameter struct.
* eddsa-expand.c (_eddsa_expand_key): Replace input
struct nettle_hash with struct ecc_eddsa, and generalize for
ed448. Update all callers.
* eddsa-sign.c (_eddsa_sign): Likewise.
* eddsa-verify.c (_eddsa_verify): Likewise.
* eddsa-compress.c (_eddsa_compress): Store sign bit in most
significant bit of last byte, as specified by RFC 8032.
* eddsa-decompress.c (_eddsa_decompress): Corresponding update.
Also generalize to support ed448, and make validity checks
stricter.
* testsuite/eddsa-sign-test.c (test_ed25519_sign): New function.
(test_main): Use it.
* testsuite/eddsa-verify-test.c (test_ed25519): New function.
(test_main): Use it.

1 files changed, 36 insertions, 9 deletions

diff --git a/eddsa-decompress.c b/eddsa-decompress.c
index f114b576..441ccfbf 100644
--- a/eddsa-decompress.c
+++ b/eddsa-decompress.c
@@ -33,6 +33,8 @@
 # include "config.h"
 #endif
 
+#include <assert.h>
+
 #include "eddsa.h"
 #include "eddsa-internal.h"
 
@@ -51,6 +53,8 @@ _eddsa_decompress (const struct ecc_curve *ecc, mp_limb_t *p,
 		   mp_limb_t *scratch)
 {
   mp_limb_t sign, cy;
+  mp_size_t nlimbs;
+  size_t nbytes;
   int res;
 
 #define xp p
@@ -62,23 +66,46 @@ _eddsa_decompress (const struct ecc_curve *ecc, mp_limb_t *p,
 #define tp (scratch + 2*ecc->p.size)
 #define scratch_out (scratch + 4*ecc->p.size)
 
-  sign = cp[ecc->p.bit_size / 8] >> (ecc->p.bit_size & 7);
-  if (sign > 1)
-    return 0;
-  mpn_set_base256_le (yp, ecc->p.size, cp, 1 + ecc->p.bit_size / 8);
-  /* Clear out the sign bit (if it fits) */
-  yp[ecc->p.size - 1] &= ~(mp_limb_t) 0
-    >> (ecc->p.size * GMP_NUMB_BITS - ecc->p.bit_size);
+  nbytes = 1 + ecc->p.bit_size / 8;
+  /* By RFC 8032, sign bit is always the most significant bit of the
+     last byte. */
+  sign = cp[nbytes-1] >> 7;
+
+  /* May need an extra limb. */
+  nlimbs = (nbytes * 8 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS;
+  assert (nlimbs <= ecc->p.size + 1);
+  mpn_set_base256_le (scratch, nlimbs, cp, nbytes);
+
+  /* Clear out the sign bit */
+  scratch[nlimbs - 1] &=
+    ((mp_limb_t) 1 << ((nbytes * 8 - 1) % GMP_NUMB_BITS)) - 1;
+  mpn_copyi (yp, scratch, ecc->p.size);
+
+  /* Check range. */
+  if (nlimbs > ecc->p.size)
+    res = (scratch[nlimbs - 1] == 0);
+  else
+    res = 1;
+
+  /* For a valid input, y < p, so subtraction should underflow. */
+  res &= mpn_sub_n (scratch, scratch, ecc->p.m, ecc->p.size);
+
   ecc_modp_sqr (ecc, y2, yp);
   ecc_modp_mul (ecc, vp, y2, ecc->b);
   ecc_modp_sub (ecc, vp, vp, ecc->unit);
-  ecc_modp_sub (ecc, up, ecc->unit, y2);
-  res = ecc->p.sqrt (&ecc->p, tp, up, vp, scratch_out);
+  /* The sign is different between curve25519 and curve448.  */
+  if (ecc->p.bit_size == 255)
+    ecc_modp_sub (ecc, up, ecc->unit, y2);
+  else
+    ecc_modp_sub (ecc, up, y2, ecc->unit);
+  res &= ecc->p.sqrt (&ecc->p, tp, up, vp, scratch_out);
 
   cy = mpn_sub_n (xp, tp, ecc->p.m, ecc->p.size);
   cnd_copy (cy, xp, tp, ecc->p.size);
   sign ^= xp[0] & 1;
   mpn_sub_n (tp, ecc->p.m, xp, ecc->p.size);
   cnd_copy (sign, xp, tp, ecc->p.size);
+  /* Fails if the square root is zero but (original) sign was 1 */
+  res &= mpn_sub_n (tp, xp, ecc->p.m, ecc->p.size);
   return res;
 }