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