release/src/router/nettle/ecc-random.c

   1 /* ecc-random.c */
   2
   3 /* nettle, low-level cryptographics library
   4  *
   5  * Copyright (C) 2013 Niels Möller
   6  *
   7  * The nettle library is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as published by
   9  * the Free Software Foundation; either version 2.1 of the License, or (at your
  10  * option) any later version.
  11  *
  12  * The nettle library is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15  * License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  20  * MA 02111-1301, USA.
  21  */
  22
  23 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  24
  25 #if HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include <assert.h>
  30
  31 #include "ecc.h"
  32 #include "ecc-internal.h"
  33 #include "nettle-internal.h"
  34
  35 static int
  36 zero_p (const struct ecc_curve *ecc,
  37         const mp_limb_t *xp)
  38 {
  39   mp_limb_t t;
  40   mp_size_t i;
  41
  42   for (i = t = 0; i < ecc->size; i++)
  43     t |= xp[i];
  44
  45   return t == 0;
  46 }
  47
  48 static int
  49 ecdsa_in_range (const struct ecc_curve *ecc,
  50                 const mp_limb_t *xp, mp_limb_t *scratch)
  51 {
  52   /* Check if 0 < x < q, with data independent timing. */
  53   return !zero_p (ecc, xp)
  54     & (mpn_sub_n (scratch, xp, ecc->q, ecc->size) != 0);
  55 }
  56
  57 void
  58 ecc_modq_random (const struct ecc_curve *ecc, mp_limb_t *xp,
  59                  void *ctx, nettle_random_func *random, mp_limb_t *scratch)
  60 {
  61   uint8_t *buf = (uint8_t *) scratch;
  62   unsigned nbytes = (ecc->bit_size + 7)/8;
  63
  64   /* The bytes ought to fit in the scratch area, unless we have very
  65      unusual limb and byte sizes. */
  66   assert (nbytes <= ecc->size * sizeof (mp_limb_t));
  67
  68   do
  69     {
  70       /* q and p are of the same bitsize. */
  71       random (ctx, nbytes, buf);
  72       buf[0] &= 0xff >> (nbytes * 8 - ecc->bit_size);
  73
  74       mpn_set_base256 (xp, ecc->size, buf, nbytes);
  75     }
  76   while (!ecdsa_in_range (ecc, xp, scratch));
  77 }
  78
  79 void
  80 ecc_scalar_random (struct ecc_scalar *x,
  81                    void *random_ctx, nettle_random_func *random)
  82 {
  83   TMP_DECL (scratch, mp_limb_t, ECC_MODQ_RANDOM_ITCH (ECC_MAX_SIZE));
  84   TMP_ALLOC (scratch, ECC_MODQ_RANDOM_ITCH (x->ecc->size));
  85
  86   ecc_modq_random (x->ecc, x->p, random_ctx, random, scratch);
  87 }
  88
  89