Minor cleanup to eccdata program

3 files changed, 51 insertions, 44 deletions

diff --git a/ChangeLog b/ChangeLog
index d3a962d8..15ad3384 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2022-08-16  Niels Möller  <nisse@lysator.liu.se>
+
+	* eccdata.c (output_modulo): Output the limb size, delete return
+	value.
+	(output_curve): Update calls to output_modulo, other minor cleanup.
+
 2022-08-07  Niels Möller  <nisse@lysator.liu.se>
 
 	Based on patch from Corentin Labbe:
diff --git a/ecc-internal.h b/ecc-internal.h
index 2ea553b5..eb53a9b3 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -174,7 +174,9 @@ struct ecc_modulo
   /* B^size mod m. Expected to have at least 32 leading zeros
      (equality for secp_256r1). */
   const mp_limb_t *B;
-  /* 2^{bit_size} - m, same value as above, but shifted. */
+  /* 2^{bit_size} - m. When different from B above, for numbers of
+     interest, usually B has trailing zeros and this is B shifted
+     right. */
   const mp_limb_t *B_shifted;
   /* m +/- 1, for redc, excluding redc_size low limbs. */
   const mp_limb_t *redc_mpm1;
diff --git a/eccdata.c b/eccdata.c
index a7e7e18a..f9b2f402 100644
--- a/eccdata.c
+++ b/eccdata.c
@@ -71,6 +71,7 @@ struct ecc_curve
 
   /* Prime */
   mpz_t p;
+  /* Curve constant */
   mpz_t b;
 
   /* Curve order */
@@ -626,15 +627,15 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve)
 
 	   x^2 + y^2 = 1 + (121665/121666) x^2 y^2 (mod p).
 
-	   -x^2 + y^2 = 1 - (121665/121666) x^2 y^2, with p = 2^{255} - 19.
+	 But instead of using this curve, we use a twisted curve, following RFC 7748,
+
+	   -x^2 + y^2 = 1 - (121665/121666) x^2 y^2 (mod p)
+
+         (this is possible because -1 is a square modulo p).
 
 	 The generator is
 	   x = 0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a
            y = 0x6666666666666666666666666666666666666666666666666666666666666658
