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