1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
56 */
57/* ====================================================================
58 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
59 *
60 * Redistribution and use in source and binary forms, with or without
61 * modification, are permitted provided that the following conditions
62 * are met:
63 *
64 * 1. Redistributions of source code must retain the above copyright
65 * notice, this list of conditions and the following disclaimer.
66 *
67 * 2. Redistributions in binary form must reproduce the above copyright
68 * notice, this list of conditions and the following disclaimer in
69 * the documentation and/or other materials provided with the
70 * distribution.
71 *
72 * 3. All advertising materials mentioning features or use of this
73 * software must display the following acknowledgment:
74 * "This product includes software developed by the OpenSSL Project
75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
76 *
77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
78 * endorse or promote products derived from this software without
79 * prior written permission. For written permission, please contact
80 * openssl-core@openssl.org.
81 *
82 * 5. Products derived from this software may not be called "OpenSSL"
83 * nor may "OpenSSL" appear in their names without prior written
84 * permission of the OpenSSL Project.
85 *
86 * 6. Redistributions of any form whatsoever must retain the following
87 * acknowledgment:
88 * "This product includes software developed by the OpenSSL Project
89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
90 *
91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
102 * OF THE POSSIBILITY OF SUCH DAMAGE.
103 * ====================================================================
104 *
105 * This product includes cryptographic software written by Eric Young
106 * (eay@cryptsoft.com). This product includes software written by Tim
107 * Hudson (tjh@cryptsoft.com). */
108
109#include <openssl/bn.h>
110
111#include <openssl/err.h>
112#include <openssl/mem.h>
113
114#include "internal.h"
115#include "../../internal.h"
116
117
118// The quick sieve algorithm approach to weeding out primes is Philip
119// Zimmermann's, as implemented in PGP. I have had a read of his comments and
120// implemented my own version.
121
122// kPrimes contains the first 2048 primes.
123static const uint16_t kPrimes[] = {
124 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
125 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
126 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
127 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
128 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
129 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
130 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
131 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
132 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
133 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
134 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
135 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
136 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
137 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
138 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977,
139 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
140 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117,
141 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
142 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289,
143 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
144 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
145 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531,
146 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607,
147 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
148 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777,
149 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
150 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951,
151 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029,
152 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113,
153 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
154 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
155 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
156 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
157 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
158 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659,
159 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713,
160 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797,
161 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887,
162 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971,
163 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
164 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187,
165 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
166 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
167 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461,
168 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539,
169 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617,
170 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701,
171 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
172 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889,
173 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
174 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073,
175 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157,
176 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253,
177 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349,
178 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451,
179 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
180 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643,
181 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
182 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817,
183 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
184 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009,
185 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101,
186 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209,
187 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
188 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417,
189 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501,
190 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581,
191 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683,
192 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783,
193 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
194 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953,
195 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
196 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163,
197 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263,
198 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337,
199 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427,
200 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553,
201 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659,
202 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737,
203 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
204 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947,
205 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013,
206 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127,
207 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229,
208 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333,
209 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477,
210 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547,
211 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
212 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717,
213 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
214 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927,
215 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053,
216 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147,
217 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237,
218 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329,
219 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443,
220 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563,
221 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663,
222 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737,
223 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831,
224 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933,
225 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029,
226 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137,
227 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
228 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337,
229 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421,
230 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497,
231 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623,
232 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721,
233 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811,
234 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901,
235 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037,
236 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133,
237 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223,
238 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313,
239 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429,
240 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529,
241 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639,
242 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733,
243 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
244 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957,
245 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071,
246 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171,
247 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279,
248 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393,
249 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491,
250 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617,
251 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
252 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831,
253 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
254 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
255 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119,
256 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241,
257 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343,
258 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437,
259 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
260 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613,
261 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713,
262 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823,
263 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
264 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009,
265 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127,
266 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229,
267 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
268 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457,
269 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577,
270 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687,
271 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759,
272 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877,
273 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
274 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083,
275 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
276 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347,
277 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447,
278 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551,
279 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653,
280 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747,
281 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831,
282 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939,
283 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
284 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161,
285 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269,
286 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349,
287 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443,
288 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559,
289 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649,
290 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749,
291 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
292 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959,
293 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
294 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187,
295 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301,
296 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421,
297 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529,
298 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649,
299 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
300 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883,
301 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981,
302 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077,
303 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
304 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321,
305 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401,
306 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491,
307 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
308 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729,
309 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839,
310 17851, 17863,
311};
312
313// BN_prime_checks_for_size returns the number of Miller-Rabin iterations
314// necessary for a 'bits'-bit prime.
315//
316//
317// This table is generated using the algorithm of FIPS PUB 186-4
318// Digital Signature Standard (DSS), section F.1, page 117.
319// (https://doi.org/10.6028/NIST.FIPS.186-4)
320// The following magma script was used to generate the output:
321// securitybits:=125;
322// k:=1024;
323// for t:=1 to 65 do
324// for M:=3 to Floor(2*Sqrt(k-1)-1) do
325// S:=0;
326// // Sum over m
327// for m:=3 to M do
328// s:=0;
329// // Sum over j
330// for j:=2 to m do
331// s+:=(RealField(32)!2)^-(j+(k-1)/j);
332// end for;
333// S+:=2^(m-(m-1)*t)*s;
334// end for;
335// A:=2^(k-2-M*t);
336// B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S;
337// pkt:=2.00743*Log(2)*k*2^-k*(A+B);
338// seclevel:=Floor(-Log(2,pkt));
339// if seclevel ge securitybits then
340// printf "k: %5o, security: %o bits (t: %o, M: %o)\n",k,seclevel,t,M;
341// break;
342// end if;
343// end for;
344// if seclevel ge securitybits then break; end if;
345// end for;
346//
347// It can be run online at: http://magma.maths.usyd.edu.au/calc
348// And will output:
349// k: 1024, security: 129 bits (t: 6, M: 23)
350// k is the number of bits of the prime, securitybits is the level we want to
351// reach.
352// prime length | RSA key size | # MR tests | security level
353// -------------+--------------|------------+---------------
354// (b) >= 6394 | >= 12788 | 3 | 256 bit
355// (b) >= 3747 | >= 7494 | 3 | 192 bit
356// (b) >= 1345 | >= 2690 | 4 | 128 bit
357// (b) >= 1080 | >= 2160 | 5 | 128 bit
358// (b) >= 852 | >= 1704 | 5 | 112 bit
359// (b) >= 476 | >= 952 | 5 | 80 bit
360// (b) >= 400 | >= 800 | 6 | 80 bit
361// (b) >= 347 | >= 694 | 7 | 80 bit
362// (b) >= 308 | >= 616 | 8 | 80 bit
363// (b) >= 55 | >= 110 | 27 | 64 bit
364// (b) >= 6 | >= 12 | 34 | 64 bit
365static int BN_prime_checks_for_size(int bits) {
366 if (bits >= 3747) {
367 return 3;
368 }
369 if (bits >= 1345) {
370 return 4;
371 }
372 if (bits >= 476) {
373 return 5;
374 }
375 if (bits >= 400) {
376 return 6;
377 }
378 if (bits >= 347) {
379 return 7;
380 }
381 if (bits >= 308) {
382 return 8;
383 }
384 if (bits >= 55) {
385 return 27;
386 }
387 return 34;
388}
389
390// num_trial_division_primes returns the number of primes to try with trial
391// division before using more expensive checks. For larger numbers, the value
392// of excluding a candidate with trial division is larger.
393static size_t num_trial_division_primes(const BIGNUM *n) {
394 if (n->width * BN_BITS2 > 1024) {
395 return OPENSSL_ARRAY_SIZE(kPrimes);
396 }
397 return OPENSSL_ARRAY_SIZE(kPrimes) / 4;
398}
399
400// BN_PRIME_CHECKS_BLINDED is the iteration count for blinding the constant-time
401// primality test. See |BN_primality_test| for details. This number is selected
402// so that, for a candidate N-bit RSA prime, picking |BN_PRIME_CHECKS_BLINDED|
403// random N-bit numbers will have at least |BN_prime_checks_for_size(N)| values
404// in range with high probability.
405//
406// The following Python script computes the blinding factor needed for the
407// corresponding iteration count.
408/*
409import math
410
411# We choose candidate RSA primes between sqrt(2)/2 * 2^N and 2^N and select
412# witnesses by generating random N-bit numbers. Thus the probability of
413# selecting one in range is at least sqrt(2)/2.
414p = math.sqrt(2) / 2
415
416# Target around 2^-8 probability of the blinding being insufficient given that
417# key generation is a one-time, noisy operation.
418epsilon = 2**-8
419
420def choose(a, b):
421 r = 1
422 for i in xrange(b):
423 r *= a - i
424 r /= (i + 1)
425 return r
426
427def failure_rate(min_uniform, iterations):
428 """ Returns the probability that, for |iterations| candidate witnesses, fewer
429 than |min_uniform| of them will be uniform. """
430 prob = 0.0
431 for i in xrange(min_uniform):
432 prob += (choose(iterations, i) *
433 p**i * (1-p)**(iterations - i))
434 return prob
435
436for min_uniform in (3, 4, 5, 6, 8, 13, 19, 28):
437 # Find the smallest number of iterations under the target failure rate.
438 iterations = min_uniform
439 while True:
440 prob = failure_rate(min_uniform, iterations)
441 if prob < epsilon:
442 print min_uniform, iterations, prob
443 break
444 iterations += 1
445
446Output:
447 3 9 0.00368894873911
448 4 11 0.00363319494662
449 5 13 0.00336215573898
450 6 15 0.00300145783158
451 8 19 0.00225214119331
452 13 27 0.00385610026955
453 19 38 0.0021410539126
454 28 52 0.00325405801769
455
45616 iterations suffices for 400-bit primes and larger (6 uniform samples needed),
457which is already well below the minimum acceptable key size for RSA.
458*/
459#define BN_PRIME_CHECKS_BLINDED 16
460
461static int probable_prime(BIGNUM *rnd, int bits);
462static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
463 const BIGNUM *rem, BN_CTX *ctx);
464static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add,
465 const BIGNUM *rem, BN_CTX *ctx);
466
467void BN_GENCB_set(BN_GENCB *callback,
468 int (*f)(int event, int n, struct bn_gencb_st *),
469 void *arg) {
470 callback->callback = f;
471 callback->arg = arg;
472}
473
474int BN_GENCB_call(BN_GENCB *callback, int event, int n) {
475 if (!callback) {
476 return 1;
477 }
478
479 return callback->callback(event, n, callback);
480}
481
482int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
483 const BIGNUM *rem, BN_GENCB *cb) {
484 BIGNUM *t;
485 int found = 0;
486 int i, j, c1 = 0;
487 BN_CTX *ctx;
488 int checks = BN_prime_checks_for_size(bits);
489
490 if (bits < 2) {
491 // There are no prime numbers this small.
492 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
493 return 0;
494 } else if (bits == 2 && safe) {
495 // The smallest safe prime (7) is three bits.
496 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
497 return 0;
498 }
499
500 ctx = BN_CTX_new();
501 if (ctx == NULL) {
502 goto err;
503 }
504 BN_CTX_start(ctx);
505 t = BN_CTX_get(ctx);
506 if (!t) {
507 goto err;
508 }
509
510loop:
511 // make a random number and set the top and bottom bits
512 if (add == NULL) {
513 if (!probable_prime(ret, bits)) {
514 goto err;
515 }
516 } else {
517 if (safe) {
518 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) {
519 goto err;
520 }
521 } else {
522 if (!probable_prime_dh(ret, bits, add, rem, ctx)) {
523 goto err;
524 }
525 }
526 }
527
528 if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) {
529 // aborted
530 goto err;
531 }
532
533 if (!safe) {
534 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
535 if (i == -1) {
536 goto err;
537 } else if (i == 0) {
538 goto loop;
539 }
540 } else {
541 // for "safe prime" generation, check that (p-1)/2 is prime. Since a prime
542 // is odd, We just need to divide by 2
543 if (!BN_rshift1(t, ret)) {
544 goto err;
545 }
546
547 for (i = 0; i < checks; i++) {
548 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL);
549 if (j == -1) {
550 goto err;
551 } else if (j == 0) {
552 goto loop;
553 }
554
555 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL);
556 if (j == -1) {
557 goto err;
558 } else if (j == 0) {
559 goto loop;
560 }
561
562 if (!BN_GENCB_call(cb, i, c1 - 1)) {
563 goto err;
564 }
565 // We have a safe prime test pass
566 }
567 }
568
569 // we have a prime :-)
570 found = 1;
571
572err:
573 if (ctx != NULL) {
574 BN_CTX_end(ctx);
575 BN_CTX_free(ctx);
576 }
577
578 return found;
579}
580
581static int bn_trial_division(uint16_t *out, const BIGNUM *bn) {
582 const size_t num_primes = num_trial_division_primes(bn);
583 for (size_t i = 1; i < num_primes; i++) {
584 if (bn_mod_u16_consttime(bn, kPrimes[i]) == 0) {
585 *out = kPrimes[i];
586 return 1;
587 }
588 }
589 return 0;
590}
591
592int bn_odd_number_is_obviously_composite(const BIGNUM *bn) {
593 uint16_t prime;
594 return bn_trial_division(&prime, bn) && !BN_is_word(bn, prime);
595}
596
597int BN_primality_test(int *is_probably_prime, const BIGNUM *w,
598 int iterations, BN_CTX *ctx, int do_trial_division,
599 BN_GENCB *cb) {
600 *is_probably_prime = 0;
601
602 // To support RSA key generation, this function should treat |w| as secret if
603 // it is a large prime. Composite numbers are discarded, so they may return
604 // early.
605
606 if (BN_cmp(w, BN_value_one()) <= 0) {
607 return 1;
608 }
609
610 if (!BN_is_odd(w)) {
611 // The only even prime is two.
612 *is_probably_prime = BN_is_word(w, 2);
613 return 1;
614 }
615
616 // Miller-Rabin does not work for three.
617 if (BN_is_word(w, 3)) {
618 *is_probably_prime = 1;
619 return 1;
620 }
621
622 if (do_trial_division) {
623 // Perform additional trial division checks to discard small primes.
624 uint16_t prime;
625 if (bn_trial_division(&prime, w)) {
626 *is_probably_prime = BN_is_word(w, prime);
627 return 1;
628 }
629 if (!BN_GENCB_call(cb, 1, -1)) {
630 return 0;
631 }
632 }
633
634 if (iterations == BN_prime_checks) {
635 iterations = BN_prime_checks_for_size(BN_num_bits(w));
636 }
637
638 BN_CTX *new_ctx = NULL;
639 if (ctx == NULL) {
640 new_ctx = BN_CTX_new();
641 if (new_ctx == NULL) {
642 return 0;
643 }
644 ctx = new_ctx;
645 }
646
647 // See C.3.1 from FIPS 186-4.
648 int ret = 0;
649 BN_MONT_CTX *mont = NULL;
650 BN_CTX_start(ctx);
651 BIGNUM *w1 = BN_CTX_get(ctx);
652 if (w1 == NULL ||
653 !bn_usub_consttime(w1, w, BN_value_one())) {
654 goto err;
655 }
656
657 // Write w1 as m * 2^a (Steps 1 and 2).
658 int w_len = BN_num_bits(w);
659 int a = BN_count_low_zero_bits(w1);
660 BIGNUM *m = BN_CTX_get(ctx);
661 if (m == NULL ||
662 !bn_rshift_secret_shift(m, w1, a, ctx)) {
663 goto err;
664 }
665
666 // Montgomery setup for computations mod w. Additionally, compute 1 and w - 1
667 // in the Montgomery domain for later comparisons.
668 BIGNUM *b = BN_CTX_get(ctx);
669 BIGNUM *z = BN_CTX_get(ctx);
670 BIGNUM *one_mont = BN_CTX_get(ctx);
671 BIGNUM *w1_mont = BN_CTX_get(ctx);
672 mont = BN_MONT_CTX_new_consttime(w, ctx);
673 if (b == NULL || z == NULL || one_mont == NULL || w1_mont == NULL ||
674 mont == NULL ||
675 !bn_one_to_montgomery(one_mont, mont, ctx) ||
676 // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R,
677 // with a subtraction. (|one_mont| cannot be zero.)
678 !bn_usub_consttime(w1_mont, w, one_mont)) {
679 goto err;
680 }
681
682 // The following loop performs in inner iteration of the Miller-Rabin
683 // Primality test (Step 4).
684 //
685 // The algorithm as specified in FIPS 186-4 leaks information on |w|, the RSA
686 // private key. Instead, we run through each iteration unconditionally,
687 // performing modular multiplications, masking off any effects to behave
688 // equivalently to the specified algorithm.
689 //
690 // We also blind the number of values of |b| we try. Steps 4.1–4.2 say to
691 // discard out-of-range values. To avoid leaking information on |w|, we use
692 // |bn_rand_secret_range| which, rather than discarding bad values, adjusts
693 // them to be in range. Though not uniformly selected, these adjusted values
694 // are still usable as Rabin-Miller checks.
695 //
696 // Rabin-Miller is already probabilistic, so we could reach the desired
697 // confidence levels by just suitably increasing the iteration count. However,
698 // to align with FIPS 186-4, we use a more pessimal analysis: we do not count
699 // the non-uniform values towards the iteration count. As a result, this
700 // function is more complex and has more timing risk than necessary.
701 //
702 // We count both total iterations and uniform ones and iterate until we've
703 // reached at least |BN_PRIME_CHECKS_BLINDED| and |iterations|, respectively.
704 // If the latter is large enough, it will be the limiting factor with high
705 // probability and we won't leak information.
706 //
707 // Note this blinding does not impact most calls when picking primes because
708 // composites are rejected early. Only the two secret primes see extra work.
709
710 crypto_word_t uniform_iterations = 0;
711 // Using |constant_time_lt_w| seems to prevent the compiler from optimizing
712 // this into two jumps.
713 for (int i = 1; (i <= BN_PRIME_CHECKS_BLINDED) |
714 constant_time_lt_w(uniform_iterations, iterations);
715 i++) {
716 int is_uniform;
717 if (// Step 4.1-4.2
718 !bn_rand_secret_range(b, &is_uniform, 2, w1) ||
719 // Step 4.3
720 !BN_mod_exp_mont_consttime(z, b, m, w, ctx, mont)) {
721 goto err;
722 }
723 uniform_iterations += is_uniform;
724
725 // loop_done is all ones if the loop has completed and all zeros otherwise.
726 crypto_word_t loop_done = 0;
727 // next_iteration is all ones if we should continue to the next iteration
728 // (|b| is not a composite witness for |w|). This is equivalent to going to
729 // step 4.7 in the original algorithm.
730 crypto_word_t next_iteration = 0;
731
732 // Step 4.4. If z = 1 or z = w-1, mask off the loop and continue to the next
733 // iteration (go to step 4.7).
734 loop_done = BN_equal_consttime(z, BN_value_one()) |
735 BN_equal_consttime(z, w1);
736 loop_done = 0 - loop_done; // Make it all zeros or all ones.
737 next_iteration = loop_done; // Go to step 4.7 if |loop_done|.
738
739 // Step 4.5. We use Montgomery-encoding for better performance and to avoid
740 // timing leaks.
741 if (!BN_to_montgomery(z, z, mont, ctx)) {
742 goto err;
743 }
744
745 // To avoid leaking |a|, we run the loop to |w_len| and mask off all
746 // iterations once |j| = |a|.
747 for (int j = 1; j < w_len; j++) {
748 loop_done |= constant_time_eq_int(j, a);
749
750 // Step 4.5.1.
751 if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) {
752 goto err;
753 }
754
755 // Step 4.5.2. If z = w-1 and the loop is not done, run through the next
756 // iteration.
757 crypto_word_t z_is_w1_mont = BN_equal_consttime(z, w1_mont) & ~loop_done;
758 z_is_w1_mont = 0 - z_is_w1_mont; // Make it all zeros or all ones.
759 loop_done |= z_is_w1_mont;
760 next_iteration |= z_is_w1_mont; // Go to step 4.7 if |z_is_w1_mont|.
761
762 // Step 4.5.3. If z = 1 and the loop is not done, w is composite and we
763 // may exit in variable time.
764 if (BN_equal_consttime(z, one_mont) & ~loop_done) {
765 assert(!next_iteration);
766 break;
767 }
768 }
769
770 if (!next_iteration) {
771 // Step 4.6. We did not see z = w-1 before z = 1, so w must be composite.
772 // (For any prime, the value of z immediately preceding 1 must be -1.
773 // There are no non-trivial square roots of 1 modulo a prime.)
774 *is_probably_prime = 0;
775 ret = 1;
776 goto err;
777 }
778
779 // Step 4.7
780 if (!BN_GENCB_call(cb, 1, i)) {
781 goto err;
782 }
783 }
784
785 assert(uniform_iterations >= (crypto_word_t)iterations);
786 *is_probably_prime = 1;
787 ret = 1;
788
789err:
790 BN_MONT_CTX_free(mont);
791 BN_CTX_end(ctx);
792 BN_CTX_free(new_ctx);
793 return ret;
794}
795
796int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx,
797 BN_GENCB *cb) {
798 return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
799}
800
801int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx,
802 int do_trial_division, BN_GENCB *cb) {
803 int is_probably_prime;
804 if (!BN_primality_test(&is_probably_prime, a, checks, ctx, do_trial_division,
805 cb)) {
806 return -1;
807 }
808 return is_probably_prime;
809}
810
811int BN_enhanced_miller_rabin_primality_test(
812 enum bn_primality_result_t *out_result, const BIGNUM *w, int iterations,
813 BN_CTX *ctx, BN_GENCB *cb) {
814 // Enhanced Miller-Rabin is only valid on odd integers greater than 3.
815 if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) {
816 OPENSSL_PUT_ERROR(BN, BN_R_INVALID_INPUT);
817 return 0;
818 }
819
820 if (iterations == BN_prime_checks) {
821 iterations = BN_prime_checks_for_size(BN_num_bits(w));
822 }
823
824 int ret = 0;
825 BN_MONT_CTX *mont = NULL;
826
827 BN_CTX_start(ctx);
828
829 BIGNUM *w1 = BN_CTX_get(ctx);
830 if (w1 == NULL ||
831 !BN_copy(w1, w) ||
832 !BN_sub_word(w1, 1)) {
833 goto err;
834 }
835
836 // Write w1 as m*2^a (Steps 1 and 2).
837 int a = 0;
838 while (!BN_is_bit_set(w1, a)) {
839 a++;
840 }
841 BIGNUM *m = BN_CTX_get(ctx);
842 if (m == NULL ||
843 !BN_rshift(m, w1, a)) {
844 goto err;
845 }
846
847 BIGNUM *b = BN_CTX_get(ctx);
848 BIGNUM *g = BN_CTX_get(ctx);
849 BIGNUM *z = BN_CTX_get(ctx);
850 BIGNUM *x = BN_CTX_get(ctx);
851 BIGNUM *x1 = BN_CTX_get(ctx);
852 if (b == NULL ||
853 g == NULL ||
854 z == NULL ||
855 x == NULL ||
856 x1 == NULL) {
857 goto err;
858 }
859
860 // Montgomery setup for computations mod w
861 mont = BN_MONT_CTX_new_for_modulus(w, ctx);
862 if (mont == NULL) {
863 goto err;
864 }
865
866 // The following loop performs in inner iteration of the Enhanced Miller-Rabin
867 // Primality test (Step 4).
868 for (int i = 1; i <= iterations; i++) {
869 // Step 4.1-4.2
870 if (!BN_rand_range_ex(b, 2, w1)) {
871 goto err;
872 }
873
874 // Step 4.3-4.4
875 if (!BN_gcd(g, b, w, ctx)) {
876 goto err;
877 }
878 if (BN_cmp_word(g, 1) > 0) {
879 *out_result = bn_composite;
880 ret = 1;
881 goto err;
882 }
883
884 // Step 4.5
885 if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) {
886 goto err;
887 }
888
889 // Step 4.6
890 if (BN_is_one(z) || BN_cmp(z, w1) == 0) {
891 goto loop;
892 }
893
894 // Step 4.7
895 for (int j = 1; j < a; j++) {
896 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
897 goto err;
898 }
899 if (BN_cmp(z, w1) == 0) {
900 goto loop;
901 }
902 if (BN_is_one(z)) {
903 goto composite;
904 }
905 }
906
907 // Step 4.8-4.9
908 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
909 goto err;
910 }
911
912 // Step 4.10-4.11
913 if (!BN_is_one(z) && !BN_copy(x, z)) {
914 goto err;
915 }
916
917 composite:
918 // Step 4.12-4.14
919 if (!BN_copy(x1, x) ||
920 !BN_sub_word(x1, 1) ||
921 !BN_gcd(g, x1, w, ctx)) {
922 goto err;
923 }
924 if (BN_cmp_word(g, 1) > 0) {
925 *out_result = bn_composite;
926 } else {
927 *out_result = bn_non_prime_power_composite;
928 }
929
930 ret = 1;
931 goto err;
932
933 loop:
934 // Step 4.15
935 if (!BN_GENCB_call(cb, 1, i)) {
936 goto err;
937 }
938 }
939
940 *out_result = bn_probably_prime;
941 ret = 1;
942
943err:
944 BN_MONT_CTX_free(mont);
945 BN_CTX_end(ctx);
946
947 return ret;
948}
949
950static int probable_prime(BIGNUM *rnd, int bits) {
951 uint16_t mods[OPENSSL_ARRAY_SIZE(kPrimes)];
952 const size_t num_primes = num_trial_division_primes(rnd);
953 BN_ULONG delta;
954 BN_ULONG maxdelta = BN_MASK2 - kPrimes[num_primes - 1];
955 char is_single_word = bits <= BN_BITS2;
956
957again:
958 if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) {
959 return 0;
960 }
961
962 // we now have a random number 'rnd' to test.
963 for (size_t i = 1; i < num_primes; i++) {
964 mods[i] = bn_mod_u16_consttime(rnd, kPrimes[i]);
965 }
966 // If bits is so small that it fits into a single word then we
967 // additionally don't want to exceed that many bits.
968 if (is_single_word) {
969 BN_ULONG size_limit;
970 if (bits == BN_BITS2) {
971 // Avoid undefined behavior.
972 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
973 } else {
974 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
975 }
976 if (size_limit < maxdelta) {
977 maxdelta = size_limit;
978 }
979 }
980 delta = 0;
981
982loop:
983 if (is_single_word) {
984 BN_ULONG rnd_word = BN_get_word(rnd);
985
986 // In the case that the candidate prime is a single word then
987 // we check that:
988 // 1) It's greater than kPrimes[i] because we shouldn't reject
989 // 3 as being a prime number because it's a multiple of
990 // three.
991 // 2) That it's not a multiple of a known prime. We don't
992 // check that rnd-1 is also coprime to all the known
993 // primes because there aren't many small primes where
994 // that's true.
995 for (size_t i = 1; i < num_primes && kPrimes[i] < rnd_word; i++) {
996 if ((mods[i] + delta) % kPrimes[i] == 0) {
997 delta += 2;
998 if (delta > maxdelta) {
999 goto again;
1000 }
1001 goto loop;
1002 }
1003 }
1004 } else {
1005 for (size_t i = 1; i < num_primes; i++) {
1006 // check that rnd is not a prime and also
1007 // that gcd(rnd-1,primes) == 1 (except for 2)
1008 if (((mods[i] + delta) % kPrimes[i]) <= 1) {
1009 delta += 2;
1010 if (delta > maxdelta) {
1011 goto again;
1012 }
1013 goto loop;
1014 }
1015 }
1016 }
1017
1018 if (!BN_add_word(rnd, delta)) {
1019 return 0;
1020 }
1021 if (BN_num_bits(rnd) != (unsigned)bits) {
1022 goto again;
1023 }
1024
1025 return 1;
1026}
1027
1028static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
1029 const BIGNUM *rem, BN_CTX *ctx) {
1030 int ret = 0;
1031 BIGNUM *t1;
1032
1033 BN_CTX_start(ctx);
1034 if ((t1 = BN_CTX_get(ctx)) == NULL) {
1035 goto err;
1036 }
1037
1038 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
1039 goto err;
1040 }
1041
1042 // we need ((rnd-rem) % add) == 0
1043
1044 if (!BN_mod(t1, rnd, add, ctx)) {
1045 goto err;
1046 }
1047 if (!BN_sub(rnd, rnd, t1)) {
1048 goto err;
1049 }
1050 if (rem == NULL) {
1051 if (!BN_add_word(rnd, 1)) {
1052 goto err;
1053 }
1054 } else {
1055 if (!BN_add(rnd, rnd, rem)) {
1056 goto err;
1057 }
1058 }
1059 // we now have a random number 'rand' to test.
1060
1061 const size_t num_primes = num_trial_division_primes(rnd);
1062loop:
1063 for (size_t i = 1; i < num_primes; i++) {
1064 // check that rnd is a prime
1065 if (bn_mod_u16_consttime(rnd, kPrimes[i]) <= 1) {
1066 if (!BN_add(rnd, rnd, add)) {
1067 goto err;
1068 }
1069 goto loop;
1070 }
1071 }
1072
1073 ret = 1;
1074
1075err:
1076 BN_CTX_end(ctx);
1077 return ret;
1078}
1079
1080static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
1081 const BIGNUM *rem, BN_CTX *ctx) {
1082 int ret = 0;
1083 BIGNUM *t1, *qadd, *q;
1084
1085 bits--;
1086 BN_CTX_start(ctx);
1087 t1 = BN_CTX_get(ctx);
1088 q = BN_CTX_get(ctx);
1089 qadd = BN_CTX_get(ctx);
1090 if (qadd == NULL) {
1091 goto err;
1092 }
1093
1094 if (!BN_rshift1(qadd, padd)) {
1095 goto err;
1096 }
1097
1098 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
1099 goto err;
1100 }
1101
1102 // we need ((rnd-rem) % add) == 0
1103 if (!BN_mod(t1, q, qadd, ctx)) {
1104 goto err;
1105 }
1106
1107 if (!BN_sub(q, q, t1)) {
1108 goto err;
1109 }
1110
1111 if (rem == NULL) {
1112 if (!BN_add_word(q, 1)) {
1113 goto err;
1114 }
1115 } else {
1116 if (!BN_rshift1(t1, rem)) {
1117 goto err;
1118 }
1119 if (!BN_add(q, q, t1)) {
1120 goto err;
1121 }
1122 }
1123
1124 // we now have a random number 'rand' to test.
1125 if (!BN_lshift1(p, q)) {
1126 goto err;
1127 }
1128 if (!BN_add_word(p, 1)) {
1129 goto err;
1130 }
1131
1132 const size_t num_primes = num_trial_division_primes(p);
1133loop:
1134 for (size_t i = 1; i < num_primes; i++) {
1135 // check that p and q are prime
1136 // check that for p and q
1137 // gcd(p-1,primes) == 1 (except for 2)
1138 if (bn_mod_u16_consttime(p, kPrimes[i]) == 0 ||
1139 bn_mod_u16_consttime(q, kPrimes[i]) == 0) {
1140 if (!BN_add(p, p, padd)) {
1141 goto err;
1142 }
1143 if (!BN_add(q, q, qadd)) {
1144 goto err;
1145 }
1146 goto loop;
1147 }
1148 }
1149
1150 ret = 1;
1151
1152err:
1153 BN_CTX_end(ctx);
1154 return ret;
1155}
1156