5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 1997 - 2005 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/SILC MP 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/SilcMPAPI/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/SilcMPAPI/silc_mp_init
67 * void silc_mp_init(SilcMPInt mp);
71 * Initializes the SilcMPInt *that is the actual MP Integer.
72 * This must be called before any of the silc_mp_ routines can be
73 * used. The integer is uninitialized with the silc_mp_uninit function.
76 void silc_mp_init(SilcMPInt *mp);
78 /****f* silcmath/SilcMPAPI/silc_mp_sinit
82 * bool silc_mp_sinit(SilcStack stack, SilcMPInt *mp);
86 * Initializes the SilcMPInt *that is the actual MP Integer.
87 * This must be called before any of the silc_mp_ routines can be
88 * used. The integer is uninitialized with the silc_mp_uninit function.
89 * This routine is equivalent to silc_mp_init but allocates the memory
94 * The `stack' is saved into the `mp' for the duration of the existence
95 * of `mp'. This means that `stack' must not become invalid while `mp'
96 * is used. It also means that any routine that may need memory allocation
97 * to for example enlarge `mp' will allocate the memory from `stack'.
100 bool silc_mp_sinit(SilcStack stack, SilcMPInt *mp);
102 /****f* silcmath/SilcMPAPI/silc_mp_uninit
106 * void silc_mp_uninit(SilcMPInt *mp);
110 * Uninitializes the MP Integer.
113 void silc_mp_uninit(SilcMPInt *mp);
115 /****f* silcmath/SilcMPAPI/silc_mp_size
119 * size_t silc_mp_size(SilcMPInt *mp);
123 * Return the precision size of the integer `mp'.
126 size_t silc_mp_size(SilcMPInt *mp);
128 /****f* silcmath/SilcMPAPI/silc_mp_sizeinbase
132 * size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
136 * Return the size of the integer in base `base'.
140 * For any other base but 2 this function usually returns only an
141 * approximated size in the base. It is however guaranteed that the
142 * the returned size is always at least the size of the integer or
145 * For base 2 this returns the exact bit-size of the integer.
148 size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
150 /****f* silcmath/SilcMPAPI/silc_mp_set
154 * void silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
158 * Set `dst' integer from `src' integer. The `dst' must already be
162 void silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
164 /****f* silcmath/SilcMPAPI/silc_mp_set_ui
168 * void silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui);
172 * Set `dst' integer from unsigned word `ui'. The `dst' must already be
176 void silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui);
178 /****f* silcmath/SilcMPAPI/silc_mp_set_si
182 * void silc_mp_set_si(SilcMPInt *dst, SilcInt32 si);
186 * Set `dst' integer from single word `si'. The `dst' must
187 * already be initialized.
190 void silc_mp_set_si(SilcMPInt *dst, SilcInt32 si);
192 /****f* silcmath/SilcMPAPI/silc_mp_set_str
196 * void silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
200 * Set `dst' integer from string `str' of base `base'. The `dst' must
201 * already be initialized.
205 * For base 2 the string must be in ASCII bit presentation, not in
206 * binary. Use the silc_mp_bin2mp to decode binary into integer.
209 void silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
211 /****f* silcmath/SilcMPAPI/silc_mp_get_ui
215 * SilcUInt32 silc_mp_get_ui(SilcMPInt *mp);
219 * Returns the least significant unsigned word from `mp'.
222 SilcUInt32 silc_mp_get_ui(SilcMPInt *mp);
224 /****f* silcmath/SilcMPAPI/silc_mp_get_str
228 * void silc_mp_get_str(char *str, SilcMPInt *mp, int base);
232 * Converts integer `mp' into a string of base `base'. The `str'
233 * must already have space allocated. The function returns the same
234 * as `str' or NULL on error.
238 * For base 2 the returned string is in ASCII bit presentation, not
239 * in binary. Use the silc_mp_mp2bin to encode integer into binary.
242 char *silc_mp_get_str(char *str, SilcMPInt *mp, int base);
244 /****f* silcmath/SilcMPAPI/silc_mp_add
248 * void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
252 * Add two integers `mp1' and `mp2' and save the result to `dst'.
255 void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
257 /****f* silcmath/SilcMPAPI/silc_mp_add_ui
261 * void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
265 * Add two integers `mp1' and unsigned word `ui' and save the result
269 void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
271 /****f* silcmath/SilcMPAPI/silc_mp_sub
275 * void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
279 * Subtract two integers `mp1' and `mp2' and save the result to `dst'.
282 void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
284 /****f* silcmath/SilcMPAPI/silc_mp_sub_ui
288 * void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
292 * Subtract integers `mp1' and unsigned word `ui' and save the result
296 void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
298 /****f* silcmath/SilcMPAPI/silc_mp_mul
302 * void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
306 * Multiply two integers `mp1' and `mp2' and save the result to `dst'.
309 void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
311 /****f* silcmath/SilcMPAPI/silc_mp_mul_ui
315 * void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
319 * Multiply integer `mp1' and unsigned word `ui' and save the result
323 void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
325 /****f* silcmath/SilcMPAPI/silc_mp_mul_2exp
329 * void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
333 * Multiply integers `mp1' with 2 ** `exp' and save the result to
334 * `dst'. This is equivalent to dst = mp1 * (2 ^ exp).
337 void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
339 /****f* silcmath/SilcMPAPI/silc_mp_sqrt
343 * void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
347 * Compute square root of floor(sqrt(src)) and save the result to `dst'.
350 void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
352 /****f* silcmath/SilcMPAPI/silc_mp_div
356 * void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
360 * Divide the `mp1' and `mp2' and save the result to the `dst'. This
361 * is equivalent to dst = mp1 / mp2;
364 void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
366 /****f* silcmath/SilcMPAPI/silc_mp_div_ui
370 * void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
374 * Divide the `mp1' and unsigned word `ui' and save the result to the
375 * `dst'. This is equivalent to dst = mp1 / ui;
378 void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
380 /****f* silcmath/SilcMPAPI/silc_mp_div_qr
384 * void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
389 * Divide the `mp1' and `mp2' and save the quotient to the `q' and
390 * the remainder to the `r'. This is equivalent to the q = mp1 / mp2,
391 * r = mp1 mod mp2 (or mp1 = mp2 * q + r). If the `q' or `r' is NULL
392 * then the operation is omitted.
395 void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
398 /****f* silcmath/SilcMPAPI/silc_mp_div_2exp
402 * void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
406 * Divide the `mp1' with 2 ** `exp' and save the result to `dst'.
407 * This is equivalent to dst = mp1 / (2 ^ exp).
410 void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
412 /****f* silcmath/SilcMPAPI/silc_mp_div_2exp_qr
416 * void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
421 * Divide the `mp1' with 2 ** `exp' and save the quotient to `q' and
422 * the remainder to `r'. This is equivalent to q = mp1 / (2 ^ exp),
423 * r = mp1 mod (2 ^ exp). If the `q' or `r' is NULL then the operation
427 void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
430 /****f* silcmath/SilcMPAPI/silc_mp_mod
434 * void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
438 * Mathematical MOD function. Produces the remainder of `mp1' and `mp2'
439 * and saves the result to `dst'. This is equivalent to dst = mp1 mod mp2.
440 * The same result can also be get with silc_mp_div_qr as that function
441 * returns the remainder as well.
444 void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
446 /****f* silcmath/SilcMPAPI/silc_mp_mod_ui
450 * void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
454 * Mathematical MOD function. Produces the remainder of `mp1' and
455 * unsigned word `ui' and saves the result to `dst'. This is equivalent
456 * to dst = mp1 mod ui.
459 void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
461 /****f* silcmath/SilcMPAPI/silc_mp_mod_2exp
465 * void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
469 * Computes the remainder of `mp1' with 2 ** `exp' and saves the
470 * result to `dst'. This is equivalent to dst = mp1 mod (2 ^ exp).
471 * The same result can also be get with silc_mp_div_2exp_qr as that
472 * function returns the remainder as well.
475 void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
477 /****f* silcmath/SilcMPAPI/silc_mp_pow
481 * void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp);
485 * Compute `mp1' ** `exp' and save the result to `dst'. This is
486 * equivalent to dst = mp1 ^ exp.
489 void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp);
491 /****f* silcmath/SilcMPAPI/silc_mp_pow_ui
495 * void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
499 * Compute `mp1' ** `exp' and save the result to `dst'. This is
500 * equivalent to dst = mp1 ^ exp.
503 void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
505 /****f* silcmath/SilcMPAPI/silc_mp_pow_mod
509 * void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
514 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
515 * This is equivalent to dst = (mp1 ^ exp) mod mod.
518 void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
521 /****f* silcmath/SilcMPAPI/silc_mp_pow_mod_ui
525 * void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp,
530 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
531 * This is equivalent to dst = (mp1 ^ exp) mod mod.
534 void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp,
537 /****f* silcmath/SilcMPAPI/silc_mp_modinv
541 * void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
545 * Find multiplicative inverse using Euclid's extended algorithm.
546 * Computes inverse such that a * inv mod n = 1, where 0 < a < n.
547 * Algorithm goes like this:
553 * g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i)
554 * v(i+1) = v(i-1) - y * v(i)
556 * do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n,
557 * is added to inverse making it positive again. (Sometimes the algorithm
558 * has a variable u defined too and it behaves just like v, except that
559 * initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is
560 * not needed by the algorithm so it does not have to be included.)
563 void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
565 /****f* silcmath/SilcMPAPI/silc_mp_gcd
569 * void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
573 * Calculate the greatest common divisor of the integers `mp1' and `mp2'
574 * and save the result to `dst'.
577 void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
579 /****f* silcmath/SilcMPAPI/silc_mp_gcdext
583 * void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t,
584 * SilcMPInt *mp1, SilcMPInt *mp2);
588 * Calculate the extended greatest common divisor `g', `s' and `t' such
589 * that g = mp1 * s + mp2 * + t.
592 void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t, SilcMPInt *mp1,
595 /****f* silcmath/SilcMPAPI/silc_mp_cmp
599 * int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
603 * Compare `mp1' and `mp2'. Returns posivite, zero, or negative
604 * if `mp1' > `mp2', `mp1' == `mp2', or `mp1' < `mp2', respectively.
607 int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
609 /****f* silcmath/SilcMPAPI/silc_mp_cmp_si
613 * int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si);
617 * Compare `mp1' and single word `si'. Returns posivite, zero, or negative
618 * if `mp1' > `si', `mp1' == `si', or `mp1' < `si', respectively.
621 int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si);
623 /****f* silcmath/SilcMPAPI/silc_mp_cmp_ui
627 * int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui);
631 * Compare `mp1' and unsigned word `ui'. Returns posivite, zero, or
632 * negative if `mp1' > `ui', `mp1' == `ui', or `mp1' < `ui',
636 int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui);
638 /****f* silcmath/SilcMPAPI/silc_mp_mp2bin
642 * unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len,
643 * SilcUInt32 *ret_len);
647 * Encodes MP integer into binary data. Returns allocated data that
648 * must be free'd by the caller. If `len' is provided the destination
649 * buffer is allocated that large. If zero then the size is approximated.
652 unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len,
653 SilcUInt32 *ret_len);
655 /****f* silcmath/SilcMPAPI/silc_mp_mp2bin_noalloc
659 * void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
660 * SilcUInt32 dst_len);
664 * Same as silc_mp_mp2bin but does not allocate any memory. The
665 * encoded data is returned into `dst' and it's length to the `ret_len'.
668 void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
671 /****f* silcmath/SilcMPAPI/silc_mp_bin2mp
675 * void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len,
680 * Decodes binary data into MP integer. The integer sent as argument
681 * must be initialized.
684 void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len, SilcMPInt *ret);
686 /****f* silcmath/SilcMPAPI/silc_mp_abs
690 * void silc_mp_abs(SilcMPInt *src, SilcMPInt *dst);
694 * Assign the absolute value of `src' to `dst'.
697 void silc_mp_abs(SilcMPInt *dst, SilcMPInt *src);
699 /****f* silcmath/SilcMPAPI/silc_mp_neg
703 * void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
707 * Negate `src' and save the result to `dst'.
710 void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
712 /****f* silcmath/SilcMPAPI/silc_mp_and
716 * void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
720 * Logical and operator. The result is saved to `dst'.
723 void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
725 /****f* silcmath/SilcMPAPI/silc_mp_or
729 * void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
733 * Logical inclusive OR operator. The result is saved to `dst'.
736 void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
738 /****f* silcmath/SilcMPAPI/silc_mp_xor
742 * void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
746 * Logical exclusive OR operator. The result is saved to `dst'.
749 void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);