[thirdparty/openssl.git] / crypto / bn / bn_exp.c

/* crypto/bn/bn_exp.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.]
 */

#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"

#define TABLE_SIZE	16

/* slow but works */
int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx)
	{
	BIGNUM *t;
	int r=0;

	bn_check_top(a);
	bn_check_top(b);
	bn_check_top(m);

	t= &(ctx->bn[ctx->tos++]);
	if (a == b)
		{ if (!BN_sqr(t,a,ctx)) goto err; }
	else
		{ if (!BN_mul(t,a,b,ctx)) goto err; }
	if (!BN_mod(ret,t,m,ctx)) goto err;
	r=1;
err:
	ctx->tos--;
	return(r);
	}

#if 0
/* this one works - simple but works */
int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
	{
	int i,bits,ret=0;
	BIGNUM *v,*tmp;

	v= &(ctx->bn[ctx->tos++]);
	tmp= &(ctx->bn[ctx->tos++]);

	if (BN_copy(v,a) == NULL) goto err;
	bits=BN_num_bits(p);

	if (BN_is_odd(p))
		{ if (BN_copy(r,a) == NULL) goto err; }
	else	{ if (!BN_one(r)) goto err; }

	for (i=1; i<bits; i++)
		{
		if (!BN_sqr(tmp,v,ctx)) goto err;
		if (!BN_mod(v,tmp,m,ctx)) goto err;
		if (BN_is_bit_set(p,i))
			{
			if (!BN_mul(tmp,r,v,ctx)) goto err;
			if (!BN_mod(r,tmp,m,ctx)) goto err;
			}
		}
	ret=1;
err:
	ctx->tos-=2;
	return(ret);
	}

#endif

/* this one works - simple but works */
int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
	{
	int i,bits,ret=0,tos;
	BIGNUM *v,*rr;

	tos=ctx->tos;
	v= &(ctx->bn[ctx->tos++]);
	if ((r == a) || (r == p))
		rr= &(ctx->bn[ctx->tos++]);
	else
		rr=r;

	if (BN_copy(v,a) == NULL) goto err;
	bits=BN_num_bits(p);

	if (BN_is_odd(p))
		{ if (BN_copy(rr,a) == NULL) goto err; }
	else	{ if (!BN_one(rr)) goto err; }

	for (i=1; i<bits; i++)
		{
		if (!BN_sqr(v,v,ctx)) goto err;
		if (BN_is_bit_set(p,i))
			{
			if (!BN_mul(rr,rr,v,ctx)) goto err;
			}
		}
	ret=1;
err:
	ctx->tos=tos;
	if (r != rr) BN_copy(r,rr);
	return(ret);
	}

