Line data    Source code

       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://libtom.org
      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           0 : 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           0 :    if (size <= 1 || t <= 0) {
      41           0 :       return MP_VAL;
      42             :    }
      43             : 
      44             :    /* LTM_PRIME_SAFE implies LTM_PRIME_BBS */
      45           0 :    if (flags & LTM_PRIME_SAFE) {
      46           0 :       flags |= LTM_PRIME_BBS;
      47             :    }
      48             : 
      49             :    /* calc the byte size */
      50           0 :    bsize = (size>>3) + ((size&7)?1:0);
      51             : 
      52             :    /* we need a buffer of bsize bytes */
      53           0 :    tmp = OPT_CAST(unsigned char) XMALLOC(bsize);
      54           0 :    if (tmp == NULL) {
      55           0 :       return MP_MEM;
      56             :    }
      57             : 
      58             :    /* calc the maskAND value for the MSbyte*/
      59           0 :    maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7)));
      60             : 
      61             :    /* calc the maskOR_msb */
      62           0 :    maskOR_msb        = 0;
      63           0 :    maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0;
      64           0 :    if (flags & LTM_PRIME_2MSB_ON) {
      65           0 :       maskOR_msb       |= 0x80 >> ((9 - size) & 7);
      66             :    }
      67             : 
      68             :    /* get the maskOR_lsb */
      69           0 :    maskOR_lsb         = 1;
      70           0 :    if (flags & LTM_PRIME_BBS) {
      71           0 :       maskOR_lsb     |= 3;
      72             :    }
      73             : 
      74             :    do {
      75             :       /* read the bytes */
      76           0 :       if (cb(tmp, bsize, dat) != bsize) {
      77           0 :          err = MP_VAL;
      78           0 :          goto error;
      79             :       }
      80             : 
      81             :       /* work over the MSbyte */
      82           0 :       tmp[0]    &= maskAND;
      83           0 :       tmp[0]    |= 1 << ((size - 1) & 7);
      84             : 
      85             :       /* mix in the maskORs */
      86           0 :       tmp[maskOR_msb_offset]   |= maskOR_msb;
      87           0 :       tmp[bsize-1]             |= maskOR_lsb;
      88             : 
      89             :       /* read it in */
      90           0 :       if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY)     { goto error; }
      91             : 
      92             :       /* is it prime? */
      93           0 :       if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY)           { goto error; }
      94           0 :       if (res == MP_NO) {
      95           0 :          continue;
      96             :       }
      97             : 
      98           0 :       if (flags & LTM_PRIME_SAFE) {
      99             :          /* see if (a-1)/2 is prime */
     100           0 :          if ((err = mp_sub_d(a, 1, a)) != MP_OKAY)                    { goto error; }
     101           0 :          if ((err = mp_div_2(a, a)) != MP_OKAY)                       { goto error; }
     102             : 
     103             :          /* is it prime? */
     104           0 :          if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY)        { goto error; }
     105             :       }
     106           0 :    } while (res == MP_NO);
     107             : 
     108           0 :    if (flags & LTM_PRIME_SAFE) {
     109             :       /* restore a to the original value */
     110           0 :       if ((err = mp_mul_2(a, a)) != MP_OKAY)                          { goto error; }
     111           0 :       if ((err = mp_add_d(a, 1, a)) != MP_OKAY)                       { goto error; }
     112             :    }
     113             : 
     114           0 :    err = MP_OKAY;
     115           0 : error:
     116           0 :    XFREE(tmp);
     117           0 :    return err;
     118             : }
     119             : 
     120             : 
     121             : #endif
     122             : 
     123             : /* $Source: /cvs/libtom/libtommath/bn_mp_prime_random_ex.c,v $ */
     124             : /* $Revision: 1.5 $ */
     125             : /* $Date: 2006/12/28 01:25:13 $ */