5 #define UPPER_LIMIT PRIME_SIZE
7 /* figures out if a number is prime (MR test) */
8 int is_prime(mp_int *N, int *result)
11 if ((err = mp_prime_is_prime(N, 8, result)) != MP_OKAY) {
17 static int next_prime(mp_int *N, mp_digit step)
19 long x, s, j, total_dist;
22 mp_digit dist, residues[UPPER_LIMIT];
26 /* first find the residues */
27 for (x = 0; x < (long)UPPER_LIMIT; x++) {
28 if (mp_mod_d(N, __prime_tab[x], &residues[x]) != MP_OKAY) {
34 if (mp_init_multi(&r, &n1, &a, &y, NULL) != MP_OKAY) {
40 /* while one of the residues is zero keep looping */
42 for (x = 0; (dist < (MP_DIGIT_MAX-step-1)) && (x < (long)UPPER_LIMIT); x++) {
43 j = (long)residues[x] + (long)dist + total_dist;
44 if (j % (long)__prime_tab[x] == 0) {
49 /* recalc the total distance from where we started */
53 if (mp_add_d(N, dist, N) != MP_OKAY) { goto error; }
56 if (mp_sub_d(N, 1, &n1) != MP_OKAY) { goto error; }
59 if (mp_copy(&n1, &r) != MP_OKAY) { goto error; }
61 /* find s such that N-1 = (2^s)r */
63 while (mp_iseven(&r)) {
65 if (mp_div_2(&r, &r) != MP_OKAY) {
69 for (x = 0; x < 8; x++) {
71 mp_set(&a, __prime_tab[x]);
73 /* compute y = a^r mod n */
74 if (mp_exptmod(&a, &r, N, &y) != MP_OKAY) { goto error; }
76 /* (y != 1) AND (y != N-1) */
77 if ((mp_cmp_d(&y, 1) != 0) && (mp_cmp(&y, &n1) != 0)) {
78 /* while j <= s-1 and y != n-1 */
79 for (j = 1; (j <= (s-1)) && (mp_cmp(&y, &n1) != 0); j++) {
81 if (mp_sqrmod(&y, N, &y) != MP_OKAY) { goto error; }
83 /* if y == 1 return false */
84 if (mp_cmp_d(&y, 1) == 0) { goto loop; }
87 /* if y != n-1 return false */
88 if (mp_cmp(&y, &n1) != 0) { goto loop; }
97 mp_clear_multi(&a, &y, &n1, &r, NULL);
100 zeromem(residues, sizeof(residues));
105 int rand_prime(mp_int *N, long len, prng_state *prng, int wprng)
107 unsigned char buf[260];
108 int err, step, ormask;
112 /* pass a negative size if you want a prime congruent to 3 mod 4 */
122 /* allow sizes between 2 and 256 bytes for a prime size */
123 if (len < 2 || len > 256) {
124 return CRYPT_INVALID_PRIME_SIZE;
128 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
133 if (prng_descriptor[wprng].read(buf+2, (unsigned long)len, prng) != (unsigned long)len) {
134 return CRYPT_ERROR_READPRNG;
137 /* set sign byte to zero */
138 buf[0] = (unsigned char)0;
140 /* Set the top byte to 0x01 which makes the number a len*8 bit number */
141 buf[1] = (unsigned char)0x01;
143 /* set the LSB to the desired settings
144 * (1 for any prime, 3 for primes congruent to 3 mod 4)
146 buf[len+1] |= (unsigned char)ormask;
148 /* read the number in */
149 if (mp_read_raw(N, buf, 2+len) != MP_OKAY) {
153 /* add the step size to it while N is not prime */
154 if ((err = next_prime(N, step)) != CRYPT_OK) {
159 zeromem(buf, sizeof(buf));