ecc-modinv-test.c 3.5 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1 2
#include "testutils.h"

3 4 5 6 7 8 9 10
#if NETTLE_USE_MINI_GMP
void
test_main (void)
{
  SKIP();
}
#else /* ! NETTLE_USE_MINI_GMP */

Niels Möller's avatar
Niels Möller committed
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
static int
ref_modinv (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
{
  mp_limb_t tp[4*(mn+1)];
  mp_limb_t *up = tp;
  mp_limb_t *vp = tp + mn+1;
  mp_limb_t *gp = tp + 2*(mn+1);
  mp_limb_t *sp = tp + 3*(mn+1);
  mp_size_t gn, sn;

  mpn_copyi (up, ap, mn);
  mpn_copyi (vp, mp, mn);
  gn = mpn_gcdext (gp, sp, &sn, up, mn, vp, mn);
  if (gn != 1 || gp[0] != 1)
    return 0;
  
  if (sn < 0)
    mpn_sub (sp, mp, mn, sp, -sn);
  else if (sn < mn)
    /* Zero-pad. */
    mpn_zero (sp + sn, mn - sn);

  mpn_copyi (rp, sp, mn);
  return 1;
}

#define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
#define COUNT 500

void
test_main (void)
{
43
  gmp_randstate_t rands;
Niels Möller's avatar
Niels Möller committed
44 45 46 47 48 49 50
  mp_limb_t a[MAX_ECC_SIZE];
  mp_limb_t ai[MAX_ECC_SIZE];
  mp_limb_t ref[MAX_ECC_SIZE];
  mp_limb_t scratch[ECC_MODINV_ITCH (MAX_ECC_SIZE)];
  unsigned i;
  mpz_t r;

51
  gmp_randinit_default (rands);
Niels Möller's avatar
Niels Möller committed
52 53 54 55 56 57
  mpz_init (r);
  
  for (i = 0; ecc_curves[i]; i++)
    {
      const struct ecc_curve *ecc = ecc_curves[i];
      unsigned j;
58
      /* Check behaviour for zero input */
Niels Möller's avatar
Niels Möller committed
59 60
      mpn_zero (a, ecc->p.size);
      memset (ai, 17, ecc->p.size * sizeof(*ai));
61
      ecc->p.invert (&ecc->p, ai, a, scratch);
Niels Möller's avatar
Niels Möller committed
62
      if (!mpn_zero_p (ai, ecc->p.size))
63
	{
64
	  fprintf (stderr, "ecc->p.invert failed for zero input (bit size %u):\n",
Niels Möller's avatar
Niels Möller committed
65
		       ecc->p.bit_size);
66 67
	  gmp_fprintf (stderr, "p = %Nx\n"
		       "t = %Nx (bad)\n",
Niels Möller's avatar
Niels Möller committed
68 69
		       ecc->p.m, ecc->p.size,
		       ai, ecc->p.size);
70 71 72 73
	  abort ();
	}
	  
      /* Check behaviour for a = p */
Niels Möller's avatar
Niels Möller committed
74 75
      mpn_copyi (a, ecc->p.m, ecc->p.size);
      memset (ai, 17, ecc->p.size * sizeof(*ai));
76
      ecc->p.invert (&ecc->p, ai, a, scratch);
Niels Möller's avatar
Niels Möller committed
77
      if (!mpn_zero_p (ai, ecc->p.size))
78
	{
79
	  fprintf (stderr, "ecc->p.invert failed for a = p input (bit size %u):\n",
Niels Möller's avatar
Niels Möller committed
80
		       ecc->p.bit_size);
81 82
	  gmp_fprintf (stderr, "p = %Nx\n"
		       "t = %Nx (bad)\n",
Niels Möller's avatar
Niels Möller committed
83 84
		       ecc->p.m, ecc->p.size,
		       ai, ecc->p.size);
85 86 87
	  abort ();
	}
	
Niels Möller's avatar
Niels Möller committed
88 89 90
      for (j = 0; j < COUNT; j++)
	{
	  if (j & 1)
Niels Möller's avatar
Niels Möller committed
91
	    mpz_rrandomb (r, rands, ecc->p.size * GMP_NUMB_BITS);
Niels Möller's avatar
Niels Möller committed
92
	  else
Niels Möller's avatar
Niels Möller committed
93
	    mpz_urandomb (r, rands, ecc->p.size * GMP_NUMB_BITS);
Niels Möller's avatar
Niels Möller committed
94

Niels Möller's avatar
Niels Möller committed
95
	  mpz_limbs_copy (a, r, ecc->p.size);
Niels Möller's avatar
Niels Möller committed
96

Niels Möller's avatar
Niels Möller committed
97
	  if (!ref_modinv (ref, a, ecc->p.m, ecc->p.size))
Niels Möller's avatar
Niels Möller committed
98 99 100
	    {
	      if (verbose)
		fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
Niels Möller's avatar
Niels Möller committed
101
			 j, ecc->p.bit_size);
Niels Möller's avatar
Niels Möller committed
102 103
	      continue;
	    }
104
	  ecc->p.invert (&ecc->p, ai, a, scratch);
Niels Möller's avatar
Niels Möller committed
105
	  if (mpn_cmp (ref, ai, ecc->p.size))
Niels Möller's avatar
Niels Möller committed
106
	    {
107
	      fprintf (stderr, "ecc->p.invert failed (test %u, bit size %u):\n",
Niels Möller's avatar
Niels Möller committed
108
		       j, ecc->p.bit_size);
Niels Möller's avatar
Niels Möller committed
109 110 111 112
	      gmp_fprintf (stderr, "a = %Zx\n"
			   "p = %Nx\n"
			   "t = %Nx (bad)\n"
			   "r = %Nx\n",
Niels Möller's avatar
Niels Möller committed
113 114 115
			   r, ecc->p.m, ecc->p.size,
			   ai, ecc->p.size,
			   ref, ecc->p.size);
Niels Möller's avatar
Niels Möller committed
116 117 118
	      abort ();
	    }

Niels Möller's avatar
Niels Möller committed
119
	  mpz_limbs_copy (a, r, ecc->p.size);
Niels Möller's avatar
Niels Möller committed
120

Niels Möller's avatar
Niels Möller committed
121
	  if (!ref_modinv (ref, a, ecc->q.m, ecc->p.size))
Niels Möller's avatar
Niels Möller committed
122 123
	    {
	      fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
Niels Möller's avatar
Niels Möller committed
124
		       j, ecc->q.bit_size);
Niels Möller's avatar
Niels Möller committed
125 126
	      continue;
	    }
127
	  ecc->q.invert (&ecc->q, ai, a, scratch);
Niels Möller's avatar
Niels Möller committed
128
	  if (mpn_cmp (ref, ai, ecc->p.size))
Niels Möller's avatar
Niels Möller committed
129
	    {
130
	      fprintf (stderr, "ecc->q.invert failed (test %u, bit size %u):\n",
Niels Möller's avatar
Niels Möller committed
131
		       j, ecc->q.bit_size);
Niels Möller's avatar
Niels Möller committed
132 133 134 135
	      gmp_fprintf (stderr, "a = %Zx\n"
			   "p = %Nx\n"
			   "t = %Nx (bad)\n"
			   "r = %Nx\n",
Niels Möller's avatar
Niels Möller committed
136 137 138
			   r, ecc->p.m, ecc->p.size,
			   ai, ecc->p.size,
			   ref, ecc->p.size);
Niels Möller's avatar
Niels Möller committed
139 140 141 142
	      abort ();
	    }
	}
    }
143
  gmp_randclear (rands);
Niels Möller's avatar
Niels Möller committed
144 145
  mpz_clear (r);
}
146
#endif /* ! NETTLE_USE_MINI_GMP */