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