← Back to branch summary

~ubuntu-branches/ubuntu/dapper/nettle/dapper

« back to all changes in this revision

Viewing changes to bignum-random.c

  • Committer: Bazaar Package Importer
  • Author(s): Marek Habersack
  • Date: 2004-05-04 15:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20040504155602-7jbhw5mabvwksl3j
Tags: upstream-1.10
Import upstream version 1.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
#if HAVE_LIBGMP
 
31
 
 
32
#include <stdlib.h>
 
33
 
 
34
#include "bignum.h"
 
35
#include "nettle-internal.h"
 
36
 
 
37
void
 
38
nettle_mpz_random_size(mpz_t x,
 
39
                       void *ctx, nettle_random_func random,
 
40
                       unsigned bits)
 
41
{
 
42
  unsigned length = (bits + 7) / 8;
 
43
  TMP_DECL(data, uint8_t, NETTLE_MAX_BIGNUM_BITS / 8);
 
44
  TMP_ALLOC(data, length);
 
45
 
 
46
  random(ctx, length, data);
 
47
 
 
48
  nettle_mpz_set_str_256_u(x, length, data);
 
49
 
 
50
  if (bits % 8)
 
51
    mpz_fdiv_r_2exp(x, x, bits);
 
52
}
 
53
 
 
54
/* Returns a random number x, 0 <= x < n */
 
55
void
 
56
nettle_mpz_random(mpz_t x,
 
57
                  void *ctx, nettle_random_func random,
 
58
                  const mpz_t n)
 
59
{
 
60
  /* FIXME: This leaves some bias, which may be bad for DSA. A better
 
61
   * way might to generate a random number of mpz_sizeinbase(n, 2)
 
62
   * bits, and loop until one smaller than n is found. */
 
63
 
 
64
  /* From Daniel Bleichenbacher (via coderpunks):
 
65
   *
 
66
   * There is still a theoretical attack possible with 8 extra bits.
 
67
   * But, the attack would need about 2^66 signatures 2^66 memory and
 
68
   * 2^66 time (if I remember that correctly). Compare that to DSA,
 
69
   * where the attack requires 2^22 signatures 2^40 memory and 2^64
 
70
   * time. And of course, the numbers above are not a real threat for
 
71
   * PGP. Using 16 extra bits (i.e. generating a 176 bit random number
 
72
   * and reducing it modulo q) will defeat even this theoretical
 
73
   * attack.
 
74
   * 
 
75
   * More generally log_2(q)/8 extra bits are enough to defeat my
 
76
   * attack. NIST also plans to update the standard.
 
77
   */
 
78
 
 
79
  /* Add a few bits extra, to decrease the bias from the final modulo
 
80
   * operation. */
 
81
 
 
82
  nettle_mpz_random_size(x, 
 
83
                         ctx, random,
 
84
                         mpz_sizeinbase(n, 2) + 16);
 
85
  
 
86
  mpz_fdiv_r(x, x, n);
 
87
}
 
88
 
 
89
#endif /* HAVE_LIBGMP */