1 b3f61791 2004-03-21 devnull #include "os.h"
2 b3f61791 2004-03-21 devnull #include <mp.h>
4 cbeb0b26 2006-04-01 devnull /* extended euclid */
6 cbeb0b26 2006-04-01 devnull /* For a and b it solves, d = gcd(a,b) and finds x and y s.t. */
7 cbeb0b26 2006-04-01 devnull /* ax + by = d */
9 cbeb0b26 2006-04-01 devnull /* Handbook of Applied Cryptography, Menezes et al, 1997, pg 67 */
12 b3f61791 2004-03-21 devnull mpeuclid(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
14 b3f61791 2004-03-21 devnull mpint *tmp, *x0, *x1, *x2, *y0, *y1, *y2, *q, *r;
16 b3f61791 2004-03-21 devnull if(a->sign<0 || b->sign<0)
17 b3f61791 2004-03-21 devnull sysfatal("mpeuclid: negative arg");
19 b3f61791 2004-03-21 devnull if(mpcmp(a, b) < 0){
28 b3f61791 2004-03-21 devnull if(b->top == 0){
29 b3f61791 2004-03-21 devnull mpassign(a, d);
30 b3f61791 2004-03-21 devnull mpassign(mpone, x);
31 b3f61791 2004-03-21 devnull mpassign(mpzero, y);
35 b3f61791 2004-03-21 devnull a = mpcopy(a);
36 b3f61791 2004-03-21 devnull b = mpcopy(b);
37 b3f61791 2004-03-21 devnull x0 = mpnew(0);
38 b3f61791 2004-03-21 devnull x1 = mpcopy(mpzero);
39 b3f61791 2004-03-21 devnull x2 = mpcopy(mpone);
40 b3f61791 2004-03-21 devnull y0 = mpnew(0);
41 b3f61791 2004-03-21 devnull y1 = mpcopy(mpone);
42 b3f61791 2004-03-21 devnull y2 = mpcopy(mpzero);
43 b3f61791 2004-03-21 devnull q = mpnew(0);
44 b3f61791 2004-03-21 devnull r = mpnew(0);
46 b3f61791 2004-03-21 devnull while(b->top != 0 && b->sign > 0){
47 cbeb0b26 2006-04-01 devnull /* q = a/b */
48 cbeb0b26 2006-04-01 devnull /* r = a mod b */
49 b3f61791 2004-03-21 devnull mpdiv(a, b, q, r);
50 cbeb0b26 2006-04-01 devnull /* x0 = x2 - qx1 */
51 b3f61791 2004-03-21 devnull mpmul(q, x1, x0);
52 b3f61791 2004-03-21 devnull mpsub(x2, x0, x0);
53 cbeb0b26 2006-04-01 devnull /* y0 = y2 - qy1 */
54 b3f61791 2004-03-21 devnull mpmul(q, y1, y0);
55 b3f61791 2004-03-21 devnull mpsub(y2, y0, y0);
56 cbeb0b26 2006-04-01 devnull /* rotate values */
61 b3f61791 2004-03-21 devnull tmp = x2;
64 b3f61791 2004-03-21 devnull x0 = tmp;
65 b3f61791 2004-03-21 devnull tmp = y2;
68 b3f61791 2004-03-21 devnull y0 = tmp;
71 b3f61791 2004-03-21 devnull mpassign(a, d);
72 b3f61791 2004-03-21 devnull mpassign(x2, x);
73 b3f61791 2004-03-21 devnull mpassign(y2, y);
75 b3f61791 2004-03-21 devnull mpfree(x0);
76 b3f61791 2004-03-21 devnull mpfree(x1);
77 b3f61791 2004-03-21 devnull mpfree(x2);
78 b3f61791 2004-03-21 devnull mpfree(y0);
79 b3f61791 2004-03-21 devnull mpfree(y1);
80 b3f61791 2004-03-21 devnull mpfree(y2);
81 b3f61791 2004-03-21 devnull mpfree(q);
82 b3f61791 2004-03-21 devnull mpfree(r);
83 b3f61791 2004-03-21 devnull mpfree(a);
84 b3f61791 2004-03-21 devnull mpfree(b);