5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 1997 - 2001 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; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
21 /****h* silcmath/SILC MP Interface
25 * SILC MP Library Interface. This interface defines the arbitrary
26 * precision arithmetic routines for SILC. Currently the actual routines
27 * are implemented separately, usually by some other MP library. The
28 * interface is generic but is mainly intended for crypto usage. This
29 * interface is used by SILC routines that needs big numbers, such as
30 * RSA implementation, Diffie-Hellman implementation etc.
37 #if defined(SILC_MP_GMP)
38 #include "mp_gmp.h" /* SILC_MP_GMP */
40 #include "mp_mpi.h" /* SILC_MP_NSS_MPI */
43 /****d* silcmath/SilcMPAPI/SilcMPInt
47 * typedef SILC_MP_INT SilcMPInt;
51 * The SILC MP Integer definition. This is the actual MP integer.
52 * The type is defined as SILC_MP_INT as it is implementation specific
53 * and is unknown to the application.
57 typedef SILC_MP_INT SilcMPInt;
60 /****f* silcmath/SilcMPAPI/silc_mp_init
64 * void silc_mp_init(SilcMPInt mp);
68 * Initializes the SilcMPInt *that is the actual MP Integer.
69 * This must be called before any of the silc_mp_ routines can be
70 * used. The integer is uninitialized with the silc_mp_uninit function.
73 void silc_mp_init(SilcMPInt *mp);
75 /****f* silcmath/SilcMPAPI/silc_mp_uninit
79 * void silc_mp_uninit(SilcMPInt *mp);
83 * Uninitializes the MP Integer.
86 void silc_mp_uninit(SilcMPInt *mp);
88 /****f* silcmath/SilcMPAPI/silc_mp_size
92 * size_t silc_mp_size(SilcMPInt *mp);
96 * Return the precision size of the integer `mp'.
99 size_t silc_mp_size(SilcMPInt *mp);
101 /****f* silcmath/SilcMPAPI/silc_mp_sizeinbase
105 * size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
109 * Return the size of the integer in base `base'.
113 * For any other base but 2 this function usually returns only an
114 * approximated size in the base. It is however guaranteed that the
115 * the returned size is always at least the size of the integer or
118 * For base 2 this returns the exact bit-size of the integer.
121 size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
123 /****f* silcmath/SilcMPAPI/silc_mp_set
127 * void silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
131 * Set `dst' integer from `src' integer. The `dst' must already be
135 void silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
137 /****f* silcmath/SilcMPAPI/silc_mp_set_ui
141 * void silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui);
145 * Set `dst' integer from unsigned word `ui'. The `dst' must already be
149 void silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui);
151 /****f* silcmath/SilcMPAPI/silc_mp_set_si
155 * void silc_mp_set_si(SilcMPInt *dst, SilcInt32 si);
159 * Set `dst' integer from single word `si'. The `dst' must
160 * already be initialized.
163 void silc_mp_set_si(SilcMPInt *dst, SilcInt32 si);
165 /****f* silcmath/SilcMPAPI/silc_mp_set_str
169 * void silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
173 * Set `dst' integer from string `str' of base `base'. The `dst' must
174 * already be initialized.
178 * For base 2 the string must be in ASCII bit presentation, not in
179 * binary. Use the silc_mp_bin2mp to decode binary into integer.
182 void silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
184 /****f* silcmath/SilcMPAPI/silc_mp_get_ui
188 * SilcUInt32 silc_mp_get_ui(SilcMPInt *mp);
192 * Returns the least significant unsigned word from `mp'.
195 SilcUInt32 silc_mp_get_ui(SilcMPInt *mp);
197 /****f* silcmath/SilcMPAPI/silc_mp_get_str
201 * void silc_mp_get_str(char *str, SilcMPInt *mp, int base);
205 * Converts integer `mp' into a string of base `base'. The `str'
206 * must already have space allocated. The function returns the same
207 * as `str' or NULL on error.
211 * For base 2 the returned string is in ASCII bit presentation, not
212 * in binary. Use the silc_mp_mp2bin to encode integer into binary.
215 char *silc_mp_get_str(char *str, SilcMPInt *mp, int base);
217 /****f* silcmath/SilcMPAPI/silc_mp_add
221 * void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
225 * Add two integers `mp1' and `mp2' and save the result to `dst'.
228 void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
230 /****f* silcmath/SilcMPAPI/silc_mp_add_ui
234 * void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
238 * Add two integers `mp1' and unsigned word `ui' and save the result
242 void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
244 /****f* silcmath/SilcMPAPI/silc_mp_sub
248 * void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
252 * Subtract two integers `mp1' and `mp2' and save the result to `dst'.
255 void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
257 /****f* silcmath/SilcMPAPI/silc_mp_sub_ui
261 * void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
265 * Subtract integers `mp1' and unsigned word `ui' and save the result
269 void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
271 /****f* silcmath/SilcMPAPI/silc_mp_mul
275 * void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
279 * Multiply two integers `mp1' and `mp2' and save the result to `dst'.
282 void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
284 /****f* silcmath/SilcMPAPI/silc_mp_mul_ui
288 * void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
292 * Multiply integer `mp1' and unsigned word `ui' and save the result
296 void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
298 /****f* silcmath/SilcMPAPI/silc_mp_mul_2exp
302 * void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
306 * Multiply integers `mp1' with 2 ** `exp' and save the result to
307 * `dst'. This is equivalent to dst = mp1 * (2 ^ exp).
310 void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
312 /****f* silcmath/SilcMPAPI/silc_mp_sqrt
316 * void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
320 * Compute square root of floor(sqrt(src)) and save the result to `dst'.
323 void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
325 /****f* silcmath/SilcMPAPI/silc_mp_div
329 * void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
333 * Divide the `mp1' and `mp2' and save the result to the `dst'. This
334 * is equivalent to dst = mp1 / mp2;
337 void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
339 /****f* silcmath/SilcMPAPI/silc_mp_div_ui
343 * void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
347 * Divide the `mp1' and unsigned word `ui' and save the result to the
348 * `dst'. This is equivalent to dst = mp1 / ui;
351 void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
353 /****f* silcmath/SilcMPAPI/silc_mp_div_qr
357 * void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
362 * Divide the `mp1' and `mp2' and save the quotient to the `q' and
363 * the remainder to the `r'. This is equivalent to the q = mp1 / mp2,
364 * r = mp1 mod mp2 (or mp1 = mp2 * q + r). If the `q' or `r' is NULL
365 * then the operation is omitted.
368 void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
371 /****f* silcmath/SilcMPAPI/silc_mp_div_2exp
375 * void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
379 * Divide the `mp1' with 2 ** `exp' and save the result to `dst'.
380 * This is equivalent to dst = mp1 / (2 ^ exp).
383 void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
385 /****f* silcmath/SilcMPAPI/silc_mp_div_2exp_qr
389 * void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
394 * Divide the `mp1' with 2 ** `exp' and save the quotient to `q' and
395 * the remainder to `r'. This is equivalent to q = mp1 / (2 ^ exp),
396 * r = mp1 mod (2 ^ exp). If the `q' or `r' is NULL then the operation
400 void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
403 /****f* silcmath/SilcMPAPI/silc_mp_mod
407 * void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
411 * Mathematical MOD function. Produces the remainder of `mp1' and `mp2'
412 * and saves the result to `dst'. This is equivalent to dst = mp1 mod mp2.
413 * The same result can also be get with silc_mp_div_qr as that function
414 * returns the remainder as well.
417 void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
419 /****f* silcmath/SilcMPAPI/silc_mp_mod_ui
423 * void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
427 * Mathematical MOD function. Produces the remainder of `mp1' and
428 * unsigned word `ui' and saves the result to `dst'. This is equivalent
429 * to dst = mp1 mod ui.
432 void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
434 /****f* silcmath/SilcMPAPI/silc_mp_mod_2exp
438 * void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
442 * Computes the remainder of `mp1' with 2 ** `exp' and saves the
443 * result to `dst'. This is equivalent to dst = mp1 mod (2 ^ exp).
444 * The same result can also be get with silc_mp_div_2exp_qr as that
445 * function returns the remainder as well.
448 void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui);
450 /****f* silcmath/SilcMPAPI/silc_mp_pow
454 * void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp);
458 * Compute `mp1' ** `exp' and save the result to `dst'. This is
459 * equivalent to dst = mp1 ^ exp.
462 void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp);
464 /****f* silcmath/SilcMPAPI/silc_mp_pow_ui
468 * void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
472 * Compute `mp1' ** `exp' and save the result to `dst'. This is
473 * equivalent to dst = mp1 ^ exp.
476 void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp);
478 /****f* silcmath/SilcMPAPI/silc_mp_pow_mod
482 * void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
487 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
488 * This is equivalent to dst = (mp1 ^ exp) mod mod.
491 void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
494 /****f* silcmath/SilcMPAPI/silc_mp_pow_mod_ui
498 * void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp,
503 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
504 * This is equivalent to dst = (mp1 ^ exp) mod mod.
507 void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp,
510 /****f* silcmath/SilcMPAPI/silc_mp_modinv
514 * void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
518 * Find multiplicative inverse using Euclid's extended algorithm.
519 * Computes inverse such that a * inv mod n = 1, where 0 < a < n.
520 * Algorithm goes like this:
526 * g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i)
527 * v(i+1) = v(i-1) - y * v(i)
529 * do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n,
530 * is added to inverse making it positive again. (Sometimes the algorithm
531 * has a variable u defined too and it behaves just like v, except that
532 * initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is
533 * not needed by the algorithm so it does not have to be included.)
536 void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
538 /****f* silcmath/SilcMPAPI/silc_mp_gcd
542 * void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
546 * Calculate the greatest common divisor of the integers `mp1' and `mp2'
547 * and save the result to `dst'.
550 void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
552 /****f* silcmath/SilcMPAPI/silc_mp_gcdext
556 * void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t,
557 * SilcMPInt *mp1, SilcMPInt *mp2);
561 * Calculate the extended greatest common divisor `g', `s' and `t' such
562 * that g = mp1 * s + mp2 * + t.
565 void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t, SilcMPInt *mp1,
568 /****f* silcmath/SilcMPAPI/silc_mp_cmp
572 * int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
576 * Compare `mp1' and `mp2'. Returns posivite, zero, or negative
577 * if `mp1' > `mp2', `mp1' == `mp2', or `mp1' < `mp2', respectively.
580 int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
582 /****f* silcmath/SilcMPAPI/silc_mp_cmp_si
586 * int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si);
590 * Compare `mp1' and single word `si'. Returns posivite, zero, or negative
591 * if `mp1' > `si', `mp1' == `si', or `mp1' < `si', respectively.
594 int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si);
596 /****f* silcmath/SilcMPAPI/silc_mp_cmp_ui
600 * int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui);
604 * Compare `mp1' and unsigned word `ui'. Returns posivite, zero, or
605 * negative if `mp1' > `ui', `mp1' == `ui', or `mp1' < `ui',
609 int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui);
611 /****f* silcmath/SilcMPAPI/silc_mp_mp2bin
615 * unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len,
616 * SilcUInt32 *ret_len);
620 * Encodes MP integer into binary data. Returns allocated data that
621 * must be free'd by the caller. If `len' is provided the destination
622 * buffer is allocated that large. If zero then the size is approximated.
625 unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len,
626 SilcUInt32 *ret_len);
628 /****f* silcmath/SilcMPAPI/silc_mp_mp2bin_noalloc
632 * void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
633 * SilcUInt32 dst_len);
637 * Same as silc_mp_mp2bin but does not allocate any memory. The
638 * encoded data is returned into `dst' and it's length to the `ret_len'.
641 void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
644 /****f* silcmath/SilcMPAPI/silc_mp_bin2mp
648 * void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len,
653 * Decodes binary data into MP integer. The integer sent as argument
654 * must be initialized.
657 void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len, SilcMPInt *ret);
659 /****f* silcmath/SilcMPAPI/silc_mp_abs
663 * void silc_mp_abs(SilcMPInt *src, SilcMPInt *dst);
667 * Assign the absolute value of `src' to `dst'.
670 void silc_mp_abs(SilcMPInt *dst, SilcMPInt *src);
672 /****f* silcmath/SilcMPAPI/silc_mp_neg
676 * void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
680 * Negate `src' and save the result to `dst'.
683 void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
685 /****f* silcmath/SilcMPAPI/silc_mp_and
689 * void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
693 * Logical and operator. The result is saved to `dst'.
696 void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
698 /****f* silcmath/SilcMPAPI/silc_mp_or
702 * void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
706 * Logical inclusive OR operator. The result is saved to `dst'.
709 void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
711 /****f* silcmath/SilcMPAPI/silc_mp_xor
715 * void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
719 * Logical exclusive OR operator. The result is saved to `dst'.
722 void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);