1 /* $NetBSD: bn_mp_prime_random_ex.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */
2
3 #include <tommath.h>
4 #ifdef BN_MP_PRIME_RANDOM_EX_C
5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6 *
7 * LibTomMath is a library that provides multiple-precision
8 * integer arithmetic as well as number theoretic functionality.
9 *
10 * The library was designed directly after the MPI library by
11 * Michael Fromberger but has been written from scratch with
12 * additional optimizations in place.
13 *
14 * The library is free for all purposes without any express
15 * guarantee it works.
16 *
17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
18 */
19
20 /* makes a truly random prime of a given size (bits),
21 *
22 * Flags are as follows:
23 *
24 * LTM_PRIME_BBS - make prime congruent to 3 mod 4
25 * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS)
26 * LTM_PRIME_2MSB_OFF - make the 2nd highest bit zero
27 * LTM_PRIME_2MSB_ON - make the 2nd highest bit one
28 *
29 * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can
30 * have passed to the callback (e.g. a state or something). This function doesn't use "dat" itself
31 * so it can be NULL
32 *
33 */
34
35 /* This is possibly the mother of all prime generation functions, muahahahahaha! */
mp_prime_random_ex(mp_int * a,int t,int size,int flags,ltm_prime_callback cb,void * dat)36 int mp_prime_random_ex(mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat)
37 {
38 unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb;
39 int res, err, bsize, maskOR_msb_offset;
40
41 /* sanity check the input */
42 if (size <= 1 || t <= 0) {
43 return MP_VAL;
44 }
45
46 /* LTM_PRIME_SAFE implies LTM_PRIME_BBS */
47 if (flags & LTM_PRIME_SAFE) {
48 flags |= LTM_PRIME_BBS;
49 }
50
51 /* calc the byte size */
52 bsize = (size>>3) + ((size&7)?1:0);
53
54 /* we need a buffer of bsize bytes */
55 tmp = OPT_CAST(unsigned char) XMALLOC(bsize);
56 if (tmp == NULL) {
57 return MP_MEM;
58 }
59
60 /* calc the maskAND value for the MSbyte*/
61 maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7)));
62
63 /* calc the maskOR_msb */
64 maskOR_msb = 0;
65 maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0;
66 if (flags & LTM_PRIME_2MSB_ON) {
67 maskOR_msb |= 0x80 >> ((9 - size) & 7);
68 }
69
70 /* get the maskOR_lsb */
71 maskOR_lsb = 1;
72 if (flags & LTM_PRIME_BBS) {
73 maskOR_lsb |= 3;
74 }
75
76 do {
77 /* read the bytes */
78 if (cb(tmp, bsize, dat) != bsize) {
79 err = MP_VAL;
80 goto error;
81 }
82
83 /* work over the MSbyte */
84 tmp[0] &= maskAND;
85 tmp[0] |= 1 << ((size - 1) & 7);
86
87 /* mix in the maskORs */
88 tmp[maskOR_msb_offset] |= maskOR_msb;
89 tmp[bsize-1] |= maskOR_lsb;
90
91 /* read it in */
92 if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) { goto error; }
93
94 /* is it prime? */
95 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; }
96 if (res == MP_NO) {
97 continue;
98 }
99
100 if (flags & LTM_PRIME_SAFE) {
101 /* see if (a-1)/2 is prime */
102 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { goto error; }
103 if ((err = mp_div_2(a, a)) != MP_OKAY) { goto error; }
104
105 /* is it prime? */
106 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; }
107 }
108 } while (res == MP_NO);
109
110 if (flags & LTM_PRIME_SAFE) {
111 /* restore a to the original value */
112 if ((err = mp_mul_2(a, a)) != MP_OKAY) { goto error; }
113 if ((err = mp_add_d(a, 1, a)) != MP_OKAY) { goto error; }
114 }
115
116 err = MP_OKAY;
117 error:
118 XFREE(tmp);
119 return err;
120 }
121
122
123 #endif
124
125 /* Source: /cvs/libtom/libtommath/bn_mp_prime_random_ex.c,v */
126 /* Revision: 1.5 */
127 /* Date: 2006/12/28 01:25:13 */
128