1d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * All rights reserved. 3d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This package is an SSL implementation written 5d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * by Eric Young (eay@cryptsoft.com). 6d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The implementation was written so as to conform with Netscapes SSL. 7d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 8d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This library is free for commercial and non-commercial use as long as 9d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the following conditions are aheared to. The following conditions 10d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * apply to all code found in this distribution, be it the RC4, RSA, 11d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * included with this distribution is covered by the same copyright terms 13d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 15d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Copyright remains Eric Young's, and as such any Copyright notices in 16d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the code are not to be removed. 17d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * If this package is used in a product, Eric Young should be given attribution 18d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * as the author of the parts of the library used. 19d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This can be in the form of a textual message at program startup or 20d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * in documentation (online or textual) provided with the package. 21d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 22d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Redistribution and use in source and binary forms, with or without 23d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * modification, are permitted provided that the following conditions 24d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * are met: 25d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 1. Redistributions of source code must retain the copyright 26d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer. 27d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 2. Redistributions in binary form must reproduce the above copyright 28d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer in the 29d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * documentation and/or other materials provided with the distribution. 30d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 3. All advertising materials mentioning features or use of this software 31d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * must display the following acknowledgement: 32d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes cryptographic software written by 33d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Eric Young (eay@cryptsoft.com)" 34d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The word 'cryptographic' can be left out if the rouines from the library 35d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * being used are not cryptographic related :-). 36d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4. If you include any Windows specific code (or a derivative thereof) from 37d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the apps directory (application code) you must include an acknowledgement: 38d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 40d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SUCH DAMAGE. 51d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 52d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The licence and distribution terms for any publically available version or 53d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * derivative of this code cannot be changed. i.e. this code cannot simply be 54d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * copied and put under another distribution licence 55d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * [including the GNU Public Licence.] 56d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 57d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* ==================================================================== 58d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. 59d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 60d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Redistribution and use in source and binary forms, with or without 61d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * modification, are permitted provided that the following conditions 62d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * are met: 63d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 64d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 1. Redistributions of source code must retain the above copyright 65d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer. 66d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 67d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 2. Redistributions in binary form must reproduce the above copyright 68d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer in 69d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the documentation and/or other materials provided with the 70d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * distribution. 71d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 72d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 3. All advertising materials mentioning features or use of this 73d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * software must display the following acknowledgment: 74d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software developed by the OpenSSL Project 75d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 76d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 77d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 78d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * endorse or promote products derived from this software without 79d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * prior written permission. For written permission, please contact 80d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * openssl-core@openssl.org. 81d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 82d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 5. Products derived from this software may not be called "OpenSSL" 83d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * nor may "OpenSSL" appear in their names without prior written 84d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * permission of the OpenSSL Project. 85d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 86d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 6. Redistributions of any form whatsoever must retain the following 87d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * acknowledgment: 88d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software developed by the OpenSSL Project 89d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 90d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 91d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 92d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 93d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 94d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 95d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 96d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 97d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 98d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 99d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 100d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 101d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 102d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OF THE POSSIBILITY OF SUCH DAMAGE. 103d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ==================================================================== 104d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 105d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This product includes cryptographic software written by Eric Young 106d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * (eay@cryptsoft.com). This product includes software written by Tim 107d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Hudson (tjh@cryptsoft.com). */ 108d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 109d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/bn.h> 110d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 111d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <string.h> 112d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 113d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/mem.h> 114d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/thread.h> 115d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 116d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include "internal.h" 117e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley#include "../internal.h" 118d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 119d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 120d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#if !defined(OPENSSL_NO_ASM) && \ 121d9e397b599b13d642138480a28c14db7a136bf0Adam Langley (defined(OPENSSL_X86) || defined(OPENSSL_X86_64)) 122d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#define OPENSSL_BN_ASM_MONT 123d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#endif 124d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 125d9e397b599b13d642138480a28c14db7a136bf0Adam LangleyBN_MONT_CTX *BN_MONT_CTX_new(void) { 126d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_MONT_CTX *ret = OPENSSL_malloc(sizeof(BN_MONT_CTX)); 127d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 128d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ret == NULL) { 129d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return NULL; 130d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 131d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 132d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_MONT_CTX_init(ret); 133d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret->flags = BN_FLG_MALLOCED; 134d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 135d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 136d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 137d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyvoid BN_MONT_CTX_init(BN_MONT_CTX *mont) { 138d9e397b599b13d642138480a28c14db7a136bf0Adam Langley memset(mont, 0, sizeof(BN_MONT_CTX)); 139d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&mont->RR); 140d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&mont->N); 141d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&mont->Ni); 142d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 143d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 144d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyvoid BN_MONT_CTX_free(BN_MONT_CTX *mont) { 145d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (mont == NULL) { 146d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return; 147d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 148d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 149d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&mont->RR); 150d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&mont->N); 151d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&mont->Ni); 152d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (mont->flags & BN_FLG_MALLOCED) { 153d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_free(mont); 154d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 155d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 156d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 157d9e397b599b13d642138480a28c14db7a136bf0Adam LangleyBN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) { 158d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (to == from) { 159d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return to; 160d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 161d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 162d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_copy(&to->RR, &from->RR) || 163d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !BN_copy(&to->N, &from->N) || 164d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !BN_copy(&to->Ni, &from->Ni)) { 165d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return NULL; 166d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 167d9e397b599b13d642138480a28c14db7a136bf0Adam Langley to->ri = from->ri; 168d9e397b599b13d642138480a28c14db7a136bf0Adam Langley to->n0[0] = from->n0[0]; 169d9e397b599b13d642138480a28c14db7a136bf0Adam Langley to->n0[1] = from->n0[1]; 170d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return to; 171d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 172d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 173d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) { 174d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 175d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *Ri, *R; 176d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM tmod; 177d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG buf[2]; 178d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 179d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 180d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Ri = BN_CTX_get(ctx); 181d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (Ri == NULL) { 182d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 183d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 184d9e397b599b13d642138480a28c14db7a136bf0Adam Langley R = &mont->RR; /* grab RR as a temp */ 185d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_copy(&mont->N, mod)) { 186d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; /* Set N */ 187d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 188d9e397b599b13d642138480a28c14db7a136bf0Adam Langley mont->N.neg = 0; 189d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 190d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&tmod); 191d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.d = buf; 192d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.dmax = 2; 193d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.neg = 0; 194d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 195d9e397b599b13d642138480a28c14db7a136bf0Adam Langley mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2; 196d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 197d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2 <= 32) 198d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Only certain BN_BITS2<=32 platforms actually make use of 199d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * n0[1], and we could use the #else case (with a shorter R 200d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * value) for the others. However, currently only the assembler 201d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * files do know which is which. */ 202d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 203d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_zero(R); 204d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_set_bit(R, 2 * BN_BITS2)) { 205d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 206d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 207d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 208d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.top = 0; 209d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if ((buf[0] = mod->d[0])) { 210d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.top = 1; 211d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 212d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if ((buf[1] = mod->top > 1 ? mod->d[1] : 0)) { 213d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.top = 2; 214d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 215d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 216d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_mod_inverse(Ri, R, &tmod, ctx) == NULL) { 217d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 218d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 219d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_lshift(Ri, Ri, 2 * BN_BITS2)) { 220d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; /* R*Ri */ 221d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 222d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(Ri)) { 223d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_sub_word(Ri, 1)) { 224d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 225d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 226d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 227d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* if N mod word size == 1 */ 228d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL) { 229d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 230d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 231d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Ri-- (mod double word size) */ 232d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Ri->neg = 0; 233d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Ri->d[0] = BN_MASK2; 234d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Ri->d[1] = BN_MASK2; 235d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Ri->top = 2; 236d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 237d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 238d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_div(Ri, NULL, Ri, &tmod, ctx)) { 239d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 240d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 241d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Ni = (R*Ri-1)/N, 242d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * keep only couple of least significant words: */ 243d9e397b599b13d642138480a28c14db7a136bf0Adam Langley mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; 244d9e397b599b13d642138480a28c14db7a136bf0Adam Langley mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0; 245d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#else 246d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_zero(R); 247d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_set_bit(R, BN_BITS2)) { 248d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; /* R */ 249d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 250d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 251d9e397b599b13d642138480a28c14db7a136bf0Adam Langley buf[0] = mod->d[0]; /* tmod = N mod word size */ 252d9e397b599b13d642138480a28c14db7a136bf0Adam Langley buf[1] = 0; 253d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmod.top = buf[0] != 0 ? 1 : 0; 254d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Ri = R^-1 mod N*/ 255d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_mod_inverse(Ri, R, &tmod, ctx) == NULL) { 256d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 257d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 258d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_lshift(Ri, Ri, BN_BITS2)) { 259d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; /* R*Ri */ 260d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 261d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(Ri)) { 262d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_sub_word(Ri, 1)) { 263d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 264d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 265d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 266d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* if N mod word size == 1 */ 267d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_set_word(Ri, BN_MASK2)) { 268d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; /* Ri-- (mod word size) */ 269d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 270d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 271d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_div(Ri, NULL, Ri, &tmod, ctx)) { 272d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 273d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 274d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Ni = (R*Ri-1)/N, 275d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * keep only least significant word: */ 276d9e397b599b13d642138480a28c14db7a136bf0Adam Langley mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; 277d9e397b599b13d642138480a28c14db7a136bf0Adam Langley mont->n0[1] = 0; 278d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#endif 279d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 280d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* setup RR for conversions */ 281d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_zero(&(mont->RR)); 282d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_set_bit(&(mont->RR), mont->ri * 2)) { 283d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 284d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 285d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx)) { 286d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 287d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 288d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 289d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 290d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 291d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 292d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 293d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 294d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 295d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 296e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam LangleyBN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, CRYPTO_MUTEX *lock, 297e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley const BIGNUM *mod, BN_CTX *bn_ctx) { 298e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley CRYPTO_MUTEX_lock_read(lock); 299e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_MONT_CTX *ctx = *pmont; 300e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley CRYPTO_MUTEX_unlock(lock); 301e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley 302e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx) { 303e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley return ctx; 304d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 305d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 306e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley CRYPTO_MUTEX_lock_write(lock); 307e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley ctx = *pmont; 308e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx) { 309e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto out; 310d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 311d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 312e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley ctx = BN_MONT_CTX_new(); 313e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 314e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto out; 315e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 316e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_MONT_CTX_set(ctx, mod, bn_ctx)) { 317e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_MONT_CTX_free(ctx); 318e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley ctx = NULL; 319e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto out; 320e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 321e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley *pmont = ctx; 322d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 323e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langleyout: 324e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley CRYPTO_MUTEX_unlock(lock); 325e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley return ctx; 326d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 327d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 328d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_to_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont, 329d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 330d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_mod_mul_montgomery(ret, a, &mont->RR, mont, ctx); 331d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 332d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 333d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#if 0 334d9e397b599b13d642138480a28c14db7a136bf0Adam Langleystatic int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, 335d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BN_MONT_CTX *mont) { 336d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *n; 337d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG *ap, *np, *rp, n0, v, carry; 338d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int nl, max, i; 339d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 340d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n = &mont->N; 341d9e397b599b13d642138480a28c14db7a136bf0Adam Langley nl = n->top; 342d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (nl == 0) { 343d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret->top = 0; 344d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 345d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 346d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 347d9e397b599b13d642138480a28c14db7a136bf0Adam Langley max = (2 * nl); /* carry is stored separately */ 348d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(r, max) == NULL) { 349d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 350d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 351d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 352d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg ^= n->neg; 353d9e397b599b13d642138480a28c14db7a136bf0Adam Langley np = n->d; 354d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp = r->d; 355d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 356d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* clear the top words of T */ 357d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (max > r->top) { 358d9e397b599b13d642138480a28c14db7a136bf0Adam Langley memset(&rp[r->top], 0, (max - r->top) * sizeof(BN_ULONG)); 359d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 360d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 361d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->top = max; 362d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n0 = mont->n0[0]; 363d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 364d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (carry = 0, i = 0; i < nl; i++, rp++) { 365d9e397b599b13d642138480a28c14db7a136bf0Adam Langley v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2); 366d9e397b599b13d642138480a28c14db7a136bf0Adam Langley v = (v + carry + rp[nl]) & BN_MASK2; 367d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry |= (v != rp[nl]); 368d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry &= (v <= rp[nl]); 369d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[nl] = v; 370d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 371d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 372d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(ret, nl) == NULL) { 373d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 374d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 375d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret->top = nl; 376d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret->neg = r->neg; 377d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 378d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp = ret->d; 379d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap = &(r->d[nl]); 380d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 381d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 382d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG *nrp; 383d9e397b599b13d642138480a28c14db7a136bf0Adam Langley size_t m; 384d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 385d9e397b599b13d642138480a28c14db7a136bf0Adam Langley v = bn_sub_words(rp, ap, np, nl) - carry; 386d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* if subtraction result is real, then trick unconditional memcpy below to 387d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * perform in-place "refresh" instead of actual copy. */ 388d9e397b599b13d642138480a28c14db7a136bf0Adam Langley m = (0 - (size_t)v); 389d9e397b599b13d642138480a28c14db7a136bf0Adam Langley nrp = (BN_ULONG *)(((intptr_t)rp & ~m) | ((intptr_t)ap & m)); 390d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 391d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0, nl -= 4; i < nl; i += 4) { 392d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG t1, t2, t3, t4; 393d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 394d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = nrp[i + 0]; 395d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2 = nrp[i + 1]; 396d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t3 = nrp[i + 2]; 397d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap[i + 0] = 0; 398d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t4 = nrp[i + 3]; 399d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap[i + 1] = 0; 400d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i + 0] = t1; 401d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap[i + 2] = 0; 402d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i + 1] = t2; 403d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap[i + 3] = 0; 404d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i + 2] = t3; 405d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i + 3] = t4; 406d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 407d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 408d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (nl += 4; i < nl; i++) { 409d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i] = nrp[i], ap[i] = 0; 410d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 411d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 412d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 413d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bn_correct_top(r); 414d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bn_correct_top(ret); 415d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 416d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 417d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 418d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#endif 419d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 420d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#define PTR_SIZE_INT size_t 421d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 422d9e397b599b13d642138480a28c14db7a136bf0Adam Langleystatic int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, const BN_MONT_CTX *mont) 423d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 424d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *n; 425d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG *ap,*np,*rp,n0,v,carry; 426d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int nl,max,i; 427d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 428d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n= (BIGNUM*) &(mont->N); 429d9e397b599b13d642138480a28c14db7a136bf0Adam Langley nl=n->top; 430d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (nl == 0) { ret->top=0; return(1); } 431d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 432d9e397b599b13d642138480a28c14db7a136bf0Adam Langley max=(2*nl); /* carry is stored separately */ 433d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(r,max) == NULL) return(0); 434d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 435d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg^=n->neg; 436d9e397b599b13d642138480a28c14db7a136bf0Adam Langley np=n->d; 437d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp=r->d; 438d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 439d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* clear the top words of T */ 440d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#if 1 441d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i=r->top; i<max; i++) /* memset? XXX */ 442d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i]=0; 443d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#else 444d9e397b599b13d642138480a28c14db7a136bf0Adam Langley memset(&(rp[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); 445d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#endif 446d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 447d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->top=max; 448d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n0=mont->n0[0]; 449d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 450d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (carry=0, i=0; i<nl; i++, rp++) 451d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 452d9e397b599b13d642138480a28c14db7a136bf0Adam Langley v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); 453d9e397b599b13d642138480a28c14db7a136bf0Adam Langley v = (v+carry+rp[nl])&BN_MASK2; 454d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry |= (v != rp[nl]); 455d9e397b599b13d642138480a28c14db7a136bf0Adam Langley carry &= (v <= rp[nl]); 456d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[nl]=v; 457d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 458d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 459d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(ret,nl) == NULL) return(0); 460d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret->top=nl; 461d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret->neg=r->neg; 462d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 463d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp=ret->d; 464d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap=&(r->d[nl]); 465d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 466d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 467d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG *nrp; 468d9e397b599b13d642138480a28c14db7a136bf0Adam Langley size_t m; 469d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 470d9e397b599b13d642138480a28c14db7a136bf0Adam Langley v=bn_sub_words(rp,ap,np,nl)-carry; 471d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* if subtraction result is real, then 472d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * trick unconditional memcpy below to perform in-place 473d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "refresh" instead of actual copy. */ 474d9e397b599b13d642138480a28c14db7a136bf0Adam Langley m=(0-(size_t)v); 475d9e397b599b13d642138480a28c14db7a136bf0Adam Langley nrp=(BN_ULONG *)(((PTR_SIZE_INT)rp&~m)|((PTR_SIZE_INT)ap&m)); 476d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 477d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i=0,nl-=4; i<nl; i+=4) 478d9e397b599b13d642138480a28c14db7a136bf0Adam Langley { 479d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG t1,t2,t3,t4; 480d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 481d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1=nrp[i+0]; 482d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2=nrp[i+1]; 483d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t3=nrp[i+2]; ap[i+0]=0; 484d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t4=nrp[i+3]; ap[i+1]=0; 485d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i+0]=t1; ap[i+2]=0; 486d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i+1]=t2; ap[i+3]=0; 487d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i+2]=t3; 488d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i+3]=t4; 489d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 490d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (nl+=4; i<nl; i++) 491d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rp[i]=nrp[i], ap[i]=0; 492d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 493d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bn_correct_top(r); 494d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bn_correct_top(ret); 495d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 496d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return(1); 497d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 498d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 499d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont, 500d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 501d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int retn = 0; 502d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *t; 503d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 504d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 505d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t = BN_CTX_get(ctx); 506d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (t == NULL) { 507d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 508d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 509d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 510e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (BN_copy(t, a)) { 511d9e397b599b13d642138480a28c14db7a136bf0Adam Langley retn = BN_from_montgomery_word(ret, t, mont); 512e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 513d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 514d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 515d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return retn; 516d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 517d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 518d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 519d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BN_MONT_CTX *mont, BN_CTX *ctx) { 520d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *tmp; 521d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 522d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 523d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#if defined(OPENSSL_BN_ASM_MONT) 524d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int num = mont->N.top; 525d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 526d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (num > 1 && a->top == num && b->top == num) { 527d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_wexpand(r, num) == NULL) { 528d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 529d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 530d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) { 531d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->neg = a->neg ^ b->neg; 532d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->top = num; 533d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bn_correct_top(r); 534d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 535d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 536d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 537d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#endif 538d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 539d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 540d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp = BN_CTX_get(ctx); 541d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (tmp == NULL) { 542d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 543d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 544d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 545d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a == b) { 546d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_sqr(tmp, a, ctx)) { 547d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 548d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 549d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 550d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_mul(tmp, a, b, ctx)) { 551d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 552d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 553d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 554d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 555d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* reduce from aRR to aR */ 556d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_from_montgomery_word(r, tmp, mont)) { 557d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 558d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 559d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 560d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 561d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 562d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 563d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 564d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 565d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 566