195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * All rights reserved. 395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This package is an SSL implementation written 595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * by Eric Young (eay@cryptsoft.com). 695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The implementation was written so as to conform with Netscapes SSL. 795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This library is free for commercial and non-commercial use as long as 995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the following conditions are aheared to. The following conditions 1095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * apply to all code found in this distribution, be it the RC4, RSA, 1195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * included with this distribution is covered by the same copyright terms 1395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 1595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Copyright remains Eric Young's, and as such any Copyright notices in 1695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the code are not to be removed. 1795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * If this package is used in a product, Eric Young should be given attribution 1895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * as the author of the parts of the library used. 1995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This can be in the form of a textual message at program startup or 2095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * in documentation (online or textual) provided with the package. 2195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 2295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Redistribution and use in source and binary forms, with or without 2395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * modification, are permitted provided that the following conditions 2495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * are met: 2595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 1. Redistributions of source code must retain the copyright 2695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer. 2795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 2. Redistributions in binary form must reproduce the above copyright 2895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer in the 2995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * documentation and/or other materials provided with the distribution. 3095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 3. All advertising materials mentioning features or use of this software 3195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * must display the following acknowledgement: 3295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes cryptographic software written by 3395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Eric Young (eay@cryptsoft.com)" 3495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The word 'cryptographic' can be left out if the rouines from the library 3595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * being used are not cryptographic related :-). 3695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 4. If you include any Windows specific code (or a derivative thereof) from 3795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the apps directory (application code) you must include an acknowledgement: 3895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 3995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 4095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 4995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * SUCH DAMAGE. 5195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 5295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The licence and distribution terms for any publically available version or 5395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * derivative of this code cannot be changed. i.e. this code cannot simply be 5495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * copied and put under another distribution licence 5595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * [including the GNU Public Licence.] 5695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 5795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* ==================================================================== 5895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 5995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Redistribution and use in source and binary forms, with or without 6195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * modification, are permitted provided that the following conditions 6295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * are met: 6395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 1. Redistributions of source code must retain the above copyright 6595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer. 6695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 2. Redistributions in binary form must reproduce the above copyright 6895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer in 6995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the documentation and/or other materials provided with the 7095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * distribution. 7195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 7295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 3. All advertising materials mentioning features or use of this 7395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * software must display the following acknowledgment: 7495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes software developed by the OpenSSL Project 7595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 7695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 7795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 7895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * endorse or promote products derived from this software without 7995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * prior written permission. For written permission, please contact 8095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * openssl-core@openssl.org. 8195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 8295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 5. Products derived from this software may not be called "OpenSSL" 8395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * nor may "OpenSSL" appear in their names without prior written 8495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * permission of the OpenSSL Project. 8595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 8695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6. Redistributions of any form whatsoever must retain the following 8795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * acknowledgment: 8895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes software developed by the OpenSSL Project 8995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 9095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 9195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 9295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 9395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 9495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 9595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 9695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 9795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 9895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 9995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 10095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 10195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 10295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * OF THE POSSIBILITY OF SUCH DAMAGE. 10395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ==================================================================== 10495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 10595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This product includes cryptographic software written by Eric Young 10695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (eay@cryptsoft.com). This product includes software written by Tim 10795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Hudson (tjh@cryptsoft.com). */ 10895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include <openssl/bn.h> 11095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include <openssl/err.h> 11295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include <openssl/mem.h> 11395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include "internal.h" 11595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* number of Miller-Rabin iterations for an error rate of less than 2^-80 11795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook 11895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; 11995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * original paper: Damgaard, Landrock, Pomerance: Average case error estimates 12095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */ 12195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \ 12295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 850 ? 3 : \ 12395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 650 ? 4 : \ 12495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 550 ? 5 : \ 12595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 450 ? 6 : \ 12695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 400 ? 7 : \ 12795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 350 ? 8 : \ 12895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 300 ? 9 : \ 12995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 250 ? 12 : \ 13095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 200 ? 15 : \ 13195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (b) >= 150 ? 18 : \ 13295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* b >= 100 */ 27) 13395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* The quick sieve algorithm approach to weeding out primes is Philip 13595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Zimmermann's, as implemented in PGP. I have had a read of his comments and 13695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * implemented my own version. */ 13795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* NUMPRIMES is the number of primes that fit into a uint16_t. */ 13995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#define NUMPRIMES 2048 14095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* primes is defined at the bottom of the file and contains all the primes that 14295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * fit into a uint16_t. */ 14395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic const uint16_t primes[NUMPRIMES]; 14495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 14695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); 14795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int probable_prime(BIGNUM *rnd, int bits); 14895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 14995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *rem, BN_CTX *ctx); 15095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, 15195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *rem, BN_CTX *ctx); 15295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyvoid BN_GENCB_set(BN_GENCB *callback, 15495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int (*f)(int event, int n, struct bn_gencb_st *), 15595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley void *arg) { 15695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley callback->callback = f; 15795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley callback->arg = arg; 15895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 15995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_GENCB_call(BN_GENCB *callback, int event, int n) { 16195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!callback) { 16295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 16395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 16495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return callback->callback(event, n, callback); 16695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 16795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add, 16995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *rem, BN_GENCB *cb) { 17095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *t; 17195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int found = 0; 17295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int i, j, c1 = 0; 17395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX *ctx; 17495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int checks = BN_prime_checks_for_size(bits); 17595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17627ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (bits < 2) { 17727ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley /* There are no prime numbers this small. */ 17827ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley OPENSSL_PUT_ERROR(BN, BN_generate_prime_ex, BN_R_BITS_TOO_SMALL); 17927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley return 0; 18027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } else if (bits == 2 && safe) { 18127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley /* The smallest safe prime (7) is three bits. */ 18227ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley OPENSSL_PUT_ERROR(BN, BN_generate_prime_ex, BN_R_BITS_TOO_SMALL); 18327ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley return 0; 18427ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 18527ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley 18695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ctx = BN_CTX_new(); 18795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ctx == NULL) { 18895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 18995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 19095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 19195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = BN_CTX_get(ctx); 19295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!t) { 19395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 19495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 19595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 19695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyloop: 19795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* make a random number and set the top and bottom bits */ 19895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (add == NULL) { 19995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!probable_prime(ret, bits)) { 20095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 20195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 20295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 20395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (safe) { 20495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) { 20595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 20695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 20795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 20895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!probable_prime_dh(ret, bits, add, rem, ctx)) { 20995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 21095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 21495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) { 21595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* aborted */ 21695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 21795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 21995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!safe) { 22095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); 22195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (i == -1) { 22295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 22395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if (i == 0) { 22495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto loop; 22595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 22695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 22795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* for "safe prime" generation, check that (p-1)/2 is prime. Since a prime 22895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * is odd, We just need to divide by 2 */ 22995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(t, ret)) { 23095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 23195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 23295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 23395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 0; i < checks; i++) { 23495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL); 23595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (j == -1) { 23695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 23795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if (j == 0) { 23895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto loop; 23995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 24095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 24195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL); 24295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (j == -1) { 24395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 24495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if (j == 0) { 24595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto loop; 24695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 24795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 24895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_GENCB_call(cb, i, c1 - 1)) { 24995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 25095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* We have a safe prime test pass */ 25295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 25595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* we have a prime :-) */ 25695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley found = 1; 25795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 25895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 25995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ctx != NULL) { 26095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 26195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_free(ctx); 26295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 26495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return found; 26595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 26695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 26795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_primality_test(int *is_probably_prime, const BIGNUM *candidate, 26895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int checks, BN_CTX *ctx, int do_trial_division, 26995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_GENCB *cb) { 27095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley switch (BN_is_prime_fasttest_ex(candidate, checks, ctx, do_trial_division, cb)) { 27195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley case 1: 27295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley *is_probably_prime = 1; 27395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 27495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley case 0: 27595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley *is_probably_prime = 0; 27695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 27795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley default: 27895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley *is_probably_prime = 0; 27995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 28095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 28195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 28295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 28395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) { 28495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb); 28595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 28695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 28795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 28895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int do_trial_division, BN_GENCB *cb) { 28995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int i, j, ret = -1; 29095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int k; 29195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX *ctx = NULL; 29295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ 29395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_MONT_CTX *mont = NULL; 29495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *A = NULL; 29595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 29695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(a, BN_value_one()) <= 0) { 29795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 29895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 29995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 30095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (checks == BN_prime_checks) { 30195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley checks = BN_prime_checks_for_size(BN_num_bits(a)); 30295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 30395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 30495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* first look for small factors */ 30595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_is_odd(a)) { 30695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* a is even => a is prime if and only if a == 2 */ 30795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return BN_is_word(a, 2); 30895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 30995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 31095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (do_trial_division) { 31195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 1; i < NUMPRIMES; i++) { 31295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_mod_word(a, primes[i]) == 0) { 31395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 31495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 31595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 31695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 31795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_GENCB_call(cb, 1, -1)) { 31895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 31995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 32095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 32195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 32295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ctx_passed != NULL) { 32395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ctx = ctx_passed; 32495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if ((ctx = BN_CTX_new()) == NULL) { 32595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 32695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 32795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 32895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 32995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* A := abs(a) */ 33095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (a->neg) { 33195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *t; 33295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if ((t = BN_CTX_get(ctx)) == NULL) { 33395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 33495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 33595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_copy(t, a); 33695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t->neg = 0; 33795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A = t; 33895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 33995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A = a; 34095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 34195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 34295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A1 = BN_CTX_get(ctx); 34395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A1_odd = BN_CTX_get(ctx); 34495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley check = BN_CTX_get(ctx); 34595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (check == NULL) { 34695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 34795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 34895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 34995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* compute A1 := A - 1 */ 35095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_copy(A1, A)) { 35195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 35295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 35395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub_word(A1, 1)) { 35495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 35595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 35695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_zero(A1)) { 35795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 0; 35895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 35995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 36095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 36195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* write A1 as A1_odd * 2^k */ 36295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley k = 1; 36395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_bit_set(A1, k)) { 36495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley k++; 36595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 36695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift(A1_odd, A1, k)) { 36795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 36895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 36995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 37095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Montgomery setup for computations mod A */ 37195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont = BN_MONT_CTX_new(); 37295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (mont == NULL) { 37395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 37495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 37595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_MONT_CTX_set(mont, A, ctx)) { 37695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 37795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 37895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 37995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 0; i < checks; i++) { 38095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_pseudo_rand_range(check, A1)) { 38195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 38295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 38395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add_word(check, 1)) { 38495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 38595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 38695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* now 1 <= check < A */ 38795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 38895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley j = witness(check, A, A1, A1_odd, k, ctx, mont); 38995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (j == -1) { 39095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 39195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 39295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (j) { 39395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 0; 39495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 39595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 39695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_GENCB_call(cb, 1, i)) { 39795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 39895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 39995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 40095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 1; 40195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 40295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 40395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ctx != NULL) { 40495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 40595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ctx_passed == NULL) { 40695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_free(ctx); 40795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 40895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 40995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (mont != NULL) { 41095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_MONT_CTX_free(mont); 41195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 41395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 41495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 41595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 41695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 41795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *a1_odd, int k, BN_CTX *ctx, 41895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_MONT_CTX *mont) { 41995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) { /* w := w^a1_odd mod a */ 42095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return -1; 42195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 42295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_one(w)) { 42395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; /* probably prime */ 42495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 42595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(w, a1) == 0) { 42695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; /* w == -1 (mod a), 'a' is probably prime */ 42795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 42895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 42995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (--k) { 43095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mod_mul(w, w, w, a, ctx)) { /* w := w^2 mod a */ 43195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return -1; 43295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 43395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 43495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_one(w)) { 43595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; /* 'a' is composite, otherwise a previous 'w' would 43695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * have been == -1 (mod 'a') */ 43795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 43895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 43995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(w, a1) == 0) { 44095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; /* w == -1 (mod a), 'a' is probably prime */ 44195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 44295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 44395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', 44595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * and it is neither -1 nor +1 -- so 'a' cannot be prime */ 44695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 44795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 44895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langleystatic BN_ULONG get_word(const BIGNUM *bn) { 45027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (bn->top == 1) { 45127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley return bn->d[0]; 45227ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 45327ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley return 0; 45427ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley} 45527ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley 45695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int probable_prime(BIGNUM *rnd, int bits) { 45795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int i; 45895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley uint16_t mods[NUMPRIMES]; 45927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley BN_ULONG delta; 46027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 46127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley char is_single_word = bits <= BN_BITS2; 46295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 46395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyagain: 46495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rand(rnd, bits, 1, 1)) { 46595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 46695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 46795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 46827ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley /* we now have a random number 'rnd' to test. */ 46995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 1; i < NUMPRIMES; i++) { 47095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mods[i] = (uint16_t)BN_mod_word(rnd, (BN_ULONG)primes[i]); 47195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 47227ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley /* If bits is so small that it fits into a single word then we 47327ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * additionally don't want to exceed that many bits. */ 47427ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (is_single_word) { 47527ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley BN_ULONG size_limit = (((BN_ULONG)1) << bits) - get_word(rnd) - 1; 47627ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (size_limit < maxdelta) { 47727ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley maxdelta = size_limit; 47827ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 47927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 48095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley delta = 0; 48195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 48295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyloop: 48327ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (is_single_word) { 48427ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley BN_ULONG rnd_word = get_word(rnd); 48527ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley 48627ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley /* In the case that the candidate prime is a single word then 48727ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * we check that: 48827ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * 1) It's greater than primes[i] because we shouldn't reject 48927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * 3 as being a prime number because it's a multiple of 49027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * three. 49127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * 2) That it's not a multiple of a known prime. We don't 49227ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * check that rnd-1 is also coprime to all the known 49327ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * primes because there aren't many small primes where 49427ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * that's true. */ 49527ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { 49627ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if ((mods[i] + delta) % primes[i] == 0) { 49727ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley delta += 2; 49827ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (delta > maxdelta) 49927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley goto again; 50027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley goto loop; 50127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 50227ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 50327ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } else { 50427ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley for (i = 1; i < NUMPRIMES; i++) { 50527ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley /* check that rnd is not a prime and also 50627ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley * that gcd(rnd-1,primes) == 1 (except for 2) */ 50727ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (((mods[i] + delta) % primes[i]) <= 1) { 50827ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley delta += 2; 50927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (delta > maxdelta) 51027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley goto again; 51127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley goto loop; 51295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 51695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add_word(rnd, delta)) { 51795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 51895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51927ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley if (BN_num_bits(rnd) != bits) { 52027ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley goto again; 52127ae9ed7748d84fb84b4802958cbecaa879d4298Adam Langley } 52295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 52395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 52495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 52595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 52695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 52795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *rem, BN_CTX *ctx) { 52895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int i, ret = 0; 52995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *t1; 53095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 53195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 53295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if ((t1 = BN_CTX_get(ctx)) == NULL) { 53395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 53495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 53595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 53695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rand(rnd, bits, 0, 1)) { 53795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 53895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 53995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 54095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* we need ((rnd-rem) % add) == 0 */ 54195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 54295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mod(t1, rnd, add, ctx)) { 54395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 54495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 54595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(rnd, rnd, t1)) { 54695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 54795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 54895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (rem == NULL) { 54995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add_word(rnd, 1)) { 55095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 55195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 55295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 55395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(rnd, rnd, rem)) { 55495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 55595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 55695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 55795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* we now have a random number 'rand' to test. */ 55895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 55995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyloop: 56095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 1; i < NUMPRIMES; i++) { 56195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* check that rnd is a prime */ 56295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { 56395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(rnd, rnd, add)) { 56495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 56595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 56695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto loop; 56795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 56895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 56995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 57095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 1; 57195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 57295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 57395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 57495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 57595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 57695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 57795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 57895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *rem, BN_CTX *ctx) { 57995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int i, ret = 0; 58095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *t1, *qadd, *q; 58195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 58295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley bits--; 58395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 58495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t1 = BN_CTX_get(ctx); 58595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley q = BN_CTX_get(ctx); 58695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley qadd = BN_CTX_get(ctx); 58795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (qadd == NULL) { 58895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 58995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 59095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 59195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(qadd, padd)) { 59295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 59395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 59495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 59595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rand(q, bits, 0, 1)) { 59695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 59795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 59895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 59995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* we need ((rnd-rem) % add) == 0 */ 60095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mod(t1, q, qadd, ctx)) { 60195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 60295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 60395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 60495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(q, q, t1)) { 60595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 60695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 60795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 60895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (rem == NULL) { 60995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add_word(q, 1)) { 61095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 61195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 61295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 61395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(t1, rem)) { 61495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 61595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 61695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(q, q, t1)) { 61795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 61895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 61995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 62095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 62195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* we now have a random number 'rand' to test. */ 62295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift1(p, q)) { 62395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 62495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 62595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add_word(p, 1)) { 62695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 62795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 62895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 62995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyloop: 63095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 1; i < NUMPRIMES; i++) { 63195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* check that p and q are prime */ 63295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* check that for p and q 63395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * gcd(p-1,primes) == 1 (except for 2) */ 63495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) || 63595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) { 63695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(p, p, padd)) { 63795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 63895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 63995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(q, q, qadd)) { 64095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 64195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 64295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto loop; 64395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 64495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 64595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 64695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 1; 64795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 64895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 64995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 65095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 65195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 65295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 65395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic const uint16_t primes[NUMPRIMES] = { 65495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 65595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 65695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 65795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 65895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 65995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 66095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 66195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 66295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 66395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 66495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 66595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 66695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 66795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 66895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 66995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 67095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 67195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 67295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 67395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 67495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 67595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 67695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 67795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 67895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 67995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 68095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 68195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 68295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 68395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 68495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 68595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 68695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 68795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 68895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 68995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 69095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 69195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 69295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 69395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 69495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 69595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 69695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 69795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 69895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 69995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 70095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 70195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 70295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 70395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 70495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 70595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 70695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 70795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 70895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 70995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 71095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 71195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 71295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 71395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 71495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 71595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 71695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 71795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 71895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 71995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 72095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 72195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 72295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 72395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 72495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 72595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 72695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 72795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 72895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 72995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 73095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 73195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 73295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 73395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 73495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 73595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 73695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 73795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 73895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 73995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 74095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 74195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 74295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 74395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 74495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 74595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 74695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 74795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 74895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 74995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 75095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 75195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 75295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 75395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 75495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 75595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 75695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 75795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 75895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 75995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 76095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 76195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 76295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 76395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 76495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 76595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 76695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 76795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 76895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 76995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 77095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 77195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 77295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 77395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 77495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 77595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 77695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 77795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 77895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 77995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 78095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 78195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 78295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 78395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 78495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 78595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 78695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 78795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 78895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 78995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 79095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 79195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 79295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 79395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 79495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 79595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 79695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 79795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 79895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 79995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 80095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 80195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 80295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 80395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 80495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 80595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 80695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 80795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 80895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 80995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 81095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 81195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 81295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 81395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 81495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 81595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 81695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 81795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 81895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 81995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 82095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 82195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 82295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 82395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 82495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 82595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 82695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 82795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 82895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 82995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 83095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 83195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 83295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 83395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 83495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 83595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401, 83695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491, 83795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 83895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 83995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 84095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17851, 17863, }; 841