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 /* The quick sieve algorithm approach to weeding out primes is Philip
117 * Zimmermann's, as implemented in PGP. I have had a read of his comments and
118 * implemented my own version. */
119
120 #define NUMPRIMES 2048
121
122 /* primes contains all the primes that fit into a uint16_t. */
123 static const uint16_t primes[NUMPRIMES] = {
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, in order to maintain an error rate greater
315 * than the security level for an RSA prime of that many bits (calculated using
316 * the FIPS SP 800-57 security level and 186-4 Section F.1; original paper:
317 * Damgaard, Landrock, Pomerance: Average case error estimates for the strong
318 * probable prime test. -- Math. Comp. 61 (1993) 177-194) */
BN_prime_checks_for_size(int bits)319 static int BN_prime_checks_for_size(int bits) {
320 if (bits >= 3747) {
321 return 3;
322 }
323 if (bits >= 1345) {
324 return 4;
325 }
326 if (bits >= 476) {
327 return 5;
328 }
329 if (bits >= 400) {
330 return 6;
331 }
332 if (bits >= 308) {
333 return 8;
334 }
335 if (bits >= 205) {
336 return 13;
337 }
338 if (bits >= 155) {
339 return 19;
340 }
341 return 28;
342 }
343
344 static int probable_prime(BIGNUM *rnd, int bits);
345 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
346 const BIGNUM *rem, BN_CTX *ctx);
347 static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add,
348 const BIGNUM *rem, BN_CTX *ctx);
349
BN_GENCB_set(BN_GENCB * callback,int (* f)(int event,int n,struct bn_gencb_st *),void * arg)350 void BN_GENCB_set(BN_GENCB *callback,
351 int (*f)(int event, int n, struct bn_gencb_st *),
352 void *arg) {
353 callback->callback = f;
354 callback->arg = arg;
355 }
356
BN_GENCB_call(BN_GENCB * callback,int event,int n)357 int BN_GENCB_call(BN_GENCB *callback, int event, int n) {
358 if (!callback) {
359 return 1;
360 }
361
362 return callback->callback(event, n, callback);
363 }
364
BN_generate_prime_ex(BIGNUM * ret,int bits,int safe,const BIGNUM * add,const BIGNUM * rem,BN_GENCB * cb)365 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
366 const BIGNUM *rem, BN_GENCB *cb) {
367 BIGNUM *t;
368 int found = 0;
369 int i, j, c1 = 0;
370 BN_CTX *ctx;
371 int checks = BN_prime_checks_for_size(bits);
372
373 if (bits < 2) {
374 /* There are no prime numbers this small. */
375 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
376 return 0;
377 } else if (bits == 2 && safe) {
378 /* The smallest safe prime (7) is three bits. */
379 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL);
380 return 0;
381 }
382
383 ctx = BN_CTX_new();
384 if (ctx == NULL) {
385 goto err;
386 }
387 BN_CTX_start(ctx);
388 t = BN_CTX_get(ctx);
389 if (!t) {
390 goto err;
391 }
392
393 loop:
394 /* make a random number and set the top and bottom bits */
395 if (add == NULL) {
396 if (!probable_prime(ret, bits)) {
397 goto err;
398 }
399 } else {
400 if (safe) {
401 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) {
402 goto err;
403 }
404 } else {
405 if (!probable_prime_dh(ret, bits, add, rem, ctx)) {
406 goto err;
407 }
408 }
409 }
410
411 if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) {
412 /* aborted */
413 goto err;
414 }
415
416 if (!safe) {
417 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
418 if (i == -1) {
419 goto err;
420 } else if (i == 0) {
421 goto loop;
422 }
423 } else {
424 /* for "safe prime" generation, check that (p-1)/2 is prime. Since a prime
425 * is odd, We just need to divide by 2 */
426 if (!BN_rshift1(t, ret)) {
427 goto err;
428 }
429
430 for (i = 0; i < checks; i++) {
431 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL);
432 if (j == -1) {
433 goto err;
434 } else if (j == 0) {
435 goto loop;
436 }
437
438 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL);
439 if (j == -1) {
440 goto err;
441 } else if (j == 0) {
442 goto loop;
443 }
444
445 if (!BN_GENCB_call(cb, i, c1 - 1)) {
446 goto err;
447 }
448 /* We have a safe prime test pass */
449 }
450 }
451
452 /* we have a prime :-) */
453 found = 1;
454
455 err:
456 if (ctx != NULL) {
457 BN_CTX_end(ctx);
458 BN_CTX_free(ctx);
459 }
460
461 return found;
462 }
463
BN_primality_test(int * is_probably_prime,const BIGNUM * candidate,int checks,BN_CTX * ctx,int do_trial_division,BN_GENCB * cb)464 int BN_primality_test(int *is_probably_prime, const BIGNUM *candidate,
465 int checks, BN_CTX *ctx, int do_trial_division,
466 BN_GENCB *cb) {
467 switch (BN_is_prime_fasttest_ex(candidate, checks, ctx, do_trial_division, cb)) {
468 case 1:
469 *is_probably_prime = 1;
470 return 1;
471 case 0:
472 *is_probably_prime = 0;
473 return 1;
474 default:
475 *is_probably_prime = 0;
476 return 0;
477 }
478 }
479
BN_is_prime_ex(const BIGNUM * candidate,int checks,BN_CTX * ctx,BN_GENCB * cb)480 int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) {
481 return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
482 }
483
BN_is_prime_fasttest_ex(const BIGNUM * a,int checks,BN_CTX * ctx,int do_trial_division,BN_GENCB * cb)484 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx,
485 int do_trial_division, BN_GENCB *cb) {
486 if (BN_cmp(a, BN_value_one()) <= 0) {
487 return 0;
488 }
489
490 /* first look for small factors */
491 if (!BN_is_odd(a)) {
492 /* a is even => a is prime if and only if a == 2 */
493 return BN_is_word(a, 2);
494 }
495
496 /* Enhanced Miller-Rabin does not work for three. */
497 if (BN_is_word(a, 3)) {
498 return 1;
499 }
500
501 if (do_trial_division) {
502 for (int i = 1; i < NUMPRIMES; i++) {
503 BN_ULONG mod = BN_mod_word(a, primes[i]);
504 if (mod == (BN_ULONG)-1) {
505 return -1;
506 }
507 if (mod == 0) {
508 return BN_is_word(a, primes[i]);
509 }
510 }
511
512 if (!BN_GENCB_call(cb, 1, -1)) {
513 return -1;
514 }
515 }
516
517 int ret = -1;
518 BN_CTX *ctx_allocated = NULL;
519 if (ctx == NULL) {
520 ctx_allocated = BN_CTX_new();
521 if (ctx_allocated == NULL) {
522 return -1;
523 }
524 ctx = ctx_allocated;
525 }
526
527 enum bn_primality_result_t result;
528 if (!BN_enhanced_miller_rabin_primality_test(&result, a, checks, ctx, cb)) {
529 goto err;
530 }
531
532 ret = (result == bn_probably_prime);
533
534 err:
535 BN_CTX_free(ctx_allocated);
536 return ret;
537 }
538
BN_enhanced_miller_rabin_primality_test(enum bn_primality_result_t * out_result,const BIGNUM * w,int iterations,BN_CTX * ctx,BN_GENCB * cb)539 int BN_enhanced_miller_rabin_primality_test(
540 enum bn_primality_result_t *out_result, const BIGNUM *w, int iterations,
541 BN_CTX *ctx, BN_GENCB *cb) {
542 /* Enhanced Miller-Rabin is only valid on odd integers greater than 3. */
543 if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) {
544 OPENSSL_PUT_ERROR(BN, BN_R_INVALID_INPUT);
545 return 0;
546 }
547
548 if (iterations == BN_prime_checks) {
549 iterations = BN_prime_checks_for_size(BN_num_bits(w));
550 }
551
552 int ret = 0;
553 BN_MONT_CTX *mont = NULL;
554
555 BN_CTX_start(ctx);
556
557 BIGNUM *w1 = BN_CTX_get(ctx);
558 if (w1 == NULL ||
559 !BN_copy(w1, w) ||
560 !BN_sub_word(w1, 1)) {
561 goto err;
562 }
563
564 /* Write w1 as m*2^a (Steps 1 and 2). */
565 int a = 0;
566 while (!BN_is_bit_set(w1, a)) {
567 a++;
568 }
569 BIGNUM *m = BN_CTX_get(ctx);
570 if (m == NULL ||
571 !BN_rshift(m, w1, a)) {
572 goto err;
573 }
574
575 BIGNUM *b = BN_CTX_get(ctx);
576 BIGNUM *g = BN_CTX_get(ctx);
577 BIGNUM *z = BN_CTX_get(ctx);
578 BIGNUM *x = BN_CTX_get(ctx);
579 BIGNUM *x1 = BN_CTX_get(ctx);
580 if (b == NULL ||
581 g == NULL ||
582 z == NULL ||
583 x == NULL ||
584 x1 == NULL) {
585 goto err;
586 }
587
588 /* Montgomery setup for computations mod A */
589 mont = BN_MONT_CTX_new();
590 if (mont == NULL ||
591 !BN_MONT_CTX_set(mont, w, ctx)) {
592 goto err;
593 }
594
595 /* The following loop performs in inner iteration of the Enhanced Miller-Rabin
596 * Primality test (Step 4). */
597 for (int i = 1; i <= iterations; i++) {
598 /* Step 4.1-4.2 */
599 if (!BN_rand_range_ex(b, 2, w1)) {
600 goto err;
601 }
602
603 /* Step 4.3-4.4 */
604 if (!BN_gcd(g, b, w, ctx)) {
605 goto err;
606 }
607 if (BN_cmp_word(g, 1) > 0) {
608 *out_result = bn_composite;
609 ret = 1;
610 goto err;
611 }
612
613 /* Step 4.5 */
614 if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) {
615 goto err;
616 }
617
618 /* Step 4.6 */
619 if (BN_is_one(z) || BN_cmp(z, w1) == 0) {
620 goto loop;
621 }
622
623 /* Step 4.7 */
624 for (int j = 1; j < a; j++) {
625 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
626 goto err;
627 }
628 if (BN_cmp(z, w1) == 0) {
629 goto loop;
630 }
631 if (BN_is_one(z)) {
632 goto composite;
633 }
634 }
635
636 /* Step 4.8-4.9 */
637 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {
638 goto err;
639 }
640
641 /* Step 4.10-4.11 */
642 if (!BN_is_one(z) && !BN_copy(x, z)) {
643 goto err;
644 }
645
646 composite:
647 /* Step 4.12-4.14 */
648 if (!BN_copy(x1, x) ||
649 !BN_sub_word(x1, 1) ||
650 !BN_gcd(g, x1, w, ctx)) {
651 goto err;
652 }
653 if (BN_cmp_word(g, 1) > 0) {
654 *out_result = bn_composite;
655 } else {
656 *out_result = bn_non_prime_power_composite;
657 }
658
659 ret = 1;
660 goto err;
661
662 loop:
663 /* Step 4.15 */
664 if (!BN_GENCB_call(cb, 1, i)) {
665 goto err;
666 }
667 }
668
669 *out_result = bn_probably_prime;
670 ret = 1;
671
672 err:
673 BN_MONT_CTX_free(mont);
674 BN_CTX_end(ctx);
675
676 return ret;
677 }
678
probable_prime(BIGNUM * rnd,int bits)679 static int probable_prime(BIGNUM *rnd, int bits) {
680 int i;
681 uint16_t mods[NUMPRIMES];
682 BN_ULONG delta;
683 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
684 char is_single_word = bits <= BN_BITS2;
685
686 again:
687 if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) {
688 return 0;
689 }
690
691 /* we now have a random number 'rnd' to test. */
692 for (i = 1; i < NUMPRIMES; i++) {
693 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
694 if (mod == (BN_ULONG)-1) {
695 return 0;
696 }
697 mods[i] = (uint16_t)mod;
698 }
699 /* If bits is so small that it fits into a single word then we
700 * additionally don't want to exceed that many bits. */
701 if (is_single_word) {
702 BN_ULONG size_limit;
703 if (bits == BN_BITS2) {
704 /* Avoid undefined behavior. */
705 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
706 } else {
707 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
708 }
709 if (size_limit < maxdelta) {
710 maxdelta = size_limit;
711 }
712 }
713 delta = 0;
714
715 loop:
716 if (is_single_word) {
717 BN_ULONG rnd_word = BN_get_word(rnd);
718
719 /* In the case that the candidate prime is a single word then
720 * we check that:
721 * 1) It's greater than primes[i] because we shouldn't reject
722 * 3 as being a prime number because it's a multiple of
723 * three.
724 * 2) That it's not a multiple of a known prime. We don't
725 * check that rnd-1 is also coprime to all the known
726 * primes because there aren't many small primes where
727 * that's true. */
728 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
729 if ((mods[i] + delta) % primes[i] == 0) {
730 delta += 2;
731 if (delta > maxdelta) {
732 goto again;
733 }
734 goto loop;
735 }
736 }
737 } else {
738 for (i = 1; i < NUMPRIMES; i++) {
739 /* check that rnd is not a prime and also
740 * that gcd(rnd-1,primes) == 1 (except for 2) */
741 if (((mods[i] + delta) % primes[i]) <= 1) {
742 delta += 2;
743 if (delta > maxdelta) {
744 goto again;
745 }
746 goto loop;
747 }
748 }
749 }
750
751 if (!BN_add_word(rnd, delta)) {
752 return 0;
753 }
754 if (BN_num_bits(rnd) != (unsigned)bits) {
755 goto again;
756 }
757
758 return 1;
759 }
760
probable_prime_dh(BIGNUM * rnd,int bits,const BIGNUM * add,const BIGNUM * rem,BN_CTX * ctx)761 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
762 const BIGNUM *rem, BN_CTX *ctx) {
763 int i, ret = 0;
764 BIGNUM *t1;
765
766 BN_CTX_start(ctx);
767 if ((t1 = BN_CTX_get(ctx)) == NULL) {
768 goto err;
769 }
770
771 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
772 goto err;
773 }
774
775 /* we need ((rnd-rem) % add) == 0 */
776
777 if (!BN_mod(t1, rnd, add, ctx)) {
778 goto err;
779 }
780 if (!BN_sub(rnd, rnd, t1)) {
781 goto err;
782 }
783 if (rem == NULL) {
784 if (!BN_add_word(rnd, 1)) {
785 goto err;
786 }
787 } else {
788 if (!BN_add(rnd, rnd, rem)) {
789 goto err;
790 }
791 }
792 /* we now have a random number 'rand' to test. */
793
794 loop:
795 for (i = 1; i < NUMPRIMES; i++) {
796 /* check that rnd is a prime */
797 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
798 if (mod == (BN_ULONG)-1) {
799 goto err;
800 }
801 if (mod <= 1) {
802 if (!BN_add(rnd, rnd, add)) {
803 goto err;
804 }
805 goto loop;
806 }
807 }
808
809 ret = 1;
810
811 err:
812 BN_CTX_end(ctx);
813 return ret;
814 }
815
probable_prime_dh_safe(BIGNUM * p,int bits,const BIGNUM * padd,const BIGNUM * rem,BN_CTX * ctx)816 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
817 const BIGNUM *rem, BN_CTX *ctx) {
818 int i, ret = 0;
819 BIGNUM *t1, *qadd, *q;
820
821 bits--;
822 BN_CTX_start(ctx);
823 t1 = BN_CTX_get(ctx);
824 q = BN_CTX_get(ctx);
825 qadd = BN_CTX_get(ctx);
826 if (qadd == NULL) {
827 goto err;
828 }
829
830 if (!BN_rshift1(qadd, padd)) {
831 goto err;
832 }
833
834 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {
835 goto err;
836 }
837
838 /* we need ((rnd-rem) % add) == 0 */
839 if (!BN_mod(t1, q, qadd, ctx)) {
840 goto err;
841 }
842
843 if (!BN_sub(q, q, t1)) {
844 goto err;
845 }
846
847 if (rem == NULL) {
848 if (!BN_add_word(q, 1)) {
849 goto err;
850 }
851 } else {
852 if (!BN_rshift1(t1, rem)) {
853 goto err;
854 }
855 if (!BN_add(q, q, t1)) {
856 goto err;
857 }
858 }
859
860 /* we now have a random number 'rand' to test. */
861 if (!BN_lshift1(p, q)) {
862 goto err;
863 }
864 if (!BN_add_word(p, 1)) {
865 goto err;
866 }
867
868 loop:
869 for (i = 1; i < NUMPRIMES; i++) {
870 /* check that p and q are prime */
871 /* check that for p and q
872 * gcd(p-1,primes) == 1 (except for 2) */
873 BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
874 BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
875 if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) {
876 goto err;
877 }
878 if (pmod == 0 || qmod == 0) {
879 if (!BN_add(p, p, padd)) {
880 goto err;
881 }
882 if (!BN_add(q, q, qadd)) {
883 goto err;
884 }
885 goto loop;
886 }
887 }
888
889 ret = 1;
890
891 err:
892 BN_CTX_end(ctx);
893 return ret;
894 }
895