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   mp_limb_t tp[4*(mn+1)];
   7   mp_limb_t *up = tp;
   8   mp_limb_t *vp = tp + mn+1;
   9   mp_limb_t *gp = tp + 2*(mn+1);
  10   mp_limb_t *sp = tp + 3*(mn+1);
  11   mp_size_t gn, sn;
  12
  13   mpn_copyi (up, ap, mn);
  14   mpn_copyi (vp, mp, mn);
  15   gn = mpn_gcdext (gp, sp, &sn, up, mn, vp, mn);
  16   if (gn != 1 || gp[0] != 1)
  17     return 0;
  18
  19   if (sn < 0)
  20     mpn_sub (sp, mp, mn, sp, -sn);
  21   else if (sn < mn)
  22     /* Zero-pad. */
  23     mpn_zero (sp + sn, mn - sn);
  24
  25   mpn_copyi (rp, sp, mn);
  26   return 1;
  27 }
  28
  29 #define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
  30 #define COUNT 500
  31
  32 void
  33 test_main (void)
  34 {
  35   gmp_randstate_t state;
  36   mp_limb_t a[MAX_ECC_SIZE];
  37   mp_limb_t ai[MAX_ECC_SIZE];
  38   mp_limb_t ref[MAX_ECC_SIZE];
  39   mp_limb_t scratch[ECC_MODINV_ITCH (MAX_ECC_SIZE)];
  40   unsigned i;
  41   mpz_t r;
  42
  43   gmp_randinit_default (state);
  44   mpz_init (r);
  45
  46   for (i = 0; ecc_curves[i]; i++)
  47     {
  48       const struct ecc_curve *ecc = ecc_curves[i];
  49       unsigned j;
  50       for (j = 0; j < COUNT; j++)
  51         {
  52           if (j & 1)
  53             mpz_rrandomb (r, state, ecc->size * GMP_NUMB_BITS);
  54           else
  55             mpz_urandomb (r, state, ecc->size * GMP_NUMB_BITS);
  56
  57           mpz_limbs_copy (a, r, ecc->size);
  58
  59           if (!ref_modinv (ref, a, ecc->p, ecc->size))
  60             {
  61               if (verbose)
  62                 fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
  63                          j, ecc->bit_size);
  64               continue;
  65             }
  66           ecc_modp_inv (ecc, ai, a, scratch);
  67           if (mpn_cmp (ref, ai, ecc->size))
  68             {
  69               fprintf (stderr, "ecc_modp_inv failed (test %u, bit size %u):\n",
  70                        j, ecc->bit_size);
  71               gmp_fprintf (stderr, "a = %Zx\n"
  72                            "p = %Nx\n"
  73                            "t = %Nx (bad)\n"
  74                            "r = %Nx\n",
  75                            r, ecc->p, ecc->size,
  76                            ai, ecc->size,
  77                            ref, ecc->size);
  78               abort ();
  79             }
  80
  81           mpz_limbs_copy (a, r, ecc->size);
  82
  83           if (!ref_modinv (ref, a, ecc->q, ecc->size))
  84             {
  85               fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
  86                        j, ecc->bit_size);
  87               continue;
  88             }
  89           ecc_modq_inv (ecc, ai, a, scratch);
  90           if (mpn_cmp (ref, ai, ecc->size))
  91             {
  92               fprintf (stderr, "ecc_modq_inv failed (test %u, bit size %u):\n",
  93                        j, ecc->bit_size);
  94               gmp_fprintf (stderr, "a = %Zx\n"
  95                            "p = %Nx\n"
  96                            "t = %Nx (bad)\n"
  97                            "r = %Nx\n",
  98                            r, ecc->p, ecc->size,
  99                            ai, ecc->size,
 100                            ref, ecc->size);
 101               abort ();
 102             }
 103         }
 104     }
 105   gmp_randclear (state);
 106   mpz_clear (r);
 107 }