2
0

bn_prime.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617
  1. /*
  2. * Copyright 1995-2021 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include <stdio.h>
  10. #include <time.h>
  11. #include "internal/cryptlib.h"
  12. #include "bn_local.h"
  13. /*
  14. * The quick sieve algorithm approach to weeding out primes is Philip
  15. * Zimmermann's, as implemented in PGP. I have had a read of his comments
  16. * and implemented my own version.
  17. */
  18. #include "bn_prime.h"
  19. static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods,
  20. BN_CTX *ctx);
  21. static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
  22. const BIGNUM *add, const BIGNUM *rem,
  23. BN_CTX *ctx);
  24. static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
  25. int do_trial_division, BN_GENCB *cb);
  26. #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x))
  27. #if BN_BITS2 == 64
  28. # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
  29. #else
  30. # define BN_DEF(lo, hi) lo, hi
  31. #endif
  32. /*
  33. * See SP800 89 5.3.3 (Step f)
  34. * The product of the set of primes ranging from 3 to 751
  35. * Generated using process in test/bn_internal_test.c test_bn_small_factors().
  36. * This includes 751 (which is not currently included in SP 800-89).
  37. */
  38. static const BN_ULONG small_prime_factors[] = {
  39. BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6),
  40. BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3),
  41. BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817),
  42. BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2),
  43. BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3),
  44. BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28),
  45. BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112),
  46. BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460),
  47. (BN_ULONG)0x000017b1
  48. };
  49. #define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors)
  50. static const BIGNUM _bignum_small_prime_factors = {
  51. (BN_ULONG *)small_prime_factors,
  52. BN_SMALL_PRIME_FACTORS_TOP,
  53. BN_SMALL_PRIME_FACTORS_TOP,
  54. 0,
  55. BN_FLG_STATIC_DATA
  56. };
  57. const BIGNUM *ossl_bn_get0_small_factors(void)
  58. {
  59. return &_bignum_small_prime_factors;
  60. }
  61. /*
  62. * Calculate the number of trial divisions that gives the best speed in
  63. * combination with Miller-Rabin prime test, based on the sized of the prime.
  64. */
  65. static int calc_trial_divisions(int bits)
  66. {
  67. if (bits <= 512)
  68. return 64;
  69. else if (bits <= 1024)
  70. return 128;
  71. else if (bits <= 2048)
  72. return 384;
  73. else if (bits <= 4096)
  74. return 1024;
  75. return NUMPRIMES;
  76. }
  77. /*
  78. * Use a minimum of 64 rounds of Miller-Rabin, which should give a false
  79. * positive rate of 2^-128. If the size of the prime is larger than 2048
  80. * the user probably wants a higher security level than 128, so switch
  81. * to 128 rounds giving a false positive rate of 2^-256.
  82. * Returns the number of rounds.
  83. */
  84. static int bn_mr_min_checks(int bits)
  85. {
  86. if (bits > 2048)
  87. return 128;
  88. return 64;
  89. }
  90. int BN_GENCB_call(BN_GENCB *cb, int a, int b)
  91. {
  92. /* No callback means continue */
  93. if (!cb)
  94. return 1;
  95. switch (cb->ver) {
  96. case 1:
  97. /* Deprecated-style callbacks */
  98. if (!cb->cb.cb_1)
  99. return 1;
  100. cb->cb.cb_1(a, b, cb->arg);
  101. return 1;
  102. case 2:
  103. /* New-style callbacks */
  104. return cb->cb.cb_2(a, b, cb);
  105. default:
  106. break;
  107. }
  108. /* Unrecognised callback type */
  109. return 0;
  110. }
  111. int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe,
  112. const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb,
  113. BN_CTX *ctx)
  114. {
  115. BIGNUM *t;
  116. int found = 0;
  117. int i, j, c1 = 0;
  118. prime_t *mods = NULL;
  119. int checks = bn_mr_min_checks(bits);
  120. if (bits < 2) {
  121. /* There are no prime numbers this small. */
  122. ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL);
  123. return 0;
  124. } else if (add == NULL && safe && bits < 6 && bits != 3) {
  125. /*
  126. * The smallest safe prime (7) is three bits.
  127. * But the following two safe primes with less than 6 bits (11, 23)
  128. * are unreachable for BN_rand with BN_RAND_TOP_TWO.
  129. */
  130. ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL);
  131. return 0;
  132. }
  133. mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
  134. if (mods == NULL)
  135. return 0;
  136. BN_CTX_start(ctx);
  137. t = BN_CTX_get(ctx);
  138. if (t == NULL)
  139. goto err;
  140. loop:
  141. /* make a random number and set the top and bottom bits */
  142. if (add == NULL) {
  143. if (!probable_prime(ret, bits, safe, mods, ctx))
  144. goto err;
  145. } else {
  146. if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx))
  147. goto err;
  148. }
  149. if (!BN_GENCB_call(cb, 0, c1++))
  150. /* aborted */
  151. goto err;
  152. if (!safe) {
  153. i = bn_is_prime_int(ret, checks, ctx, 0, cb);
  154. if (i == -1)
  155. goto err;
  156. if (i == 0)
  157. goto loop;
  158. } else {
  159. /*
  160. * for "safe prime" generation, check that (p-1)/2 is prime. Since a
  161. * prime is odd, We just need to divide by 2
  162. */
  163. if (!BN_rshift1(t, ret))
  164. goto err;
  165. for (i = 0; i < checks; i++) {
  166. j = bn_is_prime_int(ret, 1, ctx, 0, cb);
  167. if (j == -1)
  168. goto err;
  169. if (j == 0)
  170. goto loop;
  171. j = bn_is_prime_int(t, 1, ctx, 0, cb);
  172. if (j == -1)
  173. goto err;
  174. if (j == 0)
  175. goto loop;
  176. if (!BN_GENCB_call(cb, 2, c1 - 1))
  177. goto err;
  178. /* We have a safe prime test pass */
  179. }
  180. }
  181. /* we have a prime :-) */
  182. found = 1;
  183. err:
  184. OPENSSL_free(mods);
  185. BN_CTX_end(ctx);
  186. bn_check_top(ret);
  187. return found;
  188. }
  189. #ifndef FIPS_MODULE
  190. int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
  191. const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
  192. {
  193. BN_CTX *ctx = BN_CTX_new();
  194. int retval;
  195. if (ctx == NULL)
  196. return 0;
  197. retval = BN_generate_prime_ex2(ret, bits, safe, add, rem, cb, ctx);
  198. BN_CTX_free(ctx);
  199. return retval;
  200. }
  201. #endif
  202. #ifndef OPENSSL_NO_DEPRECATED_3_0
  203. int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
  204. BN_GENCB *cb)
  205. {
  206. return ossl_bn_check_prime(a, checks, ctx_passed, 0, cb);
  207. }
  208. int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx,
  209. int do_trial_division, BN_GENCB *cb)
  210. {
  211. return ossl_bn_check_prime(w, checks, ctx, do_trial_division, cb);
  212. }
  213. #endif
  214. /* Wrapper around bn_is_prime_int that sets the minimum number of checks */
  215. int ossl_bn_check_prime(const BIGNUM *w, int checks, BN_CTX *ctx,
  216. int do_trial_division, BN_GENCB *cb)
  217. {
  218. int min_checks = bn_mr_min_checks(BN_num_bits(w));
  219. if (checks < min_checks)
  220. checks = min_checks;
  221. return bn_is_prime_int(w, checks, ctx, do_trial_division, cb);
  222. }
  223. /*
  224. * Use this only for key generation.
  225. * It always uses trial division. The number of checks
  226. * (MR rounds) passed in is used without being clamped to a minimum value.
  227. */
  228. int ossl_bn_check_generated_prime(const BIGNUM *w, int checks, BN_CTX *ctx,
  229. BN_GENCB *cb)
  230. {
  231. return bn_is_prime_int(w, checks, ctx, 1, cb);
  232. }
  233. int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb)
  234. {
  235. return ossl_bn_check_prime(p, 0, ctx, 1, cb);
  236. }
  237. /*
  238. * Tests that |w| is probably prime
  239. * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test.
  240. *
  241. * Returns 0 when composite, 1 when probable prime, -1 on error.
  242. */
  243. static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
  244. int do_trial_division, BN_GENCB *cb)
  245. {
  246. int i, status, ret = -1;
  247. #ifndef FIPS_MODULE
  248. BN_CTX *ctxlocal = NULL;
  249. #else
  250. if (ctx == NULL)
  251. return -1;
  252. #endif
  253. /* w must be bigger than 1 */
  254. if (BN_cmp(w, BN_value_one()) <= 0)
  255. return 0;
  256. /* w must be odd */
  257. if (BN_is_odd(w)) {
  258. /* Take care of the really small prime 3 */
  259. if (BN_is_word(w, 3))
  260. return 1;
  261. } else {
  262. /* 2 is the only even prime */
  263. return BN_is_word(w, 2);
  264. }
  265. /* first look for small factors */
  266. if (do_trial_division) {
  267. int trial_divisions = calc_trial_divisions(BN_num_bits(w));
  268. for (i = 1; i < trial_divisions; i++) {
  269. BN_ULONG mod = BN_mod_word(w, primes[i]);
  270. if (mod == (BN_ULONG)-1)
  271. return -1;
  272. if (mod == 0)
  273. return BN_is_word(w, primes[i]);
  274. }
  275. if (!BN_GENCB_call(cb, 1, -1))
  276. return -1;
  277. }
  278. #ifndef FIPS_MODULE
  279. if (ctx == NULL && (ctxlocal = ctx = BN_CTX_new()) == NULL)
  280. goto err;
  281. #endif
  282. if (!ossl_bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status)) {
  283. ret = -1;
  284. goto err;
  285. }
  286. ret = (status == BN_PRIMETEST_PROBABLY_PRIME);
  287. err:
  288. #ifndef FIPS_MODULE
  289. BN_CTX_free(ctxlocal);
  290. #endif
  291. return ret;
  292. }
  293. /*
  294. * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.
  295. * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero).
  296. * The Step numbers listed in the code refer to the enhanced case.
  297. *
  298. * if enhanced is set, then status returns one of the following:
  299. * BN_PRIMETEST_PROBABLY_PRIME
  300. * BN_PRIMETEST_COMPOSITE_WITH_FACTOR
  301. * BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
  302. * if enhanced is zero, then status returns either
  303. * BN_PRIMETEST_PROBABLY_PRIME or
  304. * BN_PRIMETEST_COMPOSITE
  305. *
  306. * returns 0 if there was an error, otherwise it returns 1.
  307. */
  308. int ossl_bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
  309. BN_GENCB *cb, int enhanced, int *status)
  310. {
  311. int i, j, a, ret = 0;
  312. BIGNUM *g, *w1, *w3, *x, *m, *z, *b;
  313. BN_MONT_CTX *mont = NULL;
  314. /* w must be odd */
  315. if (!BN_is_odd(w))
  316. return 0;
  317. BN_CTX_start(ctx);
  318. g = BN_CTX_get(ctx);
  319. w1 = BN_CTX_get(ctx);
  320. w3 = BN_CTX_get(ctx);
  321. x = BN_CTX_get(ctx);
  322. m = BN_CTX_get(ctx);
  323. z = BN_CTX_get(ctx);
  324. b = BN_CTX_get(ctx);
  325. if (!(b != NULL
  326. /* w1 := w - 1 */
  327. && BN_copy(w1, w)
  328. && BN_sub_word(w1, 1)
  329. /* w3 := w - 3 */
  330. && BN_copy(w3, w)
  331. && BN_sub_word(w3, 3)))
  332. goto err;
  333. /* check w is larger than 3, otherwise the random b will be too small */
  334. if (BN_is_zero(w3) || BN_is_negative(w3))
  335. goto err;
  336. /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */
  337. a = 1;
  338. while (!BN_is_bit_set(w1, a))
  339. a++;
  340. /* (Step 2) m = (w-1) / 2^a */
  341. if (!BN_rshift(m, w1, a))
  342. goto err;
  343. /* Montgomery setup for computations mod a */
  344. mont = BN_MONT_CTX_new();
  345. if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
  346. goto err;
  347. if (iterations == 0)
  348. iterations = bn_mr_min_checks(BN_num_bits(w));
  349. /* (Step 4) */
  350. for (i = 0; i < iterations; ++i) {
  351. /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */
  352. if (!BN_priv_rand_range_ex(b, w3, 0, ctx)
  353. || !BN_add_word(b, 2)) /* 1 < b < w-1 */
  354. goto err;
  355. if (enhanced) {
  356. /* (Step 4.3) */
  357. if (!BN_gcd(g, b, w, ctx))
  358. goto err;
  359. /* (Step 4.4) */
  360. if (!BN_is_one(g)) {
  361. *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
  362. ret = 1;
  363. goto err;
  364. }
  365. }
  366. /* (Step 4.5) z = b^m mod w */
  367. if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))
  368. goto err;
  369. /* (Step 4.6) if (z = 1 or z = w-1) */
  370. if (BN_is_one(z) || BN_cmp(z, w1) == 0)
  371. goto outer_loop;
  372. /* (Step 4.7) for j = 1 to a-1 */
  373. for (j = 1; j < a ; ++j) {
  374. /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */
  375. if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
  376. goto err;
  377. /* (Step 4.7.3) */
  378. if (BN_cmp(z, w1) == 0)
  379. goto outer_loop;
  380. /* (Step 4.7.4) */
  381. if (BN_is_one(z))
  382. goto composite;
  383. }
  384. /* At this point z = b^((w-1)/2) mod w */
  385. /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */
  386. if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
  387. goto err;
  388. /* (Step 4.10) */
  389. if (BN_is_one(z))
  390. goto composite;
  391. /* (Step 4.11) x = b^(w-1) mod w */
  392. if (!BN_copy(x, z))
  393. goto err;
  394. composite:
  395. if (enhanced) {
  396. /* (Step 4.1.2) g = GCD(x-1, w) */
  397. if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx))
  398. goto err;
  399. /* (Steps 4.1.3 - 4.1.4) */
  400. if (BN_is_one(g))
  401. *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME;
  402. else
  403. *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
  404. } else {
  405. *status = BN_PRIMETEST_COMPOSITE;
  406. }
  407. ret = 1;
  408. goto err;
  409. outer_loop: ;
  410. /* (Step 4.1.5) */
  411. if (!BN_GENCB_call(cb, 1, i))
  412. goto err;
  413. }
  414. /* (Step 5) */
  415. *status = BN_PRIMETEST_PROBABLY_PRIME;
  416. ret = 1;
  417. err:
  418. BN_clear(g);
  419. BN_clear(w1);
  420. BN_clear(w3);
  421. BN_clear(x);
  422. BN_clear(m);
  423. BN_clear(z);
  424. BN_clear(b);
  425. BN_CTX_end(ctx);
  426. BN_MONT_CTX_free(mont);
  427. return ret;
  428. }
  429. /*
  430. * Generate a random number of |bits| bits that is probably prime by sieving.
  431. * If |safe| != 0, it generates a safe prime.
  432. * |mods| is a preallocated array that gets reused when called again.
  433. *
  434. * The probably prime is saved in |rnd|.
  435. *
  436. * Returns 1 on success and 0 on error.
  437. */
  438. static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods,
  439. BN_CTX *ctx)
  440. {
  441. int i;
  442. BN_ULONG delta;
  443. int trial_divisions = calc_trial_divisions(bits);
  444. BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1];
  445. again:
  446. if (!BN_priv_rand_ex(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD, 0,
  447. ctx))
  448. return 0;
  449. if (safe && !BN_set_bit(rnd, 1))
  450. return 0;
  451. /* we now have a random number 'rnd' to test. */
  452. for (i = 1; i < trial_divisions; i++) {
  453. BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
  454. if (mod == (BN_ULONG)-1)
  455. return 0;
  456. mods[i] = (prime_t) mod;
  457. }
  458. delta = 0;
  459. loop:
  460. for (i = 1; i < trial_divisions; i++) {
  461. /*
  462. * check that rnd is a prime and also that
  463. * gcd(rnd-1,primes) == 1 (except for 2)
  464. * do the second check only if we are interested in safe primes
  465. * in the case that the candidate prime is a single word then
  466. * we check only the primes up to sqrt(rnd)
  467. */
  468. if (bits <= 31 && delta <= 0x7fffffff
  469. && square(primes[i]) > BN_get_word(rnd) + delta)
  470. break;
  471. if (safe ? (mods[i] + delta) % primes[i] <= 1
  472. : (mods[i] + delta) % primes[i] == 0) {
  473. delta += safe ? 4 : 2;
  474. if (delta > maxdelta)
  475. goto again;
  476. goto loop;
  477. }
  478. }
  479. if (!BN_add_word(rnd, delta))
  480. return 0;
  481. if (BN_num_bits(rnd) != bits)
  482. goto again;
  483. bn_check_top(rnd);
  484. return 1;
  485. }
  486. /*
  487. * Generate a random number |rnd| of |bits| bits that is probably prime
  488. * and satisfies |rnd| % |add| == |rem| by sieving.
  489. * If |safe| != 0, it generates a safe prime.
  490. * |mods| is a preallocated array that gets reused when called again.
  491. *
  492. * Returns 1 on success and 0 on error.
  493. */
  494. static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
  495. const BIGNUM *add, const BIGNUM *rem,
  496. BN_CTX *ctx)
  497. {
  498. int i, ret = 0;
  499. BIGNUM *t1;
  500. BN_ULONG delta;
  501. int trial_divisions = calc_trial_divisions(bits);
  502. BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1];
  503. BN_CTX_start(ctx);
  504. if ((t1 = BN_CTX_get(ctx)) == NULL)
  505. goto err;
  506. if (maxdelta > BN_MASK2 - BN_get_word(add))
  507. maxdelta = BN_MASK2 - BN_get_word(add);
  508. again:
  509. if (!BN_rand_ex(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, 0, ctx))
  510. goto err;
  511. /* we need ((rnd-rem) % add) == 0 */
  512. if (!BN_mod(t1, rnd, add, ctx))
  513. goto err;
  514. if (!BN_sub(rnd, rnd, t1))
  515. goto err;
  516. if (rem == NULL) {
  517. if (!BN_add_word(rnd, safe ? 3u : 1u))
  518. goto err;
  519. } else {
  520. if (!BN_add(rnd, rnd, rem))
  521. goto err;
  522. }
  523. if (BN_num_bits(rnd) < bits
  524. || BN_get_word(rnd) < (safe ? 5u : 3u)) {
  525. if (!BN_add(rnd, rnd, add))
  526. goto err;
  527. }
  528. /* we now have a random number 'rnd' to test. */
  529. for (i = 1; i < trial_divisions; i++) {
  530. BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
  531. if (mod == (BN_ULONG)-1)
  532. goto err;
  533. mods[i] = (prime_t) mod;
  534. }
  535. delta = 0;
  536. loop:
  537. for (i = 1; i < trial_divisions; i++) {
  538. /* check that rnd is a prime */
  539. if (bits <= 31 && delta <= 0x7fffffff
  540. && square(primes[i]) > BN_get_word(rnd) + delta)
  541. break;
  542. /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */
  543. if (safe ? (mods[i] + delta) % primes[i] <= 1
  544. : (mods[i] + delta) % primes[i] == 0) {
  545. delta += BN_get_word(add);
  546. if (delta > maxdelta)
  547. goto again;
  548. goto loop;
  549. }
  550. }
  551. if (!BN_add_word(rnd, delta))
  552. goto err;
  553. ret = 1;
  554. err:
  555. BN_CTX_end(ctx);
  556. bn_check_top(rnd);
  557. return ret;
  558. }