testsuite/ecc-mod-test.c

   1 #include "testutils.h"
   2
   3 #include <errno.h>
   4 #include <limits.h>
   5 #include <sys/time.h>
   6
   7 static void
   8 ref_mod (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
   9 {
  10   mpz_t r, a, m;
  11   mpz_init (r);
  12   mpz_mod (r, mpz_roinit_n (a, ap, 2*mn), mpz_roinit_n (m, mp, mn));
  13   mpz_limbs_copy (rp, r, mn);
  14
  15   mpz_clear (r);
  16 }
  17
  18 #define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
  19 #define MAX_SIZE (2*MAX_ECC_SIZE)
  20 #define COUNT 50000
  21
  22 static void
  23 test_one(const char *name,
  24          const struct ecc_modulo *m,
  25          const mpz_t r)
  26 {
  27   mp_limb_t a[MAX_SIZE];
  28   mp_limb_t t[MAX_SIZE];
  29   mp_limb_t ref[MAX_SIZE];
  30
  31   mpz_limbs_copy (a, r, 2*m->size);
  32
  33   ref_mod (ref, a, m->m, m->size);
  34
  35   mpn_copyi (t, a, 2*m->size);
  36   m->mod (m, t);
  37   if (mpn_cmp (t, m->m, m->size) >= 0)
  38     mpn_sub_n (t, t, m->m, m->size);
  39
  40   if (mpn_cmp (t, ref, m->size))
  41     {
  42       fprintf (stderr, "m->mod %s failed: bit_size = %u\n",
  43                name, m->bit_size);
  44
  45       fprintf (stderr, "a   = ");
  46       mpn_out_str (stderr, 16, a, 2*m->size);
  47       fprintf (stderr, "\nt   = ");
  48       mpn_out_str (stderr, 16, t, m->size);
  49       fprintf (stderr, " (bad)\nref = ");
  50       mpn_out_str (stderr, 16, ref, m->size);
  51       fprintf (stderr, "\n");
  52       abort ();
  53     }
  54
  55   if (m->B_size < m->size)
  56     {
  57       mpn_copyi (t, a, 2*m->size);
  58       ecc_mod (m, t);
  59       if (mpn_cmp (t, m->m, m->size) >= 0)
  60         mpn_sub_n (t, t, m->m, m->size);
  61
  62       if (mpn_cmp (t, ref, m->size))
  63         {
  64           fprintf (stderr, "ecc_mod %s failed: bit_size = %u\n",
  65                    name, m->bit_size);
  66           fprintf (stderr, "a   = ");
  67           mpn_out_str (stderr, 16, a, 2*m->size);
  68           fprintf (stderr, "\nt   = ");
  69           mpn_out_str (stderr, 16, t, m->size);
  70           fprintf (stderr, " (bad)\nref = ");
  71           mpn_out_str (stderr, 16, ref, m->size);
  72           fprintf (stderr, "\n");
  73           abort ();
  74         }
  75     }
  76 }
  77
  78 static void
  79 test_modulo (gmp_randstate_t rands, const char *name,
  80              const struct ecc_modulo *m, unsigned count)
  81 {
  82   mpz_t r;
  83   unsigned j;
  84
  85   mpz_init (r);
  86
  87   for (j = 0; j < count; j++)
  88     {
  89       if (j & 1)
  90         mpz_rrandomb (r, rands, 2*m->size * GMP_NUMB_BITS);
  91       else
  92         mpz_urandomb (r, rands, 2*m->size * GMP_NUMB_BITS);
  93
  94       test_one (name, m, r);
  95     }
  96   mpz_clear (r);
  97 }
  98
  99 static void
 100 test_fixed (void)
 101 {
 102   mpz_t r;
 103   mpz_init (r);
 104
 105   /* Triggered a bug reported by Hanno Böck. */
 106   mpz_set_str (r, "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFF001C2C00", 16);
 107   mpz_mul_2exp (r, r, 256);
 108   test_one ("p", &nettle_secp_256r1.p, r);
 109   test_one ("q", &nettle_secp_256r1.q, r);
 110
 111   mpz_set_str (r, "ffffffff00000001fffffffeffffffffffffffffffffffffffffffc0000000000007ffffffffffffffffffffffffffff00000000000000000fffffffffffffff", 16);
 112   test_one ("p", &nettle_secp_256r1.p, r);
 113   test_one ("q", &nettle_secp_256r1.q, r);
 114
 115   /* Triggered a bug reported by Hanno Böck. */
 116   mpz_set_str (r, "4c9000000000000000000000000000000000000000000000004a604db486e000000000000000000000000000000000000000121025be29575adb2c8ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 16);
 117   test_one ("p", &nettle_secp_384r1.p, r);
 118   test_one ("q", &nettle_secp_384r1.q, r);
 119
 120   /* Triggered a carry bug in development version. */
 121   mpz_set_str (r, "e64a84643150260640e4677c19ffc4faef06042132b86af6e9ee33fe1850222e57a514d5f1d6d444008bb896a96a43d5629945e57548f5e12f66be132b24110cbb2df6d7d3dd3aaadc98b0bbf29573843ad72e57f59fc5d4f56cc599da18bb99", 16);
 122
 123   test_one ("p", &nettle_secp_384r1.p, r);
 124   test_one ("q", &nettle_secp_384r1.q, r);
 125
 126   mpz_clear (r);
 127 }
 128
 129 static void
 130 test_patterns (const char *name,
 131                const struct ecc_modulo *m)
 132 {
 133   mpz_t r;
 134   unsigned j;
 135
 136   mpz_init (r);
 137
 138   for (j = m->bit_size; j < 2*m->bit_size; j++)
 139     {
 140       mpz_set_ui (r, 1);
 141       mpz_mul_2exp (r, r, j);
 142
 143       test_one (name, m, r);
 144     }
 145   mpz_clear (r);
 146 }
 147
 148 #if !NETTLE_USE_MINI_GMP
 149 static void
 150 get_random_seed(mpz_t seed)
 151 {
 152   struct timeval tv;
 153   FILE *f;
 154   f = fopen ("/dev/urandom", "rb");
 155   if (f)
 156     {
 157       uint8_t buf[8];
 158       size_t res;
 159
 160       setbuf (f, NULL);
 161       res = fread (&buf, sizeof(buf), 1, f);
 162       fclose(f);
 163       if (res == 1)
 164         {
 165           nettle_mpz_set_str_256_u (seed, sizeof(buf), buf);
 166           return;
 167         }
 168       fprintf (stderr, "Read of /dev/urandom failed: %s\n",
 169                strerror (errno));
 170     }
 171   gettimeofday(&tv, NULL);
 172   mpz_set_ui (seed, tv.tv_sec);
 173   mpz_mul_ui (seed, seed, 1000000UL);
 174   mpz_add_ui (seed, seed, tv.tv_usec);
 175 }
 176 #endif /* !NETTLE_USE_MINI_GMP */
 177
 178 void
 179 test_main (void)
 180 {
 181   const char *nettle_test_seed;
 182   gmp_randstate_t rands;
 183   unsigned count = COUNT;
 184   unsigned i;
 185
 186   gmp_randinit_default (rands);
 187
 188   test_fixed ();
 189
 190   for (i = 0; ecc_curves[i]; i++)
 191     {
 192       test_patterns ("p", &ecc_curves[i]->p);
 193       test_patterns ("q", &ecc_curves[i]->p);
 194     }
 195
 196 #if !NETTLE_USE_MINI_GMP
 197   nettle_test_seed = getenv ("NETTLE_TEST_SEED");
 198   if (nettle_test_seed && *nettle_test_seed)
 199     {
 200       mpz_t seed;
 201       mpz_init (seed);
 202       if (mpz_set_str (seed, nettle_test_seed, 0) < 0
 203           || mpz_sgn (seed) < 0)
 204         die ("Invalid NETTLE_TEST_SEED: %s\n",
 205              nettle_test_seed);
 206       if (mpz_sgn (seed) == 0)
 207         get_random_seed (seed);
 208       fprintf (stderr, "Using NETTLE_TEST_SEED=");
 209       mpz_out_str (stderr, 10, seed);
 210       fprintf (stderr, "\n");
 211
 212       gmp_randseed (rands, seed);
 213       mpz_clear (seed);
 214       count *= 20;
 215     }
 216 #endif /* !NETTLE_USE_MINI_GMP */
 217
 218   for (i = 0; ecc_curves[i]; i++)
 219     {
 220       test_modulo (rands, "p", &ecc_curves[i]->p, count);
 221       test_modulo (rands, "q", &ecc_curves[i]->q, count);
 222     }
 223   gmp_randclear (rands);
 224 }