Mercurial > dropbear

comparison libtommath/bn_mp_prime_random_ex.c @ 389:5ff8218bcee9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 2af95f00ebd5bb7a28b3817db1218442c935388e) to branch 'au.asn.ucc.matt.dropbear' (head ecd779509ef23a8cdf64888904fc9b31d78aa933)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 03:14:55 +0000
parents eed26cff980b
children 60fc6476e044
comparison
equal deleted inserted replaced
388:fb54020f78e1 389:5ff8218bcee9
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 $ */