|
142
|
1 #include <tommath.h> |
|
|
2 #ifdef BN_FAST_MP_INVMOD_C |
|
2
|
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
4 * |
|
|
5 * LibTomMath is a library that provides multiple-precision |
|
|
6 * integer arithmetic as well as number theoretic functionality. |
|
|
7 * |
|
|
8 * The library was designed directly after the MPI library by |
|
|
9 * Michael Fromberger but has been written from scratch with |
|
|
10 * additional optimizations in place. |
|
|
11 * |
|
|
12 * The library is free for all purposes without any express |
|
|
13 * guarantee it works. |
|
|
14 * |
|
|
15 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
16 */ |
|
|
17 |
|
|
18 /* computes the modular inverse via binary extended euclidean algorithm, |
|
|
19 * that is c = 1/a mod b |
|
|
20 * |
|
142
|
21 * Based on slow invmod except this is optimized for the case where b is |
|
2
|
22 * odd as per HAC Note 14.64 on pp. 610 |
|
|
23 */ |
|
|
24 int |
|
|
25 fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c) |
|
|
26 { |
|
|
27 mp_int x, y, u, v, B, D; |
|
|
28 int res, neg; |
|
|
29 |
|
|
30 /* 2. [modified] b must be odd */ |
|
|
31 if (mp_iseven (b) == 1) { |
|
|
32 return MP_VAL; |
|
|
33 } |
|
|
34 |
|
|
35 /* init all our temps */ |
|
|
36 if ((res = mp_init_multi(&x, &y, &u, &v, &B, &D, NULL)) != MP_OKAY) { |
|
|
37 return res; |
|
|
38 } |
|
|
39 |
|
|
40 /* x == modulus, y == value to invert */ |
|
|
41 if ((res = mp_copy (b, &x)) != MP_OKAY) { |
|
|
42 goto __ERR; |
|
|
43 } |
|
|
44 |
|
|
45 /* we need y = |a| */ |
|
|
46 if ((res = mp_abs (a, &y)) != MP_OKAY) { |
|
|
47 goto __ERR; |
|
|
48 } |
|
|
49 |
|
|
50 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */ |
|
|
51 if ((res = mp_copy (&x, &u)) != MP_OKAY) { |
|
|
52 goto __ERR; |
|
|
53 } |
|
|
54 if ((res = mp_copy (&y, &v)) != MP_OKAY) { |
|
|
55 goto __ERR; |
|
|
56 } |
|
|
57 mp_set (&D, 1); |
|
|
58 |
|
|
59 top: |
|
|
60 /* 4. while u is even do */ |
|
|
61 while (mp_iseven (&u) == 1) { |
|
|
62 /* 4.1 u = u/2 */ |
|
|
63 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) { |
|
|
64 goto __ERR; |
|
|
65 } |
|
|
66 /* 4.2 if B is odd then */ |
|
|
67 if (mp_isodd (&B) == 1) { |
|
|
68 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) { |
|
|
69 goto __ERR; |
|
|
70 } |
|
|
71 } |
|
|
72 /* B = B/2 */ |
|
|
73 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) { |
|
|
74 goto __ERR; |
|
|
75 } |
|
|
76 } |
|
|
77 |
|
|
78 /* 5. while v is even do */ |
|
|
79 while (mp_iseven (&v) == 1) { |
|
|
80 /* 5.1 v = v/2 */ |
|
|
81 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) { |
|
|
82 goto __ERR; |
|
|
83 } |
|
|
84 /* 5.2 if D is odd then */ |
|
|
85 if (mp_isodd (&D) == 1) { |
|
|
86 /* D = (D-x)/2 */ |
|
|
87 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) { |
|
|
88 goto __ERR; |
|
|
89 } |
|
|
90 } |
|
|
91 /* D = D/2 */ |
|
|
92 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) { |
|
|
93 goto __ERR; |
|
|
94 } |
|
|
95 } |
|
|
96 |
|
|
97 /* 6. if u >= v then */ |
|
|
98 if (mp_cmp (&u, &v) != MP_LT) { |
|
|
99 /* u = u - v, B = B - D */ |
|
|
100 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) { |
|
|
101 goto __ERR; |
|
|
102 } |
|
|
103 |
|
|
104 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) { |
|
|
105 goto __ERR; |
|
|
106 } |
|
|
107 } else { |
|
|
108 /* v - v - u, D = D - B */ |
|
|
109 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) { |
|
|
110 goto __ERR; |
|
|
111 } |
|
|
112 |
|
|
113 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) { |
|
|
114 goto __ERR; |
|
|
115 } |
|
|
116 } |
|
|
117 |
|
|
118 /* if not zero goto step 4 */ |
|
|
119 if (mp_iszero (&u) == 0) { |
|
|
120 goto top; |
|
|
121 } |
|
|
122 |
|
|
123 /* now a = C, b = D, gcd == g*v */ |
|
|
124 |
|
|
125 /* if v != 1 then there is no inverse */ |
|
|
126 if (mp_cmp_d (&v, 1) != MP_EQ) { |
|
|
127 res = MP_VAL; |
|
|
128 goto __ERR; |
|
|
129 } |
|
|
130 |
|
|
131 /* b is now the inverse */ |
|
|
132 neg = a->sign; |
|
|
133 while (D.sign == MP_NEG) { |
|
|
134 if ((res = mp_add (&D, b, &D)) != MP_OKAY) { |
|
|
135 goto __ERR; |
|
|
136 } |
|
|
137 } |
|
|
138 mp_exch (&D, c); |
|
|
139 c->sign = neg; |
|
|
140 res = MP_OKAY; |
|
|
141 |
|
|
142 __ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL); |
|
|
143 return res; |
|
|
144 } |
|
142
|
145 #endif |
