Mercurial > dropbear

comparison tomsfastmath/src/headers/tfm.h @ 643:a362b62d38b2 dropbear-tfm

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a with Makefile.in renamed
author Matt Johnston <matt@ucc.asn.au>
date Wed, 23 Nov 2011 18:10:20 +0700
parents
children
comparison
equal deleted inserted replaced
642:33fd2f3499d2 643:a362b62d38b2
1 /* TomsFastMath, a fast ISO C bignum library.
2 *
3 * This project is meant to fill in where LibTomMath
4 * falls short. That is speed ;-)
5 *
6 * This project is public domain and free for all purposes.
7 *
8 * Tom St Denis, [email protected]
9 */
10 #ifndef TFM_H_
11 #define TFM_H_
12
13 #include <stdio.h>
14 #include <string.h>
15 #include <stdlib.h>
16 #include <ctype.h>
17 #include <limits.h>
18
19 #ifndef MIN
20 #define MIN(x,y) ((x)<(y)?(x):(y))
21 #endif
22
23 #ifndef MAX
24 #define MAX(x,y) ((x)>(y)?(x):(y))
25 #endif
26
27 /* externally define this symbol to ignore the default settings, useful for changing the build from the make process */
28 #ifndef TFM_ALREADY_SET
29
30 /* do we want the large set of small multiplications ?
31 Enable these if you are going to be doing a lot of small (<= 16 digit) multiplications say in ECC
32 Or if you're on a 64-bit machine doing RSA as a 1024-bit integer == 16 digits ;-)
33 */
34 #define TFM_SMALL_SET
35
36 /* do we want huge code
37 Enable these if you are doing 20, 24, 28, 32, 48, 64 digit multiplications (useful for RSA)
38 Less important on 64-bit machines as 32 digits == 2048 bits
39 */
40 #if 0
41 #define TFM_MUL3
42 #define TFM_MUL4
43 #define TFM_MUL6
44 #define TFM_MUL7
45 #define TFM_MUL8
46 #define TFM_MUL9
47 #define TFM_MUL12
48 #define TFM_MUL17
49 #endif
50 #define TFM_MUL20
51 #define TFM_MUL24
52 #define TFM_MUL28
53 #define TFM_MUL32
54 #define TFM_MUL48
55 #define TFM_MUL64
56
57 #if 0
58 #define TFM_SQR3
59 #define TFM_SQR4
60 #define TFM_SQR6
61 #define TFM_SQR7
62 #define TFM_SQR8
63 #define TFM_SQR9
64 #define TFM_SQR12
65 #define TFM_SQR17
66 #endif
67 #define TFM_SQR20
68 #define TFM_SQR24
69 #define TFM_SQR28
70 #define TFM_SQR32
71 #define TFM_SQR48
72 #define TFM_SQR64
73
74 /* do we want some overflow checks
75 Not required if you make sure your numbers are within range (e.g. by default a modulus for fp_exptmod() can only be upto 2048 bits long)
76 */
77 /* #define TFM_CHECK */
78
79 /* Is the target a P4 Prescott
80 */
81 /* #define TFM_PRESCOTT */
82
83 /* Do we want timing resistant fp_exptmod() ?
84 * This makes it slower but also timing invariant with respect to the exponent
85 */
86 /* #define TFM_TIMING_RESISTANT */
87
88 #endif
89
90 /* Max size of any number in bits. Basically the largest size you will be multiplying
91 * should be half [or smaller] of FP_MAX_SIZE-four_digit
92 *
93 * You can externally define this or it defaults to 4096-bits [allowing multiplications upto 2048x2048 bits ]
94 */
95 #ifndef FP_MAX_SIZE
96 #define FP_MAX_SIZE (4096+(8*DIGIT_BIT))
97 #endif
98
99 /* will this lib work? */
100 #if (CHAR_BIT & 7)
101 #error CHAR_BIT must be a multiple of eight.
102 #endif
103 #if FP_MAX_SIZE % CHAR_BIT
104 #error FP_MAX_SIZE must be a multiple of CHAR_BIT
105 #endif
106
107 /* autodetect x86-64 and make sure we are using 64-bit digits with x86-64 asm */
108 #if defined(__x86_64__)
109 #if defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM)
110 #error x86-64 detected, x86-32/SSE2/ARM optimizations are not valid!
111 #endif
112 #if !defined(TFM_X86_64) && !defined(TFM_NO_ASM)
113 #define TFM_X86_64
114 #endif
115 #endif
116 #if defined(TFM_X86_64)
117 #if !defined(FP_64BIT)
118 #define FP_64BIT
119 #endif
120 #endif
121
122 /* try to detect x86-32 */
123 #if defined(__i386__) && !defined(TFM_SSE2)
124 #if defined(TFM_X86_64) || defined(TFM_ARM)
125 #error x86-32 detected, x86-64/ARM optimizations are not valid!
126 #endif
127 #if !defined(TFM_X86) && !defined(TFM_NO_ASM)
128 #define TFM_X86
129 #endif
130 #endif
131
132 /* make sure we're 32-bit for x86-32/sse/arm/ppc32 */
133 #if (defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) || defined(TFM_PPC32)) && defined(FP_64BIT)
134 #warning x86-32, SSE2 and ARM, PPC32 optimizations require 32-bit digits (undefining)
135 #undef FP_64BIT
136 #endif
137
138 /* multi asms? */
139 #ifdef TFM_X86
140 #define TFM_ASM
141 #endif
142 #ifdef TFM_X86_64
143 #ifdef TFM_ASM
144 #error TFM_ASM already defined!
145 #endif
146 #define TFM_ASM
147 #endif
148 #ifdef TFM_SSE2
149 #ifdef TFM_ASM
150 #error TFM_ASM already defined!
151 #endif
152 #define TFM_ASM
153 #endif
154 #ifdef TFM_ARM
155 #ifdef TFM_ASM
156 #error TFM_ASM already defined!
157 #endif
158 #define TFM_ASM
159 #endif
160 #ifdef TFM_PPC32
161 #ifdef TFM_ASM
162 #error TFM_ASM already defined!
163 #endif
164 #define TFM_ASM
165 #endif
166 #ifdef TFM_PPC64
167 #ifdef TFM_ASM
168 #error TFM_ASM already defined!
169 #endif
170 #define TFM_ASM
171 #endif
172 #ifdef TFM_AVR32
173 #ifdef TFM_ASM
174 #error TFM_ASM already defined!
175 #endif
176 #define TFM_ASM
177 #endif
178
179 /* we want no asm? */
180 #ifdef TFM_NO_ASM
181 #undef TFM_X86
182 #undef TFM_X86_64
183 #undef TFM_SSE2
184 #undef TFM_ARM
185 #undef TFM_PPC32
186 #undef TFM_PPC64
187 #undef TFM_AVR32
188 #undef TFM_ASM
189 #endif
190
191 /* ECC helpers */
192 #ifdef TFM_ECC192
193 #ifdef FP_64BIT
194 #define TFM_MUL3
195 #define TFM_SQR3
196 #else
197 #define TFM_MUL6
198 #define TFM_SQR6
199 #endif
200 #endif
201
202 #ifdef TFM_ECC224
203 #ifdef FP_64BIT
204 #define TFM_MUL4
205 #define TFM_SQR4
206 #else
207 #define TFM_MUL7
208 #define TFM_SQR7
209 #endif
210 #endif
211
212 #ifdef TFM_ECC256
213 #ifdef FP_64BIT
214 #define TFM_MUL4
215 #define TFM_SQR4
216 #else
217 #define TFM_MUL8
218 #define TFM_SQR8
219 #endif
220 #endif
221
222 #ifdef TFM_ECC384
223 #ifdef FP_64BIT
224 #define TFM_MUL6
225 #define TFM_SQR6
226 #else
227 #define TFM_MUL12
228 #define TFM_SQR12
229 #endif
230 #endif
231
232 #ifdef TFM_ECC521
233 #ifdef FP_64BIT
234 #define TFM_MUL9
235 #define TFM_SQR9
236 #else
237 #define TFM_MUL17
238 #define TFM_SQR17
239 #endif
240 #endif
241
242
243 /* some default configurations.
244 */
245 #if defined(FP_64BIT)
246 /* for GCC only on supported platforms */
247 #ifndef CRYPT
248 typedef unsigned long ulong64;
249 #endif
250 typedef ulong64 fp_digit;
251 typedef unsigned long fp_word __attribute__ ((mode(TI)));
252 #else
253 /* this is to make porting into LibTomCrypt easier :-) */
254 #ifndef CRYPT
255 #if defined(_MSC_VER) || defined(__BORLANDC__)
256 typedef unsigned __int64 ulong64;
257 typedef signed __int64 long64;
258 #else
259 typedef unsigned long long ulong64;
260 typedef signed long long long64;
261 #endif
262 #endif
263 typedef unsigned long fp_digit;
264 typedef ulong64 fp_word;
265 #endif
266
267 /* # of digits this is */
268 #define DIGIT_BIT (int)((CHAR_BIT) * sizeof(fp_digit))
269 #define FP_MASK (fp_digit)(-1)
270 #define FP_SIZE (FP_MAX_SIZE/DIGIT_BIT)
271
272 /* signs */
273 #define FP_ZPOS 0
274 #define FP_NEG 1
275
276 /* return codes */
277 #define FP_OKAY 0
278 #define FP_VAL 1
279 #define FP_MEM 2
280
281 /* equalities */
282 #define FP_LT -1 /* less than */
283 #define FP_EQ 0 /* equal to */
284 #define FP_GT 1 /* greater than */
285
286 /* replies */
287 #define FP_YES 1 /* yes response */
288 #define FP_NO 0 /* no response */
289
290 /* a FP type */
291 typedef struct {
292 fp_digit dp[FP_SIZE];
293 int used,
294 sign;
295 } fp_int;
296
297 /* functions */
298
299 /* returns a TFM ident string useful for debugging... */
300 const char *fp_ident(void);
301
302 /* initialize [or zero] an fp int */
303 #define fp_init(a) (void)memset((a), 0, sizeof(fp_int))
304 #define fp_zero(a) fp_init(a)
305
306 /* zero/even/odd ? */
307 #define fp_iszero(a) (((a)->used == 0) ? FP_YES : FP_NO)
308 #define fp_iseven(a) (((a)->used >= 0 && (((a)->dp[0] & 1) == 0)) ? FP_YES : FP_NO)
309 #define fp_isodd(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? FP_YES : FP_NO)
310
311 /* set to a small digit */
312 void fp_set(fp_int *a, fp_digit b);
313
314 /* copy from a to b */
315 #define fp_copy(a, b) (void)(((a) != (b)) && memcpy((b), (a), sizeof(fp_int)))
316 #define fp_init_copy(a, b) fp_copy(b, a)
317
318 /* clamp digits */
319 #define fp_clamp(a) { while ((a)->used && (a)->dp[(a)->used-1] == 0) --((a)->used); (a)->sign = (a)->used ? (a)->sign : FP_ZPOS; }
320
321 /* negate and absolute */
322 #define fp_neg(a, b) { fp_copy(a, b); (b)->sign ^= 1; fp_clamp(b); }
323 #define fp_abs(a, b) { fp_copy(a, b); (b)->sign = 0; }
324
325 /* right shift x digits */
326 void fp_rshd(fp_int *a, int x);
327
328 /* left shift x digits */
329 void fp_lshd(fp_int *a, int x);
330
331 /* signed comparison */
332 int fp_cmp(fp_int *a, fp_int *b);
333
334 /* unsigned comparison */
335 int fp_cmp_mag(fp_int *a, fp_int *b);
336
337 /* power of 2 operations */
338 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d);
339 void fp_mod_2d(fp_int *a, int b, fp_int *c);
340 void fp_mul_2d(fp_int *a, int b, fp_int *c);
341 void fp_2expt (fp_int *a, int b);
342 void fp_mul_2(fp_int *a, fp_int *c);
343 void fp_div_2(fp_int *a, fp_int *c);
344
345 /* Counts the number of lsbs which are zero before the first zero bit */
346 int fp_cnt_lsb(fp_int *a);
347
348 /* c = a + b */
349 void fp_add(fp_int *a, fp_int *b, fp_int *c);
350
351 /* c = a - b */
352 void fp_sub(fp_int *a, fp_int *b, fp_int *c);
353
354 /* c = a * b */
355 void fp_mul(fp_int *a, fp_int *b, fp_int *c);
356
357 /* b = a*a */
358 void fp_sqr(fp_int *a, fp_int *b);
359
360 /* a/b => cb + d == a */
361 int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
362
363 /* c = a mod b, 0 <= c < b */
364 int fp_mod(fp_int *a, fp_int *b, fp_int *c);
365
366 /* compare against a single digit */
367 int fp_cmp_d(fp_int *a, fp_digit b);
368
369 /* c = a + b */
370 void fp_add_d(fp_int *a, fp_digit b, fp_int *c);
371
372 /* c = a - b */
373 void fp_sub_d(fp_int *a, fp_digit b, fp_int *c);
374
375 /* c = a * b */
376 void fp_mul_d(fp_int *a, fp_digit b, fp_int *c);
377
378 /* a/b => cb + d == a */
379 int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d);
380
381 /* c = a mod b, 0 <= c < b */
382 int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c);
383
384 /* ---> number theory <--- */
385 /* d = a + b (mod c) */
386 int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
387
388 /* d = a - b (mod c) */
389 int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
390
391 /* d = a * b (mod c) */
392 int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
393
394 /* c = a * a (mod b) */
395 int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c);
396
397 /* c = 1/a (mod b) */
398 int fp_invmod(fp_int *a, fp_int *b, fp_int *c);
399
400 /* c = (a, b) */
401 void fp_gcd(fp_int *a, fp_int *b, fp_int *c);
402
403 /* c = [a, b] */
404 void fp_lcm(fp_int *a, fp_int *b, fp_int *c);
405
406 /* setups the montgomery reduction */
407 int fp_montgomery_setup(fp_int *a, fp_digit *mp);
408
409 /* computes a = B**n mod b without division or multiplication useful for
410 * normalizing numbers in a Montgomery system.
411 */
412 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b);
413
414 /* computes x/R == x (mod N) via Montgomery Reduction */
415 void fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp);
416
417 /* d = a**b (mod c) */
418 int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
419
420 /* primality stuff */
421
422 /* perform a Miller-Rabin test of a to the base b and store result in "result" */
423 void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result);
424
425 /* 256 trial divisions + 8 Miller-Rabins, returns FP_YES if probable prime */
426 int fp_isprime(fp_int *a);
427
428 /* Primality generation flags */
429 #define TFM_PRIME_BBS 0x0001 /* BBS style prime */
430 #define TFM_PRIME_SAFE 0x0002 /* Safe prime (p-1)/2 == prime */
431 #define TFM_PRIME_2MSB_OFF 0x0004 /* force 2nd MSB to 0 */
432 #define TFM_PRIME_2MSB_ON 0x0008 /* force 2nd MSB to 1 */
433
434 /* callback for fp_prime_random, should fill dst with random bytes and return how many read [upto len] */
435 typedef int tfm_prime_callback(unsigned char *dst, int len, void *dat);
436
437 #define fp_prime_random(a, t, size, bbs, cb, dat) fp_prime_random_ex(a, t, ((size) * 8) + 1, (bbs==1)?TFM_PRIME_BBS:0, cb, dat)
438
439 int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat);
440
441 /* radix conersions */
442 int fp_count_bits(fp_int *a);
443
444 int fp_unsigned_bin_size(fp_int *a);
445 void fp_read_unsigned_bin(fp_int *a, unsigned char *b, int c);
446 void fp_to_unsigned_bin(fp_int *a, unsigned char *b);
447
448 int fp_signed_bin_size(fp_int *a);
449 void fp_read_signed_bin(fp_int *a, unsigned char *b, int c);
450 void fp_to_signed_bin(fp_int *a, unsigned char *b);
451
452 int fp_read_radix(fp_int *a, char *str, int radix);
453 int fp_toradix(fp_int *a, char *str, int radix);
454 int fp_toradix_n(fp_int * a, char *str, int radix, int maxlen);
455
456
457 /* VARIOUS LOW LEVEL STUFFS */
458 void s_fp_add(fp_int *a, fp_int *b, fp_int *c);
459 void s_fp_sub(fp_int *a, fp_int *b, fp_int *c);
460 void fp_reverse(unsigned char *s, int len);
461
462 void fp_mul_comba(fp_int *A, fp_int *B, fp_int *C);
463
464 #ifdef TFM_SMALL_SET
465 void fp_mul_comba_small(fp_int *A, fp_int *B, fp_int *C);
466 #endif
467
468 #ifdef TFM_MUL3
469 void fp_mul_comba3(fp_int *A, fp_int *B, fp_int *C);
470 #endif
471 #ifdef TFM_MUL4
472 void fp_mul_comba4(fp_int *A, fp_int *B, fp_int *C);
473 #endif
474 #ifdef TFM_MUL6
475 void fp_mul_comba6(fp_int *A, fp_int *B, fp_int *C);
476 #endif
477 #ifdef TFM_MUL7
478 void fp_mul_comba7(fp_int *A, fp_int *B, fp_int *C);
479 #endif
480 #ifdef TFM_MUL8
481 void fp_mul_comba8(fp_int *A, fp_int *B, fp_int *C);
482 #endif
483 #ifdef TFM_MUL9
484 void fp_mul_comba9(fp_int *A, fp_int *B, fp_int *C);
485 #endif
486 #ifdef TFM_MUL12
487 void fp_mul_comba12(fp_int *A, fp_int *B, fp_int *C);
488 #endif
489 #ifdef TFM_MUL17
490 void fp_mul_comba17(fp_int *A, fp_int *B, fp_int *C);
491 #endif
492
493 #ifdef TFM_MUL20
494 void fp_mul_comba20(fp_int *A, fp_int *B, fp_int *C);
495 #endif
496 #ifdef TFM_MUL24
497 void fp_mul_comba24(fp_int *A, fp_int *B, fp_int *C);
498 #endif
499 #ifdef TFM_MUL28
500 void fp_mul_comba28(fp_int *A, fp_int *B, fp_int *C);
501 #endif
502 #ifdef TFM_MUL32
503 void fp_mul_comba32(fp_int *A, fp_int *B, fp_int *C);
504 #endif
505 #ifdef TFM_MUL48
506 void fp_mul_comba48(fp_int *A, fp_int *B, fp_int *C);
507 #endif
508 #ifdef TFM_MUL64
509 void fp_mul_comba64(fp_int *A, fp_int *B, fp_int *C);
510 #endif
511
512 void fp_sqr_comba(fp_int *A, fp_int *B);
513
514 #ifdef TFM_SMALL_SET
515 void fp_sqr_comba_small(fp_int *A, fp_int *B);
516 #endif
517
518 #ifdef TFM_SQR3
519 void fp_sqr_comba3(fp_int *A, fp_int *B);
520 #endif
521 #ifdef TFM_SQR4
522 void fp_sqr_comba4(fp_int *A, fp_int *B);
523 #endif
524 #ifdef TFM_SQR6
525 void fp_sqr_comba6(fp_int *A, fp_int *B);
526 #endif
527 #ifdef TFM_SQR7
528 void fp_sqr_comba7(fp_int *A, fp_int *B);
529 #endif
530 #ifdef TFM_SQR8
531 void fp_sqr_comba8(fp_int *A, fp_int *B);
532 #endif
533 #ifdef TFM_SQR9
534 void fp_sqr_comba9(fp_int *A, fp_int *B);
535 #endif
536 #ifdef TFM_SQR12
537 void fp_sqr_comba12(fp_int *A, fp_int *B);
538 #endif
539 #ifdef TFM_SQR17
540 void fp_sqr_comba17(fp_int *A, fp_int *B);
541 #endif
542
543 #ifdef TFM_SQR20
544 void fp_sqr_comba20(fp_int *A, fp_int *B);
545 #endif
546 #ifdef TFM_SQR24
547 void fp_sqr_comba24(fp_int *A, fp_int *B);
548 #endif
549 #ifdef TFM_SQR28
550 void fp_sqr_comba28(fp_int *A, fp_int *B);
551 #endif
552 #ifdef TFM_SQR32
553 void fp_sqr_comba32(fp_int *A, fp_int *B);
554 #endif
555 #ifdef TFM_SQR48
556 void fp_sqr_comba48(fp_int *A, fp_int *B);
557 #endif
558 #ifdef TFM_SQR64
559 void fp_sqr_comba64(fp_int *A, fp_int *B);
560 #endif
561 extern const char *fp_s_rmap;
562
563 #endif
564
565
566 /* $Source$ */
567 /* $Revision$ */
568 /* $Date$ */