1656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* crypto/bn/bn_prime.c */ 2656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * All rights reserved. 4656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 5656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This package is an SSL implementation written 6656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * by Eric Young (eay@cryptsoft.com). 7656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The implementation was written so as to conform with Netscapes SSL. 8656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 9656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This library is free for commercial and non-commercial use as long as 10656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the following conditions are aheared to. The following conditions 11656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * apply to all code found in this distribution, be it the RC4, RSA, 12656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * included with this distribution is covered by the same copyright terms 14656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 16656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Copyright remains Eric Young's, and as such any Copyright notices in 17656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the code are not to be removed. 18656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * If this package is used in a product, Eric Young should be given attribution 19656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * as the author of the parts of the library used. 20656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This can be in the form of a textual message at program startup or 21656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * in documentation (online or textual) provided with the package. 22656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 23656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Redistribution and use in source and binary forms, with or without 24656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * modification, are permitted provided that the following conditions 25656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * are met: 26656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 1. Redistributions of source code must retain the copyright 27656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer. 28656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 29656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer in the 30656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * documentation and/or other materials provided with the distribution. 31656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 3. All advertising materials mentioning features or use of this software 32656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * must display the following acknowledgement: 33656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes cryptographic software written by 34656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Eric Young (eay@cryptsoft.com)" 35656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The word 'cryptographic' can be left out if the rouines from the library 36656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * being used are not cryptographic related :-). 37656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 4. If you include any Windows specific code (or a derivative thereof) from 38656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the apps directory (application code) you must include an acknowledgement: 39656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 41656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * SUCH DAMAGE. 52656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 53656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The licence and distribution terms for any publically available version or 54656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * derivative of this code cannot be changed. i.e. this code cannot simply be 55656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * copied and put under another distribution licence 56656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * [including the GNU Public Licence.] 57656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 58656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* ==================================================================== 59656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 60656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 61656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Redistribution and use in source and binary forms, with or without 62656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * modification, are permitted provided that the following conditions 63656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * are met: 64656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 65656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 1. Redistributions of source code must retain the above copyright 66656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer. 67656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 68656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 69656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer in 70656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the documentation and/or other materials provided with the 71656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * distribution. 72656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 73656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 3. All advertising materials mentioning features or use of this 74656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * software must display the following acknowledgment: 75656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes software developed by the OpenSSL Project 76656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 77656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 78656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 79656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * endorse or promote products derived from this software without 80656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * prior written permission. For written permission, please contact 81656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * openssl-core@openssl.org. 82656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 83656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 5. Products derived from this software may not be called "OpenSSL" 84656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * nor may "OpenSSL" appear in their names without prior written 85656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * permission of the OpenSSL Project. 86656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 87656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 6. Redistributions of any form whatsoever must retain the following 88656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * acknowledgment: 89656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes software developed by the OpenSSL Project 90656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 91656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 92656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 93656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 95656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 96656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 97656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 98656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 99656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 100656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 101656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 102656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 103656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OF THE POSSIBILITY OF SUCH DAMAGE. 104656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ==================================================================== 105656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 106656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This product includes cryptographic software written by Eric Young 107656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (eay@cryptsoft.com). This product includes software written by Tim 108656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Hudson (tjh@cryptsoft.com). 109656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 110656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 111656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 112656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include <stdio.h> 113656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include <time.h> 114656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "cryptlib.h" 115656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "bn_lcl.h" 116656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include <openssl/rand.h> 117656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 118656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* NB: these functions have been "upgraded", the deprecated versions (which are 119656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * compatibility wrappers using these functions) are in bn_depr.c. 120656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * - Geoff 121656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 122656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 123656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* The quick sieve algorithm approach to weeding out primes is 124656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Philip Zimmermann's, as implemented in PGP. I have had a read of 125656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * his comments and implemented my own version. 126656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 127656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "bn_prime.h" 128656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 129656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 130656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); 131656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int probable_prime(BIGNUM *rnd, int bits); 132656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int probable_prime_dh(BIGNUM *rnd, int bits, 133656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); 134656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int probable_prime_dh_safe(BIGNUM *rnd, int bits, 135656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); 136656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 137656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_GENCB_call(BN_GENCB *cb, int a, int b) 138656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 139656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* No callback means continue */ 140656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!cb) return 1; 141656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch(cb->ver) 142656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 143656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 144656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Deprecated-style callbacks */ 145656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!cb->cb.cb_1) 146656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 1; 147656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project cb->cb.cb_1(a, b, cb->arg); 148656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 1; 149656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 150656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* New-style callbacks */ 151656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return cb->cb.cb_2(a, b, cb); 152656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project default: 153656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 154656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 155656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Unrecognised callback type */ 156656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 0; 157656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 158656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 159656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, 160656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) 161656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 162656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t; 163656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int found=0; 164656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i,j,c1=0; 165656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX *ctx; 166656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int checks = BN_prime_checks_for_size(bits); 167656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 168656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ctx=BN_CTX_new(); 169656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ctx == NULL) goto err; 170656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 171656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = BN_CTX_get(ctx); 172656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!t) goto err; 173656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectloop: 174656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* make a random number and set the top and bottom bits */ 175656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (add == NULL) 176656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 177656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!probable_prime(ret,bits)) goto err; 178656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 179656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 180656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 181656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (safe) 182656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 183656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!probable_prime_dh_safe(ret,bits,add,rem,ctx)) 184656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 185656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 186656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 187656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 188656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!probable_prime_dh(ret,bits,add,rem,ctx)) 189656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 190656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 191656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 192656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ 193656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!BN_GENCB_call(cb, 0, c1++)) 194656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* aborted */ 195656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 196656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 197656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!safe) 198656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 199656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb); 200656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i == -1) goto err; 201656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i == 0) goto loop; 202656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 203656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 204656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 205656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* for "safe prime" generation, 206656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * check that (p-1)/2 is prime. 207656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Since a prime is odd, We just 208656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * need to divide by 2 */ 209656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(t,ret)) goto err; 210656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 211656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (i=0; i<checks; i++) 212656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 213656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb); 214656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j == -1) goto err; 215656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j == 0) goto loop; 216656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 217656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb); 218656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j == -1) goto err; 219656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j == 0) goto loop; 220656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 221656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!BN_GENCB_call(cb, 2, c1-1)) 222656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 223656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* We have a safe prime test pass */ 224656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 225656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 226656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* we have a prime :-) */ 227656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project found = 1; 228656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 229656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ctx != NULL) 230656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 231656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 232656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_free(ctx); 233656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 234656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(ret); 235656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return found; 236656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 237656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 238656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb) 239656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 240656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); 241656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 242656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 243656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 244656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int do_trial_division, BN_GENCB *cb) 245656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 246656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i, j, ret = -1; 247656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int k; 248656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX *ctx = NULL; 249656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ 250656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_MONT_CTX *mont = NULL; 251656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *A = NULL; 252656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 253656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(a, BN_value_one()) <= 0) 254656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 0; 255656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 256656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (checks == BN_prime_checks) 257656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project checks = BN_prime_checks_for_size(BN_num_bits(a)); 258656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 259656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* first look for small factors */ 260656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_is_odd(a)) 261656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* a is even => a is prime if and only if a == 2 */ 262656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return BN_is_word(a, 2); 263656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (do_trial_division) 264656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 265656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (i = 1; i < NUMPRIMES; i++) 266656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_mod_word(a, primes[i]) == 0) 267656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 0; 268656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!BN_GENCB_call(cb, 1, -1)) 269656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 270656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 271656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 272656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ctx_passed != NULL) 273656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ctx = ctx_passed; 274656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 275656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((ctx=BN_CTX_new()) == NULL) 276656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 277656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 278656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 279656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* A := abs(a) */ 280656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (a->neg) 281656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 282656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t; 283656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((t = BN_CTX_get(ctx)) == NULL) goto err; 284656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_copy(t, a); 285656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t->neg = 0; 286656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A = t; 287656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 288656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 289656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A = a; 290656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A1 = BN_CTX_get(ctx); 291656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A1_odd = BN_CTX_get(ctx); 292656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project check = BN_CTX_get(ctx); 293656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (check == NULL) goto err; 294656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 295656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* compute A1 := A - 1 */ 296656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_copy(A1, A)) 297656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 298656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub_word(A1, 1)) 299656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 300656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_zero(A1)) 301656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 302656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret = 0; 303656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 304656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 305656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 306656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* write A1 as A1_odd * 2^k */ 307656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project k = 1; 308656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_bit_set(A1, k)) 309656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project k++; 310656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift(A1_odd, A1, k)) 311656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 312656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 313656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Montgomery setup for computations mod A */ 314656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project mont = BN_MONT_CTX_new(); 315656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (mont == NULL) 316656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 317656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_MONT_CTX_set(mont, A, ctx)) 318656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 319656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 320656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (i = 0; i < checks; i++) 321656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 322656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_pseudo_rand_range(check, A1)) 323656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 324656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add_word(check, 1)) 325656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 326656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* now 1 <= check < A */ 327656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 328656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j = witness(check, A, A1, A1_odd, k, ctx, mont); 329656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j == -1) goto err; 330656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j) 331656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 332656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=0; 333656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 334656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 335656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(!BN_GENCB_call(cb, 1, i)) 336656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 337656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 338656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=1; 339656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 340656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ctx != NULL) 341656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 342656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 343656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ctx_passed == NULL) 344656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_free(ctx); 345656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 346656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (mont != NULL) 347656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_MONT_CTX_free(mont); 348656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 349656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 350656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 351656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 352656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 353656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) 354656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 355656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ 356656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return -1; 357656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_one(w)) 358656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 0; /* probably prime */ 359656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(w, a1) == 0) 360656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 0; /* w == -1 (mod a), 'a' is probably prime */ 361656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (--k) 362656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 363656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ 364656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return -1; 365656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_one(w)) 366656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 1; /* 'a' is composite, otherwise a previous 'w' would 367656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * have been == -1 (mod 'a') */ 368656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(w, a1) == 0) 369656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 0; /* w == -1 (mod a), 'a' is probably prime */ 370656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 371656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', 372656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * and it is neither -1 nor +1 -- so 'a' cannot be prime */ 373656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(w); 374656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return 1; 375656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 376656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 377656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int probable_prime(BIGNUM *rnd, int bits) 378656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 379656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i; 380656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project prime_t mods[NUMPRIMES]; 381656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG delta,maxdelta; 382656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 383656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectagain: 384656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rand(rnd,bits,1,1)) return(0); 385656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* we now have a random number 'rand' to test. */ 386656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (i=1; i<NUMPRIMES; i++) 387656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]); 388656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project maxdelta=BN_MASK2 - primes[NUMPRIMES-1]; 389656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project delta=0; 390656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project loop: for (i=1; i<NUMPRIMES; i++) 391656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 392656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* check that rnd is not a prime and also 393656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * that gcd(rnd-1,primes) == 1 (except for 2) */ 394656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (((mods[i]+delta)%primes[i]) <= 1) 395656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 396656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project delta+=2; 397656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (delta > maxdelta) goto again; 398656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto loop; 399656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 400656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 401656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add_word(rnd,delta)) return(0); 402656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(rnd); 403656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(1); 404656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 405656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 406656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int probable_prime_dh(BIGNUM *rnd, int bits, 407656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) 408656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 409656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i,ret=0; 410656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t1; 411656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 412656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 413656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; 414656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 415656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rand(rnd,bits,0,1)) goto err; 416656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 417656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* we need ((rnd-rem) % add) == 0 */ 418656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 419656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mod(t1,rnd,add,ctx)) goto err; 420656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(rnd,rnd,t1)) goto err; 421656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (rem == NULL) 422656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { if (!BN_add_word(rnd,1)) goto err; } 423656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 424656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { if (!BN_add(rnd,rnd,rem)) goto err; } 425656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 426656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* we now have a random number 'rand' to test. */ 427656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 428656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project loop: for (i=1; i<NUMPRIMES; i++) 429656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 430656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* check that rnd is a prime */ 431656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1) 432656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 433656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(rnd,rnd,add)) goto err; 434656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto loop; 435656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 436656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 437656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=1; 438656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 439656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 440656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(rnd); 441656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 442656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 443656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 444656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 445656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *rem, BN_CTX *ctx) 446656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 447656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i,ret=0; 448656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t1,*qadd,*q; 449656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 450656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bits--; 451656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 452656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t1 = BN_CTX_get(ctx); 453656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project q = BN_CTX_get(ctx); 454656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project qadd = BN_CTX_get(ctx); 455656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (qadd == NULL) goto err; 456656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 457656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(qadd,padd)) goto err; 458656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 459656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rand(q,bits,0,1)) goto err; 460656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 461656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* we need ((rnd-rem) % add) == 0 */ 462656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mod(t1,q,qadd,ctx)) goto err; 463656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(q,q,t1)) goto err; 464656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (rem == NULL) 465656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { if (!BN_add_word(q,1)) goto err; } 466656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 467656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 468656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(t1,rem)) goto err; 469656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(q,q,t1)) goto err; 470656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 471656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 472656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* we now have a random number 'rand' to test. */ 473656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_lshift1(p,q)) goto err; 474656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add_word(p,1)) goto err; 475656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 476656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project loop: for (i=1; i<NUMPRIMES; i++) 477656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 478656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* check that p and q are prime */ 479656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* check that for p and q 480656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * gcd(p-1,primes) == 1 (except for 2) */ 481656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ( (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) || 482656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project (BN_mod_word(q,(BN_ULONG)primes[i]) == 0)) 483656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 484656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(p,p,padd)) goto err; 485656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(q,q,qadd)) goto err; 486656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto loop; 487656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 488656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 489656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=1; 490656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 491656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 492656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(p); 493656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 494656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 495