testsuite/ecc-modinv-test.c

   1 #include "testutils.h"
   2
   3 static int
   4 ref_modinv (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
   5 {
   6   mpz_t g, s, a, m;
   7   int res;
   8
   9   mpz_init (g);
  10   mpz_init (s);
  11   mpz_roinit_n (a, ap, mn);
  12   mpz_roinit_n (m, mp, mn);
  13
  14   mpz_gcdext (g, s, NULL, a, m);
  15   if (mpz_cmp_ui (g, 1) == 0)
  16     {
  17       if (mpz_sgn (s) < 0)
  18         {
  19           mpz_add (s, s, m);
  20           ASSERT (mpz_sgn (s) > 0);
  21         }
  22       mpz_limbs_copy (rp, s, mn);
  23       res = 1;
  24     }
  25   else
  26     res = 0;
  27
  28   mpz_clear (g);
  29   mpz_clear (s);
  30   return res;
  31 }
  32
  33 static int
  34 zero_p (const struct ecc_modulo *m, const mp_limb_t *xp)
  35 {
  36   return mpn_zero_p (xp, m->size)
  37     || mpn_cmp (xp, m->m, m->size) == 0;
  38 }
  39
  40 #define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
  41 #define COUNT 500
  42
  43 static void
  44 test_modulo (gmp_randstate_t rands, const char *name,
  45              const struct ecc_modulo *m)
  46 {
  47   mp_limb_t *a;
  48   mp_limb_t *ai;
  49   mp_limb_t *ref;
  50   mp_limb_t *scratch;
  51   unsigned j;
  52   mpz_t r;
  53
  54   mpz_init (r);
  55
  56   a = xalloc_limbs (m->size);
  57   ai = xalloc_limbs (2*m->size);
  58   ref = xalloc_limbs (m->size);;
  59   scratch = xalloc_limbs (m->invert_itch);
  60
  61   /* Check behaviour for zero input */
  62   mpn_zero (a, m->size);
  63   memset (ai, 17, m->size * sizeof(*ai));
  64   m->invert (m, ai, a, scratch);
  65   if (!zero_p (m, ai))
  66     {
  67       fprintf (stderr, "%s->invert failed for zero input (bit size %u):\n",
  68                name, m->bit_size);
  69       fprintf (stderr, "p = ");
  70       mpn_out_str (stderr, 16, m->m, m->size);
  71       fprintf (stderr, "\nt = ");
  72       mpn_out_str (stderr, 16, ai, m->size);
  73       fprintf (stderr, " (bad)\n");
  74       abort ();
  75     }
  76
  77   /* Check behaviour for a = m */
  78   memset (ai, 17, m->size * sizeof(*ai));
  79   m->invert (m, ai, m->m, scratch);
  80   if (!zero_p (m, ai))
  81     {
  82       fprintf (stderr, "%s->invert failed for a = p input (bit size %u):\n",
  83                name, m->bit_size);
  84
  85       fprintf (stderr, "p = ");
  86       mpn_out_str (stderr, 16, m->m, m->size);
  87       fprintf (stderr, "\nt = ");
  88       mpn_out_str (stderr, 16, ai, m->size);
  89       fprintf (stderr, " (bad)\n");
  90       abort ();
  91     }
  92
  93   for (j = 0; j < COUNT; j++)
  94     {
  95       if (j & 1)
  96         mpz_rrandomb (r, rands, m->size * GMP_NUMB_BITS);
  97       else
  98         mpz_urandomb (r, rands, m->size * GMP_NUMB_BITS);
  99
 100       mpz_limbs_copy (a, r, m->size);
 101
 102       if (!ref_modinv (ref, a, m->m, m->size))
 103         {
 104           if (verbose)
 105             fprintf (stderr, "Test %u (bit size %u) not invertible mod %s.\n",
 106                      j, m->bit_size, name);
 107           continue;
 108         }
 109       m->invert (m, ai, a, scratch);
 110       if (mpn_cmp (ref, ai, m->size))
 111         {
 112           fprintf (stderr, "%s->invert failed (test %u, bit size %u):\n",
 113                    name, j, m->bit_size);
 114           fprintf (stderr, "a = ");
 115           mpz_out_str (stderr, 16, r);
 116           fprintf (stderr, "\np = ");
 117           mpn_out_str (stderr, 16, m->m, m->size);
 118           fprintf (stderr, "\nt = ");
 119           mpn_out_str (stderr, 16, ai, m->size);
 120           fprintf (stderr, " (bad)\nr = ");
 121           mpn_out_str (stderr, 16, ref, m->size);
 122
 123           abort ();
 124         }
 125
 126     }
 127   mpz_clear (r);
 128   free (a);
 129   free (ai);
 130   free (ref);
 131   free (scratch);
 132 }
 133
 134 void
 135 test_main (void)
 136 {
 137   gmp_randstate_t rands;
 138   unsigned i;
 139
 140   gmp_randinit_default (rands);
 141
 142   for (i = 0; ecc_curves[i]; i++)
 143     {
 144       test_modulo (rands, "p", &ecc_curves[i]->p);
 145       test_modulo (rands, "q", &ecc_curves[i]->q);
 146     }
 147   gmp_randclear (rands);
 148 }