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
116 /* number of Miller-Rabin iterations for an error rate of less than 2^-80
117 * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
118 * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
119 * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
120 * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
121 #define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \
122 (b) >= 850 ? 3 : \
123 (b) >= 650 ? 4 : \
124 (b) >= 550 ? 5 : \
125 (b) >= 450 ? 6 : \
126 (b) >= 400 ? 7 : \
127 (b) >= 350 ? 8 : \
128 (b) >= 300 ? 9 : \
129 (b) >= 250 ? 12 : \
130 (b) >= 200 ? 15 : \
131 (b) >= 150 ? 18 : \
132 /* b >= 100 */ 27)
133
134 /* The quick sieve algorithm approach to weeding out primes is Philip
135 * Zimmermann's, as implemented in PGP. I have had a read of his comments and
136 * implemented my own version. */
137
138 /* NUMPRIMES is the number of primes that fit into a uint16_t. */
139 #define NUMPRIMES 2048
140
141 /* primes contains all the primes that fit into a uint16_t. */
142 static const uint16_t primes[NUMPRIMES] = {
143 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
144 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
145 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
146 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
147 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
148 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
149 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
150 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
151 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
152 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
153 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
154 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
155 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
156 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
157 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977,
158 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
159 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117,
160 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
161 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289,
162 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
163 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
164 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531,
165 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607,
166 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
167 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777,
168 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
169 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951,
170 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029,
171 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113,
172 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
173 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
174 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
175 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
176 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
177 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659,
178 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713,
179 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797,
180 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887,
181 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971,
182 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
183 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187,
184 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
185 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
186 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461,
187 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539,
188 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617,
189 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701,
190 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
191 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889,
192 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
193 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073,
194 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157,
195 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253,
196 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349,
197 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451,
198 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
199 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643,
200 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
201 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817,
202 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
203 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009,
204 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101,
205 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209,
206 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
207 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417,
208 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501,
209 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581,
210 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683,
211 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783,
212 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
213 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953,
214 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
215 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163,
216 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263,
217 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337,
218 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427,
219 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553,
220 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659,
221 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737,
222 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
223 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947,
224 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013,
225 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127,
226 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229,
227 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333,
228 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477,
229 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547,
230 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
231 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717,
232 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
233 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927,
234 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053,
235 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147,
236 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237,
237 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329,
238 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443,
239 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563,
240 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663,
241 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737,
242 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831,
243 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933,
244 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029,
245 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137,
246 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
247 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337,
248 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421,
249 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497,
250 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623,
251 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721,
252 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811,
253 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901,
254 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037,
255 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133,
256 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223,
257 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313,
258 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429,
259 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529,
260 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639,
261 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733,
262 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
263 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957,
264 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071,
265 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171,
266 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279,
267 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393,
268 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491,
269 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617,
270 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
271 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831,
272 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
273 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
274 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119,
275 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241,
276 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343,
277 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437,
278 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
279 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613,
280 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713,
281 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823,
282 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
283 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009,
284 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127,
285 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229,
286 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
287 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457,
288 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577,
289 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687,
290 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759,
291 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877,
292 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
293 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083,
294 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
295 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347,
296 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447,
297 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551,
298 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653,
299 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747,
300 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831,
301 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939,
302 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
303 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161,
304 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269,
305 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349,
306 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443,
307 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559,
308 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649,
309 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749,
310 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
311 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959,
312 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
313 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187,
314 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301,
315 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421,
316 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529,
317 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649,
318 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
319 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883,
320 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981,
321 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077,
322 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
323 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321,
324 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401,
325 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491,
326 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
327 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729,
328 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839,
329 17851, 17863,
330 };
331
332 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
333 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
334 static int probable_prime(BIGNUM *rnd, int bits);
335 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
336 const BIGNUM *rem, BN_CTX *ctx);
337 static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add,
338 const BIGNUM *rem, BN_CTX *ctx);
339
BN_GENCB_set(BN_GENCB * callback,int (* f)(int event,int n,struct bn_gencb_st *),void * arg)340 void BN_GENCB_set(BN_GENCB *callback,
341 int (*f)(int event, int n, struct bn_gencb_st *),
342 void *arg) {
343 callback->callback = f;
344 callback->arg = arg;
345 }
346
BN_GENCB_call(BN_GENCB * callback,int event,int n)347 int BN_GENCB_call(BN_GENCB *callback, int event, int n) {
348 if (!callback) {
349 return 1;
350 }
351
352 return callback->callback(event, n, callback);
353 }
354
BN_generate_prime_ex(BIGNUM * ret,int bits,int safe,const BIGNUM * add,const BIGNUM * rem,BN_GENCB * cb)355 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
356 const BIGNUM *rem, BN_GENCB *cb) {
357 BIGNUM *t;
358 int found = 0;
359 int i, j, c1 = 0;
360 BN_CTX *ctx;
361 int checks = BN_prime_checks_for_size(bits);
362
363 if (bits < 2) {
364 /* There are no prime numbers this small. */
365 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
366 return 0;
367 } else if (bits == 2 && safe) {
368 /* The smallest safe prime (7) is three bits. */
369 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
370 return 0;
371 }
372
373 ctx = BN_CTX_new();
374 if (ctx == NULL) {
375 goto err;
376 }
377 BN_CTX_start(ctx);
378 t = BN_CTX_get(ctx);
379 if (!t) {
380 goto err;
381 }
382
383 loop:
384 /* make a random number and set the top and bottom bits */
385 if (add == NULL) {
386 if (!probable_prime(ret, bits)) {
387 goto err;
388 }
389 } else {
390 if (safe) {
391 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) {
392 goto err;
393 }
394 } else {
395 if (!probable_prime_dh(ret, bits, add, rem, ctx)) {
396 goto err;
397 }
398 }
399 }
400
401 if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) {
402 /* aborted */
403 goto err;
404 }
405
406 if (!safe) {
407 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
408 if (i == -1) {
409 goto err;
410 } else if (i == 0) {
411 goto loop;
412 }
413 } else {
414 /* for "safe prime" generation, check that (p-1)/2 is prime. Since a prime
415 * is odd, We just need to divide by 2 */
416 if (!BN_rshift1(t, ret)) {
417 goto err;
418 }
419
420 for (i = 0; i < checks; i++) {
421 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL);
422 if (j == -1) {
423 goto err;
424 } else if (j == 0) {
425 goto loop;
426 }
427
428 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL);
429 if (j == -1) {
430 goto err;
431 } else if (j == 0) {
432 goto loop;
433 }
434
435 if (!BN_GENCB_call(cb, i, c1 - 1)) {
436 goto err;
437 }
438 /* We have a safe prime test pass */
439 }
440 }
441
442 /* we have a prime :-) */
443 found = 1;
444
445 err:
446 if (ctx != NULL) {
447 BN_CTX_end(ctx);
448 BN_CTX_free(ctx);
449 }
450
451 return found;
452 }
453
BN_primality_test(int * is_probably_prime,const BIGNUM * candidate,int checks,BN_CTX * ctx,int do_trial_division,BN_GENCB * cb)454 int BN_primality_test(int *is_probably_prime, const BIGNUM *candidate,
455 int checks, BN_CTX *ctx, int do_trial_division,
456 BN_GENCB *cb) {
457 switch (BN_is_prime_fasttest_ex(candidate, checks, ctx, do_trial_division, cb)) {
458 case 1:
459 *is_probably_prime = 1;
460 return 1;
461 case 0:
462 *is_probably_prime = 0;
463 return 1;
464 default:
465 *is_probably_prime = 0;
466 return 0;
467 }
468 }
469
BN_is_prime_ex(const BIGNUM * candidate,int checks,BN_CTX * ctx,BN_GENCB * cb)470 int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) {
471 return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
472 }
473
BN_is_prime_fasttest_ex(const BIGNUM * a,int checks,BN_CTX * ctx_passed,int do_trial_division,BN_GENCB * cb)474 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
475 int do_trial_division, BN_GENCB *cb) {
476 int i, j, ret = -1;
477 int k;
478 BN_CTX *ctx = NULL;
479 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
480 BN_MONT_CTX *mont = NULL;
481 const BIGNUM *A = NULL;
482
483 if (BN_cmp(a, BN_value_one()) <= 0) {
484 return 0;
485 }
486
487 if (checks == BN_prime_checks) {
488 checks = BN_prime_checks_for_size(BN_num_bits(a));
489 }
490
491 /* first look for small factors */
492 if (!BN_is_odd(a)) {
493 /* a is even => a is prime if and only if a == 2 */
494 return BN_is_word(a, 2);
495 }
496
497 if (do_trial_division) {
498 for (i = 1; i < NUMPRIMES; i++) {
499 BN_ULONG mod = BN_mod_word(a, primes[i]);
500 if (mod == (BN_ULONG)-1) {
501 goto err;
502 }
503 if (mod == 0) {
504 return 0;
505 }
506 }
507
508 if (!BN_GENCB_call(cb, 1, -1)) {
509 goto err;
510 }
511 }
512
513 if (ctx_passed != NULL) {
514 ctx = ctx_passed;
515 } else if ((ctx = BN_CTX_new()) == NULL) {
516 goto err;
517 }
518 BN_CTX_start(ctx);
519
520 /* A := abs(a) */
521 if (a->neg) {
522 BIGNUM *t = BN_CTX_get(ctx);
523 if (t == NULL || !BN_copy(t, a)) {
524 goto err;
525 }
526 t->neg = 0;
527 A = t;
528 } else {
529 A = a;
530 }
531
532 A1 = BN_CTX_get(ctx);
533 A1_odd = BN_CTX_get(ctx);
534 check = BN_CTX_get(ctx);
535 if (check == NULL) {
536 goto err;
537 }
538
539 /* compute A1 := A - 1 */
540 if (!BN_copy(A1, A)) {
541 goto err;
542 }
543 if (!BN_sub_word(A1, 1)) {
544 goto err;
545 }
546 if (BN_is_zero(A1)) {
547 ret = 0;
548 goto err;
549 }
550
551 /* write A1 as A1_odd * 2^k */
552 k = 1;
553 while (!BN_is_bit_set(A1, k)) {
554 k++;
555 }
556 if (!BN_rshift(A1_odd, A1, k)) {
557 goto err;
558 }
559
560 /* Montgomery setup for computations mod A */
561 mont = BN_MONT_CTX_new();
562 if (mont == NULL) {
563 goto err;
564 }
565 if (!BN_MONT_CTX_set(mont, A, ctx)) {
566 goto err;
567 }
568
569 for (i = 0; i < checks; i++) {
570 if (!BN_pseudo_rand_range(check, A1)) {
571 goto err;
572 }
573 if (!BN_add_word(check, 1)) {
574 goto err;
575 }
576 /* now 1 <= check < A */
577
578 j = witness(check, A, A1, A1_odd, k, ctx, mont);
579 if (j == -1) {
580 goto err;
581 }
582 if (j) {
583 ret = 0;
584 goto err;
585 }
586 if (!BN_GENCB_call(cb, 1, i)) {
587 goto err;
588 }
589 }
590 ret = 1;
591
592 err:
593 if (ctx != NULL) {
594 BN_CTX_end(ctx);
595 if (ctx_passed == NULL) {
596 BN_CTX_free(ctx);
597 }
598 }
599 if (mont != NULL) {
600 BN_MONT_CTX_free(mont);
601 }
602
603 return ret;
604 }
605
witness(BIGNUM * w,const BIGNUM * a,const BIGNUM * a1,const BIGNUM * a1_odd,int k,BN_CTX * ctx,BN_MONT_CTX * mont)606 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
607 const BIGNUM *a1_odd, int k, BN_CTX *ctx,
608 BN_MONT_CTX *mont) {
609 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) { /* w := w^a1_odd mod a */
610 return -1;
611 }
612 if (BN_is_one(w)) {
613 return 0; /* probably prime */
614 }
615 if (BN_cmp(w, a1) == 0) {
616 return 0; /* w == -1 (mod a), 'a' is probably prime */
617 }
618
619 while (--k) {
620 if (!BN_mod_mul(w, w, w, a, ctx)) { /* w := w^2 mod a */
621 return -1;
622 }
623
624 if (BN_is_one(w)) {
625 return 1; /* 'a' is composite, otherwise a previous 'w' would
626 * have been == -1 (mod 'a') */
627 }
628
629 if (BN_cmp(w, a1) == 0) {
630 return 0; /* w == -1 (mod a), 'a' is probably prime */
631 }
632 }
633
634 /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
635 * and it is neither -1 nor +1 -- so 'a' cannot be prime */
636 return 1;
637 }
638
get_word(const BIGNUM * bn)639 static BN_ULONG get_word(const BIGNUM *bn) {
640 if (bn->top == 1) {
641 return bn->d[0];
642 }
643 return 0;
644 }
645
probable_prime(BIGNUM * rnd,int bits)646 static int probable_prime(BIGNUM *rnd, int bits) {
647 int i;
648 uint16_t mods[NUMPRIMES];
649 BN_ULONG delta;
650 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
651 char is_single_word = bits <= BN_BITS2;
652
653 again:
654 if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) {
655 return 0;
656 }
657
658 /* we now have a random number 'rnd' to test. */
659 for (i = 1; i < NUMPRIMES; i++) {
660 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
661 if (mod == (BN_ULONG)-1) {
662 return 0;
663 }
664 mods[i] = (uint16_t)mod;
665 }
666 /* If bits is so small that it fits into a single word then we
667 * additionally don't want to exceed that many bits. */
668 if (is_single_word) {
669 BN_ULONG size_limit;
670 if (bits == BN_BITS2) {
671 /* Avoid undefined behavior. */
672 size_limit = ~((BN_ULONG)0) - get_word(rnd);
673 } else {
674 size_limit = (((BN_ULONG)1) << bits) - get_word(rnd) - 1;
675 }
676 if (size_limit < maxdelta) {
677 maxdelta = size_limit;
678 }
679 }
680 delta = 0;
681
682 loop:
683 if (is_single_word) {
684 BN_ULONG rnd_word = get_word(rnd);
685
686 /* In the case that the candidate prime is a single word then
687 * we check that:
688 * 1) It's greater than primes[i] because we shouldn't reject
689 * 3 as being a prime number because it's a multiple of
690 * three.
691 * 2) That it's not a multiple of a known prime. We don't
692 * check that rnd-1 is also coprime to all the known
693 * primes because there aren't many small primes where
694 * that's true. */
695 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
696 if ((mods[i] + delta) % primes[i] == 0) {
697 delta += 2;
698 if (delta > maxdelta) {
699 goto again;
700 }
701 goto loop;
702 }
703 }
704 } else {
705 for (i = 1; i < NUMPRIMES; i++) {
706 /* check that rnd is not a prime and also
707 * that gcd(rnd-1,primes) == 1 (except for 2) */
708 if (((mods[i] + delta) % primes[i]) <= 1) {
709 delta += 2;
710 if (delta > maxdelta) {
711 goto again;
712 }
713 goto loop;
714 }
715 }
716 }
717
718 if (!BN_add_word(rnd, delta)) {
719 return 0;
720 }
721 if (BN_num_bits(rnd) != (unsigned)bits) {
722 goto again;
723 }
724
725 return 1;
726 }
727
probable_prime_dh(BIGNUM * rnd,int bits,const BIGNUM * add,const BIGNUM * rem,BN_CTX * ctx)728 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
729 const BIGNUM *rem, BN_CTX *ctx) {
730 int i, ret = 0;
731 BIGNUM *t1;
732
733 BN_CTX_start(ctx);
734 if ((t1 = BN_CTX_get(ctx)) == NULL) {
735 goto err;
736 }
737
738 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
739 goto err;
740 }
741
742 /* we need ((rnd-rem) % add) == 0 */
743
744 if (!BN_mod(t1, rnd, add, ctx)) {
745 goto err;
746 }
747 if (!BN_sub(rnd, rnd, t1)) {
748 goto err;
749 }
750 if (rem == NULL) {
751 if (!BN_add_word(rnd, 1)) {
752 goto err;
753 }
754 } else {
755 if (!BN_add(rnd, rnd, rem)) {
756 goto err;
757 }
758 }
759 /* we now have a random number 'rand' to test. */
760
761 loop:
762 for (i = 1; i < NUMPRIMES; i++) {
763 /* check that rnd is a prime */
764 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
765 if (mod == (BN_ULONG)-1) {
766 goto err;
767 }
768 if (mod <= 1) {
769 if (!BN_add(rnd, rnd, add)) {
770 goto err;
771 }
772 goto loop;
773 }
774 }
775
776 ret = 1;
777
778 err:
779 BN_CTX_end(ctx);
780 return ret;
781 }
782
probable_prime_dh_safe(BIGNUM * p,int bits,const BIGNUM * padd,const BIGNUM * rem,BN_CTX * ctx)783 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
784 const BIGNUM *rem, BN_CTX *ctx) {
785 int i, ret = 0;
786 BIGNUM *t1, *qadd, *q;
787
788 bits--;
789 BN_CTX_start(ctx);
790 t1 = BN_CTX_get(ctx);
791 q = BN_CTX_get(ctx);
792 qadd = BN_CTX_get(ctx);
793 if (qadd == NULL) {
794 goto err;
795 }
796
797 if (!BN_rshift1(qadd, padd)) {
798 goto err;
799 }
800
801 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
802 goto err;
803 }
804
805 /* we need ((rnd-rem) % add) == 0 */
806 if (!BN_mod(t1, q, qadd, ctx)) {
807 goto err;
808 }
809
810 if (!BN_sub(q, q, t1)) {
811 goto err;
812 }
813
814 if (rem == NULL) {
815 if (!BN_add_word(q, 1)) {
816 goto err;
817 }
818 } else {
819 if (!BN_rshift1(t1, rem)) {
820 goto err;
821 }
822 if (!BN_add(q, q, t1)) {
823 goto err;
824 }
825 }
826
827 /* we now have a random number 'rand' to test. */
828 if (!BN_lshift1(p, q)) {
829 goto err;
830 }
831 if (!BN_add_word(p, 1)) {
832 goto err;
833 }
834
835 loop:
836 for (i = 1; i < NUMPRIMES; i++) {
837 /* check that p and q are prime */
838 /* check that for p and q
839 * gcd(p-1,primes) == 1 (except for 2) */
840 BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
841 BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
842 if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) {
843 goto err;
844 }
845 if (pmod == 0 || qmod == 0) {
846 if (!BN_add(p, p, padd)) {
847 goto err;
848 }
849 if (!BN_add(q, q, qadd)) {
850 goto err;
851 }
852 goto loop;
853 }
854 }
855
856 ret = 1;
857
858 err:
859 BN_CTX_end(ctx);
860 return ret;
861 }
862