int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
	{
	int ret;

	bn_check_top(a);
	bn_check_top(p);
	bn_check_top(m);

#ifdef MONT_MUL_MOD
	/* I have finally been able to take out this pre-condition of
	 * the top bit being set.  It was caused by an error in BN_div
	 * with negatives.  There was also another problem when for a^b%m
	 * a >= m.  eay 07-May-97 */
/*	if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */

	if (BN_is_odd(m))
		{ ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
	else
#endif
#ifdef RECP_MUL_MOD
		{ ret=BN_mod_exp_recp(r,a,p,m,ctx); }
#else
		{ ret=BN_mod_exp_simple(r,a,p,m,ctx); }
#endif

	return(ret);
	}

/* #ifdef RECP_MUL_MOD */
int BN_mod_exp_recp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
	{
	int i,j,bits,ret=0,wstart,wend,window,wvalue;
	int start=1,ts=0;
	BIGNUM *aa;
	BIGNUM val[TABLE_SIZE];
	BN_RECP_CTX recp;

	aa= &(ctx->bn[ctx->tos++]);
	bits=BN_num_bits(p);

	if (bits == 0)
		{
		BN_one(r);
		return(1);
		}
	BN_RECP_CTX_init(&recp);
	if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;

	BN_init(&(val[0]));
	ts=1;

	if (!BN_mod(&(val[0]),a,m,ctx)) goto err;		/* 1 */
	if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
		goto err;				/* 2 */

	if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
		window=1;
	else if (bits >= 256)
		window=5;	/* max size of window */
	else if (bits >= 128)
		window=4;
	else
		window=3;

	j=1<<(window-1);
	for (i=1; i<j; i++)
		{
		BN_init(&val[i]);
		if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
			goto err;
		}
	ts=i;

	start=1;	/* This is used to avoid multiplication etc
			 * when there is only the value '1' in the
			 * buffer. */
	wvalue=0;	/* The 'value' of the window */
	wstart=bits-1;	/* The top bit of the window */
	wend=0;		/* The bottom bit of the window */

	if (!BN_one(r)) goto err;

	for (;;)
		{
		if (BN_is_bit_set(p,wstart) == 0)
			{
			if (!start)
				if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
				goto err;
			if (wstart == 0) break;
			wstart--;
			continue;
			}
		/* We now have wstart on a 'set' bit, we now need to work out
		 * how bit a window to do.  To do this we need to scan
		 * forward until the last set bit before the end of the
		 * window */
		j=wstart;
		wvalue=1;
		wend=0;
		for (i=1; i<window; i++)
			{
			if (wstart-i < 0) break;
			if (BN_is_bit_set(p,wstart-i))
				{
				wvalue<<=(i-wend);
				wvalue|=1;
				wend=i;
				}
			}

		/* wend is the size of the current window */
		j=wend+1;
		/* add the 'bytes above' */
		if (!start)
			for (i=0; i<j; i++)
				{
				if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
					goto err;
				}
		
		/* wvalue will be an odd number < 2^window */
		if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
			goto err;

		/* move the 'window' down further */
		wstart-=wend+1;
		wvalue=0;
		start=0;
		if (wstart < 0) break;
		}
	ret=1;
err:
	ctx->tos--;
	for (i=0; i<ts; i++)
		BN_clear_free(&(val[i]));
	BN_RECP_CTX_free(&recp);
	return(ret);
	}
/* #endif */

/* #ifdef MONT_MUL_MOD */
int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx,
	     BN_MONT_CTX *in_mont)
	{
	int i,j,bits,ret=0,wstart,wend,window,wvalue;
	int start=1,ts=0;
	BIGNUM *d,*aa,*r;
	BIGNUM val[TABLE_SIZE];
	BN_MONT_CTX *mont=NULL;

	bn_check_top(a);
	bn_check_top(p);
	bn_check_top(m);

	if (!(m->d[0] & 1))
		{
		BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
		return(0);
		}
	d= &(ctx->bn[ctx->tos++]);
	r= &(ctx->bn[ctx->tos++]);
	bits=BN_num_bits(p);
	if (bits == 0)
		{
		BN_one(r);
		return(1);
		}

	/* If this is not done, things will break in the montgomery
	 * part */

#if 1
	if (in_mont != NULL)
		mont=in_mont;
	else
#endif
		{
		if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
		if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
		}

	BN_init(&val[0]);
	ts=1;
	if (BN_ucmp(a,m) >= 0)
		{
		BN_mod(&(val[0]),a,m,ctx);
		aa= &(val[0]);
		}
	else
		aa=a;
	if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
	if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */

	if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
		window=1;
	else if (bits >= 256)
		window=5;	/* max size of window */
	else if (bits >= 128)
		window=4;
	else
		window=3;

	j=1<<(window-1);
	for (i=1; i<j; i++)
		{
		BN_init(&(val[i]));
		if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
			goto err;
		}
	ts=i;

	start=1;	/* This is used to avoid multiplication etc
			 * when there is only the value '1' in the
			 * buffer. */
	wvalue=0;	/* The 'value' of the window */
	wstart=bits-1;	/* The top bit of the window */
	wend=0;		/* The bottom bit of the window */

        if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
	for (;;)
		{
		if (BN_is_bit_set(p,wstart) == 0)
			{
			if (!start)
				{
				if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
				goto err;
				}
			if (wstart == 0) break;
			wstart--;
			continue;
			}
		/* We now have wstart on a 'set' bit, we now need to work out
		 * how bit a window to do.  To do this we need to scan
		 * forward until the last set bit before the end of the
		 * window */
		j=wstart;
		wvalue=1;
		wend=0;
		for (i=1; i<window; i++)
			{
			if (wstart-i < 0) break;
			if (BN_is_bit_set(p,wstart-i))
				{
				wvalue<<=(i-wend);
				wvalue|=1;
				wend=i;
				}
			}

		/* wend is the size of the current window */
		j=wend+1;
		/* add the 'bytes above' */
		if (!start)
			for (i=0; i<j; i++)
				{
				if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
					goto err;
				}
		
		/* wvalue will be an odd number < 2^window */
		if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
			goto err;

		/* move the 'window' down further */
		wstart-=wend+1;
		wvalue=0;
		start=0;
		if (wstart < 0) break;
		}
	BN_from_montgomery(rr,r,mont,ctx);
	ret=1;
err:
	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
	ctx->tos-=2;
	for (i=0; i<ts; i++)
		BN_clear_free(&(val[i]));
	return(ret);
	}
