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

/* crypto/bn/bn_gcd.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"

static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
int BN_gcd(BIGNUM *r, BIGNUM *in_a, BIGNUM *in_b, BN_CTX *ctx)
	{
	BIGNUM *a,*b,*t;
	int ret=0;

	bn_check_top(in_a);
	bn_check_top(in_b);

	a= &(ctx->bn[ctx->tos]);
	b= &(ctx->bn[ctx->tos+1]);

	if (BN_copy(a,in_a) == NULL) goto err;
	if (BN_copy(b,in_b) == NULL) goto err;

	if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; }
	t=euclid(a,b);
	if (t == NULL) goto err;

	if (BN_copy(r,t) == NULL) goto err;
	ret=1;
err:
	return(ret);
	}

static BIGNUM *euclid(BIGNUM *a, BIGNUM *b)
	{
	BIGNUM *t;
	int shifts=0;

	bn_check_top(a);
	bn_check_top(b);

	for (;;)
		{
		if (BN_is_zero(b))
			break;

		if (BN_is_odd(a))
			{
			if (BN_is_odd(b))
				{
				if (!BN_sub(a,a,b)) goto err;
				if (!BN_rshift1(a,a)) goto err;
				if (BN_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			else		/* a odd - b even */
				{
				if (!BN_rshift1(b,b)) goto err;
				if (BN_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			}
		else			/* a is even */
			{
			if (BN_is_odd(b))
				{
				if (!BN_rshift1(a,a)) goto err;
				if (BN_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			else		/* a even - b even */
				{
				if (!BN_rshift1(a,a)) goto err;
				if (!BN_rshift1(b,b)) goto err;
				shifts++;
				}
			}
		}
	if (shifts)
		{
		if (!BN_lshift(a,a,shifts)) goto err;
		}
	return(a);
err:
	return(NULL);
	}

/* solves ax == 1 (mod n) */
BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, BIGNUM *n, BN_CTX *ctx)
	{
	BIGNUM *A,*B,*X,*Y,*M,*D,*R;
	BIGNUM *T,*ret=NULL;
	int sign;

	bn_check_top(a);
	bn_check_top(n);

	A= &(ctx->bn[ctx->tos]);
	B= &(ctx->bn[ctx->tos+1]);
	X= &(ctx->bn[ctx->tos+2]);
	D= &(ctx->bn[ctx->tos+3]);
	M= &(ctx->bn[ctx->tos+4]);
	Y= &(ctx->bn[ctx->tos+5]);
	ctx->tos+=6;
	if (in == NULL)
		R=BN_new();
	else
		R=in;
	if (R == NULL) goto err;

	BN_zero(X);
	BN_one(Y);
	if (BN_copy(A,a) == NULL) goto err;
	if (BN_copy(B,n) == NULL) goto err;
	sign=1;

	while (!BN_is_zero(B))
		{
		if (!BN_div(D,M,A,B,ctx)) goto err;
		T=A;
		A=B;
		B=M;
		/* T has a struct, M does not */

		if (!BN_mul(T,D,X,ctx)) goto err;
		if (!BN_add(T,T,Y)) goto err;
		M=Y;
		Y=X;
		X=T;
		sign= -sign;
		}
	if (sign < 0)
		{
		if (!BN_sub(Y,n,Y)) goto err;
		}

	if (BN_is_one(A))
		{ if (!BN_mod(R,Y,n,ctx)) goto err; }
	else
		{
		BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
		goto err;
		}
	ret=R;
err:
	if ((ret == NULL) && (in == NULL)) BN_free(R);
	ctx->tos-=6;
	return(ret);
	}
