testsuite/ecc-sqrt-test.c

   1 /* ecc-sqrt.c
   2
   3    Copyright (C) 2014 Niels Möller
   4
   5    This file is part of GNU Nettle.
   6
   7    GNU Nettle is free software: you can redistribute it and/or
   8    modify it under the terms of either:
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at your
  12        option) any later version.
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at your
  18        option) any later version.
  19
  20    or both in parallel, as here.
  21
  22    GNU Nettle is distributed in the hope that it will be useful,
  23    but WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see http://www.gnu.org/licenses/.
  30 */
  31
  32 #include "testutils.h"
  33
  34 #define COUNT 5000
  35
  36 #if NETTLE_USE_MINI_GMP
  37 /* Implements Legendre symbol only, requiring that p is an odd prime */
  38 static int
  39 mpz_ui_kronecker (mp_limb_t ul, const mpz_t p)
  40 {
  41   mpz_t t, u;
  42   int r;
  43
  44   mpz_init_set_ui (u, ul);
  45   mpz_init_set (t, p);
  46   mpz_sub_ui (t, t, 1);
  47   mpz_tdiv_q_2exp (t, t, 1);
  48   mpz_powm (t, u, t, p);
  49
  50   r = mpz_cmp_ui (t, 1);
  51   if (r < 0)
  52     r = 0;
  53   else if (r == 0)
  54     r = 1;
  55   else
  56     {
  57       mpz_sub (t, p, t);
  58       ASSERT (mpz_cmp_ui (t, 1) == 0);
  59       r = -1;
  60     }
  61   mpz_clear (t);
  62   mpz_clear (u);
  63
  64   return r;
  65 }
  66 #endif /* NETTLE_USE_MINI_GMP */
  67
  68 static void
  69 test_modulo (gmp_randstate_t rands, const struct ecc_modulo *m)
  70 {
  71   mpz_t u;
  72   mpz_t v;
  73   mpz_t p;
  74   mpz_t r;
  75   mpz_t t;
  76
  77   unsigned z, i;
  78   mp_limb_t *up;
  79   mp_limb_t *vp;
  80   mp_limb_t *rp;
  81   mp_limb_t *scratch;
  82
  83   mpz_init (u);
  84   mpz_init (v);
  85   mpz_init (t);
  86
  87   mpz_roinit_n (p, m->m, m->size);
  88
  89   up = xalloc_limbs (m->size);
  90   vp = xalloc_limbs (m->size);
  91   rp = xalloc_limbs (2*m->size);
  92   scratch = xalloc_limbs (m->sqrt_itch);
  93
  94   /* Find a non-square */
  95   for (z = 2; mpz_ui_kronecker (z, p) != -1; z++)
  96     ;
  97
  98   if (verbose)
  99     fprintf(stderr, "Non square: %d\n", z);
 100
 101   for (i = 0; i < COUNT; i++)
 102     {
 103       if (i & 1)
 104         {
 105           mpz_rrandomb (u, rands, m->bit_size);
 106           mpz_rrandomb (v, rands, m->bit_size);
 107         }
 108       else
 109         {
 110           mpz_urandomb (u, rands, m->bit_size);
 111           mpz_urandomb (v, rands, m->bit_size);
 112         }
 113       mpz_limbs_copy (up, u, m->size);
 114       mpz_limbs_copy (vp, v, m->size);
 115       if (!m->sqrt (m, rp, up, vp, scratch))
 116         {
 117           mpz_mul_ui (u, u, z);
 118           mpz_mod (u, u, p);
 119           mpz_limbs_copy (up, u, m->size);
 120           if (!m->sqrt (m, rp, up, vp, scratch))
 121             {
 122               fprintf (stderr, "m->sqrt returned failure, bit_size = %d\n"
 123                        "u = 0x",
 124                        m->bit_size);
 125               mpz_out_str (stderr, 16, u);
 126               fprintf (stderr, "\nv = 0x");
 127               mpz_out_str (stderr, 16, v);
 128               fprintf (stderr, "\n");
 129               abort ();
 130             }
 131         }
 132       /* Check that r^2 v = u */
 133       mpz_roinit_n (r, rp, m->size);
 134       mpz_mul (t, r, r);
 135       mpz_mul (t, t, v);
 136       if (!mpz_congruent_p (t, u, p))
 137         {
 138           fprintf (stderr, "m->sqrt gave incorrect result, bit_size = %d\n"
 139                    "u = 0x",
 140                    m->bit_size);
 141           mpz_out_str (stderr, 16, u);
 142           fprintf (stderr, "\nv = 0x");
 143           mpz_out_str (stderr, 16, v);
 144           fprintf (stderr, "\nr = 0x");
 145           mpz_out_str (stderr, 16, r);
 146           fprintf (stderr, "\n");
 147           abort ();
 148         }
 149     }
 150   mpz_clear (u);
 151   mpz_clear (v);
 152   mpz_clear (t);
 153   free (up);
 154   free (vp);
 155   free (rp);
 156   free (scratch);
 157 }
 158
 159 void
 160 test_main (void)
 161 {
 162   gmp_randstate_t rands;
 163   unsigned i;
 164
 165   gmp_randinit_default (rands);
 166   for (i = 0; ecc_curves[i]; i++)
 167     {
 168       if (ecc_curves[i]->p.sqrt)
 169         test_modulo (rands, &ecc_curves[i]->p);
 170     }
 171   gmp_randclear (rands);
 172 }