/* crypto/bn/bn_mont.c *//* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written * by Eric Young (eay@cryptsoft.com). * The implementation was written so as to conform with Netscapes SSL. *  * This library is free for commercial and non-commercial use as long as * the following conditions are aheared to.  The following conditions * apply to all code found in this distribution, be it the RC4, RSA, * lhash, DES, etc., code; not just the SSL code.  The SSL documentation * included with this distribution is covered by the same copyright terms * except that the holder is Tim Hudson (tjh@cryptsoft.com). *  * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed. * If this package is used in a product, Eric Young should be given attribution * as the author of the parts of the library used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. *  * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software *    must display the following acknowledgement: *    "This product includes cryptographic software written by *     Eric Young (eay@cryptsoft.com)" *    The word 'cryptographic' can be left out if the rouines from the library *    being used are not cryptographic related :-). * 4. If you include any Windows specific code (or a derivative thereof) from  *    the apps directory (application code) you must include an acknowledgement: *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" *  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. *  * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed.  i.e. this code cannot simply be * copied and put under another distribution licence * [including the GNU Public Licence.] *//* ==================================================================== * Copyright (c) 1998-2006 The OpenSSL Project.  All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer.  * * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in *    the documentation and/or other materials provided with the *    distribution. * * 3. All advertising materials mentioning features or use of this *    software must display the following acknowledgment: *    "This product includes software developed by the OpenSSL Project *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)" * * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to *    endorse or promote products derived from this software without *    prior written permission. For written permission, please contact *    openssl-core@openssl.org. * * 5. Products derived from this software may not be called "OpenSSL" *    nor may "OpenSSL" appear in their names without prior written *    permission of the OpenSSL Project. * * 6. Redistributions of any form whatsoever must retain the following *    acknowledgment: *    "This product includes software developed by the OpenSSL Project *    for use in the OpenSSL Toolkit (http://www.openssl.org/)" * * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. * ==================================================================== * * This product includes cryptographic software written by Eric Young * (eay@cryptsoft.com).  This product includes software written by Tim * Hudson (tjh@cryptsoft.com). * *//* * Details about Montgomery multiplication algorithms can be found at * http://security.ece.orst.edu/publications.html, e.g. * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf */#include <stdio.h>#include "cryptlib.h"#include "bn_lcl.h"#define MONT_WORD /* use the faster word-based algorithm */#if defined(MONT_WORD) && defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)/* This condition means we have a specific non-default build: * In the 0.9.8 branch, OPENSSL_BN_ASM_MONT is normally not set for any * BN_BITS2<=32 platform; an explicit "enable-montasm" is required. * I.e., if we are here, the user intentionally deviates from the * normal stable build to get better Montgomery performance from * the 0.9.9-dev backport. * * In this case only, we also enable BN_from_montgomery_word() * (another non-stable feature from 0.9.9-dev). */#define MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD#endif#ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILDstatic int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);#endifint BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,			  BN_MONT_CTX *mont, BN_CTX *ctx)	{	BIGNUM *tmp;	int ret=0;#if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)	int num = mont->N.top;	if (num>1 && a->top==num && b->top==num)		{		if (bn_wexpand(r,num) == NULL) return(0);#if 0 /* for OpenSSL 0.9.9 mont->n0 */		if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num))#else		if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,&mont->n0,num))#endif			{			r->neg = a->neg^b->neg;			r->top = num;			bn_correct_top(r);			return(1);			}		}#endif	BN_CTX_start(ctx);	tmp = BN_CTX_get(ctx);	if (tmp == NULL) goto err;	bn_check_top(tmp);	if (a == b)		{		if (!BN_sqr(tmp,a,ctx)) goto err;		}	else		{		if (!BN_mul(tmp,a,b,ctx)) goto err;		}	/* reduce from aRR to aR */#ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD	if (!BN_from_montgomery_word(r,tmp,mont)) goto err;#else	if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;#endif	bn_check_top(r);	ret=1;err:	BN_CTX_end(ctx);	return(ret);	}#ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILDstatic int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)	{	BIGNUM *n;	BN_ULONG *ap,*np,*rp,n0,v,*nrp;	int al,nl,max,i,x,ri;	n= &(mont->N);	/* mont->ri is the size of mont->N in bits (rounded up	   to the word size) */	al=ri=mont->ri/BN_BITS2;	nl=n->top;	if ((al == 0) || (nl == 0)) { ret->top=0; return(1); }	max=(nl+al+1); /* allow for overflow (no?) XXX */	if (bn_wexpand(r,max) == NULL) return(0);	r->neg^=n->neg;	np=n->d;	rp=r->d;	nrp= &(r->d[nl]);	/* clear the top words of T */	for (i=r->top; i<max; i++) /* memset? XXX */		r->d[i]=0;	r->top=max;#if 0 /* for OpenSSL 0.9.9 mont->n0 */	n0=mont->n0[0];#else	n0=mont->n0;#endif#ifdef BN_COUNT	fprintf(stderr,"word BN_from_montgomery_word %d * %d\n",nl,nl);#endif	for (i=0; i<nl; i++)		{#ifdef __TANDEM                {                   long long t1;                   long long t2;                   long long t3;                   t1 = rp[0] * (n0 & 0177777);                   t2 = 037777600000l;                   t2 = n0 & t2;                   t3 = rp[0] & 0177777;                   t2 = (t3 * t2) & BN_MASK2;                   t1 = t1 + t2;                   v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1);                }#else		v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2);#endif		nrp++;		rp++;		if (((nrp[-1]+=v)&BN_MASK2) >= v)			continue;		else			{			if (((++nrp[0])&BN_MASK2) != 0) continue;			if (((++nrp[1])&BN_MASK2) != 0) continue;			for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ;			}		}	bn_correct_top(r);	/* mont->ri will be a multiple of the word size and below code	 * is kind of BN_rshift(ret,r,mont->ri) equivalent */	if (r->top <= ri)		{		ret->top=0;		return(1);		}	al=r->top-ri;	if (bn_wexpand(ret,ri) == NULL) return(0);	x=0-(((al-ri)>>(sizeof(al)*8-1))&1);	ret->top=x=(ri&~x)|(al&x);	/* min(ri,al) */	ret->neg=r->neg;	rp=ret->d;	ap=&(r->d[ri]);	{	size_t m1,m2;	v=bn_sub_words(rp,ap,np,ri);	/* this ----------------^^ works even in al<ri case	 * thanks to zealous zeroing of top of the vector in the	 * beginning. */	/* if (al==ri && !v) || al>ri) nrp=rp; else nrp=ap; */	/* in other words if subtraction result is real, then	 * trick unconditional memcpy below to perform in-place	 * "refresh" instead of actual copy. */	m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1);	/* al<ri */	m2=0-(size_t)(((ri-al)>>(sizeof(al)*8-1))&1);	/* al>ri */	m1|=m2;			/* (al!=ri) */	m1|=(0-(size_t)v);	/* (al!=ri || v) */	m1&=~m2;		/* (al!=ri || v) && !al>ri */	nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1));	}	/* 'i<ri' is chosen to eliminate dependency on input data, even	 * though it results in redundant copy in al<ri case. */	for (i=0,ri-=4; i<ri; i+=4)		{		BN_ULONG t1,t2,t3,t4;				t1=nrp[i+0];		t2=nrp[i+1];		t3=nrp[i+2];	ap[i+0]=0;		t4=nrp[i+3];	ap[i+1]=0;		rp[i+0]=t1;	ap[i+2]=0;		rp[i+1]=t2;	ap[i+3]=0;		rp[i+2]=t3;		rp[i+3]=t4;		}	for (ri+=4; i<ri; i++)		rp[i]=nrp[i], ap[i]=0;	bn_correct_top(r);	bn_correct_top(ret);	bn_check_top(ret);	return(1);	}int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,	     BN_CTX *ctx)	{	int retn=0;	BIGNUM *t;	BN_CTX_start(ctx);	if ((t = BN_CTX_get(ctx)) && BN_copy(t,a))		retn = BN_from_montgomery_word(ret,t,mont);	BN_CTX_end(ctx);	return retn;	}#else /* !MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD */int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,	     BN_CTX *ctx)	{	int retn=0;#ifdef MONT_WORD	BIGNUM *n,*r;	BN_ULONG *ap,*np,*rp,n0,v,*nrp;	int al,nl,max,i,x,ri;	BN_CTX_start(ctx);	if ((r = BN_CTX_get(ctx)) == NULL) goto err;	if (!BN_copy(r,a)) goto err;	n= &(mont->N);	ap=a->d;	/* mont->ri is the size of mont->N in bits (rounded up	   to the word size) */	al=ri=mont->ri/BN_BITS2;		nl=n->top;	if ((al == 0) || (nl == 0)) { r->top=0; return(1); }	max=(nl+al+1); /* allow for overflow (no?) XXX */	if (bn_wexpand(r,max) == NULL) goto err;	r->neg=a->neg^n->neg;