/* #endif */

/* The old fallback, simple version :-) */
int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
	     BN_CTX *ctx)
	{
	int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
	int start=1;
	BIGNUM *d;
	BIGNUM val[TABLE_SIZE];

	d= &(ctx->bn[ctx->tos++]);
	bits=BN_num_bits(p);

	if (bits == 0)
		{
		BN_one(r);
		return(1);
		}

	BN_init(&(val[0]));
	ts=1;
	if (!BN_mod(&(val[0]),a,m,ctx)) goto err;		/* 1 */
	if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
		goto err;				/* 2 */

	if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
		window=1;
	else if (bits >= 256)
		window=5;	/* max size of window */
	else if (bits >= 128)
		window=4;
	else
		window=3;

	j=1<<(window-1);
	for (i=1; i<j; i++)
		{
		BN_init(&(val[i]));
		if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
			goto err;
		}
	ts=i;

	start=1;	/* This is used to avoid multiplication etc
			 * when there is only the value '1' in the
			 * buffer. */
	wvalue=0;	/* The 'value' of the window */
	wstart=bits-1;	/* The top bit of the window */
	wend=0;		/* The bottom bit of the window */

	if (!BN_one(r)) goto err;

	for (;;)
		{
		if (BN_is_bit_set(p,wstart) == 0)
			{
			if (!start)
				if (!BN_mod_mul(r,r,r,m,ctx))
				goto err;
			if (wstart == 0) break;
			wstart--;
			continue;
			}
		/* We now have wstart on a 'set' bit, we now need to work out
		 * how bit a window to do.  To do this we need to scan
		 * forward until the last set bit before the end of the
		 * window */
		j=wstart;
		wvalue=1;
		wend=0;
		for (i=1; i<window; i++)
			{
			if (wstart-i < 0) break;
			if (BN_is_bit_set(p,wstart-i))
				{
				wvalue<<=(i-wend);
				wvalue|=1;
				wend=i;
				}
			}

		/* wend is the size of the current window */
		j=wend+1;
		/* add the 'bytes above' */
		if (!start)
			for (i=0; i<j; i++)
				{
				if (!BN_mod_mul(r,r,r,m,ctx))
					goto err;
				}
		
		/* wvalue will be an odd number < 2^window */
		if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
			goto err;

		/* move the 'window' down further */
		wstart-=wend+1;
		wvalue=0;
		start=0;
		if (wstart < 0) break;
		}
	ret=1;
err:
	ctx->tos--;
	for (i=0; i<ts; i++)
		BN_clear_free(&(val[i]));
	return(ret);
	}
