/* silcmp.h Author: Pekka Riikonen Copyright (C) 1997 - 2005 Pekka Riikonen The contents of this file are subject to one of the Licenses specified in the COPYING file; You may not use this file except in compliance with the License. The software distributed under the License is distributed on an "AS IS" basis, in the hope that it will be useful, but WITHOUT WARRANTY OF ANY KIND, either expressed or implied. See the COPYING file for more information. */ /****h* silcmath/SILC MP Interface * * DESCRIPTION * * SILC MP Library Interface. This interface defines the arbitrary * precision arithmetic routines for SILC. The interface is generic but * is mainly intended for crypto usage. This interface is used by SILC * routines that needs big numbers, such as RSA implementation, * Diffie-Hellman implementation etc. * ***/ #ifndef SILCMP_H #define SILCMP_H #if defined(SILC_MP_GMP) #include "mp_gmp.h" /* SILC_MP_GMP */ #else #include "mp_tma.h" #endif /****d* silcmath/SilcMPAPI/SilcMPInt * * NAME * * typedef SILC_MP_INT SilcMPInt; * * DESCRIPTION * * The SILC MP Integer definition. This is the actual MP integer. * The type is defined as SILC_MP_INT as it is implementation specific * and is unknown to the application. * * SOURCE */ typedef SILC_MP_INT SilcMPInt; /***/ /****f* silcmath/SilcMPAPI/silc_mp_init * * SYNOPSIS * * void silc_mp_init(SilcMPInt mp); * * DESCRIPTION * * Initializes the SilcMPInt *that is the actual MP Integer. * This must be called before any of the silc_mp_ routines can be * used. The integer is uninitialized with the silc_mp_uninit function. * ***/ void silc_mp_init(SilcMPInt *mp); /****f* silcmath/SilcMPAPI/silc_mp_uninit * * SYNOPSIS * * void silc_mp_uninit(SilcMPInt *mp); * * DESCRIPTION * * Uninitializes the MP Integer. * ***/ void silc_mp_uninit(SilcMPInt *mp); /****f* silcmath/SilcMPAPI/silc_mp_size * * SYNOPSIS * * size_t silc_mp_size(SilcMPInt *mp); * * DESCRIPTION * * Return the precision size of the integer `mp'. * ***/ size_t silc_mp_size(SilcMPInt *mp); /****f* silcmath/SilcMPAPI/silc_mp_sizeinbase * * SYNOPSIS * * size_t silc_mp_sizeinbase(SilcMPInt *mp, int base); * * DESCRIPTION * * Return the size of the integer in base `base'. * * NOTES * * For any other base but 2 this function usually returns only an * approximated size in the base. It is however guaranteed that the * the returned size is always at least the size of the integer or * larger. * * For base 2 this returns the exact bit-size of the integer. * ***/ size_t silc_mp_sizeinbase(SilcMPInt *mp, int base); /****f* silcmath/SilcMPAPI/silc_mp_set * * SYNOPSIS * * void silc_mp_set(SilcMPInt *dst, SilcMPInt *src); * * DESCRIPTION * * Set `dst' integer from `src' integer. The `dst' must already be * initialized. * ***/ void silc_mp_set(SilcMPInt *dst, SilcMPInt *src); /****f* silcmath/SilcMPAPI/silc_mp_set_ui * * SYNOPSIS * * void silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui); * * DESCRIPTION * * Set `dst' integer from unsigned word `ui'. The `dst' must already be * initialized. * ***/ void silc_mp_set_ui(SilcMPInt *dst, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_set_si * * SYNOPSIS * * void silc_mp_set_si(SilcMPInt *dst, SilcInt32 si); * * DESCRIPTION * * Set `dst' integer from single word `si'. The `dst' must * already be initialized. * ***/ void silc_mp_set_si(SilcMPInt *dst, SilcInt32 si); /****f* silcmath/SilcMPAPI/silc_mp_set_str * * SYNOPSIS * * void silc_mp_set_str(SilcMPInt *dst, const char *str, int base); * * DESCRIPTION * * Set `dst' integer from string `str' of base `base'. The `dst' must * already be initialized. * * NOTES * * For base 2 the string must be in ASCII bit presentation, not in * binary. Use the silc_mp_bin2mp to decode binary into integer. * ***/ void silc_mp_set_str(SilcMPInt *dst, const char *str, int base); /****f* silcmath/SilcMPAPI/silc_mp_get_ui * * SYNOPSIS * * SilcUInt32 silc_mp_get_ui(SilcMPInt *mp); * * DESCRIPTION * * Returns the least significant unsigned word from `mp'. * ***/ SilcUInt32 silc_mp_get_ui(SilcMPInt *mp); /****f* silcmath/SilcMPAPI/silc_mp_get_str * * SYNOPSIS * * void silc_mp_get_str(char *str, SilcMPInt *mp, int base); * * DESCRIPTION * * Converts integer `mp' into a string of base `base'. The `str' * must already have space allocated. The function returns the same * as `str' or NULL on error. * * NOTES * * For base 2 the returned string is in ASCII bit presentation, not * in binary. Use the silc_mp_mp2bin to encode integer into binary. * ***/ char *silc_mp_get_str(char *str, SilcMPInt *mp, int base); /****f* silcmath/SilcMPAPI/silc_mp_add * * SYNOPSIS * * void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Add two integers `mp1' and `mp2' and save the result to `dst'. * ***/ void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_add_ui * * SYNOPSIS * * void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); * * DESCRIPTION * * Add two integers `mp1' and unsigned word `ui' and save the result * to `dst'. * ***/ void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_sub * * SYNOPSIS * * void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Subtract two integers `mp1' and `mp2' and save the result to `dst'. * ***/ void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_sub_ui * * SYNOPSIS * * void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); * * DESCRIPTION * * Subtract integers `mp1' and unsigned word `ui' and save the result * to `dst'. * ***/ void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_mul * * SYNOPSIS * * void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Multiply two integers `mp1' and `mp2' and save the result to `dst'. * ***/ void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_mul_ui * * SYNOPSIS * * void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); * * DESCRIPTION * * Multiply integer `mp1' and unsigned word `ui' and save the result * to `dst'. * ***/ void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_mul_2exp * * SYNOPSIS * * void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp); * * DESCRIPTION * * Multiply integers `mp1' with 2 ** `exp' and save the result to * `dst'. This is equivalent to dst = mp1 * (2 ^ exp). * ***/ void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp); /****f* silcmath/SilcMPAPI/silc_mp_sqrt * * SYNOPSIS * * void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src); * * DESCRIPTION * * Compute square root of floor(sqrt(src)) and save the result to `dst'. * ***/ void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src); /****f* silcmath/SilcMPAPI/silc_mp_div * * SYNOPSIS * * void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Divide the `mp1' and `mp2' and save the result to the `dst'. This * is equivalent to dst = mp1 / mp2; * ***/ void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_div_ui * * SYNOPSIS * * void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); * * DESCRIPTION * * Divide the `mp1' and unsigned word `ui' and save the result to the * `dst'. This is equivalent to dst = mp1 / ui; * ***/ void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_div_qr * * SYNOPSIS * * void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1, * SilcMPInt *mp2); * * DESCRIPTION * * Divide the `mp1' and `mp2' and save the quotient to the `q' and * the remainder to the `r'. This is equivalent to the q = mp1 / mp2, * r = mp1 mod mp2 (or mp1 = mp2 * q + r). If the `q' or `r' is NULL * then the operation is omitted. * ***/ void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_div_2exp * * SYNOPSIS * * void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Divide the `mp1' with 2 ** `exp' and save the result to `dst'. * This is equivalent to dst = mp1 / (2 ^ exp). * ***/ void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp); /****f* silcmath/SilcMPAPI/silc_mp_div_2exp_qr * * SYNOPSIS * * void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1, * SilcUInt32 exp); * * DESCRIPTION * * Divide the `mp1' with 2 ** `exp' and save the quotient to `q' and * the remainder to `r'. This is equivalent to q = mp1 / (2 ^ exp), * r = mp1 mod (2 ^ exp). If the `q' or `r' is NULL then the operation * is omitted. * ***/ void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1, SilcUInt32 exp); /****f* silcmath/SilcMPAPI/silc_mp_mod * * SYNOPSIS * * void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Mathematical MOD function. Produces the remainder of `mp1' and `mp2' * and saves the result to `dst'. This is equivalent to dst = mp1 mod mp2. * The same result can also be get with silc_mp_div_qr as that function * returns the remainder as well. * ***/ void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_mod_ui * * SYNOPSIS * * void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); * * DESCRIPTION * * Mathematical MOD function. Produces the remainder of `mp1' and * unsigned word `ui' and saves the result to `dst'. This is equivalent * to dst = mp1 mod ui. * ***/ void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_mod_2exp * * SYNOPSIS * * void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Computes the remainder of `mp1' with 2 ** `exp' and saves the * result to `dst'. This is equivalent to dst = mp1 mod (2 ^ exp). * The same result can also be get with silc_mp_div_2exp_qr as that * function returns the remainder as well. * ***/ void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_pow * * SYNOPSIS * * void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp); * * DESCRIPTION * * Compute `mp1' ** `exp' and save the result to `dst'. This is * equivalent to dst = mp1 ^ exp. * ***/ void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp); /****f* silcmath/SilcMPAPI/silc_mp_pow_ui * * SYNOPSIS * * void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp); * * DESCRIPTION * * Compute `mp1' ** `exp' and save the result to `dst'. This is * equivalent to dst = mp1 ^ exp. * ***/ void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp); /****f* silcmath/SilcMPAPI/silc_mp_pow_mod * * SYNOPSIS * * void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp, * SilcMPInt *mod); * * DESCRIPTION * * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'. * This is equivalent to dst = (mp1 ^ exp) mod mod. * ***/ void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp, SilcMPInt *mod); /****f* silcmath/SilcMPAPI/silc_mp_pow_mod_ui * * SYNOPSIS * * void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp, * SilcMPInt *mod); * * DESCRIPTION * * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'. * This is equivalent to dst = (mp1 ^ exp) mod mod. * ***/ void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, SilcUInt32 exp, SilcMPInt *mod); /****f* silcmath/SilcMPAPI/silc_mp_modinv * * SYNOPSIS * * void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n); * * DESCRIPTION * * Find multiplicative inverse using Euclid's extended algorithm. * Computes inverse such that a * inv mod n = 1, where 0 < a < n. * Algorithm goes like this: * * g(0) = n v(0) = 0 * g(1) = a v(1) = 1 * * y = g(i-1) / g(i) * g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i) * v(i+1) = v(i-1) - y * v(i) * * do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n, * is added to inverse making it positive again. (Sometimes the algorithm * has a variable u defined too and it behaves just like v, except that * initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is * not needed by the algorithm so it does not have to be included.) * ***/ void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n); /****f* silcmath/SilcMPAPI/silc_mp_gcd * * SYNOPSIS * * void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Calculate the greatest common divisor of the integers `mp1' and `mp2' * and save the result to `dst'. * ***/ void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_gcdext * * SYNOPSIS * * void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t, * SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Calculate the extended greatest common divisor `g', `s' and `t' such * that g = mp1 * s + mp2 * + t. * ***/ void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_cmp * * SYNOPSIS * * int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Compare `mp1' and `mp2'. Returns posivite, zero, or negative * if `mp1' > `mp2', `mp1' == `mp2', or `mp1' < `mp2', respectively. * ***/ int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_cmp_si * * SYNOPSIS * * int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si); * * DESCRIPTION * * Compare `mp1' and single word `si'. Returns posivite, zero, or negative * if `mp1' > `si', `mp1' == `si', or `mp1' < `si', respectively. * ***/ int silc_mp_cmp_si(SilcMPInt *mp1, SilcInt32 si); /****f* silcmath/SilcMPAPI/silc_mp_cmp_ui * * SYNOPSIS * * int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui); * * DESCRIPTION * * Compare `mp1' and unsigned word `ui'. Returns posivite, zero, or * negative if `mp1' > `ui', `mp1' == `ui', or `mp1' < `ui', * respectively. * ***/ int silc_mp_cmp_ui(SilcMPInt *mp1, SilcUInt32 ui); /****f* silcmath/SilcMPAPI/silc_mp_mp2bin * * SYNOPSIS * * unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len, * SilcUInt32 *ret_len); * * DESCRIPTION * * Encodes MP integer into binary data. Returns allocated data that * must be free'd by the caller. If `len' is provided the destination * buffer is allocated that large. If zero then the size is approximated. * ***/ unsigned char *silc_mp_mp2bin(SilcMPInt *val, SilcUInt32 len, SilcUInt32 *ret_len); /****f* silcmath/SilcMPAPI/silc_mp_mp2bin_noalloc * * SYNOPSIS * * void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst, * SilcUInt32 dst_len); * * DESCRIPTION * * Same as silc_mp_mp2bin but does not allocate any memory. The * encoded data is returned into `dst' and it's length to the `ret_len'. * ***/ void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst, SilcUInt32 dst_len); /****f* silcmath/SilcMPAPI/silc_mp_bin2mp * * SYNOPSIS * * void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len, * SilcMPInt *ret); * * DESCRIPTION * * Decodes binary data into MP integer. The integer sent as argument * must be initialized. * ***/ void silc_mp_bin2mp(unsigned char *data, SilcUInt32 len, SilcMPInt *ret); /****f* silcmath/SilcMPAPI/silc_mp_abs * * SYNOPSIS * * void silc_mp_abs(SilcMPInt *src, SilcMPInt *dst); * * DESCRIPTION * * Assign the absolute value of `src' to `dst'. * ***/ void silc_mp_abs(SilcMPInt *dst, SilcMPInt *src); /****f* silcmath/SilcMPAPI/silc_mp_neg * * SYNOPSIS * * void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src); * * DESCRIPTION * * Negate `src' and save the result to `dst'. * ***/ void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src); /****f* silcmath/SilcMPAPI/silc_mp_and * * SYNOPSIS * * void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Logical and operator. The result is saved to `dst'. * ***/ void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_or * * SYNOPSIS * * void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Logical inclusive OR operator. The result is saved to `dst'. * ***/ void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); /****f* silcmath/SilcMPAPI/silc_mp_xor * * SYNOPSIS * * void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); * * DESCRIPTION * * Logical exclusive OR operator. The result is saved to `dst'. * ***/ void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2); #endif