| 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, [email protected], 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 |
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.5 $ */ |
| 125 |
/* $Date: 2006/12/28 01:25:13 $ */ |