5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 1997 - 2008 Pekka Riikonen
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; version 2 of the License.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
20 /****h* silcmath/MP Integer Interface
24 * SILC MP Library Interface. This interface defines the arbitrary
25 * precision arithmetic routines for SILC. The interface is generic but
26 * is mainly intended for crypto usage. This interface is used by SILC
27 * routines that needs big numbers, such as RSA implementation,
28 * Diffie-Hellman implementation etc.
35 #if defined(SILC_MP_GMP)
36 #include "mp_gmp.h" /* SILC_MP_GMP */
40 #endif /* SILC_DIST_TMA */
43 #endif /* SILC_DIST_TFM */
46 /****d* silcmath/SilcMPInt
50 * typedef SILC_MP_INT SilcMPInt;
54 * The SILC MP Integer definition. This is the actual MP integer.
55 * The type is defined as SILC_MP_INT as it is implementation specific
56 * and is unknown to the application.
60 typedef SILC_MP_INT SilcMPInt;
63 /****f* silcmath/silc_mp_init
67 * SilcBool silc_mp_init(SilcMPInt mp);
71 * Initializes the MP integer. This must be called before calling any
72 * other routine in SILC MP API. The silc_mp_uninit must be called
73 * to uninitialize the integer. Returns FALSE on error, TRUE otherwise.
76 SilcBool silc_mp_init(SilcMPInt *mp);
78 /****f* silcmath/silc_mp_sinit
82 * SilcBool silc_mp_sinit(SilcStack stack, SilcMPInt *mp);
86 * Initializes the MP integer. This must be called before calling any
87 * other routine in SILC MP API. The silc_mp_uninit must be called
88 * to uninitialize the integer. Returns FALSE on error, TRUE otherwise.
90 * If `stack' is non-NULL all memory is allocated from `stack'. If it
91 * is NULL this is equivalent to silc_mp_init. The silc_mp_uninit must
92 * be called to uninitialize the integer even when `stack' is non-NULL.
95 SilcBool silc_mp_sinit(SilcStack stack, SilcMPInt *mp);
97 /****f* silcmath/silc_mp_uninit
101 * void silc_mp_uninit(SilcMPInt *mp);
105 * Uninitializes the MP Integer.
108 void silc_mp_uninit(SilcMPInt *mp);
110 /****f* silcmath/silc_mp_size
114 * size_t silc_mp_size(SilcMPInt *mp);
118 * Return the precision size of the integer `mp'.
121 size_t silc_mp_size(SilcMPInt *mp);
123 /****f* silcmath/silc_mp_sizeinbase
127 * size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
131 * Return the size of the integer in base `base'.
135 * For any other base but 2 this function usually returns only an
136 * approximated size in the base. It is however guaranteed that the
137 * the returned size is always at least the size of the integer or
140 * For base 2 this returns the exact bit-size of the integer.
143 size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
145 /****f* silcmath/silc_mp_set
149 * SilcBool silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
153 * Set `dst' integer from `src' integer. The `dst' must already be
154 * initialized. This in effect copies the integer from `src' to `dst'.
157 SilcBool silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
159 /****f* silcmath/silc_mp_set_ui
163 * SilcBool silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui);
167 * Set `dst' integer from unsigned word `ui'. The `dst' must already be
171 SilcBool silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui);
173 /****f* silcmath/silc_mp_set_si
177 * SilcBool silc_mp_set_si(SilcMPInt *dst, SilcInt32 si);
181 * Set `dst' integer from single word `si'. The `dst' must
182 * already be initialized.
185 SilcBool silc_mp_set_si(SilcMPInt *dst, SilcInt32 si);
187 /****f* silcmath/silc_mp_set_str
191 * SilcBool silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
195 * Set `dst' integer from string `str' of base `base'. The `dst' must
196 * already be initialized.
200 * For base 2 the string must be in ASCII bit presentation, not in
201 * binary. Use the silc_mp_bin2mp to decode binary into integer.
204 SilcBool silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
206 /****f* silcmath/silc_mp_get_ui
210 * SilcUInt32 silc_mp_get_ui(SilcMPInt *mp);
214 * Returns the least significant unsigned word from `mp'.
217 SilcUInt32 silc_mp_get_ui(SilcMPInt *mp);
219 /****f* silcmath/silc_mp_get_str
223 * char *silc_mp_get_str(char *str, SilcMPInt *mp, int base);
227 * Converts integer `mp' into a string of base `base'. The `str'
228 * must already have space allocated. The function returns the same
229 * as `str' or NULL on error.
233 * For base 2 the returned string is in ASCII bit presentation, not
234 * in binary. Use the silc_mp_mp2bin to encode integer into binary.
237 char *silc_mp_get_str(char *str, SilcMPInt *mp, int base);
239 /****f* silcmath/silc_mp_add
243 * SilcBool silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
247 * Add two integers `mp1' and `mp2' and save the result to `dst'.
250 SilcBool silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
252 /****f* silcmath/silc_mp_add_ui
256 * SilcBool silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
260 * Add two integers `mp1' and unsigned word `ui' and save the result
264 SilcBool silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
266 /****f* silcmath/silc_mp_sub
270 * SilcBool silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
274 * Subtract two integers `mp1' and `mp2' and save the result to `dst'.
277 SilcBool silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
279 /****f* silcmath/silc_mp_sub_ui
283 * SilcBool silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
287 * Subtract integers `mp1' and unsigned word `ui' and save the result
291 SilcBool silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
293 /****f* silcmath/silc_mp_mul
297 * SilcBool silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
301 * Multiply two integers `mp1' and `mp2' and save the result to `dst'.
304 SilcBool silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
306 /****f* silcmath/silc_mp_mul_ui
310 * SilcBool silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
314 * Multiply integer `mp1' and unsigned word `ui' and save the result
318 SilcBool silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
320 /****f* silcmath/silc_mp_mul_2exp
324 * SilcBool silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
328 * Multiply integers `mp1' with 2 ** `exp' and save the result to
329 * `dst'. This is equivalent to dst = mp1 * (2 ^ exp).
332 SilcBool silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
334 /****f* silcmath/silc_mp_sqrt
338 * SilcBool silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
342 * Compute square root of floor(sqrt(src)) and save the result to `dst'.
345 SilcBool silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
347 /****f* silcmath/silc_mp_div
351 * SilcBool silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
355 * Divide the `mp1' and `mp2' and save the result to the `dst'. This
356 * is equivalent to dst = mp1 / mp2;
359 SilcBool silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
361 /****f* silcmath/silc_mp_div_ui
365 * SilcBool silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
369 * Divide the `mp1' and unsigned word `ui' and save the result to the
370 * `dst'. This is equivalent to dst = mp1 / ui;
373 SilcBool silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
375 /****f* silcmath/silc_mp_div_qr
379 * SilcBool silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
384 * Divide the `mp1' and `mp2' and save the quotient to the `q' and
385 * the remainder to the `r'. This is equivalent to the q = mp1 / mp2,
386 * r = mp1 mod mp2 (or mp1 = mp2 * q + r). If the `q' or `r' is NULL
387 * then the operation is omitted.
390 SilcBool silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
393 /****f* silcmath/silc_mp_div_2exp
397 * SilcBool silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
401 * Divide the `mp1' with 2 ** `exp' and save the result to `dst'.
402 * This is equivalent to dst = mp1 / (2 ^ exp).
405 SilcBool silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
407 /****f* silcmath/silc_mp_div_2exp_qr
411 * SilcBool silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
416 * Divide the `mp1' with 2 ** `exp' and save the quotient to `q' and
417 * the remainder to `r'. This is equivalent to q = mp1 / (2 ^ exp),
418 * r = mp1 mod (2 ^ exp). If the `q' or `r' is NULL then the operation
422 SilcBool silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
425 /****f* silcmath/silc_mp_mod
429 * SilcBool silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
433 * Mathematical MOD function. Produces the remainder of `mp1' and `mp2'
434 * and saves the result to `dst'. This is equivalent to dst = mp1 mod mp2.
435 * The same result can also be get with silc_mp_div_qr as that function
436 * returns the remainder as well.
439 SilcBool silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
441 /****f* silcmath/silc_mp_mod_ui
445 * SilcBool silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
449 * Mathematical MOD function. Produces the remainder of `mp1' and
450 * unsigned word `ui' and saves the result to `dst'. This is equivalent
451 * to dst = mp1 mod ui.
454 SilcBool silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
456 /****f* silcmath/silc_mp_mod_2exp
460 * SilcBool silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
464 * Computes the remainder of `mp1' with 2 ** `exp' and saves the
465 * result to `dst'. This is equivalent to dst = mp1 mod (2 ^ exp).
466 * The same result can also be get with silc_mp_div_2exp_qr as that
467 * function returns the remainder as well.
470 SilcBool silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
472 /****f* silcmath/silc_mp_pow_ui
476 * SilcBool silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
480 * Compute `mp1' ** `exp' and save the result to `dst'. This is
481 * equivalent to dst = mp1 ^ exp.
484 SilcBool silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
486 /****f* silcmath/silc_mp_pow_mod
490 * SilcBool silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
495 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
496 * This is equivalent to dst = (mp1 ^ exp) mod mod.
499 SilcBool silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
502 /****f* silcmath/silc_mp_pow_mod_ui
506 * SilcBool silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1,
507 * SilcUInt32 exp, SilcMPInt *mod);
511 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
512 * This is equivalent to dst = (mp1 ^ exp) mod mod.
515 SilcBool silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp,
518 /****f* silcmath/silc_mp_modinv
522 * SilcBool silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
526 * Find multiplicative inverse using Euclid's extended algorithm.
527 * Computes inverse such that a * inv mod n = 1, where 0 < a < n.
528 * Algorithm goes like this:
534 * g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i)
535 * v(i+1) = v(i-1) - y * v(i)
537 * do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n,
538 * is added to inverse making it positive again. (Sometimes the algorithm
539 * has a variable u defined too and it behaves just like v, except that
540 * initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is
541 * not needed by the algorithm so it does not have to be included.)
544 SilcBool silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
546 /****f* silcmath/silc_mp_gcd
550 * SilcBool silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
554 * Calculate the greatest common divisor of the integers `mp1' and `mp2'
555 * and save the result to `dst'.
558 SilcBool silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
560 /****f* silcmath/silc_mp_cmp
564 * int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
568 * Compare `mp1' and `mp2'. Returns posivite, zero, or negative
569 * if `mp1' > `mp2', `mp1' == `mp2', or `mp1' < `mp2', respectively.
572 int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
574 /****f* silcmath/silc_mp_cmp_si
578 * int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si);
582 * Compare `mp1' and single word `si'. Returns posivite, zero, or negative
583 * if `mp1' > `si', `mp1' == `si', or `mp1' < `si', respectively.
586 int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si);
588 /****f* silcmath/silc_mp_cmp_ui
592 * int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui);
596 * Compare `mp1' and unsigned word `ui'. Returns posivite, zero, or
597 * negative if `mp1' > `ui', `mp1' == `ui', or `mp1' < `ui',
601 int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui);
603 /****f* silcmath/silc_mp_mp2bin
607 * unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len,
608 * SilcUInt32 *ret_len);
612 * Encodes MP integer into binary data. Returns allocated data that
613 * must be free'd by the caller. If `len' is provided the destination
614 * buffer is allocated that large. If zero then the size is approximated.
617 unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len,
618 SilcUInt32 *ret_len);
620 /****f* silcmath/silc_mp_mp2bin_noalloc
624 * void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
625 * SilcUInt32 dst_len);
629 * Same as silc_mp_mp2bin but does not allocate any memory. The
630 * encoded data is returned into `dst' of size of `dst_len'.
633 void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
636 /****f* silcmath/silc_mp_bin2mp
640 * void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len,
645 * Decodes binary data into MP integer. The integer sent as argument
646 * must be initialized.
649 void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len, SilcMPInt *ret);
651 /****f* silcmath/silc_mp_abs
655 * SilcBool silc_mp_abs(SilcMPInt *src, SilcMPInt *dst);
659 * Assign the absolute value of `src' to `dst'.
662 SilcBool silc_mp_abs(SilcMPInt *dst, SilcMPInt *src);
664 /****f* silcmath/silc_mp_neg
668 * SilcBool silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
672 * Negate `src' and save the result to `dst'.
675 SilcBool silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
677 /****f* silcmath/silc_mp_and
681 * SilcBool silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
685 * Bitwise AND operator. The result is saved to `dst'.
688 SilcBool silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
690 /****f* silcmath/silc_mp_or
694 * SilcBool silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
698 * Bitwise inclusive OR operator. The result is saved to `dst'.
701 SilcBool silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
703 /****f* silcmath/silc_mp_xor
707 * SilcBool silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
711 * Bitwise exclusive OR operator. The result is saved to `dst'.
714 SilcBool silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
716 /* Utility functions */
718 /****f* silcmath/silc_mp_format
722 * int silc_mp_format(SilcStack stack, SilcBuffer buffer,
723 * void *value, void *context)
727 * MP integer encoding function to be used with silc_buffer_format and
728 * SILC_STR_FUNC formatter. The encoded data is of following format:
730 * SILC_STR_UINT32, integer_len,
731 * SILC_STR_DATA integer_data
735 * silc_buffer_format(buf,
736 * SILC_STR_FUNC(silc_mp_format, mpint, NULL),
740 int silc_mp_format(SilcStack stack, SilcBuffer buffer,
741 void *value, void *context);
743 /****f* silcmath/silc_mp_unformat
747 * int silc_mp_unformat(SilcStack stack, SilcBuffer buffer,
748 * void **value, void *context)
752 * MP integer decoding function to be used with silc_buffer_unformat and
753 * SILC_STR_FUNC unformatter. This function expects that the length of
754 * the integer is encoded as 32-bit integer and precedes the integer
761 * silc_mp_init(&mpint);
764 * silc_buffer_unformat(buf,
765 * SILC_STR_FUNC(silc_mp_unformat, &mp_ptr, NULL),
769 int silc_mp_unformat(SilcStack stack, SilcBuffer buffer,
770 void **value, void *context);