1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) 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 (at) 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 (at) 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 (at) 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 (at) 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 (at) cryptsoft.com). This product includes software written by Tim 107 * Hudson (tjh (at) 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) */ 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 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 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 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 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 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 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 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 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 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 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
