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