-
-	 Also birationally equivalent to the curve25519 Montgomery curve,
-
-	   y^2 = x^3 + 486662 x^2 + x (mod p)
       */
       ecc_curve_init_str (ecc, ECC_TYPE_TWISTED_EDWARDS,
 			  "7fffffffffffffffffffffffffffffff"
@@ -1151,8 +1152,8 @@ output_point (const struct ecc_curve *ecc,
   mpz_clear (t);
 }
 
-static unsigned
-output_modulo (const char *name, const mpz_t x,
+static void
+output_modulo (const char *limb_name, const char *size_name, const mpz_t x,
 	       unsigned size, unsigned bits_per_limb)
 {
   mpz_t mod;
@@ -1164,10 +1165,11 @@ output_modulo (const char *name, const mpz_t x,
   mpz_mod (mod, mod, x);
 
   bits = mpz_sizeinbase (mod, 2);
-  output_bignum (name, mod, size, bits_per_limb);
+  output_bignum (limb_name, mod, size, bits_per_limb);
+  printf ("#define %s %u\n", size_name,
+	  (bits + bits_per_limb - 1) / bits_per_limb);
   
   mpz_clear (mod);
-  return bits;
 }
 
 static void
@@ -1175,7 +1177,7 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb)
 {
   unsigned limb_size = (ecc->bit_size + bits_per_limb - 1)/bits_per_limb;
   unsigned i;
-  unsigned bits;
+  unsigned qbits;
   int redc_limbs;
   mpz_t t;
   mpz_t z;
@@ -1193,28 +1195,26 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb)
   output_bignum ("ecc_b", ecc->b, limb_size, bits_per_limb);
   output_bignum ("ecc_q", ecc->q, limb_size, bits_per_limb);
   
-  bits = output_modulo ("ecc_Bmodp", ecc->p, limb_size, bits_per_limb);
-  printf ("#define ECC_BMODP_SIZE %u\n",
-	  (bits + bits_per_limb - 1) / bits_per_limb);
-  bits = output_modulo ("ecc_Bmodq", ecc->q, limb_size, bits_per_limb);
-  printf ("#define ECC_BMODQ_SIZE %u\n",
-	  (bits + bits_per_limb - 1) / bits_per_limb);
-  bits = mpz_sizeinbase (ecc->q, 2);
-  if (bits < ecc->bit_size)
+  output_modulo ("ecc_Bmodp", "ECC_BMODP_SIZE",
+		 ecc->p, limb_size, bits_per_limb);
+  output_modulo ("ecc_Bmodq", "ECC_BMODQ_SIZE", ecc->q, limb_size, bits_per_limb);
+
+  qbits = mpz_sizeinbase (ecc->q, 2);
+  if (qbits < ecc->bit_size)
     {
       /* for curve25519, with q = 2^k + q', with a much smaller q' */
       unsigned mbits;
       unsigned shift;
 
       /* Shift to align the one bit at B */
-      shift = bits_per_limb * limb_size + 1 - bits;
+      shift = bits_per_limb * limb_size + 1 - qbits;
       
       mpz_set (t, ecc->q);
-      mpz_clrbit (t, bits-1);
+      mpz_clrbit (t, qbits-1);
       mbits = mpz_sizeinbase (t, 2);
 
       /* The shifted value must be a limb smaller than q. */
-      if (mbits + shift + bits_per_limb <= bits)
+      if (mbits + shift + bits_per_limb <= qbits)
 	{
 	  /* q of the form 2^k + q', with q' a limb smaller */
 	  mpz_mul_2exp (t, t, shift);
@@ -1232,39 +1232,38 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb)
       output_bignum ("ecc_Bmodp_shifted", t, limb_size, bits_per_limb);
 
       shift = limb_size * bits_per_limb - ecc->bit_size;
-      if (shift > 0)
-	{
-	  /* Check condition for reducing hi limbs. If s is the
-	     normalization shift and n is the bit size (so that s + n
-	     = limb_size * bite_per_limb), then we need
+      assert (shift > 0);
 
-	       (2^n - 1) + (2^s - 1) (2^n - p) < 2p
+      /* Check condition for reducing hi limbs. If s is the
+	 normalization shift and n is the bit size (so that s + n
+	 = limb_size * bite_per_limb), then we need
 
-	     or equivalently,
+	 (2^n - 1) + (2^s - 1) (2^n - p) < 2p
 
-	       2^s (2^n - p) <= p
+	 or equivalently,
 
-	     To a allow a carry limb to be added in at the same time,
-	     substitute s+1 for s.
-	  */
-	  /* FIXME: For ecdsa verify, we actually need the stricter
-	     inequality < 2 q. */
-	  mpz_mul_2exp (t, t, shift + 1);
-	  if (mpz_cmp (t, ecc->p) > 0)
-	    {
-	      fprintf (stderr, "Reduction condition failed for %u-bit curve.\n",
-		       ecc->bit_size);
-	      exit (EXIT_FAILURE);
-	    }
+	 2^s (2^n - p) <= p
+
+	 To a allow a carry limb to be added in at the same time,
+	 substitute s+1 for s.
+      */
+      /* FIXME: For ecdsa verify, we actually need the stricter
+	 inequality < 2 q. */
+      mpz_mul_2exp (t, t, shift + 1);
+      if (mpz_cmp (t, ecc->p) > 0)
+	{
+	  fprintf (stderr, "Reduction condition failed for %u-bit curve.\n",
+		   ecc->bit_size);
+	  exit (EXIT_FAILURE);
 	}
     }
   else
     printf ("#define ecc_Bmodp_shifted ecc_Bmodp\n");
 
-  if (bits < limb_size * bits_per_limb)
+  if (qbits < limb_size * bits_per_limb)
     {
       mpz_set_ui (t, 0);
-      mpz_setbit (t, bits);
+      mpz_setbit (t, qbits);
       mpz_sub (t, t, ecc->q);      
       output_bignum ("ecc_Bmodq_shifted", t, limb_size, bits_per_limb);      
     }