|
282
|
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 * |
|
386
|
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com |
|
282
|
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) { |
|
386
|
65 maskOR_msb |= 0x80 >> ((9 - size) & 7); |
|
|
66 } |
|
282
|
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 |
|
386
|
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 $ */ |