Commit	Line	Data
d02b48c6	1	/* crypto/bn/bn_exp.c */
58964a49	2	/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
d02b48c6 RE	3	* All rights reserved.
	4	*
	5	* This package is an SSL implementation written
	6	* by Eric Young (eay@cryptsoft.com).
	7	* The implementation was written so as to conform with Netscapes SSL.
	8	*
	9	* This library is free for commercial and non-commercial use as long as
	10	* the following conditions are aheared to. The following conditions
	11	* apply to all code found in this distribution, be it the RC4, RSA,
	12	* lhash, DES, etc., code; not just the SSL code. The SSL documentation
	13	* included with this distribution is covered by the same copyright terms
	14	* except that the holder is Tim Hudson (tjh@cryptsoft.com).
	15	*
	16	* Copyright remains Eric Young's, and as such any Copyright notices in
	17	* the code are not to be removed.
	18	* If this package is used in a product, Eric Young should be given attribution
	19	* as the author of the parts of the library used.
	20	* This can be in the form of a textual message at program startup or
	21	* in documentation (online or textual) provided with the package.
	22	*
	23	* Redistribution and use in source and binary forms, with or without
	24	* modification, are permitted provided that the following conditions
	25	* are met:
	26	* 1. Redistributions of source code must retain the copyright
	27	* notice, this list of conditions and the following disclaimer.
	28	* 2. Redistributions in binary form must reproduce the above copyright
	29	* notice, this list of conditions and the following disclaimer in the
	30	* documentation and/or other materials provided with the distribution.
	31	* 3. All advertising materials mentioning features or use of this software
	32	* must display the following acknowledgement:
	33	* "This product includes cryptographic software written by
	34	* Eric Young (eay@cryptsoft.com)"
	35	* The word 'cryptographic' can be left out if the rouines from the library
	36	* being used are not cryptographic related :-).
	37	* 4. If you include any Windows specific code (or a derivative thereof) from
	38	* the apps directory (application code) you must include an acknowledgement:
	39	* "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
	40	*
	41	* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
	42	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	43	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	44	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	45	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	46	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	47	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	48	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	49	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	50	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	51	* SUCH DAMAGE.
	52	*
	53	* The licence and distribution terms for any publically available version or
	54	* derivative of this code cannot be changed. i.e. this code cannot simply be
	55	* copied and put under another distribution licence
	56	* [including the GNU Public Licence.]
	57	*/
	58
	59	#include <stdio.h>
	60	#include "cryptlib.h"
	61	#include "bn_lcl.h"
	62
dfeab068 RE	63	#define TABLE_SIZE 16
dfeab068 RE	64
d02b48c6	65	/* slow but works */
6b691a5c	66	int BN_mod_mul(BIGNUM ret, BIGNUM a, BIGNUM b, BIGNUM m, BN_CTX *ctx)
d02b48c6 RE	67	{
	68	BIGNUM *t;
	69	int r=0;
	70
dfeab068 RE	71	bn_check_top(a);
	72	bn_check_top(b);
	73	bn_check_top(m);
	74
	75	t= &(ctx->bn[ctx->tos++]);
d02b48c6 RE	76	if (a == b)
	77	{ if (!BN_sqr(t,a,ctx)) goto err; }
	78	else
dfeab068	79	{ if (!BN_mul(t,a,b,ctx)) goto err; }
d02b48c6 RE	80	if (!BN_mod(ret,t,m,ctx)) goto err;
	81	r=1;
	82	err:
	83	ctx->tos--;
	84	return(r);
	85	}
	86
	87	#if 0
	88	/* this one works - simple but works */
