[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, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
	{
	BIGNUM *a,*b,*t;
	int ret=0;

	bn_check_top(in_a);
	bn_check_top(in_b);

	BN_CTX_start(ctx);
	a = BN_CTX_get(ctx);
	b = BN_CTX_get(ctx);
	if (a == NULL || b == NULL) goto err;

	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:
	BN_CTX_end(ctx);
	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,
	const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
	{
	BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL;
	BIGNUM *T,*ret=NULL;
	int sign;

	bn_check_top(a);
	bn_check_top(n);

	BN_CTX_start(ctx);
	A = BN_CTX_get(ctx);
	B = BN_CTX_get(ctx);
	X = BN_CTX_get(ctx);
	D = BN_CTX_get(ctx);
	M = BN_CTX_get(ctx);
	Y = BN_CTX_get(ctx);
	if (Y == NULL) goto err;

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