ecc-modinv-test.c 2.41 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
2
3
4
5
6
7
8
9
10
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "testutils.h"

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)
{
  gmp_randstate_t state;
  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;

  gmp_randinit_default (state);
  mpz_init (r);
  
  for (i = 0; ecc_curves[i]; i++)
    {
      const struct ecc_curve *ecc = ecc_curves[i];
      unsigned j;
      for (j = 0; j < COUNT; j++)
	{
	  if (j & 1)
	    mpz_rrandomb (r, state, ecc->size * GMP_NUMB_BITS);
	  else
	    mpz_urandomb (r, state, ecc->size * GMP_NUMB_BITS);

57
	  mpz_limbs_copy (a, r, ecc->size);
Niels Möller's avatar
Niels Möller committed
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

	  if (!ref_modinv (ref, a, ecc->p, ecc->size))
	    {
	      if (verbose)
		fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
			 j, ecc->bit_size);
	      continue;
	    }
	  ecc_modp_inv (ecc, ai, a, scratch);
	  if (mpn_cmp (ref, ai, ecc->size))
	    {
	      fprintf (stderr, "ecc_modp_inv failed (test %u, bit size %u):\n",
		       j, ecc->bit_size);
	      gmp_fprintf (stderr, "a = %Zx\n"
			   "p = %Nx\n"
			   "t = %Nx (bad)\n"
			   "r = %Nx\n",
			   r, ecc->p, ecc->size,
			   ai, ecc->size,
			   ref, ecc->size);
	      abort ();
	    }

81
	  mpz_limbs_copy (a, r, ecc->size);
Niels Möller's avatar
Niels Möller committed
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

	  if (!ref_modinv (ref, a, ecc->q, ecc->size))
	    {
	      fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
		       j, ecc->bit_size);
	      continue;
	    }
	  ecc_modq_inv (ecc, ai, a, scratch);
	  if (mpn_cmp (ref, ai, ecc->size))
	    {
	      fprintf (stderr, "ecc_modq_inv failed (test %u, bit size %u):\n",
		       j, ecc->bit_size);
	      gmp_fprintf (stderr, "a = %Zx\n"
			   "p = %Nx\n"
			   "t = %Nx (bad)\n"
			   "r = %Nx\n",
			   r, ecc->p, ecc->size,
			   ai, ecc->size,
			   ref, ecc->size);
	      abort ();
	    }
	}
    }
  gmp_randclear (state);
  mpz_clear (r);
}