168651Skris/* crypto/bn/bn_exp2.c */ 268651Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 368651Skris * All rights reserved. 468651Skris * 568651Skris * This package is an SSL implementation written 668651Skris * by Eric Young (eay@cryptsoft.com). 768651Skris * The implementation was written so as to conform with Netscapes SSL. 868651Skris * 968651Skris * This library is free for commercial and non-commercial use as long as 1068651Skris * the following conditions are aheared to. The following conditions 1168651Skris * apply to all code found in this distribution, be it the RC4, RSA, 1268651Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1368651Skris * included with this distribution is covered by the same copyright terms 1468651Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1568651Skris * 1668651Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1768651Skris * the code are not to be removed. 1868651Skris * If this package is used in a product, Eric Young should be given attribution 1968651Skris * as the author of the parts of the library used. 2068651Skris * This can be in the form of a textual message at program startup or 2168651Skris * in documentation (online or textual) provided with the package. 2268651Skris * 2368651Skris * Redistribution and use in source and binary forms, with or without 2468651Skris * modification, are permitted provided that the following conditions 2568651Skris * are met: 2668651Skris * 1. Redistributions of source code must retain the copyright 2768651Skris * notice, this list of conditions and the following disclaimer. 2868651Skris * 2. Redistributions in binary form must reproduce the above copyright 2968651Skris * notice, this list of conditions and the following disclaimer in the 3068651Skris * documentation and/or other materials provided with the distribution. 3168651Skris * 3. All advertising materials mentioning features or use of this software 3268651Skris * must display the following acknowledgement: 3368651Skris * "This product includes cryptographic software written by 3468651Skris * Eric Young (eay@cryptsoft.com)" 3568651Skris * The word 'cryptographic' can be left out if the rouines from the library 3668651Skris * being used are not cryptographic related :-). 3768651Skris * 4. If you include any Windows specific code (or a derivative thereof) from 3868651Skris * the apps directory (application code) you must include an acknowledgement: 3968651Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4068651Skris * 4168651Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4268651Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4368651Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4468651Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4568651Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4668651Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4768651Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4868651Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4968651Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5068651Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5168651Skris * SUCH DAMAGE. 5268651Skris * 5368651Skris * The licence and distribution terms for any publically available version or 5468651Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5568651Skris * copied and put under another distribution licence 5668651Skris * [including the GNU Public Licence.] 5768651Skris */ 5868651Skris/* ==================================================================== 5968651Skris * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. 6068651Skris * 6168651Skris * Redistribution and use in source and binary forms, with or without 6268651Skris * modification, are permitted provided that the following conditions 6368651Skris * are met: 6468651Skris * 6568651Skris * 1. Redistributions of source code must retain the above copyright 6668651Skris * notice, this list of conditions and the following disclaimer. 6768651Skris * 6868651Skris * 2. Redistributions in binary form must reproduce the above copyright 6968651Skris * notice, this list of conditions and the following disclaimer in 7068651Skris * the documentation and/or other materials provided with the 7168651Skris * distribution. 7268651Skris * 7368651Skris * 3. All advertising materials mentioning features or use of this 7468651Skris * software must display the following acknowledgment: 7568651Skris * "This product includes software developed by the OpenSSL Project 7668651Skris * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 7768651Skris * 7868651Skris * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 7968651Skris * endorse or promote products derived from this software without 8068651Skris * prior written permission. For written permission, please contact 8168651Skris * openssl-core@openssl.org. 8268651Skris * 8368651Skris * 5. Products derived from this software may not be called "OpenSSL" 8468651Skris * nor may "OpenSSL" appear in their names without prior written 8568651Skris * permission of the OpenSSL Project. 8668651Skris * 8768651Skris * 6. Redistributions of any form whatsoever must retain the following 8868651Skris * acknowledgment: 8968651Skris * "This product includes software developed by the OpenSSL Project 9068651Skris * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 9168651Skris * 9268651Skris * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 9368651Skris * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 9468651Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 9568651Skris * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 9668651Skris * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 9768651Skris * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 9868651Skris * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 9968651Skris * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 10068651Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 10168651Skris * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 10268651Skris * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 10368651Skris * OF THE POSSIBILITY OF SUCH DAMAGE. 10468651Skris * ==================================================================== 10568651Skris * 10668651Skris * This product includes cryptographic software written by Eric Young 10768651Skris * (eay@cryptsoft.com). This product includes software written by Tim 10868651Skris * Hudson (tjh@cryptsoft.com). 10968651Skris * 11068651Skris */ 11168651Skris 11255714Skris#include <stdio.h> 11355714Skris#include "cryptlib.h" 11455714Skris#include "bn_lcl.h" 11555714Skris 11668651Skris#define TABLE_SIZE 32 11755714Skris 118109998Smarkmint BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, 119109998Smarkm const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, 120109998Smarkm BN_CTX *ctx, BN_MONT_CTX *in_mont) 12155714Skris { 12268651Skris int i,j,bits,b,bits1,bits2,ret=0,wpos1,wpos2,window1,window2,wvalue1,wvalue2; 123160814Ssimon int r_is_one=1; 12468651Skris BIGNUM *d,*r; 125109998Smarkm const BIGNUM *a_mod_m; 126160814Ssimon /* Tables of variables obtained from 'ctx' */ 127160814Ssimon BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE]; 12855714Skris BN_MONT_CTX *mont=NULL; 12955714Skris 13055714Skris bn_check_top(a1); 13155714Skris bn_check_top(p1); 13255714Skris bn_check_top(a2); 13355714Skris bn_check_top(p2); 13455714Skris bn_check_top(m); 13555714Skris 13655714Skris if (!(m->d[0] & 1)) 13755714Skris { 13868651Skris BNerr(BN_F_BN_MOD_EXP2_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); 13955714Skris return(0); 14055714Skris } 14155714Skris bits1=BN_num_bits(p1); 14255714Skris bits2=BN_num_bits(p2); 14355714Skris if ((bits1 == 0) && (bits2 == 0)) 14455714Skris { 145109998Smarkm ret = BN_one(rr); 146109998Smarkm return ret; 14755714Skris } 148109998Smarkm 14968651Skris bits=(bits1 > bits2)?bits1:bits2; 15059191Skris 15159191Skris BN_CTX_start(ctx); 15259191Skris d = BN_CTX_get(ctx); 15359191Skris r = BN_CTX_get(ctx); 154160814Ssimon val1[0] = BN_CTX_get(ctx); 155160814Ssimon val2[0] = BN_CTX_get(ctx); 156160814Ssimon if(!d || !r || !val1[0] || !val2[0]) goto err; 15759191Skris 15855714Skris if (in_mont != NULL) 15955714Skris mont=in_mont; 16055714Skris else 16155714Skris { 16255714Skris if ((mont=BN_MONT_CTX_new()) == NULL) goto err; 16355714Skris if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; 16455714Skris } 16555714Skris 16668651Skris window1 = BN_window_bits_for_exponent_size(bits1); 16768651Skris window2 = BN_window_bits_for_exponent_size(bits2); 16868651Skris 16968651Skris /* 17068651Skris * Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1) 17168651Skris */ 172109998Smarkm if (a1->neg || BN_ucmp(a1,m) >= 0) 17355714Skris { 174160814Ssimon if (!BN_mod(val1[0],a1,m,ctx)) 17568651Skris goto err; 176160814Ssimon a_mod_m = val1[0]; 17755714Skris } 17855714Skris else 17968651Skris a_mod_m = a1; 180109998Smarkm if (BN_is_zero(a_mod_m)) 181109998Smarkm { 182160814Ssimon BN_zero(rr); 183160814Ssimon ret = 1; 184109998Smarkm goto err; 185109998Smarkm } 186109998Smarkm 187160814Ssimon if (!BN_to_montgomery(val1[0],a_mod_m,mont,ctx)) goto err; 18868651Skris if (window1 > 1) 18968651Skris { 190160814Ssimon if (!BN_mod_mul_montgomery(d,val1[0],val1[0],mont,ctx)) goto err; 19168651Skris 19268651Skris j=1<<(window1-1); 19368651Skris for (i=1; i<j; i++) 19468651Skris { 195160814Ssimon if(((val1[i] = BN_CTX_get(ctx)) == NULL) || 196160814Ssimon !BN_mod_mul_montgomery(val1[i],val1[i-1], 197160814Ssimon d,mont,ctx)) 19868651Skris goto err; 19968651Skris } 20068651Skris } 20168651Skris 20268651Skris 20368651Skris /* 20468651Skris * Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1) 20568651Skris */ 206109998Smarkm if (a2->neg || BN_ucmp(a2,m) >= 0) 20755714Skris { 208160814Ssimon if (!BN_mod(val2[0],a2,m,ctx)) 20968651Skris goto err; 210160814Ssimon a_mod_m = val2[0]; 21155714Skris } 21255714Skris else 21368651Skris a_mod_m = a2; 214109998Smarkm if (BN_is_zero(a_mod_m)) 215109998Smarkm { 216160814Ssimon BN_zero(rr); 217160814Ssimon ret = 1; 218109998Smarkm goto err; 219109998Smarkm } 220160814Ssimon if (!BN_to_montgomery(val2[0],a_mod_m,mont,ctx)) goto err; 22168651Skris if (window2 > 1) 22268651Skris { 223160814Ssimon if (!BN_mod_mul_montgomery(d,val2[0],val2[0],mont,ctx)) goto err; 22455714Skris 22568651Skris j=1<<(window2-1); 22668651Skris for (i=1; i<j; i++) 22755714Skris { 228160814Ssimon if(((val2[i] = BN_CTX_get(ctx)) == NULL) || 229160814Ssimon !BN_mod_mul_montgomery(val2[i],val2[i-1], 230160814Ssimon d,mont,ctx)) 23155714Skris goto err; 23255714Skris } 23355714Skris } 23455714Skris 23555714Skris 23668651Skris /* Now compute the power product, using independent windows. */ 23768651Skris r_is_one=1; 23868651Skris wvalue1=0; /* The 'value' of the first window */ 23968651Skris wvalue2=0; /* The 'value' of the second window */ 24068651Skris wpos1=0; /* If wvalue1 > 0, the bottom bit of the first window */ 24168651Skris wpos2=0; /* If wvalue2 > 0, the bottom bit of the second window */ 24268651Skris 24368651Skris if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; 24468651Skris for (b=bits-1; b>=0; b--) 24555714Skris { 24668651Skris if (!r_is_one) 24755714Skris { 24868651Skris if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) 24968651Skris goto err; 25068651Skris } 25168651Skris 25268651Skris if (!wvalue1) 25368651Skris if (BN_is_bit_set(p1, b)) 25455714Skris { 25568651Skris /* consider bits b-window1+1 .. b for this window */ 25668651Skris i = b-window1+1; 25768651Skris while (!BN_is_bit_set(p1, i)) /* works for i<0 */ 25868651Skris i++; 25968651Skris wpos1 = i; 26068651Skris wvalue1 = 1; 26168651Skris for (i = b-1; i >= wpos1; i--) 26268651Skris { 26368651Skris wvalue1 <<= 1; 26468651Skris if (BN_is_bit_set(p1, i)) 26568651Skris wvalue1++; 26668651Skris } 26755714Skris } 26868651Skris 26968651Skris if (!wvalue2) 27068651Skris if (BN_is_bit_set(p2, b)) 27168651Skris { 27268651Skris /* consider bits b-window2+1 .. b for this window */ 27368651Skris i = b-window2+1; 27468651Skris while (!BN_is_bit_set(p2, i)) 27568651Skris i++; 27668651Skris wpos2 = i; 27768651Skris wvalue2 = 1; 27868651Skris for (i = b-1; i >= wpos2; i--) 27968651Skris { 28068651Skris wvalue2 <<= 1; 28168651Skris if (BN_is_bit_set(p2, i)) 28268651Skris wvalue2++; 28368651Skris } 28468651Skris } 28568651Skris 28668651Skris if (wvalue1 && b == wpos1) 28755714Skris { 28868651Skris /* wvalue1 is odd and < 2^window1 */ 289160814Ssimon if (!BN_mod_mul_montgomery(r,r,val1[wvalue1>>1],mont,ctx)) 29068651Skris goto err; 29168651Skris wvalue1 = 0; 29268651Skris r_is_one = 0; 29355714Skris } 29455714Skris 29568651Skris if (wvalue2 && b == wpos2) 29655714Skris { 29768651Skris /* wvalue2 is odd and < 2^window2 */ 298160814Ssimon if (!BN_mod_mul_montgomery(r,r,val2[wvalue2>>1],mont,ctx)) 29968651Skris goto err; 30068651Skris wvalue2 = 0; 30168651Skris r_is_one = 0; 30255714Skris } 30355714Skris } 304215697Ssimon if (!BN_from_montgomery(rr,r,mont,ctx)) 305215697Ssimon goto err; 30655714Skris ret=1; 30755714Skriserr: 30855714Skris if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); 30959191Skris BN_CTX_end(ctx); 310160814Ssimon bn_check_top(rr); 31155714Skris return(ret); 31255714Skris } 313