Commit	Line	Data
d02b48c6	1	/* crypto/bn/bn_gcd.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
d02b48c6	63	static BIGNUM euclid(BIGNUM a, BIGNUM *b);
6b691a5c	64	int BN_gcd(BIGNUM r, BIGNUM in_a, BIGNUM in_b, BN_CTX ctx)
d02b48c6 RE	65	{
	66	BIGNUM a,b,*t;
	67	int ret=0;
	68
dfeab068 RE	69	bn_check_top(in_a);
	70	bn_check_top(in_b);
	71
	72	a= &(ctx->bn[ctx->tos]);
	73	b= &(ctx->bn[ctx->tos+1]);
d02b48c6 RE	74
	75	if (BN_copy(a,in_a) == NULL) goto err;
	76	if (BN_copy(b,in_b) == NULL) goto err;
	77
	78	if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; }
	79	t=euclid(a,b);
	80	if (t == NULL) goto err;
	81
	82	if (BN_copy(r,t) == NULL) goto err;
	83	ret=1;
	84	err:
	85	return(ret);
	86	}
	87
6b691a5c	88	static BIGNUM euclid(BIGNUM a, BIGNUM *b)
d02b48c6 RE	89	{
	90	BIGNUM *t;
	91	int shifts=0;
	92
dfeab068 RE	93	bn_check_top(a);
	94	bn_check_top(b);
	95
d02b48c6 RE	96	for (;;)
	97	{
	98	if (BN_is_zero(b))
	99	break;
	100
	101	if (BN_is_odd(a))
	102	{
	103	if (BN_is_odd(b))
	104	{
	105	if (!BN_sub(a,a,b)) goto err;
	106	if (!BN_rshift1(a,a)) goto err;
	107	if (BN_cmp(a,b) < 0)
	108	{ t=a; a=b; b=t; }
	109	}
	110	else /* a odd - b even */
	111	{
	112	if (!BN_rshift1(b,b)) goto err;
	113	if (BN_cmp(a,b) < 0)
	114	{ t=a; a=b; b=t; }
	115	}
	116	}
	117	else /* a is even */
	118	{
	119	if (BN_is_odd(b))
	120	{
	121	if (!BN_rshift1(a,a)) goto err;
	122	if (BN_cmp(a,b) < 0)
	123	{ t=a; a=b; b=t; }
	124	}
	125	else /* a even - b even */
	126	{
	127	if (!BN_rshift1(a,a)) goto err;
	128	if (!BN_rshift1(b,b)) goto err;
	129	shifts++;
	130	}
	131	}
	132	}
	133	if (shifts)
	134	{
	135	if (!BN_lshift(a,a,shifts)) goto err;
	136	}
	137	return(a);
	138	err:
	139	return(NULL);
	140	}
	141
	142	/* solves ax == 1 (mod n) */
6b691a5c	143	BIGNUM BN_mod_inverse(BIGNUM in, BIGNUM a, BIGNUM n, BN_CTX *ctx)
d02b48c6 RE	144	{
d02b48c6 RE	145	BIGNUM A,B,X,Y,M,D,*R;
dfeab068	146	BIGNUM T,ret=NULL;
d02b48c6 RE	147	int sign;
d02b48c6 RE	148
dfeab068 RE	149	bn_check_top(a);
	150	bn_check_top(n);
	151
	152	A= &(ctx->bn[ctx->tos]);
	153	B= &(ctx->bn[ctx->tos+1]);
	154	X= &(ctx->bn[ctx->tos+2]);
	155	D= &(ctx->bn[ctx->tos+3]);
	156	M= &(ctx->bn[ctx->tos+4]);
	157	Y= &(ctx->bn[ctx->tos+5]);
d02b48c6	158	ctx->tos+=6;
dfeab068 RE	159	if (in == NULL)
	160	R=BN_new();
	161	else
	162	R=in;
d02b48c6 RE	163	if (R == NULL) goto err;
	164
	165	BN_zero(X);
	166	BN_one(Y);
	167	if (BN_copy(A,a) == NULL) goto err;
	168	if (BN_copy(B,n) == NULL) goto err;
	169	sign=1;
	170
	171	while (!BN_is_zero(B))
	172	{
	173	if (!BN_div(D,M,A,B,ctx)) goto err;
	174	T=A;
	175	A=B;
	176	B=M;
	177	/* T has a struct, M does not */
	178
dfeab068	179	if (!BN_mul(T,D,X,ctx)) goto err;
d02b48c6 RE	180	if (!BN_add(T,T,Y)) goto err;
	181	M=Y;
	182	Y=X;
	183	X=T;
	184	sign= -sign;
	185	}
	186	if (sign < 0)
	187	{
	188	if (!BN_sub(Y,n,Y)) goto err;
	189	}
	190
	191	if (BN_is_one(A))
	192	{ if (!BN_mod(R,Y,n,ctx)) goto err; }
	193	else
	194	{
	195	BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);
	196	goto err;
	197	}
	198	ret=R;
	199	err:
dfeab068	200	if ((ret == NULL) && (in == NULL)) BN_free(R);
d02b48c6 RE	201	ctx->tos-=6;
	202	return(ret);
	203	}
	204