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_for_modulus(w, ctx); 590 if (mont == NULL) { 591 goto err; 592 } 593 594 // The following loop performs in inner iteration of the Enhanced Miller-Rabin 595 // Primality test (Step 4). 596 for (int i = 1; i <= iterations; i++) { 597 // Step 4.1-4.2 598 if (!BN_rand_range_ex(b, 2, w1)) { 599 goto err; 600 } 601 602 // Step 4.3-4.4 603 if (!BN_gcd(g, b, w, ctx)) { 604 goto err; 605 } 606 if (BN_cmp_word(g, 1) > 0) { 607 *out_result = bn_composite; 608 ret = 1; 609 goto err; 610 } 611 612 // Step 4.5 613 if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) { 614 goto err; 615 } 616 617 // Step 4.6 618 if (BN_is_one(z) || BN_cmp(z, w1) == 0) { 619 goto loop; 620 } 621 622 // Step 4.7 623 for (int j = 1; j < a; j++) { 624 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) { 625 goto err; 626 } 627 if (BN_cmp(z, w1) == 0) { 628 goto loop; 629 } 630 if (BN_is_one(z)) { 631 goto composite; 632 } 633 } 634 635 // Step 4.8-4.9 636 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) { 637 goto err; 638 } 639 640 // Step 4.10-4.11 641 if (!BN_is_one(z) && !BN_copy(x, z)) { 642 goto err; 643 } 644 645 composite: 646 // Step 4.12-4.14 647 if (!BN_copy(x1, x) || 648 !BN_sub_word(x1, 1) || 649 !BN_gcd(g, x1, w, ctx)) { 650 goto err; 651 } 652 if (BN_cmp_word(g, 1) > 0) { 653 *out_result = bn_composite; 654 } else { 655 *out_result = bn_non_prime_power_composite; 656 } 657 658 ret = 1; 659 goto err; 660 661 loop: 662 // Step 4.15 663 if (!BN_GENCB_call(cb, 1, i)) { 664 goto err; 665 } 666 } 667 668 *out_result = bn_probably_prime; 669 ret = 1; 670 671 err: 672 BN_MONT_CTX_free(mont); 673 BN_CTX_end(ctx); 674 675 return ret; 676 } 677 678 static int probable_prime(BIGNUM *rnd, int bits) { 679 int i; 680 uint16_t mods[NUMPRIMES]; 681 BN_ULONG delta; 682 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 683 char is_single_word = bits <= BN_BITS2; 684 685 again: 686 if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) { 687 return 0; 688 } 689 690 // we now have a random number 'rnd' to test. 691 for (i = 1; i < NUMPRIMES; i++) { 692 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 693 if (mod == (BN_ULONG)-1) { 694 return 0; 695 } 696 mods[i] = (uint16_t)mod; 697 } 698 // If bits is so small that it fits into a single word then we 699 // additionally don't want to exceed that many bits. 700 if (is_single_word) { 701 BN_ULONG size_limit; 702 if (bits == BN_BITS2) { 703 // Avoid undefined behavior. 704 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd); 705 } else { 706 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1; 707 } 708 if (size_limit < maxdelta) { 709 maxdelta = size_limit; 710 } 711 } 712 delta = 0; 713 714 loop: 715 if (is_single_word) { 716 BN_ULONG rnd_word = BN_get_word(rnd); 717 718 // In the case that the candidate prime is a single word then 719 // we check that: 720 // 1) It's greater than primes[i] because we shouldn't reject 721 // 3 as being a prime number because it's a multiple of 722 // three. 723 // 2) That it's not a multiple of a known prime. We don't 724 // check that rnd-1 is also coprime to all the known 725 // primes because there aren't many small primes where 726 // that's true. 727 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { 728 if ((mods[i] + delta) % primes[i] == 0) { 729 delta += 2; 730 if (delta > maxdelta) { 731 goto again; 732 } 733 goto loop; 734 } 735 } 736 } else { 737 for (i = 1; i < NUMPRIMES; i++) { 738 // check that rnd is not a prime and also 739 // that gcd(rnd-1,primes) == 1 (except for 2) 740 if (((mods[i] + delta) % primes[i]) <= 1) { 741 delta += 2; 742 if (delta > maxdelta) { 743 goto again; 744 } 745 goto loop; 746 } 747 } 748 } 749 750 if (!BN_add_word(rnd, delta)) { 751 return 0; 752 } 753 if (BN_num_bits(rnd) != (unsigned)bits) { 754 goto again; 755 } 756 757 return 1; 758 } 759 760 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 761 const BIGNUM *rem, BN_CTX *ctx) { 762 int i, ret = 0; 763 BIGNUM *t1; 764 765 BN_CTX_start(ctx); 766 if ((t1 = BN_CTX_get(ctx)) == NULL) { 767 goto err; 768 } 769 770 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) { 771 goto err; 772 } 773 774 // we need ((rnd-rem) % add) == 0 775 776 if (!BN_mod(t1, rnd, add, ctx)) { 777 goto err; 778 } 779 if (!BN_sub(rnd, rnd, t1)) { 780 goto err; 781 } 782 if (rem == NULL) { 783 if (!BN_add_word(rnd, 1)) { 784 goto err; 785 } 786 } else { 787 if (!BN_add(rnd, rnd, rem)) { 788 goto err; 789 } 790 } 791 // we now have a random number 'rand' to test. 792 793 loop: 794 for (i = 1; i < NUMPRIMES; i++) { 795 // check that rnd is a prime 796 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 797 if (mod == (BN_ULONG)-1) { 798 goto err; 799 } 800 if (mod <= 1) { 801 if (!BN_add(rnd, rnd, add)) { 802 goto err; 803 } 804 goto loop; 805 } 806 } 807 808 ret = 1; 809 810 err: 811 BN_CTX_end(ctx); 812 return ret; 813 } 814 815 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 816 const BIGNUM *rem, BN_CTX *ctx) { 817 int i, ret = 0; 818 BIGNUM *t1, *qadd, *q; 819 820 bits--; 821 BN_CTX_start(ctx); 822 t1 = BN_CTX_get(ctx); 823 q = BN_CTX_get(ctx); 824 qadd = BN_CTX_get(ctx); 825 if (qadd == NULL) { 826 goto err; 827 } 828 829 if (!BN_rshift1(qadd, padd)) { 830 goto err; 831 } 832 833 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) { 834 goto err; 835 } 836 837 // we need ((rnd-rem) % add) == 0 838 if (!BN_mod(t1, q, qadd, ctx)) { 839 goto err; 840 } 841 842 if (!BN_sub(q, q, t1)) { 843 goto err; 844 } 845 846 if (rem == NULL) { 847 if (!BN_add_word(q, 1)) { 848 goto err; 849 } 850 } else { 851 if (!BN_rshift1(t1, rem)) { 852 goto err; 853 } 854 if (!BN_add(q, q, t1)) { 855 goto err; 856 } 857 } 858 859 // we now have a random number 'rand' to test. 860 if (!BN_lshift1(p, q)) { 861 goto err; 862 } 863 if (!BN_add_word(p, 1)) { 864 goto err; 865 } 866 867 loop: 868 for (i = 1; i < NUMPRIMES; i++) { 869 // check that p and q are prime 870 // check that for p and q 871 // gcd(p-1,primes) == 1 (except for 2) 872 BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); 873 BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); 874 if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) { 875 goto err; 876 } 877 if (pmod == 0 || qmod == 0) { 878 if (!BN_add(p, p, padd)) { 879 goto err; 880 } 881 if (!BN_add(q, q, qadd)) { 882 goto err; 883 } 884 goto loop; 885 } 886 } 887 888 ret = 1; 889 890 err: 891 BN_CTX_end(ctx); 892 return ret; 893 } 894
