|
2
|
1 /* Start: bn_error.c */ |
|
142
|
2 #include <tommath.h> |
|
|
3 #ifdef BN_ERROR_C |
|
|
4 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
5 * |
|
|
6 * LibTomMath is a library that provides multiple-precision |
|
|
7 * integer arithmetic as well as number theoretic functionality. |
|
|
8 * |
|
|
9 * The library was designed directly after the MPI library by |
|
|
10 * Michael Fromberger but has been written from scratch with |
|
|
11 * additional optimizations in place. |
|
|
12 * |
|
|
13 * The library is free for all purposes without any express |
|
|
14 * guarantee it works. |
|
|
15 * |
|
|
16 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
17 */ |
|
2
|
18 |
|
|
19 static const struct { |
|
|
20 int code; |
|
|
21 char *msg; |
|
|
22 } msgs[] = { |
|
|
23 { MP_OKAY, "Successful" }, |
|
|
24 { MP_MEM, "Out of heap" }, |
|
|
25 { MP_VAL, "Value out of range" } |
|
|
26 }; |
|
|
27 |
|
|
28 /* return a char * string for a given code */ |
|
|
29 char *mp_error_to_string(int code) |
|
|
30 { |
|
|
31 int x; |
|
|
32 |
|
|
33 /* scan the lookup table for the given message */ |
|
|
34 for (x = 0; x < (int)(sizeof(msgs) / sizeof(msgs[0])); x++) { |
|
|
35 if (msgs[x].code == code) { |
|
|
36 return msgs[x].msg; |
|
|
37 } |
|
|
38 } |
|
|
39 |
|
|
40 /* generic reply for invalid code */ |
|
|
41 return "Invalid error code"; |
|
|
42 } |
|
|
43 |
|
142
|
44 #endif |
|
2
|
45 |
|
|
46 /* End: bn_error.c */ |
|
|
47 |
|
|
48 /* Start: bn_fast_mp_invmod.c */ |
|
142
|
49 #include <tommath.h> |
|
|
50 #ifdef BN_FAST_MP_INVMOD_C |
|
|
51 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
52 * |
|
|
53 * LibTomMath is a library that provides multiple-precision |
|
|
54 * integer arithmetic as well as number theoretic functionality. |
|
|
55 * |
|
|
56 * The library was designed directly after the MPI library by |
|
|
57 * Michael Fromberger but has been written from scratch with |
|
|
58 * additional optimizations in place. |
|
|
59 * |
|
|
60 * The library is free for all purposes without any express |
|
|
61 * guarantee it works. |
|
|
62 * |
|
|
63 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
64 */ |
|
2
|
65 |
|
|
66 /* computes the modular inverse via binary extended euclidean algorithm, |
|
|
67 * that is c = 1/a mod b |
|
|
68 * |
|
142
|
69 * Based on slow invmod except this is optimized for the case where b is |
|
2
|
70 * odd as per HAC Note 14.64 on pp. 610 |
|
|
71 */ |
|
|
72 int |
|
|
73 fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c) |
|
|
74 { |
|
|
75 mp_int x, y, u, v, B, D; |
|
|
76 int res, neg; |
|
|
77 |
|
|
78 /* 2. [modified] b must be odd */ |
|
|
79 if (mp_iseven (b) == 1) { |
|
|
80 return MP_VAL; |
|
|
81 } |
|
|
82 |
|
|
83 /* init all our temps */ |
|
|
84 if ((res = mp_init_multi(&x, &y, &u, &v, &B, &D, NULL)) != MP_OKAY) { |
|
|
85 return res; |
|
|
86 } |
|
|
87 |
|
|
88 /* x == modulus, y == value to invert */ |
|
|
89 if ((res = mp_copy (b, &x)) != MP_OKAY) { |
|
|
90 goto __ERR; |
|
|
91 } |
|
|
92 |
|
|
93 /* we need y = |a| */ |
|
|
94 if ((res = mp_abs (a, &y)) != MP_OKAY) { |
|
|
95 goto __ERR; |
|
|
96 } |
|
|
97 |
|
|
98 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */ |
|
|
99 if ((res = mp_copy (&x, &u)) != MP_OKAY) { |
|
|
100 goto __ERR; |
|
|
101 } |
|
|
102 if ((res = mp_copy (&y, &v)) != MP_OKAY) { |
|
|
103 goto __ERR; |
|
|
104 } |
|
|
105 mp_set (&D, 1); |
|
|
106 |
|
|
107 top: |
|
|
108 /* 4. while u is even do */ |
|
|
109 while (mp_iseven (&u) == 1) { |
|
|
110 /* 4.1 u = u/2 */ |
|
|
111 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) { |
|
|
112 goto __ERR; |
|
|
113 } |
|
|
114 /* 4.2 if B is odd then */ |
|
|
115 if (mp_isodd (&B) == 1) { |
|
|
116 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) { |
|
|
117 goto __ERR; |
|
|
118 } |
|
|
119 } |
|
|
120 /* B = B/2 */ |
|
|
121 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) { |
|
|
122 goto __ERR; |
|
|
123 } |
|
|
124 } |
|
|
125 |
|
|
126 /* 5. while v is even do */ |
|
|
127 while (mp_iseven (&v) == 1) { |
|
|
128 /* 5.1 v = v/2 */ |
|
|
129 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) { |
|
|
130 goto __ERR; |
|
|
131 } |
|
|
132 /* 5.2 if D is odd then */ |
|
|
133 if (mp_isodd (&D) == 1) { |
|
|
134 /* D = (D-x)/2 */ |
|
|
135 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) { |
|
|
136 goto __ERR; |
|
|
137 } |
|
|
138 } |
|
|
139 /* D = D/2 */ |
|
|
140 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) { |
|
|
141 goto __ERR; |
|
|
142 } |
|
|
143 } |
|
|
144 |
|
|
145 /* 6. if u >= v then */ |
|
|
146 if (mp_cmp (&u, &v) != MP_LT) { |
|
|
147 /* u = u - v, B = B - D */ |
|
|
148 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) { |
|
|
149 goto __ERR; |
|
|
150 } |
|
|
151 |
|
|
152 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) { |
|
|
153 goto __ERR; |
|
|
154 } |
|
|
155 } else { |
|
|
156 /* v - v - u, D = D - B */ |
|
|
157 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) { |
|
|
158 goto __ERR; |
|
|
159 } |
|
|
160 |
|
|
161 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) { |
|
|
162 goto __ERR; |
|
|
163 } |
|
|
164 } |
|
|
165 |
|
|
166 /* if not zero goto step 4 */ |
|
|
167 if (mp_iszero (&u) == 0) { |
|
|
168 goto top; |
|
|
169 } |
|
|
170 |
|
|
171 /* now a = C, b = D, gcd == g*v */ |
|
|
172 |
|
|
173 /* if v != 1 then there is no inverse */ |
|
|
174 if (mp_cmp_d (&v, 1) != MP_EQ) { |
|
|
175 res = MP_VAL; |
|
|
176 goto __ERR; |
|
|
177 } |
|
|
178 |
|
|
179 /* b is now the inverse */ |
|
|
180 neg = a->sign; |
|
|
181 while (D.sign == MP_NEG) { |
|
|
182 if ((res = mp_add (&D, b, &D)) != MP_OKAY) { |
|
|
183 goto __ERR; |
|
|
184 } |
|
|
185 } |
|
|
186 mp_exch (&D, c); |
|
|
187 c->sign = neg; |
|
|
188 res = MP_OKAY; |
|
|
189 |
|
|
190 __ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL); |
|
|
191 return res; |
|
|
192 } |
|
142
|
193 #endif |
|
2
|
194 |
|
|
195 /* End: bn_fast_mp_invmod.c */ |
|
|
196 |
|
|
197 /* Start: bn_fast_mp_montgomery_reduce.c */ |
|
142
|
198 #include <tommath.h> |
|
|
199 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C |
|
|
200 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
201 * |
|
|
202 * LibTomMath is a library that provides multiple-precision |
|
|
203 * integer arithmetic as well as number theoretic functionality. |
|
|
204 * |
|
|
205 * The library was designed directly after the MPI library by |
|
|
206 * Michael Fromberger but has been written from scratch with |
|
|
207 * additional optimizations in place. |
|
|
208 * |
|
|
209 * The library is free for all purposes without any express |
|
|
210 * guarantee it works. |
|
|
211 * |
|
|
212 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
213 */ |
|
2
|
214 |
|
|
215 /* computes xR**-1 == x (mod N) via Montgomery Reduction |
|
|
216 * |
|
142
|
217 * This is an optimized implementation of montgomery_reduce |
|
2
|
218 * which uses the comba method to quickly calculate the columns of the |
|
|
219 * reduction. |
|
|
220 * |
|
|
221 * Based on Algorithm 14.32 on pp.601 of HAC. |
|
|
222 */ |
|
|
223 int |
|
|
224 fast_mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho) |
|
|
225 { |
|
|
226 int ix, res, olduse; |
|
|
227 mp_word W[MP_WARRAY]; |
|
|
228 |
|
|
229 /* get old used count */ |
|
|
230 olduse = x->used; |
|
|
231 |
|
|
232 /* grow a as required */ |
|
|
233 if (x->alloc < n->used + 1) { |
|
|
234 if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) { |
|
|
235 return res; |
|
|
236 } |
|
|
237 } |
|
|
238 |
|
|
239 /* first we have to get the digits of the input into |
|
|
240 * an array of double precision words W[...] |
|
|
241 */ |
|
|
242 { |
|
|
243 register mp_word *_W; |
|
|
244 register mp_digit *tmpx; |
|
|
245 |
|
|
246 /* alias for the W[] array */ |
|
|
247 _W = W; |
|
|
248 |
|
|
249 /* alias for the digits of x*/ |
|
|
250 tmpx = x->dp; |
|
|
251 |
|
|
252 /* copy the digits of a into W[0..a->used-1] */ |
|
|
253 for (ix = 0; ix < x->used; ix++) { |
|
|
254 *_W++ = *tmpx++; |
|
|
255 } |
|
|
256 |
|
|
257 /* zero the high words of W[a->used..m->used*2] */ |
|
|
258 for (; ix < n->used * 2 + 1; ix++) { |
|
|
259 *_W++ = 0; |
|
|
260 } |
|
|
261 } |
|
|
262 |
|
|
263 /* now we proceed to zero successive digits |
|
|
264 * from the least significant upwards |
|
|
265 */ |
|
|
266 for (ix = 0; ix < n->used; ix++) { |
|
|
267 /* mu = ai * m' mod b |
|
|
268 * |
|
|
269 * We avoid a double precision multiplication (which isn't required) |
|
|
270 * by casting the value down to a mp_digit. Note this requires |
|
|
271 * that W[ix-1] have the carry cleared (see after the inner loop) |
|
|
272 */ |
|
|
273 register mp_digit mu; |
|
|
274 mu = (mp_digit) (((W[ix] & MP_MASK) * rho) & MP_MASK); |
|
|
275 |
|
|
276 /* a = a + mu * m * b**i |
|
|
277 * |
|
|
278 * This is computed in place and on the fly. The multiplication |
|
|
279 * by b**i is handled by offseting which columns the results |
|
|
280 * are added to. |
|
|
281 * |
|
|
282 * Note the comba method normally doesn't handle carries in the |
|
|
283 * inner loop In this case we fix the carry from the previous |
|
|
284 * column since the Montgomery reduction requires digits of the |
|
|
285 * result (so far) [see above] to work. This is |
|
|
286 * handled by fixing up one carry after the inner loop. The |
|
|
287 * carry fixups are done in order so after these loops the |
|
|
288 * first m->used words of W[] have the carries fixed |
|
|
289 */ |
|
|
290 { |
|
|
291 register int iy; |
|
|
292 register mp_digit *tmpn; |
|
|
293 register mp_word *_W; |
|
|
294 |
|
|
295 /* alias for the digits of the modulus */ |
|
|
296 tmpn = n->dp; |
|
|
297 |
|
|
298 /* Alias for the columns set by an offset of ix */ |
|
|
299 _W = W + ix; |
|
|
300 |
|
|
301 /* inner loop */ |
|
|
302 for (iy = 0; iy < n->used; iy++) { |
|
|
303 *_W++ += ((mp_word)mu) * ((mp_word)*tmpn++); |
|
|
304 } |
|
|
305 } |
|
|
306 |
|
|
307 /* now fix carry for next digit, W[ix+1] */ |
|
|
308 W[ix + 1] += W[ix] >> ((mp_word) DIGIT_BIT); |
|
|
309 } |
|
|
310 |
|
|
311 /* now we have to propagate the carries and |
|
|
312 * shift the words downward [all those least |
|
|
313 * significant digits we zeroed]. |
|
|
314 */ |
|
|
315 { |
|
|
316 register mp_digit *tmpx; |
|
|
317 register mp_word *_W, *_W1; |
|
|
318 |
|
|
319 /* nox fix rest of carries */ |
|
|
320 |
|
|
321 /* alias for current word */ |
|
|
322 _W1 = W + ix; |
|
|
323 |
|
|
324 /* alias for next word, where the carry goes */ |
|
|
325 _W = W + ++ix; |
|
|
326 |
|
|
327 for (; ix <= n->used * 2 + 1; ix++) { |
|
|
328 *_W++ += *_W1++ >> ((mp_word) DIGIT_BIT); |
|
|
329 } |
|
|
330 |
|
|
331 /* copy out, A = A/b**n |
|
|
332 * |
|
|
333 * The result is A/b**n but instead of converting from an |
|
|
334 * array of mp_word to mp_digit than calling mp_rshd |
|
|
335 * we just copy them in the right order |
|
|
336 */ |
|
|
337 |
|
|
338 /* alias for destination word */ |
|
|
339 tmpx = x->dp; |
|
|
340 |
|
|
341 /* alias for shifted double precision result */ |
|
|
342 _W = W + n->used; |
|
|
343 |
|
|
344 for (ix = 0; ix < n->used + 1; ix++) { |
|
|
345 *tmpx++ = (mp_digit)(*_W++ & ((mp_word) MP_MASK)); |
|
|
346 } |
|
|
347 |
|
|
348 /* zero oldused digits, if the input a was larger than |
|
|
349 * m->used+1 we'll have to clear the digits |
|
|
350 */ |
|
|
351 for (; ix < olduse; ix++) { |
|
|
352 *tmpx++ = 0; |
|
|
353 } |
|
|
354 } |
|
|
355 |
|
|
356 /* set the max used and clamp */ |
|
|
357 x->used = n->used + 1; |
|
|
358 mp_clamp (x); |
|
|
359 |
|
|
360 /* if A >= m then A = A - m */ |
|
|
361 if (mp_cmp_mag (x, n) != MP_LT) { |
|
|
362 return s_mp_sub (x, n, x); |
|
|
363 } |
|
|
364 return MP_OKAY; |
|
|
365 } |
|
142
|
366 #endif |
|
2
|
367 |
|
|
368 /* End: bn_fast_mp_montgomery_reduce.c */ |
|
|
369 |
|
|
370 /* Start: bn_fast_s_mp_mul_digs.c */ |
|
142
|
371 #include <tommath.h> |
|
|
372 #ifdef BN_FAST_S_MP_MUL_DIGS_C |
|
|
373 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
374 * |
|
|
375 * LibTomMath is a library that provides multiple-precision |
|
|
376 * integer arithmetic as well as number theoretic functionality. |
|
|
377 * |
|
|
378 * The library was designed directly after the MPI library by |
|
|
379 * Michael Fromberger but has been written from scratch with |
|
|
380 * additional optimizations in place. |
|
|
381 * |
|
|
382 * The library is free for all purposes without any express |
|
|
383 * guarantee it works. |
|
|
384 * |
|
|
385 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
386 */ |
|
2
|
387 |
|
|
388 /* Fast (comba) multiplier |
|
|
389 * |
|
|
390 * This is the fast column-array [comba] multiplier. It is |
|
|
391 * designed to compute the columns of the product first |
|
|
392 * then handle the carries afterwards. This has the effect |
|
|
393 * of making the nested loops that compute the columns very |
|
|
394 * simple and schedulable on super-scalar processors. |
|
|
395 * |
|
|
396 * This has been modified to produce a variable number of |
|
|
397 * digits of output so if say only a half-product is required |
|
|
398 * you don't have to compute the upper half (a feature |
|
|
399 * required for fast Barrett reduction). |
|
|
400 * |
|
|
401 * Based on Algorithm 14.12 on pp.595 of HAC. |
|
|
402 * |
|
|
403 */ |
|
|
404 int |
|
|
405 fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs) |
|
|
406 { |
|
142
|
407 int olduse, res, pa, ix, iz; |
|
|
408 mp_digit W[MP_WARRAY]; |
|
|
409 register mp_word _W; |
|
2
|
410 |
|
|
411 /* grow the destination as required */ |
|
|
412 if (c->alloc < digs) { |
|
|
413 if ((res = mp_grow (c, digs)) != MP_OKAY) { |
|
|
414 return res; |
|
|
415 } |
|
|
416 } |
|
|
417 |
|
142
|
418 /* number of output digits to produce */ |
|
|
419 pa = MIN(digs, a->used + b->used); |
|
|
420 |
|
|
421 /* clear the carry */ |
|
|
422 _W = 0; |
|
|
423 for (ix = 0; ix <= pa; ix++) { |
|
|
424 int tx, ty; |
|
|
425 int iy; |
|
|
426 mp_digit *tmpx, *tmpy; |
|
|
427 |
|
|
428 /* get offsets into the two bignums */ |
|
|
429 ty = MIN(b->used-1, ix); |
|
|
430 tx = ix - ty; |
|
|
431 |
|
|
432 /* setup temp aliases */ |
|
|
433 tmpx = a->dp + tx; |
|
|
434 tmpy = b->dp + ty; |
|
|
435 |
|
|
436 /* this is the number of times the loop will iterrate, essentially its |
|
|
437 while (tx++ < a->used && ty-- >= 0) { ... } |
|
2
|
438 */ |
|
142
|
439 iy = MIN(a->used-tx, ty+1); |
|
|
440 |
|
|
441 /* execute loop */ |
|
|
442 for (iz = 0; iz < iy; ++iz) { |
|
|
443 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); |
|
2
|
444 } |
|
142
|
445 |
|
|
446 /* store term */ |
|
|
447 W[ix] = ((mp_digit)_W) & MP_MASK; |
|
|
448 |
|
|
449 /* make next carry */ |
|
|
450 _W = _W >> ((mp_word)DIGIT_BIT); |
|
2
|
451 } |
|
|
452 |
|
|
453 /* setup dest */ |
|
142
|
454 olduse = c->used; |
|
2
|
455 c->used = digs; |
|
|
456 |
|
|
457 { |
|
|
458 register mp_digit *tmpc; |
|
|
459 tmpc = c->dp; |
|
142
|
460 for (ix = 0; ix < digs; ix++) { |
|
2
|
461 /* now extract the previous digit [below the carry] */ |
|
142
|
462 *tmpc++ = W[ix]; |
|
|
463 } |
|
2
|
464 |
|
|
465 /* clear unused digits [that existed in the old copy of c] */ |
|
|
466 for (; ix < olduse; ix++) { |
|
|
467 *tmpc++ = 0; |
|
|
468 } |
|
|
469 } |
|
|
470 mp_clamp (c); |
|
|
471 return MP_OKAY; |
|
|
472 } |
|
142
|
473 #endif |
|
2
|
474 |
|
|
475 /* End: bn_fast_s_mp_mul_digs.c */ |
|
|
476 |
|
|
477 /* Start: bn_fast_s_mp_mul_high_digs.c */ |
|
142
|
478 #include <tommath.h> |
|
|
479 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C |
|
|
480 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
481 * |
|
|
482 * LibTomMath is a library that provides multiple-precision |
|
|
483 * integer arithmetic as well as number theoretic functionality. |
|
|
484 * |
|
|
485 * The library was designed directly after the MPI library by |
|
|
486 * Michael Fromberger but has been written from scratch with |
|
|
487 * additional optimizations in place. |
|
|
488 * |
|
|
489 * The library is free for all purposes without any express |
|
|
490 * guarantee it works. |
|
|
491 * |
|
|
492 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
493 */ |
|
|
494 |
|
|
495 /* this is a modified version of fast_s_mul_digs that only produces |
|
|
496 * output digits *above* digs. See the comments for fast_s_mul_digs |
|
2
|
497 * to see how it works. |
|
|
498 * |
|
|
499 * This is used in the Barrett reduction since for one of the multiplications |
|
|
500 * only the higher digits were needed. This essentially halves the work. |
|
|
501 * |
|
|
502 * Based on Algorithm 14.12 on pp.595 of HAC. |
|
|
503 */ |
|
|
504 int |
|
|
505 fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) |
|
|
506 { |
|
142
|
507 int olduse, res, pa, ix, iz; |
|
|
508 mp_digit W[MP_WARRAY]; |
|
|
509 mp_word _W; |
|
|
510 |
|
|
511 /* grow the destination as required */ |
|
|
512 pa = a->used + b->used; |
|
|
513 if (c->alloc < pa) { |
|
|
514 if ((res = mp_grow (c, pa)) != MP_OKAY) { |
|
2
|
515 return res; |
|
|
516 } |
|
|
517 } |
|
|
518 |
|
142
|
519 /* number of output digits to produce */ |
|
|
520 pa = a->used + b->used; |
|
|
521 _W = 0; |
|
|
522 for (ix = digs; ix <= pa; ix++) { |
|
|
523 int tx, ty, iy; |
|
|
524 mp_digit *tmpx, *tmpy; |
|
|
525 |
|
|
526 /* get offsets into the two bignums */ |
|
|
527 ty = MIN(b->used-1, ix); |
|
|
528 tx = ix - ty; |
|
|
529 |
|
|
530 /* setup temp aliases */ |
|
|
531 tmpx = a->dp + tx; |
|
|
532 tmpy = b->dp + ty; |
|
|
533 |
|
|
534 /* this is the number of times the loop will iterrate, essentially its |
|
|
535 while (tx++ < a->used && ty-- >= 0) { ... } |
|
2
|
536 */ |
|
142
|
537 iy = MIN(a->used-tx, ty+1); |
|
|
538 |
|
|
539 /* execute loop */ |
|
|
540 for (iz = 0; iz < iy; iz++) { |
|
|
541 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); |
|
2
|
542 } |
|
|
543 |
|
142
|
544 /* store term */ |
|
|
545 W[ix] = ((mp_digit)_W) & MP_MASK; |
|
|
546 |
|
|
547 /* make next carry */ |
|
|
548 _W = _W >> ((mp_word)DIGIT_BIT); |
|
2
|
549 } |
|
|
550 |
|
|
551 /* setup dest */ |
|
142
|
552 olduse = c->used; |
|
|
553 c->used = pa; |
|
|
554 |
|
|
555 { |
|
|
556 register mp_digit *tmpc; |
|
|
557 |
|
|
558 tmpc = c->dp + digs; |
|
|
559 for (ix = digs; ix <= pa; ix++) { |
|
|
560 /* now extract the previous digit [below the carry] */ |
|
|
561 *tmpc++ = W[ix]; |
|
|
562 } |
|
|
563 |
|
|
564 /* clear unused digits [that existed in the old copy of c] */ |
|
|
565 for (; ix < olduse; ix++) { |
|
|
566 *tmpc++ = 0; |
|
|
567 } |
|
2
|
568 } |
|
|
569 mp_clamp (c); |
|
|
570 return MP_OKAY; |
|
|
571 } |
|
142
|
572 #endif |
|
2
|
573 |
|
|
574 /* End: bn_fast_s_mp_mul_high_digs.c */ |
|
|
575 |
|
|
576 /* Start: bn_fast_s_mp_sqr.c */ |
|
142
|
577 #include <tommath.h> |
|
|
578 #ifdef BN_FAST_S_MP_SQR_C |
|
|
579 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
580 * |
|
|
581 * LibTomMath is a library that provides multiple-precision |
|
|
582 * integer arithmetic as well as number theoretic functionality. |
|
|
583 * |
|
|
584 * The library was designed directly after the MPI library by |
|
|
585 * Michael Fromberger but has been written from scratch with |
|
|
586 * additional optimizations in place. |
|
|
587 * |
|
|
588 * The library is free for all purposes without any express |
|
|
589 * guarantee it works. |
|
|
590 * |
|
|
591 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
592 */ |
|
2
|
593 |
|
|
594 /* fast squaring |
|
|
595 * |
|
|
596 * This is the comba method where the columns of the product |
|
|
597 * are computed first then the carries are computed. This |
|
|
598 * has the effect of making a very simple inner loop that |
|
|
599 * is executed the most |
|
|
600 * |
|
|
601 * W2 represents the outer products and W the inner. |
|
|
602 * |
|
|
603 * A further optimizations is made because the inner |
|
|
604 * products are of the form "A * B * 2". The *2 part does |
|
|
605 * not need to be computed until the end which is good |
|
|
606 * because 64-bit shifts are slow! |
|
|
607 * |
|
|
608 * Based on Algorithm 14.16 on pp.597 of HAC. |
|
|
609 * |
|
|
610 */ |
|
142
|
611 /* the jist of squaring... |
|
|
612 |
|
|
613 you do like mult except the offset of the tmpx [one that starts closer to zero] |
|
|
614 can't equal the offset of tmpy. So basically you set up iy like before then you min it with |
|
|
615 (ty-tx) so that it never happens. You double all those you add in the inner loop |
|
|
616 |
|
|
617 After that loop you do the squares and add them in. |
|
|
618 |
|
|
619 Remove W2 and don't memset W |
|
|
620 |
|
|
621 */ |
|
|
622 |
|
2
|
623 int fast_s_mp_sqr (mp_int * a, mp_int * b) |
|
|
624 { |
|
142
|
625 int olduse, res, pa, ix, iz; |
|
|
626 mp_digit W[MP_WARRAY], *tmpx; |
|
|
627 mp_word W1; |
|
|
628 |
|
|
629 /* grow the destination as required */ |
|
|
630 pa = a->used + a->used; |
|
|
631 if (b->alloc < pa) { |
|
|
632 if ((res = mp_grow (b, pa)) != MP_OKAY) { |
|
2
|
633 return res; |
|
|
634 } |
|
|
635 } |
|
|
636 |
|
142
|
637 /* number of output digits to produce */ |
|
|
638 W1 = 0; |
|
|
639 for (ix = 0; ix <= pa; ix++) { |
|
|
640 int tx, ty, iy; |
|
|
641 mp_word _W; |
|
|
642 mp_digit *tmpy; |
|
|
643 |
|
|
644 /* clear counter */ |
|
|
645 _W = 0; |
|
|
646 |
|
|
647 /* get offsets into the two bignums */ |
|
|
648 ty = MIN(a->used-1, ix); |
|
|
649 tx = ix - ty; |
|
|
650 |
|
|
651 /* setup temp aliases */ |
|
|
652 tmpx = a->dp + tx; |
|
|
653 tmpy = a->dp + ty; |
|
|
654 |
|
|
655 /* this is the number of times the loop will iterrate, essentially its |
|
|
656 while (tx++ < a->used && ty-- >= 0) { ... } |
|
|
657 */ |
|
|
658 iy = MIN(a->used-tx, ty+1); |
|
|
659 |
|
|
660 /* now for squaring tx can never equal ty |
|
|
661 * we halve the distance since they approach at a rate of 2x |
|
|
662 * and we have to round because odd cases need to be executed |
|
|
663 */ |
|
|
664 iy = MIN(iy, (ty-tx+1)>>1); |
|
|
665 |
|
|
666 /* execute loop */ |
|
|
667 for (iz = 0; iz < iy; iz++) { |
|
|
668 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--); |
|
2
|
669 } |
|
142
|
670 |
|
|
671 /* double the inner product and add carry */ |
|
|
672 _W = _W + _W + W1; |
|
|
673 |
|
|
674 /* even columns have the square term in them */ |
|
|
675 if ((ix&1) == 0) { |
|
|
676 _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]); |
|
|
677 } |
|
|
678 |
|
|
679 /* store it */ |
|
|
680 W[ix] = _W; |
|
|
681 |
|
|
682 /* make next carry */ |
|
|
683 W1 = _W >> ((mp_word)DIGIT_BIT); |
|
2
|
684 } |
|
|
685 |
|
|
686 /* setup dest */ |
|
|
687 olduse = b->used; |
|
142
|
688 b->used = a->used+a->used; |
|
|
689 |
|
2
|
690 { |
|
142
|
691 mp_digit *tmpb; |
|
2
|
692 tmpb = b->dp; |
|
142
|
693 for (ix = 0; ix < pa; ix++) { |
|
|
694 *tmpb++ = W[ix] & MP_MASK; |
|
|
695 } |
|
|
696 |
|
|
697 /* clear unused digits [that existed in the old copy of c] */ |
|
2
|
698 for (; ix < olduse; ix++) { |
|
|
699 *tmpb++ = 0; |
|
|
700 } |
|
|
701 } |
|
|
702 mp_clamp (b); |
|
|
703 return MP_OKAY; |
|
|
704 } |
|
142
|
705 #endif |
|
2
|
706 |
|
|
707 /* End: bn_fast_s_mp_sqr.c */ |
|
|
708 |
|
|
709 /* Start: bn_mp_2expt.c */ |
|
142
|
710 #include <tommath.h> |
|
|
711 #ifdef BN_MP_2EXPT_C |
|
|
712 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
713 * |
|
|
714 * LibTomMath is a library that provides multiple-precision |
|
|
715 * integer arithmetic as well as number theoretic functionality. |
|
|
716 * |
|
|
717 * The library was designed directly after the MPI library by |
|
|
718 * Michael Fromberger but has been written from scratch with |
|
|
719 * additional optimizations in place. |
|
|
720 * |
|
|
721 * The library is free for all purposes without any express |
|
|
722 * guarantee it works. |
|
|
723 * |
|
|
724 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
725 */ |
|
2
|
726 |
|
|
727 /* computes a = 2**b |
|
|
728 * |
|
|
729 * Simple algorithm which zeroes the int, grows it then just sets one bit |
|
|
730 * as required. |
|
|
731 */ |
|
|
732 int |
|
|
733 mp_2expt (mp_int * a, int b) |
|
|
734 { |
|
|
735 int res; |
|
|
736 |
|
|
737 /* zero a as per default */ |
|
|
738 mp_zero (a); |
|
|
739 |
|
|
740 /* grow a to accomodate the single bit */ |
|
|
741 if ((res = mp_grow (a, b / DIGIT_BIT + 1)) != MP_OKAY) { |
|
|
742 return res; |
|
|
743 } |
|
|
744 |
|
|
745 /* set the used count of where the bit will go */ |
|
|
746 a->used = b / DIGIT_BIT + 1; |
|
|
747 |
|
|
748 /* put the single bit in its place */ |
|
142
|
749 a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT); |
|
2
|
750 |
|
|
751 return MP_OKAY; |
|
|
752 } |
|
142
|
753 #endif |
|
2
|
754 |
|
|
755 /* End: bn_mp_2expt.c */ |
|
|
756 |
|
|
757 /* Start: bn_mp_abs.c */ |
|
142
|
758 #include <tommath.h> |
|
|
759 #ifdef BN_MP_ABS_C |
|
|
760 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
761 * |
|
|
762 * LibTomMath is a library that provides multiple-precision |
|
|
763 * integer arithmetic as well as number theoretic functionality. |
|
|
764 * |
|
|
765 * The library was designed directly after the MPI library by |
|
|
766 * Michael Fromberger but has been written from scratch with |
|
|
767 * additional optimizations in place. |
|
|
768 * |
|
|
769 * The library is free for all purposes without any express |
|
|
770 * guarantee it works. |
|
|
771 * |
|
|
772 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
773 */ |
|
2
|
774 |
|
|
775 /* b = |a| |
|
|
776 * |
|
|
777 * Simple function copies the input and fixes the sign to positive |
|
|
778 */ |
|
|
779 int |
|
|
780 mp_abs (mp_int * a, mp_int * b) |
|
|
781 { |
|
|
782 int res; |
|
|
783 |
|
|
784 /* copy a to b */ |
|
|
785 if (a != b) { |
|
|
786 if ((res = mp_copy (a, b)) != MP_OKAY) { |
|
|
787 return res; |
|
|
788 } |
|
|
789 } |
|
|
790 |
|
|
791 /* force the sign of b to positive */ |
|
|
792 b->sign = MP_ZPOS; |
|
|
793 |
|
|
794 return MP_OKAY; |
|
|
795 } |
|
142
|
796 #endif |
|
2
|
797 |
|
|
798 /* End: bn_mp_abs.c */ |
|
|
799 |
|
|
800 /* Start: bn_mp_add.c */ |
|
142
|
801 #include <tommath.h> |
|
|
802 #ifdef BN_MP_ADD_C |
|
|
803 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
804 * |
|
|
805 * LibTomMath is a library that provides multiple-precision |
|
|
806 * integer arithmetic as well as number theoretic functionality. |
|
|
807 * |
|
|
808 * The library was designed directly after the MPI library by |
|
|
809 * Michael Fromberger but has been written from scratch with |
|
|
810 * additional optimizations in place. |
|
|
811 * |
|
|
812 * The library is free for all purposes without any express |
|
|
813 * guarantee it works. |
|
|
814 * |
|
|
815 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
816 */ |
|
2
|
817 |
|
|
818 /* high level addition (handles signs) */ |
|
|
819 int mp_add (mp_int * a, mp_int * b, mp_int * c) |
|
|
820 { |
|
|
821 int sa, sb, res; |
|
|
822 |
|
|
823 /* get sign of both inputs */ |
|
|
824 sa = a->sign; |
|
|
825 sb = b->sign; |
|
|
826 |
|
|
827 /* handle two cases, not four */ |
|
|
828 if (sa == sb) { |
|
|
829 /* both positive or both negative */ |
|
|
830 /* add their magnitudes, copy the sign */ |
|
|
831 c->sign = sa; |
|
|
832 res = s_mp_add (a, b, c); |
|
|
833 } else { |
|
|
834 /* one positive, the other negative */ |
|
|
835 /* subtract the one with the greater magnitude from */ |
|
|
836 /* the one of the lesser magnitude. The result gets */ |
|
|
837 /* the sign of the one with the greater magnitude. */ |
|
|
838 if (mp_cmp_mag (a, b) == MP_LT) { |
|
|
839 c->sign = sb; |
|
|
840 res = s_mp_sub (b, a, c); |
|
|
841 } else { |
|
|
842 c->sign = sa; |
|
|
843 res = s_mp_sub (a, b, c); |
|
|
844 } |
|
|
845 } |
|
|
846 return res; |
|
|
847 } |
|
|
848 |
|
142
|
849 #endif |
|
2
|
850 |
|
|
851 /* End: bn_mp_add.c */ |
|
|
852 |
|
|
853 /* Start: bn_mp_add_d.c */ |
|
142
|
854 #include <tommath.h> |
|
|
855 #ifdef BN_MP_ADD_D_C |
|
|
856 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
857 * |
|
|
858 * LibTomMath is a library that provides multiple-precision |
|
|
859 * integer arithmetic as well as number theoretic functionality. |
|
|
860 * |
|
|
861 * The library was designed directly after the MPI library by |
|
|
862 * Michael Fromberger but has been written from scratch with |
|
|
863 * additional optimizations in place. |
|
|
864 * |
|
|
865 * The library is free for all purposes without any express |
|
|
866 * guarantee it works. |
|
|
867 * |
|
|
868 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
869 */ |
|
2
|
870 |
|
|
871 /* single digit addition */ |
|
|
872 int |
|
|
873 mp_add_d (mp_int * a, mp_digit b, mp_int * c) |
|
|
874 { |
|
|
875 int res, ix, oldused; |
|
|
876 mp_digit *tmpa, *tmpc, mu; |
|
|
877 |
|
|
878 /* grow c as required */ |
|
|
879 if (c->alloc < a->used + 1) { |
|
|
880 if ((res = mp_grow(c, a->used + 1)) != MP_OKAY) { |
|
|
881 return res; |
|
|
882 } |
|
|
883 } |
|
|
884 |
|
|
885 /* if a is negative and |a| >= b, call c = |a| - b */ |
|
|
886 if (a->sign == MP_NEG && (a->used > 1 || a->dp[0] >= b)) { |
|
|
887 /* temporarily fix sign of a */ |
|
|
888 a->sign = MP_ZPOS; |
|
|
889 |
|
|
890 /* c = |a| - b */ |
|
|
891 res = mp_sub_d(a, b, c); |
|
|
892 |
|
|
893 /* fix sign */ |
|
|
894 a->sign = c->sign = MP_NEG; |
|
|
895 |
|
|
896 return res; |
|
|
897 } |
|
|
898 |
|
|
899 /* old number of used digits in c */ |
|
|
900 oldused = c->used; |
|
|
901 |
|
|
902 /* sign always positive */ |
|
|
903 c->sign = MP_ZPOS; |
|
|
904 |
|
|
905 /* source alias */ |
|
|
906 tmpa = a->dp; |
|
|
907 |
|
|
908 /* destination alias */ |
|
|
909 tmpc = c->dp; |
|
|
910 |
|
|
911 /* if a is positive */ |
|
|
912 if (a->sign == MP_ZPOS) { |
|
|
913 /* add digit, after this we're propagating |
|
|
914 * the carry. |
|
|
915 */ |
|
|
916 *tmpc = *tmpa++ + b; |
|
|
917 mu = *tmpc >> DIGIT_BIT; |
|
|
918 *tmpc++ &= MP_MASK; |
|
|
919 |
|
|
920 /* now handle rest of the digits */ |
|
|
921 for (ix = 1; ix < a->used; ix++) { |
|
|
922 *tmpc = *tmpa++ + mu; |
|
|
923 mu = *tmpc >> DIGIT_BIT; |
|
|
924 *tmpc++ &= MP_MASK; |
|
|
925 } |
|
|
926 /* set final carry */ |
|
|
927 ix++; |
|
|
928 *tmpc++ = mu; |
|
|
929 |
|
|
930 /* setup size */ |
|
|
931 c->used = a->used + 1; |
|
|
932 } else { |
|
|
933 /* a was negative and |a| < b */ |
|
|
934 c->used = 1; |
|
|
935 |
|
|
936 /* the result is a single digit */ |
|
|
937 if (a->used == 1) { |
|
|
938 *tmpc++ = b - a->dp[0]; |
|
|
939 } else { |
|
|
940 *tmpc++ = b; |
|
|
941 } |
|
|
942 |
|
|
943 /* setup count so the clearing of oldused |
|
|
944 * can fall through correctly |
|
|
945 */ |
|
|
946 ix = 1; |
|
|
947 } |
|
|
948 |
|
|
949 /* now zero to oldused */ |
|
|
950 while (ix++ < oldused) { |
|
|
951 *tmpc++ = 0; |
|
|
952 } |
|
|
953 mp_clamp(c); |
|
|
954 |
|
|
955 return MP_OKAY; |
|
|
956 } |
|
|
957 |
|
142
|
958 #endif |
|
2
|
959 |
|
|
960 /* End: bn_mp_add_d.c */ |
|
|
961 |
|
|
962 /* Start: bn_mp_addmod.c */ |
|
142
|
963 #include <tommath.h> |
|
|
964 #ifdef BN_MP_ADDMOD_C |
|
|
965 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
966 * |
|
|
967 * LibTomMath is a library that provides multiple-precision |
|
|
968 * integer arithmetic as well as number theoretic functionality. |
|
|
969 * |
|
|
970 * The library was designed directly after the MPI library by |
|
|
971 * Michael Fromberger but has been written from scratch with |
|
|
972 * additional optimizations in place. |
|
|
973 * |
|
|
974 * The library is free for all purposes without any express |
|
|
975 * guarantee it works. |
|
|
976 * |
|
|
977 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
978 */ |
|
2
|
979 |
|
|
980 /* d = a + b (mod c) */ |
|
|
981 int |
|
|
982 mp_addmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d) |
|
|
983 { |
|
|
984 int res; |
|
|
985 mp_int t; |
|
|
986 |
|
|
987 if ((res = mp_init (&t)) != MP_OKAY) { |
|
|
988 return res; |
|
|
989 } |
|
|
990 |
|
|
991 if ((res = mp_add (a, b, &t)) != MP_OKAY) { |
|
|
992 mp_clear (&t); |
|
|
993 return res; |
|
|
994 } |
|
|
995 res = mp_mod (&t, c, d); |
|
|
996 mp_clear (&t); |
|
|
997 return res; |
|
|
998 } |
|
142
|
999 #endif |
|
2
|
1000 |
|
|
1001 /* End: bn_mp_addmod.c */ |
|
|
1002 |
|
|
1003 /* Start: bn_mp_and.c */ |
|
142
|
1004 #include <tommath.h> |
|
|
1005 #ifdef BN_MP_AND_C |
|
|
1006 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1007 * |
|
|
1008 * LibTomMath is a library that provides multiple-precision |
|
|
1009 * integer arithmetic as well as number theoretic functionality. |
|
|
1010 * |
|
|
1011 * The library was designed directly after the MPI library by |
|
|
1012 * Michael Fromberger but has been written from scratch with |
|
|
1013 * additional optimizations in place. |
|
|
1014 * |
|
|
1015 * The library is free for all purposes without any express |
|
|
1016 * guarantee it works. |
|
|
1017 * |
|
|
1018 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1019 */ |
|
2
|
1020 |
|
|
1021 /* AND two ints together */ |
|
|
1022 int |
|
|
1023 mp_and (mp_int * a, mp_int * b, mp_int * c) |
|
|
1024 { |
|
|
1025 int res, ix, px; |
|
|
1026 mp_int t, *x; |
|
|
1027 |
|
|
1028 if (a->used > b->used) { |
|
|
1029 if ((res = mp_init_copy (&t, a)) != MP_OKAY) { |
|
|
1030 return res; |
|
|
1031 } |
|
|
1032 px = b->used; |
|
|
1033 x = b; |
|
|
1034 } else { |
|
|
1035 if ((res = mp_init_copy (&t, b)) != MP_OKAY) { |
|
|
1036 return res; |
|
|
1037 } |
|
|
1038 px = a->used; |
|
|
1039 x = a; |
|
|
1040 } |
|
|
1041 |
|
|
1042 for (ix = 0; ix < px; ix++) { |
|
|
1043 t.dp[ix] &= x->dp[ix]; |
|
|
1044 } |
|
|
1045 |
|
|
1046 /* zero digits above the last from the smallest mp_int */ |
|
|
1047 for (; ix < t.used; ix++) { |
|
|
1048 t.dp[ix] = 0; |
|
|
1049 } |
|
|
1050 |
|
|
1051 mp_clamp (&t); |
|
|
1052 mp_exch (c, &t); |
|
|
1053 mp_clear (&t); |
|
|
1054 return MP_OKAY; |
|
|
1055 } |
|
142
|
1056 #endif |
|
2
|
1057 |
|
|
1058 /* End: bn_mp_and.c */ |
|
|
1059 |
|
|
1060 /* Start: bn_mp_clamp.c */ |
|
142
|
1061 #include <tommath.h> |
|
|
1062 #ifdef BN_MP_CLAMP_C |
|
|
1063 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1064 * |
|
|
1065 * LibTomMath is a library that provides multiple-precision |
|
|
1066 * integer arithmetic as well as number theoretic functionality. |
|
|
1067 * |
|
|
1068 * The library was designed directly after the MPI library by |
|
|
1069 * Michael Fromberger but has been written from scratch with |
|
|
1070 * additional optimizations in place. |
|
|
1071 * |
|
|
1072 * The library is free for all purposes without any express |
|
|
1073 * guarantee it works. |
|
|
1074 * |
|
|
1075 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1076 */ |
|
2
|
1077 |
|
|
1078 /* trim unused digits |
|
|
1079 * |
|
|
1080 * This is used to ensure that leading zero digits are |
|
|
1081 * trimed and the leading "used" digit will be non-zero |
|
|
1082 * Typically very fast. Also fixes the sign if there |
|
|
1083 * are no more leading digits |
|
|
1084 */ |
|
|
1085 void |
|
|
1086 mp_clamp (mp_int * a) |
|
|
1087 { |
|
|
1088 /* decrease used while the most significant digit is |
|
|
1089 * zero. |
|
|
1090 */ |
|
|
1091 while (a->used > 0 && a->dp[a->used - 1] == 0) { |
|
|
1092 --(a->used); |
|
|
1093 } |
|
|
1094 |
|
|
1095 /* reset the sign flag if used == 0 */ |
|
|
1096 if (a->used == 0) { |
|
|
1097 a->sign = MP_ZPOS; |
|
|
1098 } |
|
|
1099 } |
|
142
|
1100 #endif |
|
2
|
1101 |
|
|
1102 /* End: bn_mp_clamp.c */ |
|
|
1103 |
|
|
1104 /* Start: bn_mp_clear.c */ |
|
142
|
1105 #include <tommath.h> |
|
|
1106 #ifdef BN_MP_CLEAR_C |
|
|
1107 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1108 * |
|
|
1109 * LibTomMath is a library that provides multiple-precision |
|
|
1110 * integer arithmetic as well as number theoretic functionality. |
|
|
1111 * |
|
|
1112 * The library was designed directly after the MPI library by |
|
|
1113 * Michael Fromberger but has been written from scratch with |
|
|
1114 * additional optimizations in place. |
|
|
1115 * |
|
|
1116 * The library is free for all purposes without any express |
|
|
1117 * guarantee it works. |
|
|
1118 * |
|
|
1119 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1120 */ |
|
2
|
1121 |
|
|
1122 /* clear one (frees) */ |
|
|
1123 void |
|
|
1124 mp_clear (mp_int * a) |
|
|
1125 { |
|
142
|
1126 int i; |
|
|
1127 |
|
2
|
1128 /* only do anything if a hasn't been freed previously */ |
|
|
1129 if (a->dp != NULL) { |
|
|
1130 /* first zero the digits */ |
|
142
|
1131 for (i = 0; i < a->used; i++) { |
|
|
1132 a->dp[i] = 0; |
|
|
1133 } |
|
2
|
1134 |
|
|
1135 /* free ram */ |
|
|
1136 XFREE(a->dp); |
|
|
1137 |
|
|
1138 /* reset members to make debugging easier */ |
|
|
1139 a->dp = NULL; |
|
|
1140 a->alloc = a->used = 0; |
|
|
1141 a->sign = MP_ZPOS; |
|
|
1142 } |
|
|
1143 } |
|
142
|
1144 #endif |
|
2
|
1145 |
|
|
1146 /* End: bn_mp_clear.c */ |
|
|
1147 |
|
|
1148 /* Start: bn_mp_clear_multi.c */ |
|
142
|
1149 #include <tommath.h> |
|
|
1150 #ifdef BN_MP_CLEAR_MULTI_C |
|
|
1151 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1152 * |
|
|
1153 * LibTomMath is a library that provides multiple-precision |
|
|
1154 * integer arithmetic as well as number theoretic functionality. |
|
|
1155 * |
|
|
1156 * The library was designed directly after the MPI library by |
|
|
1157 * Michael Fromberger but has been written from scratch with |
|
|
1158 * additional optimizations in place. |
|
|
1159 * |
|
|
1160 * The library is free for all purposes without any express |
|
|
1161 * guarantee it works. |
|
|
1162 * |
|
|
1163 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1164 */ |
|
2
|
1165 #include <stdarg.h> |
|
|
1166 |
|
|
1167 void mp_clear_multi(mp_int *mp, ...) |
|
|
1168 { |
|
|
1169 mp_int* next_mp = mp; |
|
|
1170 va_list args; |
|
|
1171 va_start(args, mp); |
|
|
1172 while (next_mp != NULL) { |
|
|
1173 mp_clear(next_mp); |
|
|
1174 next_mp = va_arg(args, mp_int*); |
|
|
1175 } |
|
|
1176 va_end(args); |
|
|
1177 } |
|
142
|
1178 #endif |
|
2
|
1179 |
|
|
1180 /* End: bn_mp_clear_multi.c */ |
|
|
1181 |
|
|
1182 /* Start: bn_mp_cmp.c */ |
|
142
|
1183 #include <tommath.h> |
|
|
1184 #ifdef BN_MP_CMP_C |
|
|
1185 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1186 * |
|
|
1187 * LibTomMath is a library that provides multiple-precision |
|
|
1188 * integer arithmetic as well as number theoretic functionality. |
|
|
1189 * |
|
|
1190 * The library was designed directly after the MPI library by |
|
|
1191 * Michael Fromberger but has been written from scratch with |
|
|
1192 * additional optimizations in place. |
|
|
1193 * |
|
|
1194 * The library is free for all purposes without any express |
|
|
1195 * guarantee it works. |
|
|
1196 * |
|
|
1197 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1198 */ |
|
2
|
1199 |
|
|
1200 /* compare two ints (signed)*/ |
|
|
1201 int |
|
|
1202 mp_cmp (mp_int * a, mp_int * b) |
|
|
1203 { |
|
|
1204 /* compare based on sign */ |
|
|
1205 if (a->sign != b->sign) { |
|
|
1206 if (a->sign == MP_NEG) { |
|
|
1207 return MP_LT; |
|
|
1208 } else { |
|
|
1209 return MP_GT; |
|
|
1210 } |
|
|
1211 } |
|
|
1212 |
|
|
1213 /* compare digits */ |
|
|
1214 if (a->sign == MP_NEG) { |
|
|
1215 /* if negative compare opposite direction */ |
|
|
1216 return mp_cmp_mag(b, a); |
|
|
1217 } else { |
|
|
1218 return mp_cmp_mag(a, b); |
|
|
1219 } |
|
|
1220 } |
|
142
|
1221 #endif |
|
2
|
1222 |
|
|
1223 /* End: bn_mp_cmp.c */ |
|
|
1224 |
|
|
1225 /* Start: bn_mp_cmp_d.c */ |
|
142
|
1226 #include <tommath.h> |
|
|
1227 #ifdef BN_MP_CMP_D_C |
|
|
1228 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1229 * |
|
|
1230 * LibTomMath is a library that provides multiple-precision |
|
|
1231 * integer arithmetic as well as number theoretic functionality. |
|
|
1232 * |
|
|
1233 * The library was designed directly after the MPI library by |
|
|
1234 * Michael Fromberger but has been written from scratch with |
|
|
1235 * additional optimizations in place. |
|
|
1236 * |
|
|
1237 * The library is free for all purposes without any express |
|
|
1238 * guarantee it works. |
|
|
1239 * |
|
|
1240 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1241 */ |
|
2
|
1242 |
|
|
1243 /* compare a digit */ |
|
|
1244 int mp_cmp_d(mp_int * a, mp_digit b) |
|
|
1245 { |
|
|
1246 /* compare based on sign */ |
|
|
1247 if (a->sign == MP_NEG) { |
|
|
1248 return MP_LT; |
|
|
1249 } |
|
|
1250 |
|
|
1251 /* compare based on magnitude */ |
|
|
1252 if (a->used > 1) { |
|
|
1253 return MP_GT; |
|
|
1254 } |
|
|
1255 |
|
|
1256 /* compare the only digit of a to b */ |
|
|
1257 if (a->dp[0] > b) { |
|
|
1258 return MP_GT; |
|
|
1259 } else if (a->dp[0] < b) { |
|
|
1260 return MP_LT; |
|
|
1261 } else { |
|
|
1262 return MP_EQ; |
|
|
1263 } |
|
|
1264 } |
|
142
|
1265 #endif |
|
2
|
1266 |
|
|
1267 /* End: bn_mp_cmp_d.c */ |
|
|
1268 |
|
|
1269 /* Start: bn_mp_cmp_mag.c */ |
|
142
|
1270 #include <tommath.h> |
|
|
1271 #ifdef BN_MP_CMP_MAG_C |
|
|
1272 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1273 * |
|
|
1274 * LibTomMath is a library that provides multiple-precision |
|
|
1275 * integer arithmetic as well as number theoretic functionality. |
|
|
1276 * |
|
|
1277 * The library was designed directly after the MPI library by |
|
|
1278 * Michael Fromberger but has been written from scratch with |
|
|
1279 * additional optimizations in place. |
|
|
1280 * |
|
|
1281 * The library is free for all purposes without any express |
|
|
1282 * guarantee it works. |
|
|
1283 * |
|
|
1284 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1285 */ |
|
2
|
1286 |
|
|
1287 /* compare maginitude of two ints (unsigned) */ |
|
|
1288 int mp_cmp_mag (mp_int * a, mp_int * b) |
|
|
1289 { |
|
|
1290 int n; |
|
|
1291 mp_digit *tmpa, *tmpb; |
|
|
1292 |
|
|
1293 /* compare based on # of non-zero digits */ |
|
|
1294 if (a->used > b->used) { |
|
|
1295 return MP_GT; |
|
|
1296 } |
|
|
1297 |
|
|
1298 if (a->used < b->used) { |
|
|
1299 return MP_LT; |
|
|
1300 } |
|
|
1301 |
|
|
1302 /* alias for a */ |
|
|
1303 tmpa = a->dp + (a->used - 1); |
|
|
1304 |
|
|
1305 /* alias for b */ |
|
|
1306 tmpb = b->dp + (a->used - 1); |
|
|
1307 |
|
|
1308 /* compare based on digits */ |
|
|
1309 for (n = 0; n < a->used; ++n, --tmpa, --tmpb) { |
|
|
1310 if (*tmpa > *tmpb) { |
|
|
1311 return MP_GT; |
|
|
1312 } |
|
|
1313 |
|
|
1314 if (*tmpa < *tmpb) { |
|
|
1315 return MP_LT; |
|
|
1316 } |
|
|
1317 } |
|
|
1318 return MP_EQ; |
|
|
1319 } |
|
142
|
1320 #endif |
|
2
|
1321 |
|
|
1322 /* End: bn_mp_cmp_mag.c */ |
|
|
1323 |
|
|
1324 /* Start: bn_mp_cnt_lsb.c */ |
|
142
|
1325 #include <tommath.h> |
|
|
1326 #ifdef BN_MP_CNT_LSB_C |
|
|
1327 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1328 * |
|
|
1329 * LibTomMath is a library that provides multiple-precision |
|
|
1330 * integer arithmetic as well as number theoretic functionality. |
|
|
1331 * |
|
|
1332 * The library was designed directly after the MPI library by |
|
|
1333 * Michael Fromberger but has been written from scratch with |
|
|
1334 * additional optimizations in place. |
|
|
1335 * |
|
|
1336 * The library is free for all purposes without any express |
|
|
1337 * guarantee it works. |
|
|
1338 * |
|
|
1339 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1340 */ |
|
2
|
1341 |
|
|
1342 static const int lnz[16] = { |
|
|
1343 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 |
|
|
1344 }; |
|
|
1345 |
|
|
1346 /* Counts the number of lsbs which are zero before the first zero bit */ |
|
|
1347 int mp_cnt_lsb(mp_int *a) |
|
|
1348 { |
|
|
1349 int x; |
|
|
1350 mp_digit q, qq; |
|
|
1351 |
|
|
1352 /* easy out */ |
|
|
1353 if (mp_iszero(a) == 1) { |
|
|
1354 return 0; |
|
|
1355 } |
|
|
1356 |
|
|
1357 /* scan lower digits until non-zero */ |
|
|
1358 for (x = 0; x < a->used && a->dp[x] == 0; x++); |
|
|
1359 q = a->dp[x]; |
|
|
1360 x *= DIGIT_BIT; |
|
|
1361 |
|
|
1362 /* now scan this digit until a 1 is found */ |
|
|
1363 if ((q & 1) == 0) { |
|
|
1364 do { |
|
|
1365 qq = q & 15; |
|
|
1366 x += lnz[qq]; |
|
|
1367 q >>= 4; |
|
|
1368 } while (qq == 0); |
|
|
1369 } |
|
|
1370 return x; |
|
|
1371 } |
|
|
1372 |
|
142
|
1373 #endif |
|
2
|
1374 |
|
|
1375 /* End: bn_mp_cnt_lsb.c */ |
|
|
1376 |
|
|
1377 /* Start: bn_mp_copy.c */ |
|
142
|
1378 #include <tommath.h> |
|
|
1379 #ifdef BN_MP_COPY_C |
|
|
1380 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1381 * |
|
|
1382 * LibTomMath is a library that provides multiple-precision |
|
|
1383 * integer arithmetic as well as number theoretic functionality. |
|
|
1384 * |
|
|
1385 * The library was designed directly after the MPI library by |
|
|
1386 * Michael Fromberger but has been written from scratch with |
|
|
1387 * additional optimizations in place. |
|
|
1388 * |
|
|
1389 * The library is free for all purposes without any express |
|
|
1390 * guarantee it works. |
|
|
1391 * |
|
|
1392 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1393 */ |
|
2
|
1394 |
|
|
1395 /* copy, b = a */ |
|
|
1396 int |
|
|
1397 mp_copy (mp_int * a, mp_int * b) |
|
|
1398 { |
|
|
1399 int res, n; |
|
|
1400 |
|
|
1401 /* if dst == src do nothing */ |
|
|
1402 if (a == b) { |
|
|
1403 return MP_OKAY; |
|
|
1404 } |
|
|
1405 |
|
|
1406 /* grow dest */ |
|
|
1407 if (b->alloc < a->used) { |
|
|
1408 if ((res = mp_grow (b, a->used)) != MP_OKAY) { |
|
|
1409 return res; |
|
|
1410 } |
|
|
1411 } |
|
|
1412 |
|
|
1413 /* zero b and copy the parameters over */ |
|
|
1414 { |
|
|
1415 register mp_digit *tmpa, *tmpb; |
|
|
1416 |
|
|
1417 /* pointer aliases */ |
|
|
1418 |
|
|
1419 /* source */ |
|
|
1420 tmpa = a->dp; |
|
|
1421 |
|
|
1422 /* destination */ |
|
|
1423 tmpb = b->dp; |
|
|
1424 |
|
|
1425 /* copy all the digits */ |
|
|
1426 for (n = 0; n < a->used; n++) { |
|
|
1427 *tmpb++ = *tmpa++; |
|
|
1428 } |
|
|
1429 |
|
|
1430 /* clear high digits */ |
|
|
1431 for (; n < b->used; n++) { |
|
|
1432 *tmpb++ = 0; |
|
|
1433 } |
|
|
1434 } |
|
|
1435 |
|
|
1436 /* copy used count and sign */ |
|
|
1437 b->used = a->used; |
|
|
1438 b->sign = a->sign; |
|
|
1439 return MP_OKAY; |
|
|
1440 } |
|
142
|
1441 #endif |
|
2
|
1442 |
|
|
1443 /* End: bn_mp_copy.c */ |
|
|
1444 |
|
|
1445 /* Start: bn_mp_count_bits.c */ |
|
142
|
1446 #include <tommath.h> |
|
|
1447 #ifdef BN_MP_COUNT_BITS_C |
|
|
1448 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1449 * |
|
|
1450 * LibTomMath is a library that provides multiple-precision |
|
|
1451 * integer arithmetic as well as number theoretic functionality. |
|
|
1452 * |
|
|
1453 * The library was designed directly after the MPI library by |
|
|
1454 * Michael Fromberger but has been written from scratch with |
|
|
1455 * additional optimizations in place. |
|
|
1456 * |
|
|
1457 * The library is free for all purposes without any express |
|
|
1458 * guarantee it works. |
|
|
1459 * |
|
|
1460 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1461 */ |
|
2
|
1462 |
|
|
1463 /* returns the number of bits in an int */ |
|
|
1464 int |
|
|
1465 mp_count_bits (mp_int * a) |
|
|
1466 { |
|
|
1467 int r; |
|
|
1468 mp_digit q; |
|
|
1469 |
|
|
1470 /* shortcut */ |
|
|
1471 if (a->used == 0) { |
|
|
1472 return 0; |
|
|
1473 } |
|
|
1474 |
|
|
1475 /* get number of digits and add that */ |
|
|
1476 r = (a->used - 1) * DIGIT_BIT; |
|
|
1477 |
|
|
1478 /* take the last digit and count the bits in it */ |
|
|
1479 q = a->dp[a->used - 1]; |
|
|
1480 while (q > ((mp_digit) 0)) { |
|
|
1481 ++r; |
|
|
1482 q >>= ((mp_digit) 1); |
|
|
1483 } |
|
|
1484 return r; |
|
|
1485 } |
|
142
|
1486 #endif |
|
2
|
1487 |
|
|
1488 /* End: bn_mp_count_bits.c */ |
|
|
1489 |
|
|
1490 /* Start: bn_mp_div.c */ |
|
142
|
1491 #include <tommath.h> |
|
|
1492 #ifdef BN_MP_DIV_C |
|
|
1493 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
1494 * |
|
|
1495 * LibTomMath is a library that provides multiple-precision |
|
|
1496 * integer arithmetic as well as number theoretic functionality. |
|
|
1497 * |
|
|
1498 * The library was designed directly after the MPI library by |
|
|
1499 * Michael Fromberger but has been written from scratch with |
|
|
1500 * additional optimizations in place. |
|
|
1501 * |
|
|
1502 * The library is free for all purposes without any express |
|
|
1503 * guarantee it works. |
|
|
1504 * |
|
|
1505 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
1506 */ |
|
|
1507 |
|
|
1508 #ifdef BN_MP_DIV_SMALL |
|
|
1509 |
|
|
1510 /* slower bit-bang division... also smaller */ |
|
|
1511 int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) |
Matt Johnston <matt@ucc.asn.au>
diff
|
