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! */
34int 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;
115error:
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.5 $ */
125/* $Date: 2006/12/28 01:25:13 $ */
126