Mercurial > dropbear

comparison libtommath/tommath.h @ 389:5ff8218bcee9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 2af95f00ebd5bb7a28b3817db1218442c935388e) to branch 'au.asn.ucc.matt.dropbear' (head ecd779509ef23a8cdf64888904fc9b31d78aa933)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 03:14:55 +0000
parents eed26cff980b
children 60fc6476e044
comparison
equal deleted inserted replaced
388:fb54020f78e1 389:5ff8218bcee9
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 *
3 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.com
14 */
15 #ifndef BN_H_
16 #define BN_H_
17
18 #include <stdio.h>
19 #include <string.h>
20 #include <stdlib.h>
21 #include <ctype.h>
22 #include <limits.h>
23
24 #include "tommath_class.h"
25
26 #ifndef MIN
27 #define MIN(x,y) ((x)<(y)?(x):(y))
28 #endif
29
30 #ifndef MAX
31 #define MAX(x,y) ((x)>(y)?(x):(y))
32 #endif
33
34 #ifdef __cplusplus
35 extern "C" {
36
37 /* C++ compilers don't like assigning void * to mp_digit * */
38 #define OPT_CAST(x) (x *)
39
40 #else
41
42 /* C on the other hand doesn't care */
43 #define OPT_CAST(x)
44
45 #endif
46
47
48 /* detect 64-bit mode if possible */
49 #if defined(__x86_64__)
50 #if !(defined(MP_64BIT) && defined(MP_16BIT) && defined(MP_8BIT))
51 #define MP_64BIT
52 #endif
53 #endif
54
55 /* some default configurations.
56 *
57 * A "mp_digit" must be able to hold DIGIT_BIT + 1 bits
58 * A "mp_word" must be able to hold 2*DIGIT_BIT + 1 bits
59 *
60 * At the very least a mp_digit must be able to hold 7 bits
61 * [any size beyond that is ok provided it doesn't overflow the data type]
62 */
63 #ifdef MP_8BIT
64 typedef unsigned char mp_digit;
65 typedef unsigned short mp_word;
66 #elif defined(MP_16BIT)
67 typedef unsigned short mp_digit;
68 typedef unsigned long mp_word;
69 #elif defined(MP_64BIT)
70 /* for GCC only on supported platforms */
71 #ifndef CRYPT
72 typedef unsigned long long ulong64;
73 typedef signed long long long64;
74 #endif
75
76 typedef unsigned long mp_digit;
77 typedef unsigned long mp_word __attribute__ ((mode(TI)));
78
79 #define DIGIT_BIT 60
80 #else
81 /* this is the default case, 28-bit digits */
82
83 /* this is to make porting into LibTomCrypt easier :-) */
84 #ifndef CRYPT
85 #if defined(_MSC_VER) || defined(__BORLANDC__)
86 typedef unsigned __int64 ulong64;
87 typedef signed __int64 long64;
88 #else
89 typedef unsigned long long ulong64;
90 typedef signed long long long64;
91 #endif
92 #endif
93
94 typedef unsigned long mp_digit;
95 typedef ulong64 mp_word;
96
97 #ifdef MP_31BIT
98 /* this is an extension that uses 31-bit digits */
99 #define DIGIT_BIT 31
100 #else
101 /* default case is 28-bit digits, defines MP_28BIT as a handy macro to test */
102 #define DIGIT_BIT 28
103 #define MP_28BIT
104 #endif
105 #endif
106
107 /* define heap macros */
108 #ifndef CRYPT
109 /* default to libc stuff */
110 #ifndef XMALLOC
111 #define XMALLOC malloc
112 #define XFREE free
113 #define XREALLOC realloc
114 #define XCALLOC calloc
115 #else
116 /* prototypes for our heap functions */
117 extern void *XMALLOC(size_t n);
118 extern void *XREALLOC(void *p, size_t n);
119 extern void *XCALLOC(size_t n, size_t s);
120 extern void XFREE(void *p);
121 #endif
122 #endif
123
124
125 /* otherwise the bits per digit is calculated automatically from the size of a mp_digit */
126 #ifndef DIGIT_BIT
127 #define DIGIT_BIT ((int)((CHAR_BIT * sizeof(mp_digit) - 1))) /* bits per digit */
128 #endif
129
130 #define MP_DIGIT_BIT DIGIT_BIT
131 #define MP_MASK ((((mp_digit)1)<<((mp_digit)DIGIT_BIT))-((mp_digit)1))
132 #define MP_DIGIT_MAX MP_MASK
133
134 /* equalities */
135 #define MP_LT -1 /* less than */
136 #define MP_EQ 0 /* equal to */
137 #define MP_GT 1 /* greater than */
138
139 #define MP_ZPOS 0 /* positive integer */
140 #define MP_NEG 1 /* negative */
141
142 #define MP_OKAY 0 /* ok result */
143 #define MP_MEM -2 /* out of mem */
144 #define MP_VAL -3 /* invalid input */
145 #define MP_RANGE MP_VAL
146
147 #define MP_YES 1 /* yes response */
148 #define MP_NO 0 /* no response */
149
150 /* Primality generation flags */
151 #define LTM_PRIME_BBS 0x0001 /* BBS style prime */
152 #define LTM_PRIME_SAFE 0x0002 /* Safe prime (p-1)/2 == prime */
153 #define LTM_PRIME_2MSB_ON 0x0008 /* force 2nd MSB to 1 */
154
155 typedef int mp_err;
156
157 /* you'll have to tune these... */
158 extern int KARATSUBA_MUL_CUTOFF,
159 KARATSUBA_SQR_CUTOFF,
160 TOOM_MUL_CUTOFF,
161 TOOM_SQR_CUTOFF;
162
163 /* define this to use lower memory usage routines (exptmods mostly) */
164 /* #define MP_LOW_MEM */
165
166 /* default precision */
167 #ifndef MP_PREC
168 #ifndef MP_LOW_MEM
169 #define MP_PREC 32 /* default digits of precision */
170 #else
171 #define MP_PREC 8 /* default digits of precision */
172 #endif
173 #endif
174
175 /* size of comba arrays, should be at least 2 * 2**(BITS_PER_WORD - BITS_PER_DIGIT*2) */
176 #define MP_WARRAY (1 << (sizeof(mp_word) * CHAR_BIT - 2 * DIGIT_BIT + 1))
177
178 /* the infamous mp_int structure */
179 typedef struct {
180 int used, alloc, sign;
181 mp_digit *dp;
182 } mp_int;
183
184 /* callback for mp_prime_random, should fill dst with random bytes and return how many read [upto len] */
185 typedef int ltm_prime_callback(unsigned char *dst, int len, void *dat);
186
187
188 #define USED(m) ((m)->used)
189 #define DIGIT(m,k) ((m)->dp[(k)])
190 #define SIGN(m) ((m)->sign)
191
192 /* error code to char* string */
193 char *mp_error_to_string(int code);
194
195 /* ---> init and deinit bignum functions <--- */
196 /* init a bignum */
197 int mp_init(mp_int *a);
198
199 /* free a bignum */
200 void mp_clear(mp_int *a);
201
202 /* init a null terminated series of arguments */
203 int mp_init_multi(mp_int *mp, ...);
204
205 /* clear a null terminated series of arguments */
206 void mp_clear_multi(mp_int *mp, ...);
207
208 /* exchange two ints */
209 void mp_exch(mp_int *a, mp_int *b);
210
211 /* shrink ram required for a bignum */
212 int mp_shrink(mp_int *a);
213
214 /* grow an int to a given size */
215 int mp_grow(mp_int *a, int size);
216
217 /* init to a given number of digits */
218 int mp_init_size(mp_int *a, int size);
219
220 /* ---> Basic Manipulations <--- */
221 #define mp_iszero(a) (((a)->used == 0) ? MP_YES : MP_NO)
222 #define mp_iseven(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 0)) ? MP_YES : MP_NO)
223 #define mp_isodd(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? MP_YES : MP_NO)
224
225 /* set to zero */
226 void mp_zero(mp_int *a);
227
228 /* set to a digit */
229 void mp_set(mp_int *a, mp_digit b);
230
231 /* set a 32-bit const */
232 int mp_set_int(mp_int *a, unsigned long b);
233
234 /* get a 32-bit value */
235 unsigned long mp_get_int(mp_int * a);
236
237 /* initialize and set a digit */
238 int mp_init_set (mp_int * a, mp_digit b);
239
240 /* initialize and set 32-bit value */
241 int mp_init_set_int (mp_int * a, unsigned long b);
242
243 /* copy, b = a */
244 int mp_copy(mp_int *a, mp_int *b);
245
246 /* inits and copies, a = b */
247 int mp_init_copy(mp_int *a, mp_int *b);
248
249 /* trim unused digits */
250 void mp_clamp(mp_int *a);
251
252 /* ---> digit manipulation <--- */
253
254 /* right shift by "b" digits */
255 void mp_rshd(mp_int *a, int b);
256
257 /* left shift by "b" digits */
258 int mp_lshd(mp_int *a, int b);
259
260 /* c = a / 2**b */
261 int mp_div_2d(mp_int *a, int b, mp_int *c, mp_int *d);
262
263 /* b = a/2 */
264 int mp_div_2(mp_int *a, mp_int *b);
265
266 /* c = a * 2**b */
267 int mp_mul_2d(mp_int *a, int b, mp_int *c);
268
269 /* b = a*2 */
270 int mp_mul_2(mp_int *a, mp_int *b);
271
272 /* c = a mod 2**d */
273 int mp_mod_2d(mp_int *a, int b, mp_int *c);
274
275 /* computes a = 2**b */
276 int mp_2expt(mp_int *a, int b);
277
278 /* Counts the number of lsbs which are zero before the first zero bit */
279 int mp_cnt_lsb(mp_int *a);
280
281 /* I Love Earth! */
282
283 /* makes a pseudo-random int of a given size */
284 int mp_rand(mp_int *a, int digits);
285
286 /* ---> binary operations <--- */
287 /* c = a XOR b */
288 int mp_xor(mp_int *a, mp_int *b, mp_int *c);
289
290 /* c = a OR b */
291 int mp_or(mp_int *a, mp_int *b, mp_int *c);
292
293 /* c = a AND b */
294 int mp_and(mp_int *a, mp_int *b, mp_int *c);
295
296 /* ---> Basic arithmetic <--- */
297
298 /* b = -a */
299 int mp_neg(mp_int *a, mp_int *b);
300
301 /* b = |a| */
302 int mp_abs(mp_int *a, mp_int *b);
303
304 /* compare a to b */
305 int mp_cmp(mp_int *a, mp_int *b);
306
307 /* compare |a| to |b| */
308 int mp_cmp_mag(mp_int *a, mp_int *b);
309
310 /* c = a + b */
311 int mp_add(mp_int *a, mp_int *b, mp_int *c);
312
313 /* c = a - b */
314 int mp_sub(mp_int *a, mp_int *b, mp_int *c);
315
316 /* c = a * b */
317 int mp_mul(mp_int *a, mp_int *b, mp_int *c);
318
319 /* b = a*a */
320 int mp_sqr(mp_int *a, mp_int *b);
321
322 /* a/b => cb + d == a */
323 int mp_div(mp_int *a, mp_int *b, mp_int *c, mp_int *d);
324
325 /* c = a mod b, 0 <= c < b */
326 int mp_mod(mp_int *a, mp_int *b, mp_int *c);
327
328 /* ---> single digit functions <--- */
329
330 /* compare against a single digit */
331 int mp_cmp_d(mp_int *a, mp_digit b);
332
333 /* c = a + b */
334 int mp_add_d(mp_int *a, mp_digit b, mp_int *c);
335
336 /* c = a - b */
337 int mp_sub_d(mp_int *a, mp_digit b, mp_int *c);
338
339 /* c = a * b */
340 int mp_mul_d(mp_int *a, mp_digit b, mp_int *c);
341
342 /* a/b => cb + d == a */
343 int mp_div_d(mp_int *a, mp_digit b, mp_int *c, mp_digit *d);
344
345 /* a/3 => 3c + d == a */
346 int mp_div_3(mp_int *a, mp_int *c, mp_digit *d);
347
348 /* c = a**b */
349 int mp_expt_d(mp_int *a, mp_digit b, mp_int *c);
350
351 /* c = a mod b, 0 <= c < b */
352 int mp_mod_d(mp_int *a, mp_digit b, mp_digit *c);
353
354 /* ---> number theory <--- */
355
356 /* d = a + b (mod c) */
357 int mp_addmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d);
358
359 /* d = a - b (mod c) */
360 int mp_submod(mp_int *a, mp_int *b, mp_int *c, mp_int *d);
361
362 /* d = a * b (mod c) */
363 int mp_mulmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d);
364
365 /* c = a * a (mod b) */
366 int mp_sqrmod(mp_int *a, mp_int *b, mp_int *c);
367
368 /* c = 1/a (mod b) */
369 int mp_invmod(mp_int *a, mp_int *b, mp_int *c);
370
371 /* c = (a, b) */
372 int mp_gcd(mp_int *a, mp_int *b, mp_int *c);
373
374 /* produces value such that U1*a + U2*b = U3 */
375 int mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3);
376
377 /* c = [a, b] or (a*b)/(a, b) */
378 int mp_lcm(mp_int *a, mp_int *b, mp_int *c);
379
380 /* finds one of the b'th root of a, such that |c|**b <= |a|
381 *
382 * returns error if a < 0 and b is even
383 */
384 int mp_n_root(mp_int *a, mp_digit b, mp_int *c);
385
386 /* special sqrt algo */
387 int mp_sqrt(mp_int *arg, mp_int *ret);
388
389 /* is number a square? */
390 int mp_is_square(mp_int *arg, int *ret);
391
392 /* computes the jacobi c = (a | n) (or Legendre if b is prime) */
393 int mp_jacobi(mp_int *a, mp_int *n, int *c);
394
395 /* used to setup the Barrett reduction for a given modulus b */
396 int mp_reduce_setup(mp_int *a, mp_int *b);
397
398 /* Barrett Reduction, computes a (mod b) with a precomputed value c
399 *
400 * Assumes that 0 < a <= b*b, note if 0 > a > -(b*b) then you can merely
401 * compute the reduction as -1 * mp_reduce(mp_abs(a)) [pseudo code].
402 */
403 int mp_reduce(mp_int *a, mp_int *b, mp_int *c);
404
405 /* setups the montgomery reduction */
406 int mp_montgomery_setup(mp_int *a, mp_digit *mp);
407
408 /* computes a = B**n mod b without division or multiplication useful for
409 * normalizing numbers in a Montgomery system.
410 */
411 int mp_montgomery_calc_normalization(mp_int *a, mp_int *b);
412
413 /* computes x/R == x (mod N) via Montgomery Reduction */
414 int mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
415
416 /* returns 1 if a is a valid DR modulus */
417 int mp_dr_is_modulus(mp_int *a);
418
419 /* sets the value of "d" required for mp_dr_reduce */
420 void mp_dr_setup(mp_int *a, mp_digit *d);
421
422 /* reduces a modulo b using the Diminished Radix method */
423 int mp_dr_reduce(mp_int *a, mp_int *b, mp_digit mp);
424
425 /* returns true if a can be reduced with mp_reduce_2k */
426 int mp_reduce_is_2k(mp_int *a);
427
428 /* determines k value for 2k reduction */
429 int mp_reduce_2k_setup(mp_int *a, mp_digit *d);
430
431 /* reduces a modulo b where b is of the form 2**p - k [0 <= a] */
432 int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d);
433
434 /* returns true if a can be reduced with mp_reduce_2k_l */
435 int mp_reduce_is_2k_l(mp_int *a);
436
437 /* determines k value for 2k reduction */
438 int mp_reduce_2k_setup_l(mp_int *a, mp_int *d);
439
440 /* reduces a modulo b where b is of the form 2**p - k [0 <= a] */
441 int mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d);
442
443 /* d = a**b (mod c) */
444 int mp_exptmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d);
445
446 /* ---> Primes <--- */
447
448 /* number of primes */
449 #ifdef MP_8BIT
450 #define PRIME_SIZE 31
451 #else
452 #define PRIME_SIZE 256
453 #endif
454
455 /* table of first PRIME_SIZE primes */
456 extern const mp_digit ltm_prime_tab[];
457
458 /* result=1 if a is divisible by one of the first PRIME_SIZE primes */
459 int mp_prime_is_divisible(mp_int *a, int *result);
460
461 /* performs one Fermat test of "a" using base "b".
462 * Sets result to 0 if composite or 1 if probable prime
463 */
464 int mp_prime_fermat(mp_int *a, mp_int *b, int *result);
465
466 /* performs one Miller-Rabin test of "a" using base "b".
467 * Sets result to 0 if composite or 1 if probable prime
468 */
469 int mp_prime_miller_rabin(mp_int *a, mp_int *b, int *result);
470
471 /* This gives [for a given bit size] the number of trials required
472 * such that Miller-Rabin gives a prob of failure lower than 2^-96
473 */
474 int mp_prime_rabin_miller_trials(int size);
475
476 /* performs t rounds of Miller-Rabin on "a" using the first
477 * t prime bases. Also performs an initial sieve of trial
478 * division. Determines if "a" is prime with probability
479 * of error no more than (1/4)**t.
480 *
481 * Sets result to 1 if probably prime, 0 otherwise
482 */
483 int mp_prime_is_prime(mp_int *a, int t, int *result);
484
485 /* finds the next prime after the number "a" using "t" trials
486 * of Miller-Rabin.
487 *
488 * bbs_style = 1 means the prime must be congruent to 3 mod 4
489 */
490 int mp_prime_next_prime(mp_int *a, int t, int bbs_style);
491
492 /* makes a truly random prime of a given size (bytes),
493 * call with bbs = 1 if you want it to be congruent to 3 mod 4
494 *
495 * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can
496 * have passed to the callback (e.g. a state or something). This function doesn't use "dat" itself
497 * so it can be NULL
498 *
499 * The prime generated will be larger than 2^(8*size).
500 */
501 #define mp_prime_random(a, t, size, bbs, cb, dat) mp_prime_random_ex(a, t, ((size) * 8) + 1, (bbs==1)?LTM_PRIME_BBS:0, cb, dat)
502
503 /* makes a truly random prime of a given size (bits),
504 *
505 * Flags are as follows:
506 *
507 * LTM_PRIME_BBS - make prime congruent to 3 mod 4
508 * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS)
509 * LTM_PRIME_2MSB_OFF - make the 2nd highest bit zero
510 * LTM_PRIME_2MSB_ON - make the 2nd highest bit one
511 *
512 * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can
513 * have passed to the callback (e.g. a state or something). This function doesn't use "dat" itself
514 * so it can be NULL
515 *
516 */
517 int mp_prime_random_ex(mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat);
518
519 /* ---> radix conversion <--- */
520 int mp_count_bits(mp_int *a);
521
522 int mp_unsigned_bin_size(mp_int *a);
523 int mp_read_unsigned_bin(mp_int *a, const unsigned char *b, int c);
524 int mp_to_unsigned_bin(mp_int *a, unsigned char *b);
525 int mp_to_unsigned_bin_n (mp_int * a, unsigned char *b, unsigned long *outlen);
526
527 int mp_signed_bin_size(mp_int *a);
528 int mp_read_signed_bin(mp_int *a, const unsigned char *b, int c);
529 int mp_to_signed_bin(mp_int *a, unsigned char *b);
530 int mp_to_signed_bin_n (mp_int * a, unsigned char *b, unsigned long *outlen);
531
532 int mp_read_radix(mp_int *a, const char *str, int radix);
533 int mp_toradix(mp_int *a, char *str, int radix);
534 int mp_toradix_n(mp_int * a, char *str, int radix, int maxlen);
535 int mp_radix_size(mp_int *a, int radix, int *size);
536
537 int mp_fread(mp_int *a, int radix, FILE *stream);
538 int mp_fwrite(mp_int *a, int radix, FILE *stream);
539
540 #define mp_read_raw(mp, str, len) mp_read_signed_bin((mp), (str), (len))
541 #define mp_raw_size(mp) mp_signed_bin_size(mp)
542 #define mp_toraw(mp, str) mp_to_signed_bin((mp), (str))
543 #define mp_read_mag(mp, str, len) mp_read_unsigned_bin((mp), (str), (len))
544 #define mp_mag_size(mp) mp_unsigned_bin_size(mp)
545 #define mp_tomag(mp, str) mp_to_unsigned_bin((mp), (str))
546
547 #define mp_tobinary(M, S) mp_toradix((M), (S), 2)
548 #define mp_tooctal(M, S) mp_toradix((M), (S), 8)
549 #define mp_todecimal(M, S) mp_toradix((M), (S), 10)
550 #define mp_tohex(M, S) mp_toradix((M), (S), 16)
551
552 /* lowlevel functions, do not call! */
553 int s_mp_add(mp_int *a, mp_int *b, mp_int *c);
554 int s_mp_sub(mp_int *a, mp_int *b, mp_int *c);
555 #define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)
556 int fast_s_mp_mul_digs(mp_int *a, mp_int *b, mp_int *c, int digs);
557 int s_mp_mul_digs(mp_int *a, mp_int *b, mp_int *c, int digs);
558 int fast_s_mp_mul_high_digs(mp_int *a, mp_int *b, mp_int *c, int digs);
559 int s_mp_mul_high_digs(mp_int *a, mp_int *b, mp_int *c, int digs);
560 int fast_s_mp_sqr(mp_int *a, mp_int *b);
561 int s_mp_sqr(mp_int *a, mp_int *b);
562 int mp_karatsuba_mul(mp_int *a, mp_int *b, mp_int *c);
563 int mp_toom_mul(mp_int *a, mp_int *b, mp_int *c);
564 int mp_karatsuba_sqr(mp_int *a, mp_int *b);
565 int mp_toom_sqr(mp_int *a, mp_int *b);
566 int fast_mp_invmod(mp_int *a, mp_int *b, mp_int *c);
567 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c);
568 int fast_mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp);
569 int mp_exptmod_fast(mp_int *G, mp_int *X, mp_int *P, mp_int *Y, int mode);
570 int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int mode);
571 void bn_reverse(unsigned char *s, int len);
572
573 extern const char *mp_s_rmap;
574
575 #ifdef __cplusplus
576 }
577 #endif
578
579 #endif
580
581
582 /* $Source: /cvs/libtom/libtommath/tommath.h,v $ */
583 /* $Revision: 1.8 $ */
584 /* $Date: 2006/03/31 14:18:44 $ */