6b691a5c	89	int BN_mod_exp(BIGNUM r, BIGNUM a, BIGNUM p, BIGNUM m, BN_CTX *ctx)
d02b48c6 RE	90	{
	91	int i,bits,ret=0;
	92	BIGNUM v,tmp;
	93
dfeab068 RE	94	v= &(ctx->bn[ctx->tos++]);
dfeab068 RE	95	tmp= &(ctx->bn[ctx->tos++]);
d02b48c6 RE	96
	97	if (BN_copy(v,a) == NULL) goto err;
	98	bits=BN_num_bits(p);
	99
	100	if (BN_is_odd(p))
	101	{ if (BN_copy(r,a) == NULL) goto err; }
a0a54079	102	else { if (!BN_one(r)) goto err; }
d02b48c6 RE	103
	104	for (i=1; i<bits; i++)
	105	{
	106	if (!BN_sqr(tmp,v,ctx)) goto err;
	107	if (!BN_mod(v,tmp,m,ctx)) goto err;
	108	if (BN_is_bit_set(p,i))
	109	{
dfeab068	110	if (!BN_mul(tmp,r,v,ctx)) goto err;
d02b48c6 RE	111	if (!BN_mod(r,tmp,m,ctx)) goto err;
	112	}
	113	}
	114	ret=1;
	115	err:
	116	ctx->tos-=2;
	117	return(ret);
	118	}
	119
	120	#endif
	121
58964a49	122	/* this one works - simple but works */
6b691a5c	123	int BN_exp(BIGNUM r, BIGNUM a, BIGNUM p, BN_CTX ctx)
58964a49	124	{
a0a54079 MC	125	int i,bits,ret=0,tos;
a0a54079 MC	126	BIGNUM v,rr;
58964a49	127
a0a54079	128	tos=ctx->tos;
dfeab068	129	v= &(ctx->bn[ctx->tos++]);
a0a54079 MC	130	if ((r == a) \|\| (r == p))
	131	rr= &(ctx->bn[ctx->tos++]);
	132	else
	133	rr=r;
58964a49 RE	134
	135	if (BN_copy(v,a) == NULL) goto err;
	136	bits=BN_num_bits(p);
	137
	138	if (BN_is_odd(p))
a0a54079 MC	139	{ if (BN_copy(rr,a) == NULL) goto err; }
a0a54079 MC	140	else { if (!BN_one(rr)) goto err; }
58964a49 RE	141
	142	for (i=1; i<bits; i++)
	143	{
a0a54079	144	if (!BN_sqr(v,v,ctx)) goto err;
58964a49 RE	145	if (BN_is_bit_set(p,i))
58964a49 RE	146	{
a0a54079	147	if (!BN_mul(rr,rr,v,ctx)) goto err;
58964a49 RE	148	}
	149	}
	150	ret=1;
	151	err:
a0a54079 MC	152	ctx->tos=tos;
a0a54079 MC	153	if (r != rr) BN_copy(r,rr);
58964a49 RE	154	return(ret);
	155	}
	156
