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-2006 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/mem.h> 11295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include <openssl/thread.h> 11395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#include "internal.h" 11595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 11795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#if !defined(OPENSSL_NO_ASM) && \ 11895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley (defined(OPENSSL_X86) || defined(OPENSSL_X86_64)) 11995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#define OPENSSL_BN_ASM_MONT 12095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#endif 12195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12295c29f3cd1f6c08c6c0927868683392eea727ccAdam LangleyBN_MONT_CTX *BN_MONT_CTX_new(void) { 12395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_MONT_CTX *ret = OPENSSL_malloc(sizeof(BN_MONT_CTX)); 12495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (ret == NULL) { 12695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return NULL; 12795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 12895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 12995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_MONT_CTX_init(ret); 13095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret->flags = BN_FLG_MALLOCED; 13195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 13295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 13395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 13495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyvoid BN_MONT_CTX_init(BN_MONT_CTX *mont) { 13595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley memset(mont, 0, sizeof(BN_MONT_CTX)); 13695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_init(&mont->RR); 13795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_init(&mont->N); 13895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_init(&mont->Ni); 13995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 14095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyvoid BN_MONT_CTX_free(BN_MONT_CTX *mont) { 14295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (mont == NULL) { 14395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return; 14495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 14595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 14695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_free(&mont->RR); 14795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_free(&mont->N); 14895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_free(&mont->Ni); 14995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (mont->flags & BN_FLG_MALLOCED) { 15095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley OPENSSL_free(mont); 15195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 15295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 15395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15495c29f3cd1f6c08c6c0927868683392eea727ccAdam LangleyBN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) { 15595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (to == from) { 15695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return to; 15795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 15895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 15995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_copy(&to->RR, &from->RR) || 16095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley !BN_copy(&to->N, &from->N) || 16195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley !BN_copy(&to->Ni, &from->Ni)) { 16295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return NULL; 16395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 16495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley to->ri = from->ri; 16595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley to->n0[0] = from->n0[0]; 16695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley to->n0[1] = from->n0[1]; 16795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return to; 16895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 16995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) { 17195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int ret = 0; 17295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *Ri, *R; 17395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM tmod; 17495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG buf[2]; 17595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 17695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 17795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Ri = BN_CTX_get(ctx); 17895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (Ri == NULL) { 17995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 18095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 18195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley R = &mont->RR; /* grab RR as a temp */ 18295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_copy(&mont->N, mod)) { 18395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; /* Set N */ 18495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 18595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont->N.neg = 0; 18695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 18795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_init(&tmod); 18895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.d = buf; 18995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.dmax = 2; 19095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.neg = 0; 19195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 19295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2; 19395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 19495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2 <= 32) 19595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Only certain BN_BITS2<=32 platforms actually make use of 19695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * n0[1], and we could use the #else case (with a shorter R 19795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * value) for the others. However, currently only the assembler 19895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * files do know which is which. */ 19995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 20095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_zero(R); 20195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_set_bit(R, 2 * BN_BITS2)) { 20295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 20395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 20495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 20595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.top = 0; 20695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if ((buf[0] = mod->d[0])) { 20795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.top = 1; 20895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 20995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if ((buf[1] = mod->top > 1 ? mod->d[1] : 0)) { 21095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.top = 2; 21195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 21395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_mod_inverse(Ri, R, &tmod, ctx) == NULL) { 21495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 21595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift(Ri, Ri, 2 * BN_BITS2)) { 21795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; /* R*Ri */ 21895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 21995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_is_zero(Ri)) { 22095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub_word(Ri, 1)) { 22195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 22295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 22395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 22495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* if N mod word size == 1 */ 22595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL) { 22695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 22795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 22895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Ri-- (mod double word size) */ 22995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Ri->neg = 0; 23095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Ri->d[0] = BN_MASK2; 23195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Ri->d[1] = BN_MASK2; 23295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley Ri->top = 2; 23395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 23495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 23595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_div(Ri, NULL, Ri, &tmod, ctx)) { 23695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 23795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 23895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Ni = (R*Ri-1)/N, 23995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * keep only couple of least significant words: */ 24095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; 24195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0; 24295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#else 24395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_zero(R); 24495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_set_bit(R, BN_BITS2)) { 24595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; /* R */ 24695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 24795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 24895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley buf[0] = mod->d[0]; /* tmod = N mod word size */ 24995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley buf[1] = 0; 25095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmod.top = buf[0] != 0 ? 1 : 0; 25195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Ri = R^-1 mod N*/ 25295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_mod_inverse(Ri, R, &tmod, ctx) == NULL) { 25395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 25495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_lshift(Ri, Ri, BN_BITS2)) { 25695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; /* R*Ri */ 25795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 25895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_is_zero(Ri)) { 25995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sub_word(Ri, 1)) { 26095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 26195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 26395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* if N mod word size == 1 */ 26495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_set_word(Ri, BN_MASK2)) { 26595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; /* Ri-- (mod word size) */ 26695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 26895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_div(Ri, NULL, Ri, &tmod, ctx)) { 26995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 27095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 27195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* Ni = (R*Ri-1)/N, 27295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * keep only least significant word: */ 27395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; 27495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley mont->n0[1] = 0; 27595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#endif 27695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 27795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* setup RR for conversions */ 27895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_zero(&(mont->RR)); 27995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_set_bit(&(mont->RR), mont->ri * 2)) { 28095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 28195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 28295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx)) { 28395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 28495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 28595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 28695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 1; 28795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 28895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 28995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 29095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 29195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 29295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 29395c29f3cd1f6c08c6c0927868683392eea727ccAdam LangleyBN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, 29495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *mod, BN_CTX *ctx) { 29595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_MONT_CTX *ret; 29695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 29795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley CRYPTO_r_lock(lock); 298c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley ret = *pmont; 299c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley CRYPTO_r_unlock(lock); 300c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley if (ret) { 301c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley return ret; 30295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 30395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 304c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley /* We don't want to serialise globally while doing our lazy-init math in 305c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley * BN_MONT_CTX_set. That punishes threads that are doing independent 306c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley * things. Instead, punish the case where more than one thread tries to 307c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley * lazy-init the same 'pmont', by having each do the lazy-init math work 308c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley * independently and only use the one from the thread that wins the race 309c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley * (the losers throw away the work they've done). */ 310c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley ret = BN_MONT_CTX_new(); 311c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley if (!ret) { 312c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley return NULL; 313c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley } 314c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley if (!BN_MONT_CTX_set(ret, mod, ctx)) { 315c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley BN_MONT_CTX_free(ret); 316c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley return NULL; 317c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley } 31895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 319c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley /* The locked compare-and-set, after the local work is done. */ 320c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley CRYPTO_w_lock(lock); 321c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley if (*pmont) { 322c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley BN_MONT_CTX_free(ret); 323c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley ret = *pmont; 32495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 325c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley *pmont = ret; 32695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 32795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 328c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley CRYPTO_w_unlock(lock); 329c8e91d5798d041767b50af2055d7b25af30a3263Adam Langley 33095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 33195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 33295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 33395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_to_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont, 33495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX *ctx) { 33595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return BN_mod_mul_montgomery(ret, a, &mont->RR, mont, ctx); 33695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 33795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 33895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#if 0 33995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, 34095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BN_MONT_CTX *mont) { 34195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BIGNUM *n; 34295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG *ap, *np, *rp, n0, v, carry; 34395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int nl, max, i; 34495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 34595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley n = &mont->N; 34695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley nl = n->top; 34795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (nl == 0) { 34895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret->top = 0; 34995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 35095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 35195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 35295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley max = (2 * nl); /* carry is stored separately */ 35395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_wexpand(r, max) == NULL) { 35495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 35595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 35695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 35795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley r->neg ^= n->neg; 35895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley np = n->d; 35995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp = r->d; 36095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 36195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* clear the top words of T */ 36295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (max > r->top) { 36395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley memset(&rp[r->top], 0, (max - r->top) * sizeof(BN_ULONG)); 36495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 36595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 36695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley r->top = max; 36795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley n0 = mont->n0[0]; 36895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 36995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (carry = 0, i = 0; i < nl; i++, rp++) { 37095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2); 37195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley v = (v + carry + rp[nl]) & BN_MASK2; 37295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley carry |= (v != rp[nl]); 37395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley carry &= (v <= rp[nl]); 37495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[nl] = v; 37595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 37695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 37795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_wexpand(ret, nl) == NULL) { 37895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 37995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 38095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret->top = nl; 38195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret->neg = r->neg; 38295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 38395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp = ret->d; 38495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ap = &(r->d[nl]); 38595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 38695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley { 38795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG *nrp; 38895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley size_t m; 38995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 39095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley v = bn_sub_words(rp, ap, np, nl) - carry; 39195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* if subtraction result is real, then trick unconditional memcpy below to 39295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * perform in-place "refresh" instead of actual copy. */ 39395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley m = (0 - (size_t)v); 39495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley nrp = (BN_ULONG *)(((intptr_t)rp & ~m) | ((intptr_t)ap & m)); 39595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 39695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i = 0, nl -= 4; i < nl; i += 4) { 39795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG t1, t2, t3, t4; 39895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 39995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t1 = nrp[i + 0]; 40095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t2 = nrp[i + 1]; 40195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t3 = nrp[i + 2]; 40295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ap[i + 0] = 0; 40395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t4 = nrp[i + 3]; 40495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ap[i + 1] = 0; 40595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i + 0] = t1; 40695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ap[i + 2] = 0; 40795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i + 1] = t2; 40895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ap[i + 3] = 0; 40995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i + 2] = t3; 41095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i + 3] = t4; 41195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 41395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (nl += 4; i < nl; i++) { 41495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i] = nrp[i], ap[i] = 0; 41595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 41795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 41895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley bn_correct_top(r); 41995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley bn_correct_top(ret); 42095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 42195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 42295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 42395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#endif 42495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 42595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#define PTR_SIZE_INT size_t 42695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 42795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleystatic int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, const BN_MONT_CTX *mont) 42895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley { 42995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *n; 43095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG *ap,*np,*rp,n0,v,carry; 43195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int nl,max,i; 43295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 43395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley n= (BIGNUM*) &(mont->N); 43495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley nl=n->top; 43595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (nl == 0) { ret->top=0; return(1); } 43695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 43795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley max=(2*nl); /* carry is stored separately */ 43895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_wexpand(r,max) == NULL) return(0); 43995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley r->neg^=n->neg; 44195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley np=n->d; 44295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp=r->d; 44395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 44495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* clear the top words of T */ 44595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#if 1 44695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i=r->top; i<max; i++) /* memset? XXX */ 44795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i]=0; 44895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#else 44995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley memset(&(rp[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); 45095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#endif 45195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 45295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley r->top=max; 45395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley n0=mont->n0[0]; 45495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 45595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (carry=0, i=0; i<nl; i++, rp++) 45695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley { 45795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); 45895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley v = (v+carry+rp[nl])&BN_MASK2; 45995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley carry |= (v != rp[nl]); 46095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley carry &= (v <= rp[nl]); 46195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[nl]=v; 46295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 46395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 46495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_wexpand(ret,nl) == NULL) return(0); 46595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret->top=nl; 46695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret->neg=r->neg; 46795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 46895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp=ret->d; 46995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ap=&(r->d[nl]); 47095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 47195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley { 47295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG *nrp; 47395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley size_t m; 47495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 47595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley v=bn_sub_words(rp,ap,np,nl)-carry; 47695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* if subtraction result is real, then 47795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * trick unconditional memcpy below to perform in-place 47895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley * "refresh" instead of actual copy. */ 47995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley m=(0-(size_t)v); 48095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley nrp=(BN_ULONG *)(((PTR_SIZE_INT)rp&~m)|((PTR_SIZE_INT)ap&m)); 48195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 48295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (i=0,nl-=4; i<nl; i+=4) 48395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley { 48495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_ULONG t1,t2,t3,t4; 48595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 48695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t1=nrp[i+0]; 48795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t2=nrp[i+1]; 48895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t3=nrp[i+2]; ap[i+0]=0; 48995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t4=nrp[i+3]; ap[i+1]=0; 49095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i+0]=t1; ap[i+2]=0; 49195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i+1]=t2; ap[i+3]=0; 49295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i+2]=t3; 49395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i+3]=t4; 49495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 49595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley for (nl+=4; i<nl; i++) 49695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley rp[i]=nrp[i], ap[i]=0; 49795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 49895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley bn_correct_top(r); 49995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley bn_correct_top(ret); 50095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 50195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return(1); 50295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 50395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 50495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, const BN_MONT_CTX *mont, 50595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX *ctx) { 50695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int retn = 0; 50795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *t; 50895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 50995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 51095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley t = BN_CTX_get(ctx); 51195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (t == NULL) { 51295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 51395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 51495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 51595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (BN_copy(t, a)) 51695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley retn = BN_from_montgomery_word(ret, t, mont); 51795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 51895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 51995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return retn; 52095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 52195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 52295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyint BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 52395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley const BN_MONT_CTX *mont, BN_CTX *ctx) { 52495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BIGNUM *tmp; 52595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int ret = 0; 52695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 52795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#if defined(OPENSSL_BN_ASM_MONT) 52895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley int num = mont->N.top; 52995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 53095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (num > 1 && a->top == num && b->top == num) { 53195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_wexpand(r, num) == NULL) { 53295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 0; 53395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 53495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) { 53595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley r->neg = a->neg ^ b->neg; 53695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley r->top = num; 53795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley bn_correct_top(r); 53895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return 1; 53995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 54095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 54195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley#endif 54295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 54395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_start(ctx); 54495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley tmp = BN_CTX_get(ctx); 54595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (tmp == NULL) { 54695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 54795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 54895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 54995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (a == b) { 55095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_sqr(tmp, a, ctx)) { 55195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 55295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 55395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } else { 55495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_mul(tmp, a, b, ctx)) { 55595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 55695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 55795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 55895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 55995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley /* reduce from aRR to aR */ 56095c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley if (!BN_from_montgomery_word(r, tmp, mont)) { 56195c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley goto err; 56295c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley } 56395c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 56495c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley ret = 1; 56595c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley 56695c29f3cd1f6c08c6c0927868683392eea727ccAdam Langleyerr: 56795c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley BN_CTX_end(ctx); 56895c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley return ret; 56995c29f3cd1f6c08c6c0927868683392eea727ccAdam Langley} 570