Mercurial > dropbear

comparison libtommath/tommath.h @ 284:eed26cff980b

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