bignum-random.c

   1 /* bignum-random.c
   2  *
   3  * Generating big random numbers
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2002 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23  * MA 02111-1307, USA.
  24  */
  25
  26 #if HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <stdlib.h>
  31
  32 #include "bignum.h"
  33 #include "nettle-internal.h"
  34
  35 void
  36 nettle_mpz_random_size(mpz_t x,
  37                        void *ctx, nettle_random_func random,
  38                        unsigned bits)
  39 {
  40   unsigned length = (bits + 7) / 8;
  41   TMP_DECL(data, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
  42   TMP_ALLOC(data, length);
  43
  44   random(ctx, length, data);
  45
  46   nettle_mpz_set_str_256_u(x, length, data);
  47
  48   if (bits % 8)
  49     mpz_fdiv_r_2exp(x, x, bits);
  50 }
  51
  52 /* Returns a random number x, 0 <= x < n */
  53 void
  54 nettle_mpz_random(mpz_t x,
  55                   void *ctx, nettle_random_func random,
  56                   const mpz_t n)
  57 {
  58   /* NOTE: This leaves some bias, which may be bad for DSA. A better
  59    * way might be to generate a random number of mpz_sizeinbase(n, 2)
  60    * bits, and loop until one smaller than n is found. */
  61
  62   /* From Daniel Bleichenbacher (via coderpunks):
  63    *
  64    * There is still a theoretical attack possible with 8 extra bits.
  65    * But, the attack would need about 2^66 signatures 2^66 memory and
  66    * 2^66 time (if I remember that correctly). Compare that to DSA,
  67    * where the attack requires 2^22 signatures 2^40 memory and 2^64
  68    * time. And of course, the numbers above are not a real threat for
  69    * PGP. Using 16 extra bits (i.e. generating a 176 bit random number
  70    * and reducing it modulo q) will defeat even this theoretical
  71    * attack.
  72    *
  73    * More generally log_2(q)/8 extra bits are enough to defeat my
  74    * attack. NIST also plans to update the standard.
  75    */
  76
  77   /* Add a few bits extra, to decrease the bias from the final modulo
  78    * operation. */
  79
  80   nettle_mpz_random_size(x,
  81                          ctx, random,
  82                          mpz_sizeinbase(n, 2) + 16);
  83
  84   mpz_fdiv_r(x, x, n);
  85 }