Mercurial > dropbear

comparison libtommath/bn_mp_prime_random_ex.c @ 399:a707e6148060

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge of '5fdf69ca60d1683cdd9f4c2595134bed26394834' and '6b61c50f4cf888bea302ac8fcf5dbb573b443251'
author Matt Johnston <matt@ucc.asn.au>
date Sat, 03 Feb 2007 08:20:34 +0000
parents 5ff8218bcee9
children 60fc6476e044
comparison
equal deleted inserted replaced
394:17d097fc111c 399:a707e6148060
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://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 $ */