1656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* crypto/bn/bn_gcd.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 "cryptlib.h" 113656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "bn_lcl.h" 114656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 115656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic BIGNUM *euclid(BIGNUM *a, BIGNUM *b); 116656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 117656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) 118656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 119656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *a,*b,*t; 120656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int ret=0; 121656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 122656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(in_a); 123656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(in_b); 124656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 125656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 126656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a = BN_CTX_get(ctx); 127656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b = BN_CTX_get(ctx); 128656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (a == NULL || b == NULL) goto err; 129656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 130656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(a,in_a) == NULL) goto err; 131656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(b,in_b) == NULL) goto err; 132656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a->neg = 0; 133656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b->neg = 0; 134656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 135656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; } 136656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t=euclid(a,b); 137656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t == NULL) goto err; 138656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 139656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(r,t) == NULL) goto err; 140656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=1; 141656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 142656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 143656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(r); 144656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 145656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 146656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 147656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic BIGNUM *euclid(BIGNUM *a, BIGNUM *b) 148656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 149656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t; 150656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int shifts=0; 151656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 152656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(a); 153656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(b); 154656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 155656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 0 <= b <= a */ 156656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_zero(b)) 157656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 158656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 0 < b <= a */ 159656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 160656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_odd(a)) 161656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 162656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_odd(b)) 163656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 164656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(a,a,b)) goto err; 165656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(a,a)) goto err; 166656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(a,b) < 0) 167656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { t=a; a=b; b=t; } 168656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 169656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else /* a odd - b even */ 170656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 171656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(b,b)) goto err; 172656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(a,b) < 0) 173656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { t=a; a=b; b=t; } 174656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 175656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 176656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else /* a is even */ 177656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 178656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_odd(b)) 179656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 180656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(a,a)) goto err; 181656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_cmp(a,b) < 0) 182656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { t=a; a=b; b=t; } 183656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 184656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else /* a even - b even */ 185656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 186656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(a,a)) goto err; 187656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(b,b)) goto err; 188656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project shifts++; 189656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 190656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 191656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 0 <= b <= a */ 192656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 193656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 194656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (shifts) 195656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 196656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_lshift(a,a,shifts)) goto err; 197656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 198656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(a); 199656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(a); 200656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 201656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(NULL); 202656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 203656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 204656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 205656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* solves ax == 1 (mod n) */ 206656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 207656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); 20804ef91b390dfcc6125913e2f2af502d23d7a5112Brian Carlstrom 209656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source ProjectBIGNUM *BN_mod_inverse(BIGNUM *in, 210656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 211656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 212656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; 213656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *ret=NULL; 214656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int sign; 215656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 216656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) 217656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 218656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return BN_mod_inverse_no_branch(in, a, n, ctx); 219656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 220656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 221656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(a); 222656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(n); 223656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 224656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 225656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A = BN_CTX_get(ctx); 226656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project B = BN_CTX_get(ctx); 227656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project X = BN_CTX_get(ctx); 228656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project D = BN_CTX_get(ctx); 229656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project M = BN_CTX_get(ctx); 230656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project Y = BN_CTX_get(ctx); 231656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project T = BN_CTX_get(ctx); 232656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (T == NULL) goto err; 233656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 234656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (in == NULL) 235656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project R=BN_new(); 236656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 237656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project R=in; 238656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (R == NULL) goto err; 239656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 240656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_one(X); 241656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_zero(Y); 242656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(B,a) == NULL) goto err; 243656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(A,n) == NULL) goto err; 244656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A->neg = 0; 245656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (B->neg || (BN_ucmp(B, A) >= 0)) 246656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 247656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_nnmod(B, B, A, ctx)) goto err; 248656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 249656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project sign = -1; 250656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* From B = a mod |n|, A = |n| it follows that 251656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 252656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 <= B < A, 253656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * -sign*X*a == B (mod |n|), 254656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|). 255656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 256656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 257656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) 258656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 259656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Binary inversion algorithm; requires odd modulus. 260656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This is faster than the general algorithm if the modulus 261656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * is sufficiently small (about 400 .. 500 bits on 32-bit 262656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sytems, but much more on 64-bit systems) */ 263656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int shift; 264656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 265656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_zero(B)) 266656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 267656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 268656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 < B < |n|, 269656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 < A <= |n|, 270656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (1) -sign*X*a == B (mod |n|), 271656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (2) sign*Y*a == A (mod |n|) 272656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 273656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 274656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Now divide B by the maximum possible power of two in the integers, 275656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * and divide X by the same value mod |n|. 276656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * When we're done, (1) still holds. */ 277656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project shift = 0; 278656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_bit_set(B, shift)) /* note that 0 < B */ 279656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 280656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project shift++; 281656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 282656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_odd(X)) 283656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 284656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_uadd(X, X, n)) goto err; 285656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 286656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* now X is even, so we can easily divide it by two */ 287656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(X, X)) goto err; 288656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 289656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (shift > 0) 290656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 291656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift(B, B, shift)) goto err; 292656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 293656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 294656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 295656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Same for A and Y. Afterwards, (2) still holds. */ 296656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project shift = 0; 297656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_bit_set(A, shift)) /* note that 0 < A */ 298656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 299656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project shift++; 300656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 301656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_odd(Y)) 302656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 303656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_uadd(Y, Y, n)) goto err; 304656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 305656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* now Y is even */ 306656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift1(Y, Y)) goto err; 307656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 308656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (shift > 0) 309656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 310656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift(A, A, shift)) goto err; 311656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 312656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 313656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 314656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* We still have (1) and (2). 315656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Both A and B are odd. 316656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The following computations ensure that 317656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 318656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 <= B < |n|, 319656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 < A < |n|, 320656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (1) -sign*X*a == B (mod |n|), 321656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (2) sign*Y*a == A (mod |n|), 322656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 323656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * and that either A or B is even in the next iteration. 324656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 325656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_ucmp(B, A) >= 0) 326656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 327656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* -sign*(X + Y)*a == B - A (mod |n|) */ 328656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_uadd(X, X, Y)) goto err; 329656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that 330656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * actually makes the algorithm slower */ 331656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_usub(B, B, A)) goto err; 332656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 333656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 334656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 335656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* sign*(X + Y)*a == A - B (mod |n|) */ 336656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_uadd(Y, Y, X)) goto err; 337656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */ 338656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_usub(A, A, B)) goto err; 339656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 340656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 341656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 342656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 343656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 344656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* general inversion algorithm */ 345656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 346656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_zero(B)) 347656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 348656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *tmp; 349656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 350656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 351656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 < B < A, 352656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (*) -sign*X*a == B (mod |n|), 353656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|) 354656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 355656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 356656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* (D, M) := (A/B, A%B) ... */ 357656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_num_bits(A) == BN_num_bits(B)) 358656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 359656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_one(D)) goto err; 360656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(M,A,B)) goto err; 361656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 362656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (BN_num_bits(A) == BN_num_bits(B) + 1) 363656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 364656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* A/B is 1, 2, or 3 */ 365656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_lshift1(T,B)) goto err; 366656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_ucmp(A,T) < 0) 367656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 368656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* A < 2*B, so D=1 */ 369656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_one(D)) goto err; 370656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(M,A,B)) goto err; 371656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 372656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 373656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 374656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* A >= 2*B, so D=2 or D=3 */ 375656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(M,A,T)) goto err; 376656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */ 377656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_ucmp(A,D) < 0) 378656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 379656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* A < 3*B, so D=2 */ 380656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_set_word(D,2)) goto err; 381656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* M (= A - 2*B) already has the correct value */ 382656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 383656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 384656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 385656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* only D=3 remains */ 386656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_set_word(D,3)) goto err; 387656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* currently M = A - 2*B, but we need M = A - 3*B */ 388656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(M,M,B)) goto err; 389656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 390656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 391656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 392656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 393656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 394656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_div(D,M,A,B,ctx)) goto err; 395656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 396656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 397656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Now 398656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * A = D*B + M; 399656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * thus we have 400656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (**) sign*Y*a == D*B + M (mod |n|). 401656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 402656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 403656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project tmp=A; /* keep the BIGNUM object, the value does not matter */ 404656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 405656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* (A, B) := (B, A mod B) ... */ 406656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A=B; 407656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project B=M; 408656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* ... so we have 0 <= B < A again */ 409656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 410656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Since the former M is now B and the former B is now A, 411656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (**) translates into 412656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == D*A + B (mod |n|), 413656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * i.e. 414656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a - D*A == B (mod |n|). 415656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Similarly, (*) translates into 416656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * -sign*X*a == A (mod |n|). 417656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 418656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Thus, 419656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a + D*sign*X*a == B (mod |n|), 420656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * i.e. 421656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*(Y + D*X)*a == B (mod |n|). 422656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 423656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 424656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * -sign*X*a == B (mod |n|), 425656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|). 426656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Note that X and Y stay non-negative all the time. 427656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 428656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 429656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* most of the time D is very small, so we can optimize tmp := D*X+Y */ 430656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_one(D)) 431656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 432656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(tmp,X,Y)) goto err; 433656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 434656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 435656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 436656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_word(D,2)) 437656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 438656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_lshift1(tmp,X)) goto err; 439656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 440656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (BN_is_word(D,4)) 441656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 442656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_lshift(tmp,X,2)) goto err; 443656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 444656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (D->top == 1) 445656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 446656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_copy(tmp,X)) goto err; 447656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mul_word(tmp,D->d[0])) goto err; 448656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 449656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 450656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 451656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mul(tmp,D,X,ctx)) goto err; 452656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 453656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(tmp,tmp,Y)) goto err; 454656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 455656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 456656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project M=Y; /* keep the BIGNUM object, the value does not matter */ 457656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project Y=X; 458656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project X=tmp; 459656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project sign = -sign; 460656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 461656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 462656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 463656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 464656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The while loop (Euclid's algorithm) ends when 465656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * A == gcd(a,n); 466656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * we have 467656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|), 468656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * where Y is non-negative. 469656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 470656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 471656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (sign < 0) 472656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 473656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(Y,n,Y)) goto err; 474656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 475656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Now Y*a == A (mod |n|). */ 476656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 477656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 478656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_one(A)) 479656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 480656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Y*a == 1 (mod |n|) */ 481656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!Y->neg && BN_ucmp(Y,n) < 0) 482656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 483656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_copy(R,Y)) goto err; 484656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 485656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 486656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 487656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_nnmod(R,Y,n,ctx)) goto err; 488656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 489656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 490656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 491656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 492656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE); 493656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 494656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 495656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=R; 496656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 497656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((ret == NULL) && (in == NULL)) BN_free(R); 498656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 499656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(ret); 500656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 501656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 502656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 503656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 504656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. 505656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * It does not contain branches that may leak sensitive information. 506656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 507656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectstatic BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 508656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 509656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 510656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; 511656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM local_A, local_B; 512656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *pA, *pB; 513656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *ret=NULL; 514656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int sign; 515656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 516656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(a); 517656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(n); 518656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 519656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 520656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A = BN_CTX_get(ctx); 521656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project B = BN_CTX_get(ctx); 522656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project X = BN_CTX_get(ctx); 523656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project D = BN_CTX_get(ctx); 524656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project M = BN_CTX_get(ctx); 525656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project Y = BN_CTX_get(ctx); 526656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project T = BN_CTX_get(ctx); 527656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (T == NULL) goto err; 528656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 529656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (in == NULL) 530656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project R=BN_new(); 531656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 532656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project R=in; 533656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (R == NULL) goto err; 534656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 535656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_one(X); 536656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_zero(Y); 537656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(B,a) == NULL) goto err; 538656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_copy(A,n) == NULL) goto err; 539656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A->neg = 0; 540656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 541656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (B->neg || (BN_ucmp(B, A) >= 0)) 542656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 543656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 544656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * BN_div_no_branch will be called eventually. 545656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 546656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project pB = &local_B; 547656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_with_flags(pB, B, BN_FLG_CONSTTIME); 548656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_nnmod(B, pB, A, ctx)) goto err; 549656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 550656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project sign = -1; 551656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* From B = a mod |n|, A = |n| it follows that 552656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 553656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 <= B < A, 554656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * -sign*X*a == B (mod |n|), 555656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|). 556656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 557656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 558656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (!BN_is_zero(B)) 559656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 560656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *tmp; 561656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 562656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 563656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 0 < B < A, 564656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (*) -sign*X*a == B (mod |n|), 565656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|) 566656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 567656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 568656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 569656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * BN_div_no_branch will be called eventually. 570656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 571656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project pA = &local_A; 572656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_with_flags(pA, A, BN_FLG_CONSTTIME); 573656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 574656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* (D, M) := (A/B, A%B) ... */ 575656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_div(D,M,pA,B,ctx)) goto err; 576656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 577656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Now 578656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * A = D*B + M; 579656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * thus we have 580656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (**) sign*Y*a == D*B + M (mod |n|). 581656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 582656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 583656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project tmp=A; /* keep the BIGNUM object, the value does not matter */ 584656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 585656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* (A, B) := (B, A mod B) ... */ 586656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project A=B; 587656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project B=M; 588656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* ... so we have 0 <= B < A again */ 589656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 590656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Since the former M is now B and the former B is now A, 591656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (**) translates into 592656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == D*A + B (mod |n|), 593656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * i.e. 594656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a - D*A == B (mod |n|). 595656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Similarly, (*) translates into 596656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * -sign*X*a == A (mod |n|). 597656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 598656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Thus, 599656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a + D*sign*X*a == B (mod |n|), 600656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * i.e. 601656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*(Y + D*X)*a == B (mod |n|). 602656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 603656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 604656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * -sign*X*a == B (mod |n|), 605656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|). 606656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Note that X and Y stay non-negative all the time. 607656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 608656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 609656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mul(tmp,D,X,ctx)) goto err; 610656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add(tmp,tmp,Y)) goto err; 611656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 612656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project M=Y; /* keep the BIGNUM object, the value does not matter */ 613656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project Y=X; 614656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project X=tmp; 615656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project sign = -sign; 616656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 617656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 618656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 619656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The while loop (Euclid's algorithm) ends when 620656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * A == gcd(a,n); 621656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * we have 622656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * sign*Y*a == A (mod |n|), 623656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * where Y is non-negative. 624656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 625656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 626656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (sign < 0) 627656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 628656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_sub(Y,n,Y)) goto err; 629656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 630656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Now Y*a == A (mod |n|). */ 631656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 632656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_is_one(A)) 633656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 634656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Y*a == 1 (mod |n|) */ 635656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!Y->neg && BN_ucmp(Y,n) < 0) 636656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 637656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_copy(R,Y)) goto err; 638656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 639656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 640656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 641656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_nnmod(R,Y,n,ctx)) goto err; 642656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 643656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 644656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 645656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 646656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE); 647656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 648656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 649656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=R; 650656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 651656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((ret == NULL) && (in == NULL)) BN_free(R); 652656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 653656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(ret); 654656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 655656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 656