Mercurial > dropbear

comparison bn_mp_prime_random_ex.c @ 1:22d5cf7d4b1a libtommath

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