Mercurial > dropbear

comparison bn_s_mp_exptmod.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import of libtommath 0.35
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 08:59:30 +0000
parents d29b64170cf0
children
comparison
equal deleted inserted replaced
142:d29b64170cf0 190:d8254fc979e9
19 #define TAB_SIZE 32 19 #define TAB_SIZE 32
20 #else 20 #else
21 #define TAB_SIZE 256 21 #define TAB_SIZE 256
22 #endif 22 #endif
23 23
24 int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y) 24 int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)
25 { 25 {
26 mp_int M[TAB_SIZE], res, mu; 26 mp_int M[TAB_SIZE], res, mu;
27 mp_digit buf; 27 mp_digit buf;
28 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; 28 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
29 int (*redux)(mp_int*,mp_int*,mp_int*);
29 30
30 /* find window size */ 31 /* find window size */
31 x = mp_count_bits (X); 32 x = mp_count_bits (X);
32 if (x <= 7) { 33 if (x <= 7) {
33 winsize = 2; 34 winsize = 2;
68 } 69 }
69 } 70 }
70 71
71 /* create mu, used for Barrett reduction */ 72 /* create mu, used for Barrett reduction */
72 if ((err = mp_init (&mu)) != MP_OKAY) { 73 if ((err = mp_init (&mu)) != MP_OKAY) {
73 goto __M; 74 goto LBL_M;
74 } 75 }
75 if ((err = mp_reduce_setup (&mu, P)) != MP_OKAY) { 76
76 goto __MU; 77 if (redmode == 0) {
77 } 78 if ((err = mp_reduce_setup (&mu, P)) != MP_OKAY) {
79 goto LBL_MU;
80 }
81 redux = mp_reduce;
82 } else {
83 if ((err = mp_reduce_2k_setup_l (P, &mu)) != MP_OKAY) {
84 goto LBL_MU;
85 }
86 redux = mp_reduce_2k_l;
87 }
78 88
79 /* create M table 89 /* create M table
80 * 90 *
81 * The M table contains powers of the base, 91 * The M table contains powers of the base,
82 * e.g. M[x] = G**x mod P 92 * e.g. M[x] = G**x mod P
83 * 93 *
84 * The first half of the table is not 94 * The first half of the table is not
85 * computed though accept for M[0] and M[1] 95 * computed though accept for M[0] and M[1]
86 */ 96 */
87 if ((err = mp_mod (G, P, &M[1])) != MP_OKAY) { 97 if ((err = mp_mod (G, P, &M[1])) != MP_OKAY) {
88 goto __MU; 98 goto LBL_MU;
89 } 99 }
90 100
91 /* compute the value at M[1<<(winsize-1)] by squaring 101 /* compute the value at M[1<<(winsize-1)] by squaring
92 * M[1] (winsize-1) times 102 * M[1] (winsize-1) times
93 */ 103 */
94 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) { 104 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) {
95 goto __MU; 105 goto LBL_MU;
96 } 106 }
97 107
98 for (x = 0; x < (winsize - 1); x++) { 108 for (x = 0; x < (winsize - 1); x++) {
109 /* square it */
99 if ((err = mp_sqr (&M[1 << (winsize - 1)], 110 if ((err = mp_sqr (&M[1 << (winsize - 1)],
100 &M[1 << (winsize - 1)])) != MP_OKAY) { 111 &M[1 << (winsize - 1)])) != MP_OKAY) {
101 goto __MU; 112 goto LBL_MU;
102 } 113 }
103 if ((err = mp_reduce (&M[1 << (winsize - 1)], P, &mu)) != MP_OKAY) { 114
104 goto __MU; 115 /* reduce modulo P */
116 if ((err = redux (&M[1 << (winsize - 1)], P, &mu)) != MP_OKAY) {
117 goto LBL_MU;
105 } 118 }
106 } 119 }
107 120
108 /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) 121 /* create upper table, that is M[x] = M[x-1] * M[1] (mod P)
109 * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) 122 * for x = (2**(winsize - 1) + 1) to (2**winsize - 1)
110 */ 123 */
111 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { 124 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
112 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) { 125 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) {
113 goto __MU; 126 goto LBL_MU;
114 } 127 }
115 if ((err = mp_reduce (&M[x], P, &mu)) != MP_OKAY) { 128 if ((err = redux (&M[x], P, &mu)) != MP_OKAY) {
116 goto __MU; 129 goto LBL_MU;
117 } 130 }
118 } 131 }
119 132
120 /* setup result */ 133 /* setup result */
121 if ((err = mp_init (&res)) != MP_OKAY) { 134 if ((err = mp_init (&res)) != MP_OKAY) {
122 goto __MU; 135 goto LBL_MU;
123 } 136 }
124 mp_set (&res, 1); 137 mp_set (&res, 1);
125 138
126 /* set initial mode and bit cnt */ 139 /* set initial mode and bit cnt */
127 mode = 0; 140 mode = 0;
157 } 170 }
158 171
159 /* if the bit is zero and mode == 1 then we square */ 172 /* if the bit is zero and mode == 1 then we square */
160 if (mode == 1 && y == 0) { 173 if (mode == 1 && y == 0) {
161 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 174 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
162 goto __RES; 175 goto LBL_RES;
163 } 176 }
164 if ((err = mp_reduce (&res, P, &mu)) != MP_OKAY) { 177 if ((err = redux (&res, P, &mu)) != MP_OKAY) {
165 goto __RES; 178 goto LBL_RES;
166 } 179 }
167 continue; 180 continue;
168 } 181 }
169 182
170 /* else we add it to the window */ 183 /* else we add it to the window */
174 if (bitcpy == winsize) { 187 if (bitcpy == winsize) {
175 /* ok window is filled so square as required and multiply */ 188 /* ok window is filled so square as required and multiply */
176 /* square first */ 189 /* square first */
177 for (x = 0; x < winsize; x++) { 190 for (x = 0; x < winsize; x++) {
178 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 191 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
179 goto __RES; 192 goto LBL_RES;
180 } 193 }
181 if ((err = mp_reduce (&res, P, &mu)) != MP_OKAY) { 194 if ((err = redux (&res, P, &mu)) != MP_OKAY) {
182 goto __RES; 195 goto LBL_RES;
183 } 196 }
184 } 197 }
185 198
186 /* then multiply */ 199 /* then multiply */
187 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) { 200 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) {
188 goto __RES; 201 goto LBL_RES;
189 } 202 }
190 if ((err = mp_reduce (&res, P, &mu)) != MP_OKAY) { 203 if ((err = redux (&res, P, &mu)) != MP_OKAY) {
191 goto __RES; 204 goto LBL_RES;
192 } 205 }
193 206
194 /* empty window and reset */ 207 /* empty window and reset */
195 bitcpy = 0; 208 bitcpy = 0;
196 bitbuf = 0; 209 bitbuf = 0;
201 /* if bits remain then square/multiply */ 214 /* if bits remain then square/multiply */
202 if (mode == 2 && bitcpy > 0) { 215 if (mode == 2 && bitcpy > 0) {
203 /* square then multiply if the bit is set */ 216 /* square then multiply if the bit is set */
204 for (x = 0; x < bitcpy; x++) { 217 for (x = 0; x < bitcpy; x++) {
205 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 218 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
206 goto __RES; 219 goto LBL_RES;
207 } 220 }
208 if ((err = mp_reduce (&res, P, &mu)) != MP_OKAY) { 221 if ((err = redux (&res, P, &mu)) != MP_OKAY) {
209 goto __RES; 222 goto LBL_RES;
210 } 223 }
211 224
212 bitbuf <<= 1; 225 bitbuf <<= 1;
213 if ((bitbuf & (1 << winsize)) != 0) { 226 if ((bitbuf & (1 << winsize)) != 0) {
214 /* then multiply */ 227 /* then multiply */
215 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) { 228 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) {
216 goto __RES; 229 goto LBL_RES;
217 } 230 }
218 if ((err = mp_reduce (&res, P, &mu)) != MP_OKAY) { 231 if ((err = redux (&res, P, &mu)) != MP_OKAY) {
219 goto __RES; 232 goto LBL_RES;
220 } 233 }
221 } 234 }
222 } 235 }
223 } 236 }
224 237
225 mp_exch (&res, Y); 238 mp_exch (&res, Y);
226 err = MP_OKAY; 239 err = MP_OKAY;
227 __RES:mp_clear (&res); 240 LBL_RES:mp_clear (&res);
228 __MU:mp_clear (&mu); 241 LBL_MU:mp_clear (&mu);
229 __M: 242 LBL_M:
230 mp_clear(&M[1]); 243 mp_clear(&M[1]);
231 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 244 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
232 mp_clear (&M[x]); 245 mp_clear (&M[x]);
233 } 246 }
234 return err; 247 return err;