195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * All rights reserved. 395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This package is an SSL implementation written 595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * by Eric Young (eay@cryptsoft.com). 695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The implementation was written so as to conform with Netscapes SSL. 795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This library is free for commercial and non-commercial use as long as 995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the following conditions are aheared to. The following conditions 1095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * apply to all code found in this distribution, be it the RC4, RSA, 1195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * included with this distribution is covered by the same copyright terms 1395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 1595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Copyright remains Eric Young's, and as such any Copyright notices in 1695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the code are not to be removed. 1795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * If this package is used in a product, Eric Young should be given attribution 1895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * as the author of the parts of the library used. 1995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This can be in the form of a textual message at program startup or 2095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * in documentation (online or textual) provided with the package. 2195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 2295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Redistribution and use in source and binary forms, with or without 2395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * modification, are permitted provided that the following conditions 2495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * are met: 2595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 1. Redistributions of source code must retain the copyright 2695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer. 2795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 2. Redistributions in binary form must reproduce the above copyright 2895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer in the 2995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * documentation and/or other materials provided with the distribution. 3095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 3. All advertising materials mentioning features or use of this software 3195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * must display the following acknowledgement: 3295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes cryptographic software written by 3395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Eric Young (eay@cryptsoft.com)" 3495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The word 'cryptographic' can be left out if the rouines from the library 3595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * being used are not cryptographic related :-). 3695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 4. If you include any Windows specific code (or a derivative thereof) from 3795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the apps directory (application code) you must include an acknowledgement: 3895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 3995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 4095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 4995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * SUCH DAMAGE. 5195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 5295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The licence and distribution terms for any publically available version or 5395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * derivative of this code cannot be changed. i.e. this code cannot simply be 5495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * copied and put under another distribution licence 5595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * [including the GNU Public Licence.] 5695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 5795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* ==================================================================== 5895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 5995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Redistribution and use in source and binary forms, with or without 6195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * modification, are permitted provided that the following conditions 6295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * are met: 6395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 1. Redistributions of source code must retain the above copyright 6595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer. 6695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 2. Redistributions in binary form must reproduce the above copyright 6895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * notice, this list of conditions and the following disclaimer in 6995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * the documentation and/or other materials provided with the 7095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * distribution. 7195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 7295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 3. All advertising materials mentioning features or use of this 7395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * software must display the following acknowledgment: 7495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes software developed by the OpenSSL Project 7595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 7695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 7795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 7895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * endorse or promote products derived from this software without 7995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * prior written permission. For written permission, please contact 8095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * openssl-core@openssl.org. 8195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 8295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 5. Products derived from this software may not be called "OpenSSL" 8395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * nor may "OpenSSL" appear in their names without prior written 8495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * permission of the OpenSSL Project. 8595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 8695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 6. Redistributions of any form whatsoever must retain the following 8795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * acknowledgment: 8895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "This product includes software developed by the OpenSSL Project 8995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 9095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 9195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 9295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 9395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 9495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 9595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 9695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 9795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 9895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 9995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 10095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 10195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 10295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * OF THE POSSIBILITY OF SUCH DAMAGE. 10395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * ==================================================================== 10495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 10595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This product includes cryptographic software written by Eric Young 10695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (eay@cryptsoft.com). This product includes software written by Tim 10795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Hudson (tjh@cryptsoft.com). */ 10895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 10995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include <openssl/bn.h> 11095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include <openssl/err.h> 11295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include "internal.h" 11495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic BIGNUM *euclid(BIGNUM *a, BIGNUM *b) { 11695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *t; 11795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int shifts = 0; 11895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 0 <= b <= a */ 12095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_zero(b)) { 12195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 0 < b <= a */ 12295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_odd(a)) { 12495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_odd(b)) { 12595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(a, a, b)) { 12695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 12795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 12895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(a, a)) { 12995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 13095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 13195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(a, b) < 0) { 13295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = a; 13395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley a = b; 13495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley b = t; 13595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 13695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 13795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* a odd - b even */ 13895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(b, b)) { 13995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 14095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 14195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(a, b) < 0) { 14295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = a; 14395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley a = b; 14495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley b = t; 14595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 14695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 14795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 14895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* a is even */ 14995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_odd(b)) { 15095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(a, a)) { 15195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 15295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 15395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(a, b) < 0) { 15495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = a; 15595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley a = b; 15695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley b = t; 15795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 15895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 15995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* a even - b even */ 16095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(a, a)) { 16195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 16295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 16395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(b, b)) { 16495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 16595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 16695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley shifts++; 16795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 16895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 16995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 0 <= b <= a */ 17095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 17195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (shifts) { 17395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift(a, a, shifts)) { 17495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 17595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 17695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 17795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return a; 17995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 18095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 18195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return NULL; 18295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 18395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 18495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) { 18595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *a, *b, *t; 18695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int ret = 0; 18795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 18895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 18995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley a = BN_CTX_get(ctx); 19095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley b = BN_CTX_get(ctx); 19195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 19295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (a == NULL || b == NULL) { 19395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 19495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 19595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(a, in_a) == NULL) { 19695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 19795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 19895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(b, in_b) == NULL) { 19995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 20095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 20195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 20295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley a->neg = 0; 20395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley b->neg = 0; 20495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 20595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_cmp(a, b) < 0) { 20695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = a; 20795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley a = b; 20895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley b = t; 20995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = euclid(a, b); 21195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (t == NULL) { 21295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 21395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 21595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(r, t) == NULL) { 21695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 21795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 1; 21995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 22095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 22195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 22295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 22395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 22495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 22595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* solves ax == 1 (mod n) */ 22695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic BIGNUM *BN_mod_inverse_no_branch(BIGNUM *out, const BIGNUM *a, 22795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *n, BN_CTX *ctx); 22895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 22995c29f3cd1f6c08c6c0927868683392eea727ccAdam LangleyBIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, 23095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX *ctx) { 23195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 23295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *ret = NULL; 23395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int sign; 23495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 23595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if ((a->flags & BN_FLG_CONSTTIME) != 0 || 23695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (n->flags & BN_FLG_CONSTTIME) != 0) { 23795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return BN_mod_inverse_no_branch(out, a, n, ctx); 23895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 23995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 24095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 24195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A = BN_CTX_get(ctx); 24295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley B = BN_CTX_get(ctx); 24395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley X = BN_CTX_get(ctx); 24495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley D = BN_CTX_get(ctx); 24595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley M = BN_CTX_get(ctx); 24695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Y = BN_CTX_get(ctx); 24795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley T = BN_CTX_get(ctx); 24895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (T == NULL) { 24995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 25095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 25295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (out == NULL) { 25395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley R = BN_new(); 25495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 25595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley R = out; 25695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (R == NULL) { 25895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 25995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 26195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_one(X); 26295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_zero(Y); 26395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(B, a) == NULL) { 26495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 26595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(A, n) == NULL) { 26795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 26895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A->neg = 0; 27095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (B->neg || (BN_ucmp(B, A) >= 0)) { 27195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_nnmod(B, B, A, ctx)) { 27295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 27395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 27495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 27595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley sign = -1; 27695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* From B = a mod |n|, A = |n| it follows that 27795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 27895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 <= B < A, 27995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * -sign*X*a == B (mod |n|), 28095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|). 28195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 28295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 28395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) { 28495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Binary inversion algorithm; requires odd modulus. 28595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * This is faster than the general algorithm if the modulus 28695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * is sufficiently small (about 400 .. 500 bits on 32-bit 28795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sytems, but much more on 64-bit systems) */ 28895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int shift; 28995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 29095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_zero(B)) { 29195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 0 < B < |n|, 29295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 < A <= |n|, 29395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (1) -sign*X*a == B (mod |n|), 29495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (2) sign*Y*a == A (mod |n|) */ 29595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 29695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Now divide B by the maximum possible power of two in the integers, 29795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * and divide X by the same value mod |n|. 29895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * When we're done, (1) still holds. */ 29995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley shift = 0; 30095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_bit_set(B, shift)) { 30195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* note that 0 < B */ 30295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley shift++; 30395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 30495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_odd(X)) { 30595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_uadd(X, X, n)) { 30695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 30795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 30895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 30995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* now X is even, so we can easily divide it by two */ 31095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(X, X)) { 31195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 31295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 31395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 31495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (shift > 0) { 31595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift(B, B, shift)) { 31695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 31795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 31895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 31995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 32095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Same for A and Y. Afterwards, (2) still holds. */ 32195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley shift = 0; 32295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_bit_set(A, shift)) { 32395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* note that 0 < A */ 32495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley shift++; 32595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 32695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_odd(Y)) { 32795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_uadd(Y, Y, n)) { 32895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 32995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 33095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 33195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* now Y is even */ 33295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift1(Y, Y)) { 33395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 33495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 33595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 33695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (shift > 0) { 33795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_rshift(A, A, shift)) { 33895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 33995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 34095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 34195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 34295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* We still have (1) and (2). 34395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Both A and B are odd. 34495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The following computations ensure that 34595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 34695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 <= B < |n|, 34795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 < A < |n|, 34895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (1) -sign*X*a == B (mod |n|), 34995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (2) sign*Y*a == A (mod |n|), 35095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 35195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * and that either A or B is even in the next iteration. */ 35295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_ucmp(B, A) >= 0) { 35395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* -sign*(X + Y)*a == B - A (mod |n|) */ 35495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_uadd(X, X, Y)) { 35595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 35695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 35795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that 35895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * actually makes the algorithm slower */ 35995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_usub(B, B, A)) { 36095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 36195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 36295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 36395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* sign*(X + Y)*a == A - B (mod |n|) */ 36495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_uadd(Y, Y, X)) { 36595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 36695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 36795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */ 36895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_usub(A, A, B)) { 36995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 37095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 37195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 37295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 37395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 37495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* general inversion algorithm */ 37595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 37695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_zero(B)) { 37795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *tmp; 37895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 37995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 38095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 < B < A, 38195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (*) -sign*X*a == B (mod |n|), 38295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|) */ 38395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 38495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* (D, M) := (A/B, A%B) ... */ 38595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_num_bits(A) == BN_num_bits(B)) { 38695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_one(D)) { 38795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 38895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 38995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(M, A, B)) { 39095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 39195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 39295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if (BN_num_bits(A) == BN_num_bits(B) + 1) { 39395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* A/B is 1, 2, or 3 */ 39495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift1(T, B)) { 39595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 39695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 39795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_ucmp(A, T) < 0) { 39895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* A < 2*B, so D=1 */ 39995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_one(D)) { 40095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 40195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 40295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(M, A, B)) { 40395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 40495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 40595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 40695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* A >= 2*B, so D=2 or D=3 */ 40795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(M, A, T)) { 40895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 40995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(D, T, B)) { 41195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; /* use D (:= 3*B) as temp */ 41295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_ucmp(A, D) < 0) { 41495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* A < 3*B, so D=2 */ 41595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_set_word(D, 2)) { 41695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 41795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* M (= A - 2*B) already has the correct value */ 41995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 42095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* only D=3 remains */ 42195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_set_word(D, 3)) { 42295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 42395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 42495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* currently M = A - 2*B, but we need M = A - 3*B */ 42595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(M, M, B)) { 42695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 42795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 42895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 42995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 43095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 43195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_div(D, M, A, B, ctx)) { 43295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 43395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 43495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 43595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 43695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Now 43795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * A = D*B + M; 43895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * thus we have 43995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (**) sign*Y*a == D*B + M (mod |n|). */ 44095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmp = A; /* keep the BIGNUM object, the value does not matter */ 44295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* (A, B) := (B, A mod B) ... */ 44495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A = B; 44595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley B = M; 44695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* ... so we have 0 <= B < A again */ 44795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Since the former M is now B and the former B is now A, 44995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (**) translates into 45095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == D*A + B (mod |n|), 45195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * i.e. 45295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a - D*A == B (mod |n|). 45395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Similarly, (*) translates into 45495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * -sign*X*a == A (mod |n|). 45595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 45695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Thus, 45795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a + D*sign*X*a == B (mod |n|), 45895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * i.e. 45995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*(Y + D*X)*a == B (mod |n|). 46095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 46195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 46295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * -sign*X*a == B (mod |n|), 46395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|). 46495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Note that X and Y stay non-negative all the time. */ 46595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 46695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* most of the time D is very small, so we can optimize tmp := D*X+Y */ 46795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_one(D)) { 46895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(tmp, X, Y)) { 46995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 47095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 47195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 47295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_word(D, 2)) { 47395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift1(tmp, X)) { 47495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 47595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 47695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if (BN_is_word(D, 4)) { 47795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift(tmp, X, 2)) { 47895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 47995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 48095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else if (D->top == 1) { 48195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_copy(tmp, X)) { 48295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 48395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 48495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mul_word(tmp, D->d[0])) { 48595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 48695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 48795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 48895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mul(tmp, D, X, ctx)) { 48995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 49095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 49195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 49295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(tmp, tmp, Y)) { 49395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 49495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 49595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 49695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 49795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley M = Y; /* keep the BIGNUM object, the value does not matter */ 49895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Y = X; 49995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley X = tmp; 50095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley sign = -sign; 50195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 50295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 50395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 50495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* The while loop (Euclid's algorithm) ends when 50595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * A == gcd(a,n); 50695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * we have 50795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|), 50895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * where Y is non-negative. */ 50995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 51095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (sign < 0) { 51195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(Y, n, Y)) { 51295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 51395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Now Y*a == A (mod |n|). */ 51695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 51795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_one(A)) { 51895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Y*a == 1 (mod |n|) */ 51995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!Y->neg && BN_ucmp(Y, n) < 0) { 52095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_copy(R, Y)) { 52195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 52295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 52395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 52495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_nnmod(R, Y, n, ctx)) { 52595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 52695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 52795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 52895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 52995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley OPENSSL_PUT_ERROR(BN, BN_mod_inverse, BN_R_NO_INVERSE); 53095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 53195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 53295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = R; 53395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 53495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 53595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ret == NULL && out == NULL) { 53695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_free(R); 53795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 53895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 53995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 54095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 54195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 54295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. 54395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * It does not contain branches that may leak sensitive information. */ 54495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic BIGNUM *BN_mod_inverse_no_branch(BIGNUM *out, const BIGNUM *a, 54595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *n, BN_CTX *ctx) { 54695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 54795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM local_A, local_B; 54895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *pA, *pB; 54995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *ret = NULL; 55095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int sign; 55195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 55295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 55395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A = BN_CTX_get(ctx); 55495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley B = BN_CTX_get(ctx); 55595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley X = BN_CTX_get(ctx); 55695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley D = BN_CTX_get(ctx); 55795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley M = BN_CTX_get(ctx); 55895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Y = BN_CTX_get(ctx); 55995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley T = BN_CTX_get(ctx); 56095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (T == NULL) { 56195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 56295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 56395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 56495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (out == NULL) { 56595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley R = BN_new(); 56695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 56795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley R = out; 56895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 56995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (R == NULL) { 57095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 57195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 57295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 57395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_one(X); 57495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_zero(Y); 57595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(B, a) == NULL) { 57695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 57795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 57895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(A, n) == NULL) { 57995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 58095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 58195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A->neg = 0; 58295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 58395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (B->neg || (BN_ucmp(B, A) >= 0)) { 58495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 58595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * BN_div_no_branch will be called eventually. 58695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 58795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley pB = &local_B; 58895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_with_flags(pB, B, BN_FLG_CONSTTIME); 58995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_nnmod(B, pB, A, ctx)) 59095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 59195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 59295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley sign = -1; 59395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* From B = a mod |n|, A = |n| it follows that 59495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 59595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 <= B < A, 59695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * -sign*X*a == B (mod |n|), 59795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|). 59895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 59995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 60095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley while (!BN_is_zero(B)) { 60195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *tmp; 60295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 60395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 60495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 0 < B < A, 60595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (*) -sign*X*a == B (mod |n|), 60695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|) 60795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 60895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 60995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 61095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * BN_div_no_branch will be called eventually. 61195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 61295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley pA = &local_A; 61395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_with_flags(pA, A, BN_FLG_CONSTTIME); 61495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 61595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* (D, M) := (A/B, A%B) ... */ 61695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_div(D, M, pA, B, ctx)) { 61795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 61895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 61995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 62095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Now 62195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * A = D*B + M; 62295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * thus we have 62395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (**) sign*Y*a == D*B + M (mod |n|). 62495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 62595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 62695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmp = A; /* keep the BIGNUM object, the value does not matter */ 62795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 62895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* (A, B) := (B, A mod B) ... */ 62995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley A = B; 63095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley B = M; 63195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* ... so we have 0 <= B < A again */ 63295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 63395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Since the former M is now B and the former B is now A, 63495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * (**) translates into 63595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == D*A + B (mod |n|), 63695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * i.e. 63795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a - D*A == B (mod |n|). 63895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Similarly, (*) translates into 63995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * -sign*X*a == A (mod |n|). 64095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 64195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Thus, 64295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a + D*sign*X*a == B (mod |n|), 64395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * i.e. 64495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*(Y + D*X)*a == B (mod |n|). 64595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * 64695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 64795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * -sign*X*a == B (mod |n|), 64895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|). 64995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * Note that X and Y stay non-negative all the time. 65095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 65195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 65295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mul(tmp, D, X, ctx)) { 65395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 65495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 65595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_add(tmp, tmp, Y)) { 65695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 65795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 65895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 65995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley M = Y; /* keep the BIGNUM object, the value does not matter */ 66095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Y = X; 66195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley X = tmp; 66295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley sign = -sign; 66395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 66495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 66595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* 66695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * The while loop (Euclid's algorithm) ends when 66795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * A == gcd(a,n); 66895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * we have 66995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * sign*Y*a == A (mod |n|), 67095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * where Y is non-negative. 67195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley */ 67295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 67395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (sign < 0) { 67495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub(Y, n, Y)) { 67595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 67695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 67795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 67895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Now Y*a == A (mod |n|). */ 67995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 68095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_is_one(A)) { 68195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Y*a == 1 (mod |n|) */ 68295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!Y->neg && BN_ucmp(Y, n) < 0) { 68395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_copy(R, Y)) { 68495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 68595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 68695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 68795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_nnmod(R, Y, n, ctx)) { 68895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 68995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 69095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 69195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 69295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley OPENSSL_PUT_ERROR(BN, BN_mod_inverse_no_branch, BN_R_NO_INVERSE); 69395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 69495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 69595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = R; 69695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 69795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 69895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ret == NULL && out == NULL) { 69995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_free(R); 70095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 70195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 70295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 70395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 70495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 705