6b691a5c	157	int BN_mod_exp(BIGNUM r, BIGNUM a, BIGNUM p, BIGNUM m, BN_CTX *ctx)
d02b48c6 RE	158	{
	159	int ret;
	160
dfeab068 RE	161	bn_check_top(a);
	162	bn_check_top(p);
	163	bn_check_top(m);
	164
d02b48c6 RE	165	#ifdef MONT_MUL_MOD
	166	/* I have finally been able to take out this pre-condition of
	167	* the top bit being set. It was caused by an error in BN_div
	168	* with negatives. There was also another problem when for a^b%m
	169	* a >= m. eay 07-May-97 */
	170	/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
	171
	172	if (BN_is_odd(m))
58964a49	173	{ ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
d02b48c6 RE	174	else
	175	#endif
	176	#ifdef RECP_MUL_MOD
	177	{ ret=BN_mod_exp_recp(r,a,p,m,ctx); }
	178	#else
	179	{ ret=BN_mod_exp_simple(r,a,p,m,ctx); }
	180	#endif
	181
	182	return(ret);
	183	}
	184
	185	/* #ifdef RECP_MUL_MOD */
6b691a5c	186	int BN_mod_exp_recp(BIGNUM r, BIGNUM a, BIGNUM p, BIGNUM m, BN_CTX *ctx)
d02b48c6	187	{
dfeab068 RE	188	int i,j,bits,ret=0,wstart,wend,window,wvalue;
	189	int start=1,ts=0;
	190	BIGNUM *aa;
	191	BIGNUM val[TABLE_SIZE];
	192	BN_RECP_CTX recp;
d02b48c6	193
dfeab068	194	aa= &(ctx->bn[ctx->tos++]);
d02b48c6 RE	195	bits=BN_num_bits(p);
	196
	197	if (bits == 0)
	198	{
	199	BN_one(r);
	200	return(1);
	201	}
dfeab068 RE	202	BN_RECP_CTX_init(&recp);
	203	if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
	204
	205	BN_init(&(val[0]));
	206	ts=1;
d02b48c6	207
dfeab068 RE	208	if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */
dfeab068 RE	209	if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
d02b48c6 RE	210	goto err; /* 2 */
	211
	212	if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
	213	window=1;
	214	else if (bits >= 256)
	215	window=5; /* max size of window */
	216	else if (bits >= 128)
	217	window=4;
	218	else
	219	window=3;
	220
	221	j=1<<(window-1);
	222	for (i=1; i<j; i++)
	223	{
dfeab068 RE	224	BN_init(&val[i]);
dfeab068 RE	225	if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
d02b48c6 RE	226	goto err;
d02b48c6 RE	227	}
dfeab068	228	ts=i;
d02b48c6 RE	229
	230	start=1; /* This is used to avoid multiplication etc
	231	* when there is only the value '1' in the
	232	* buffer. */
	233	wvalue=0; /* The 'value' of the window */
	234	wstart=bits-1; /* The top bit of the window */
	235	wend=0; /* The bottom bit of the window */
	236
	237	if (!BN_one(r)) goto err;
	238
	239	for (;;)
	240	{
	241	if (BN_is_bit_set(p,wstart) == 0)
	242	{
	243	if (!start)
dfeab068	244	if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
d02b48c6 RE	245	goto err;
	246	if (wstart == 0) break;
	247	wstart--;
	248	continue;
	249	}
	250	/* We now have wstart on a 'set' bit, we now need to work out
	251	* how bit a window to do. To do this we need to scan
	252	* forward until the last set bit before the end of the
	253	* window */
	254	j=wstart;
	255	wvalue=1;
	256	wend=0;
	257	for (i=1; i<window; i++)
	258	{
	259	if (wstart-i < 0) break;
	260	if (BN_is_bit_set(p,wstart-i))
	261	{
	262	wvalue<<=(i-wend);
	263	wvalue\|=1;
	264	wend=i;
	265	}
	266	}
	267
	268	/* wend is the size of the current window */
	269	j=wend+1;
	270	/* add the 'bytes above' */
	271	if (!start)
	272	for (i=0; i<j; i++)
	273	{
dfeab068	274	if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
d02b48c6 RE	275	goto err;
	276	}
	277
	278	/* wvalue will be an odd number < 2^window */
dfeab068	279	if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
d02b48c6 RE	280	goto err;
	281
	282	/* move the 'window' down further */
	283	wstart-=wend+1;
	284	wvalue=0;
	285	start=0;
	286	if (wstart < 0) break;
	287	}
	288	ret=1;
	289	err:
dfeab068 RE	290	ctx->tos--;
	291	for (i=0; i<ts; i++)
	292	BN_clear_free(&(val[i]));
	293	BN_RECP_CTX_free(&recp);
d02b48c6 RE	294	return(ret);
	295	}
	296	/* #endif */
	297
	298	/* #ifdef MONT_MUL_MOD */
6b691a5c UM	299	int BN_mod_exp_mont(BIGNUM rr, BIGNUM a, BIGNUM p, BIGNUM m, BN_CTX *ctx,
6b691a5c UM	300	BN_MONT_CTX *in_mont)
d02b48c6 RE	301	{
d02b48c6 RE	302	int i,j,bits,ret=0,wstart,wend,window,wvalue;
dfeab068 RE	303	int start=1,ts=0;
	304	BIGNUM d,aa,*r;
	305	BIGNUM val[TABLE_SIZE];
d02b48c6 RE	306	BN_MONT_CTX *mont=NULL;
d02b48c6 RE	307
dfeab068 RE	308	bn_check_top(a);
	309	bn_check_top(p);
	310	bn_check_top(m);
	311
d02b48c6 RE	312	if (!(m->d[0] & 1))
	313	{
	314	BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
	315	return(0);
	316	}
dfeab068 RE	317	d= &(ctx->bn[ctx->tos++]);
dfeab068 RE	318	r= &(ctx->bn[ctx->tos++]);
d02b48c6 RE	319	bits=BN_num_bits(p);
	320	if (bits == 0)
	321	{
	322	BN_one(r);
	323	return(1);
	324	}
	325
	326	/* If this is not done, things will break in the montgomery
	327	* part */
	328
58964a49 RE	329	#if 1
	330	if (in_mont != NULL)
	331	mont=in_mont;
	332	else
	333	#endif
	334	{
	335	if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
	336	if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
	337	}
d02b48c6	338
dfeab068 RE	339	BN_init(&val[0]);
dfeab068 RE	340	ts=1;
d02b48c6 RE	341	if (BN_ucmp(a,m) >= 0)
d02b48c6 RE	342	{
dfeab068 RE	343	BN_mod(&(val[0]),a,m,ctx);
dfeab068 RE	344	aa= &(val[0]);
d02b48c6 RE	345	}
	346	else
	347	aa=a;
dfeab068 RE	348	if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
dfeab068 RE	349	if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
d02b48c6	350
58964a49	351	if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
d02b48c6	352	window=1;
dfeab068	353	else if (bits >= 256)
d02b48c6	354	window=5; /* max size of window */
dfeab068	355	else if (bits >= 128)
d02b48c6 RE	356	window=4;
	357	else
	358	window=3;
	359
	360	j=1<<(window-1);
	361	for (i=1; i<j; i++)
	362	{
dfeab068 RE	363	BN_init(&(val[i]));
dfeab068 RE	364	if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
d02b48c6 RE	365	goto err;
d02b48c6 RE	366	}
dfeab068	367	ts=i;
d02b48c6 RE	368
	369	start=1; /* This is used to avoid multiplication etc
	370	* when there is only the value '1' in the
	371	* buffer. */
	372	wvalue=0; /* The 'value' of the window */
	373	wstart=bits-1; /* The top bit of the window */
	374	wend=0; /* The bottom bit of the window */
	375
	376	if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
	377	for (;;)
	378	{
	379	if (BN_is_bit_set(p,wstart) == 0)
	380	{
	381	if (!start)
58964a49	382	{
d02b48c6 RE	383	if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
d02b48c6 RE	384	goto err;
58964a49	385	}
d02b48c6 RE	386	if (wstart == 0) break;
	387	wstart--;
	388	continue;
	389	}
	390	/* We now have wstart on a 'set' bit, we now need to work out
	391	* how bit a window to do. To do this we need to scan
	392	* forward until the last set bit before the end of the
	393	* window */
	394	j=wstart;
	395	wvalue=1;
	396	wend=0;
	397	for (i=1; i<window; i++)
	398	{
	399	if (wstart-i < 0) break;
	400	if (BN_is_bit_set(p,wstart-i))
	401	{
	402	wvalue<<=(i-wend);
	403	wvalue\|=1;
	404	wend=i;
	405	}
	406	}
	407
	408	/* wend is the size of the current window */
	409	j=wend+1;
	410	/* add the 'bytes above' */
	411	if (!start)
	412	for (i=0; i<j; i++)
	413	{
	414	if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
	415	goto err;
	416	}
	417
	418	/* wvalue will be an odd number < 2^window */
dfeab068	419	if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
d02b48c6 RE	420	goto err;
	421
	422	/* move the 'window' down further */
	423	wstart-=wend+1;
	424	wvalue=0;
	425	start=0;
	426	if (wstart < 0) break;
	427	}
dfeab068	428	BN_from_montgomery(rr,r,mont,ctx);
d02b48c6 RE	429	ret=1;
d02b48c6 RE	430	err:
58964a49	431	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
dfeab068 RE	432	ctx->tos-=2;
	433	for (i=0; i<ts; i++)
	434	BN_clear_free(&(val[i]));
d02b48c6 RE	435	return(ret);
	436	}
	437	/* #endif */
	438
	439	/* The old fallback, simple version :-) */
6b691a5c UM	440	int BN_mod_exp_simple(BIGNUM r, BIGNUM a, BIGNUM p, BIGNUM m,
6b691a5c UM	441	BN_CTX *ctx)
d02b48c6	442	{
dfeab068	443	int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
d02b48c6 RE	444	int start=1;
d02b48c6 RE	445	BIGNUM *d;
dfeab068	446	BIGNUM val[TABLE_SIZE];
d02b48c6	447
dfeab068	448	d= &(ctx->bn[ctx->tos++]);
d02b48c6 RE	449	bits=BN_num_bits(p);
	450
	451	if (bits == 0)
	452	{
	453	BN_one(r);
	454	return(1);
	455	}
	456
dfeab068 RE	457	BN_init(&(val[0]));
	458	ts=1;
	459	if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */
	460	if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
d02b48c6 RE	461	goto err; /* 2 */
	462
	463	if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
	464	window=1;
	465	else if (bits >= 256)
	466	window=5; /* max size of window */
	467	else if (bits >= 128)
	468	window=4;
	469	else
	470	window=3;
	471
	472	j=1<<(window-1);
	473	for (i=1; i<j; i++)
	474	{
dfeab068 RE	475	BN_init(&(val[i]));
dfeab068 RE	476	if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
d02b48c6 RE	477	goto err;
d02b48c6 RE	478	}
dfeab068	479	ts=i;
d02b48c6 RE	480
	481	start=1; /* This is used to avoid multiplication etc
	482	* when there is only the value '1' in the
	483	* buffer. */
	484	wvalue=0; /* The 'value' of the window */
	485	wstart=bits-1; /* The top bit of the window */
	486	wend=0; /* The bottom bit of the window */
	487
	488	if (!BN_one(r)) goto err;
	489
	490	for (;;)
	491	{
	492	if (BN_is_bit_set(p,wstart) == 0)
	493	{
	494	if (!start)
	495	if (!BN_mod_mul(r,r,r,m,ctx))
	496	goto err;
	497	if (wstart == 0) break;
	498	wstart--;
	499	continue;
	500	}
	501	/* We now have wstart on a 'set' bit, we now need to work out
	502	* how bit a window to do. To do this we need to scan
	503	* forward until the last set bit before the end of the
	504	* window */
	505	j=wstart;
	506	wvalue=1;
	507	wend=0;
	508	for (i=1; i<window; i++)
	509	{
	510	if (wstart-i < 0) break;
	511	if (BN_is_bit_set(p,wstart-i))
	512	{
	513	wvalue<<=(i-wend);
	514	wvalue\|=1;
	515	wend=i;
	516	}
	517	}
	518
	519	/* wend is the size of the current window */
	520	j=wend+1;
	521	/* add the 'bytes above' */
	522	if (!start)
	523	for (i=0; i<j; i++)
	524	{
	525	if (!BN_mod_mul(r,r,r,m,ctx))
	526	goto err;
	527	}
	528
	529	/* wvalue will be an odd number < 2^window */
dfeab068	530	if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
d02b48c6 RE	531	goto err;
	532
	533	/* move the 'window' down further */
	534	wstart-=wend+1;
	535	wvalue=0;
	536	start=0;
	537	if (wstart < 0) break;
	538	}
	539	ret=1;
	540	err:
	541	ctx->tos--;
dfeab068 RE	542	for (i=0; i<ts; i++)
dfeab068 RE	543	BN_clear_free(&(val[i]));
d02b48c6 RE	544	return(ret);
	545	}
	546