1 b3f61791 2004-03-21 devnull #include "os.h"
  2 b3f61791 2004-03-21 devnull #include <mp.h>
  3 b3f61791 2004-03-21 devnull 
  4 b3f61791 2004-03-21 devnull #define iseven(a)	(((a)->p[0] & 1) == 0)
  5 b3f61791 2004-03-21 devnull 
  6 cbeb0b26 2006-04-01 devnull /* extended binary gcd */
  7 cbeb0b26 2006-04-01 devnull /* */
  8 cbeb0b26 2006-04-01 devnull /* For a anv b it solves, v = gcd(a,b) and finds x and y s.t. */
  9 cbeb0b26 2006-04-01 devnull /* ax + by = v */
 10 cbeb0b26 2006-04-01 devnull /* */
 11 cbeb0b26 2006-04-01 devnull /* Handbook of Applied Cryptography, Menezes et al, 1997, pg 608.   */
 12 b3f61791 2004-03-21 devnull void
 13 b3f61791 2004-03-21 devnull mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
 14 b3f61791 2004-03-21 devnull {
 15 b3f61791 2004-03-21 devnull 	mpint *u, *A, *B, *C, *D;
 16 b3f61791 2004-03-21 devnull 	int g;
 17 b3f61791 2004-03-21 devnull 
 18 b3f61791 2004-03-21 devnull 	if(a->sign < 0 || b->sign < 0){
 19 b3f61791 2004-03-21 devnull 		mpassign(mpzero, v);
 20 b3f61791 2004-03-21 devnull 		mpassign(mpzero, y);
 21 b3f61791 2004-03-21 devnull 		mpassign(mpzero, x);
 22 b3f61791 2004-03-21 devnull 		return;
 23 b3f61791 2004-03-21 devnull 	}
 24 b3f61791 2004-03-21 devnull 
 25 b3f61791 2004-03-21 devnull 	if(a->top == 0){
 26 b3f61791 2004-03-21 devnull 		mpassign(b, v);
 27 b3f61791 2004-03-21 devnull 		mpassign(mpone, y);
 28 b3f61791 2004-03-21 devnull 		mpassign(mpzero, x);
 29 b3f61791 2004-03-21 devnull 		return;
 30 b3f61791 2004-03-21 devnull 	}
 31 b3f61791 2004-03-21 devnull 	if(b->top == 0){
 32 b3f61791 2004-03-21 devnull 		mpassign(a, v);
 33 b3f61791 2004-03-21 devnull 		mpassign(mpone, x);
 34 b3f61791 2004-03-21 devnull 		mpassign(mpzero, y);
 35 b3f61791 2004-03-21 devnull 		return;
 36 b3f61791 2004-03-21 devnull 	}
 37 b3f61791 2004-03-21 devnull 
 38 b3f61791 2004-03-21 devnull 	g = 0;
 39 b3f61791 2004-03-21 devnull 	a = mpcopy(a);
 40 b3f61791 2004-03-21 devnull 	b = mpcopy(b);
 41 b3f61791 2004-03-21 devnull 
 42 b3f61791 2004-03-21 devnull 	while(iseven(a) && iseven(b)){
 43 b3f61791 2004-03-21 devnull 		mpright(a, 1, a);
 44 b3f61791 2004-03-21 devnull 		mpright(b, 1, b);
 45 b3f61791 2004-03-21 devnull 		g++;
 46 b3f61791 2004-03-21 devnull 	}
 47 b3f61791 2004-03-21 devnull 
 48 b3f61791 2004-03-21 devnull 	u = mpcopy(a);
 49 b3f61791 2004-03-21 devnull 	mpassign(b, v);
 50 b3f61791 2004-03-21 devnull 	A = mpcopy(mpone);
 51 b3f61791 2004-03-21 devnull 	B = mpcopy(mpzero);
 52 b3f61791 2004-03-21 devnull 	C = mpcopy(mpzero);
 53 b3f61791 2004-03-21 devnull 	D = mpcopy(mpone);
 54 b3f61791 2004-03-21 devnull 
 55 b3f61791 2004-03-21 devnull 	for(;;) {
 56 cbeb0b26 2006-04-01 devnull /*		print("%B %B %B %B %B %B\n", u, v, A, B, C, D); */
 57 b3f61791 2004-03-21 devnull 		while(iseven(u)){
 58 b3f61791 2004-03-21 devnull 			mpright(u, 1, u);
 59 b3f61791 2004-03-21 devnull 			if(!iseven(A) || !iseven(B)) {
 60 b3f61791 2004-03-21 devnull 				mpadd(A, b, A);
 61 b3f61791 2004-03-21 devnull 				mpsub(B, a, B);
 62 b3f61791 2004-03-21 devnull 			}
 63 b3f61791 2004-03-21 devnull 			mpright(A, 1, A);
 64 b3f61791 2004-03-21 devnull 			mpright(B, 1, B);
 65 b3f61791 2004-03-21 devnull 		}
 66 fa325e9b 2020-01-10 cross 
 67 cbeb0b26 2006-04-01 devnull /*		print("%B %B %B %B %B %B\n", u, v, A, B, C, D); */
 68 b3f61791 2004-03-21 devnull 		while(iseven(v)){
 69 b3f61791 2004-03-21 devnull 			mpright(v, 1, v);
 70 b3f61791 2004-03-21 devnull 			if(!iseven(C) || !iseven(D)) {
 71 b3f61791 2004-03-21 devnull 				mpadd(C, b, C);
 72 b3f61791 2004-03-21 devnull 				mpsub(D, a, D);
 73 b3f61791 2004-03-21 devnull 			}
 74 b3f61791 2004-03-21 devnull 			mpright(C, 1, C);
 75 b3f61791 2004-03-21 devnull 			mpright(D, 1, D);
 76 b3f61791 2004-03-21 devnull 		}
 77 fa325e9b 2020-01-10 cross 
 78 cbeb0b26 2006-04-01 devnull /*		print("%B %B %B %B %B %B\n", u, v, A, B, C, D); */
 79 b3f61791 2004-03-21 devnull 		if(mpcmp(u, v) >= 0){
 80 b3f61791 2004-03-21 devnull 			mpsub(u, v, u);
 81 b3f61791 2004-03-21 devnull 			mpsub(A, C, A);
 82 b3f61791 2004-03-21 devnull 			mpsub(B, D, B);
 83 b3f61791 2004-03-21 devnull 		} else {
 84 b3f61791 2004-03-21 devnull 			mpsub(v, u, v);
 85 b3f61791 2004-03-21 devnull 			mpsub(C, A, C);
 86 b3f61791 2004-03-21 devnull 			mpsub(D, B, D);
 87 b3f61791 2004-03-21 devnull 		}
 88 b3f61791 2004-03-21 devnull 
 89 b3f61791 2004-03-21 devnull 		if(u->top == 0)
 90 b3f61791 2004-03-21 devnull 			break;
 91 b3f61791 2004-03-21 devnull 
 92 b3f61791 2004-03-21 devnull 	}
 93 b3f61791 2004-03-21 devnull 	mpassign(C, x);
 94 b3f61791 2004-03-21 devnull 	mpassign(D, y);
 95 b3f61791 2004-03-21 devnull 	mpleft(v, g, v);
 96 b3f61791 2004-03-21 devnull 
 97 b3f61791 2004-03-21 devnull 	mpfree(A);
 98 b3f61791 2004-03-21 devnull 	mpfree(B);
 99 b3f61791 2004-03-21 devnull 	mpfree(C);
100 b3f61791 2004-03-21 devnull 	mpfree(D);
101 b3f61791 2004-03-21 devnull 	mpfree(u);
102 b3f61791 2004-03-21 devnull 	mpfree(a);
103 b3f61791 2004-03-21 devnull 	mpfree(b);
104 b3f61791 2004-03-21 devnull 
105 b3f61791 2004-03-21 devnull 	return;
106 b3f61791 2004-03-21 devnull }