release/src/router/dropbear/libtommath/bn_mp_prime_random_ex.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_PRIME_RANDOM_EX_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   4  *
   5  * LibTomMath is a library that provides multiple-precision
   6  * integer arithmetic as well as number theoretic functionality.
   7  *
   8  * The library was designed directly after the MPI library by
   9  * Michael Fromberger but has been written from scratch with
  10  * additional optimizations in place.
  11  *
  12  * The library is free for all purposes without any express
  13  * guarantee it works.
  14  *
  15  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
  16  */
  17
  18 /* makes a truly random prime of a given size (bits),
  19  *
  20  * Flags are as follows:
  21  *
  22  *   LTM_PRIME_BBS      - make prime congruent to 3 mod 4
  23  *   LTM_PRIME_SAFE     - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS)
  24  *   LTM_PRIME_2MSB_OFF - make the 2nd highest bit zero
  25  *   LTM_PRIME_2MSB_ON  - make the 2nd highest bit one
  26  *
  27  * You have to supply a callback which fills in a buffer with random bytes.  "dat" is a parameter you can
  28  * have passed to the callback (e.g. a state or something).  This function doesn't use "dat" itself
  29  * so it can be NULL
  30  *
  31  */
  32
  33 /* This is possibly the mother of all prime generation functions, muahahahahaha! */
  34 int mp_prime_random_ex(mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat)
  35 {
  36    unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb;
  37    int res, err, bsize, maskOR_msb_offset;
  38
  39    /* sanity check the input */
  40    if (size <= 1 || t <= 0) {
  41       return MP_VAL;
  42    }
  43
  44    /* LTM_PRIME_SAFE implies LTM_PRIME_BBS */
  45    if (flags & LTM_PRIME_SAFE) {
  46       flags |= LTM_PRIME_BBS;
  47    }
  48
  49    /* calc the byte size */
  50    bsize = (size>>3) + ((size&7)?1:0);
  51
  52    /* we need a buffer of bsize bytes */
  53    tmp = OPT_CAST(unsigned char) XMALLOC(bsize);
  54    if (tmp == NULL) {
  55       return MP_MEM;
  56    }
  57
  58    /* calc the maskAND value for the MSbyte*/
  59    maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7)));
  60
  61    /* calc the maskOR_msb */
  62    maskOR_msb        = 0;
  63    maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0;
  64    if (flags & LTM_PRIME_2MSB_ON) {
  65       maskOR_msb       |= 0x80 >> ((9 - size) & 7);
  66    }
  67
  68    /* get the maskOR_lsb */
  69    maskOR_lsb         = 1;
  70    if (flags & LTM_PRIME_BBS) {
  71       maskOR_lsb     |= 3;
  72    }
  73
  74    do {
  75       /* read the bytes */
  76       if (cb(tmp, bsize, dat) != bsize) {
  77          err = MP_VAL;
  78          goto error;
  79       }
  80
  81       /* work over the MSbyte */
  82       tmp[0]    &= maskAND;
  83       tmp[0]    |= 1 << ((size - 1) & 7);
  84
  85       /* mix in the maskORs */
  86       tmp[maskOR_msb_offset]   |= maskOR_msb;
  87       tmp[bsize-1]             |= maskOR_lsb;
  88
  89       /* read it in */
  90       if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY)     { goto error; }
  91
  92       /* is it prime? */
  93       if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY)           { goto error; }
  94       if (res == MP_NO) {
  95          continue;
  96       }
  97
  98       if (flags & LTM_PRIME_SAFE) {
  99          /* see if (a-1)/2 is prime */
 100          if ((err = mp_sub_d(a, 1, a)) != MP_OKAY)                    { goto error; }
 101          if ((err = mp_div_2(a, a)) != MP_OKAY)                       { goto error; }
 102
 103          /* is it prime? */
 104          if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY)        { goto error; }
 105       }
 106    } while (res == MP_NO);
 107
 108    if (flags & LTM_PRIME_SAFE) {
 109       /* restore a to the original value */
 110       if ((err = mp_mul_2(a, a)) != MP_OKAY)                          { goto error; }
 111       if ((err = mp_add_d(a, 1, a)) != MP_OKAY)                       { goto error; }
 112    }
 113
 114    err = MP_OKAY;
 115 error:
 116    XFREE(tmp);
 117    return err;
 118 }
 119
 120
 121 #endif
 122
 123 /* $Source: /cvs/libtom/libtommath/bn_mp_prime_random_ex.c,v $ */
 124 /* $Revision: 1.4 $ */
 125 /* $Date: 2006/03/31 14:18:44 $ */