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 (at) 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 $ */ 126
