/** * \file bignum.h */ #ifndef _BIGNUM_H #define _BIGNUM_H #ifdef __cplusplus extern "C" { #endif #define ERR_MPI_INVALID_CHARACTER 0x0002 #define ERR_MPI_INVALID_PARAMETER 0x0004 #define ERR_MPI_BUFFER_TOO_SMALL 0x0006 #define ERR_MPI_NEGATIVE_VALUE 0x0008 #define ERR_MPI_DIVISION_BY_ZERO 0x000A #define ERR_MPI_NOT_INVERTIBLE 0x000C #define ERR_MPI_IS_COMPOSITE 0x000E #define CHK(fc) if( ( ret = fc ) != 0 ) goto cleanup /* * Define the base limb type */ #if defined(HAVE_INT16) /* 8086 */ typedef unsigned int t_int; typedef unsigned long t_dbl; #else typedef unsigned long t_int; typedef unsigned long long t_dbl; #endif #define ciL (int) sizeof(t_int) /* chars in limb */ #define biL (ciL << 3) /* bits in limb */ #define biH (ciL << 2) /* half limb size */ /** * \brief MPI structure */ typedef struct { int s; /*!< integer sign */ int n; /*!< total # of limbs */ // t_int *p; /*!< pointer to limbs */ unsigned long long *p; /*!< pointer to limbs */ } mpi; /** * \brief Initialize one or more mpi */ void mpi_init( mpi *X, ... ); /** * \brief Unallocate one or more mpi */ void mpi_free( mpi *X, ... ); /** * \brief Enlarge X to the specified # of limbs * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_grow( mpi *X, int nblimbs ); /** * \brief Copy the contents of Y into X * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_copy( mpi *X, mpi *Y ); /** * \brief Swap the contents of X and Y */ void mpi_swap( mpi *X, mpi *Y ); /** * \brief Set value from integer * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_lset( mpi *X, int z ); /** * \brief Set value from string * * \param X destination mpi * \param s string to read the value from * \param radix numeric base of "s" * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_INVALID_PARAMETER if the radix is invalid * ERR_MPI_INVALID_CHARACTER if a non-digit is found */ int mpi_read( mpi *X, char *s, int radix ); /** * \brief Print the value of X into fout * * \param name string printed before the value * \param X mpi to be printed * \param radix chosen numeric base * \param fout output file stream * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_INVALID_PARAMETER if the radix is invalid */ int mpi_showf( char *name, mpi *X, int radix, FILE *fout ); /** * \brief Print the value of X on the console * * \param name string printed before the value * \param X mpi to be printed * \param radix chosen numeric base * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_INVALID_PARAMETER if the radix is invalid */ int mpi_show( char *name, mpi *X, int radix ); /** * \brief Import an unsigned value from binary data * * \param X destination mpi * \param buf input buffer * \param buflen size of buffer * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_import( mpi *X, unsigned char *buf, int buflen ); /** * \brief Export an unsigned value into binary data * * \param X source mpi * \param buf output buffer * \param buflen size of buffer * * \return 0 if successful, * ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough * * \note Call this function with *buflen = 0 to obtain the * required buffer size in *buflen. */ int mpi_export( mpi *X, unsigned char *buf, int *buflen ); /** * \brief Return actual size in bits (without leading 0s) */ int mpi_size( mpi *X ); /** * \brief Return number of least significant bits */ int mpi_lsb( mpi *X ); /** * \brief Left-shift: X <<= count * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_shift_l( mpi *X, int count ); /** * \brief Right-shift: X >>= count * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_shift_r( mpi *X, int count ); /** * \brief Compare unsigned values * * \return 1 if |X| is greater than |Y|, * -1 if |X| is lesser than |Y| or * 0 if |X| is equal to |Y| */ int mpi_cmp_abs( mpi *X, mpi *Y ); /** * \brief Compare signed values * * \return 1 if X is greater than Y, * -1 if X is lesser than Y or * 0 if X is equal to Y */ int mpi_cmp_mpi( mpi *X, mpi *Y ); /** * \brief Compare signed values * * \return 1 if X is greater than z, * -1 if X is lesser than z or * 0 if X is equal to z */ int mpi_cmp_int( mpi *X, int z ); /** * \brief Unsigned addition: X = |A| + |B| * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_add_abs( mpi *X, mpi *A, mpi *B ); /** * \brief Unsigned substraction: X = |A| - |B| * * \return 0 if successful, * ERR_MPI_NEGATIVE_VALUE if B is greater than A */ int mpi_sub_abs( mpi *X, mpi *A, mpi *B ); /** * \brief Signed addition: X = A + B * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_add_mpi( mpi *X, mpi *A, mpi *B ); /** * \brief Signed substraction: X = A - B * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_sub_mpi( mpi *X, mpi *A, mpi *B ); /** * \brief Signed addition: X = A + b * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_add_int( mpi *X, mpi *A, int b ); /** * \brief Signed substraction: X = A - b * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_sub_int( mpi *X, mpi *A, int b ); /** * \brief Baseline multiplication: X = A * B * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_mul_mpi( mpi *X, mpi *A, mpi *B ); /** * \brief Baseline multiplication: X = A * b * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_mul_int( mpi *X, mpi *A, t_int b ); /** * \brief Division by mpi: A = Q * B + R * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_DIVISION_BY_ZERO if B == 0 * * \note Either Q or R can be NULL. */ int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B ); /** * \brief Division by int: A = Q * b + R * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_DIVISION_BY_ZERO if b == 0 * * \note Either Q or R can be NULL. */ int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b ); /** * \brief Modulo: R = A mod B * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_DIVISION_BY_ZERO if B == 0 */ int mpi_mod_mpi( mpi *R, mpi *A, mpi *B ); /** * \brief Modulo: r = A mod b * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_DIVISION_BY_ZERO if b == 0, */ int mpi_mod_int( t_int *r, mpi *A, int b ); /** * \brief Sliding-window exponentiation: X = A^E mod N * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_INVALID_PARAMETER if N is negative or even * * \note _RR is used to avoid re-computing R*R mod N across * multiple calls, which speeds up things a bit. It can * be set to NULL if the extra performance is unneeded. */ int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR ); /** * \brief Greatest common divisor: G = gcd(A, B) * * \return 0 if successful, * 1 if memory allocation failed */ int mpi_gcd( mpi *G, mpi *A, mpi *B ); /** * \brief Modular inverse: X = A^-1 mod N * * \return 0 if successful, * 1 if memory allocation failed, * ERR_MPI_INVALID_PARAMETER if N is negative or nil * ERR_MPI_NOT_INVERTIBLE if A has no inverse mod N */ int mpi_inv_mod( mpi *X, mpi *A, mpi *N ); /** * \brief Miller-Rabin primality test * * \return 0 if successful (probably prime), * 1 if memory allocation failed, * ERR_MPI_IS_COMPOSITE if X is not prime */ int mpi_is_prime( mpi *X ); /** * \brief Prime number generation * * \param X destination mpi * \param nbits required size of X in bits * \param dh_flag set this to 1 if (X-1)/2 must also be prime * (needed for Diffie-Hellman) * \param rng_f points to the RNG function * \param rng_d points to the RNG data * * \return 0 if successful (probably prime), * 1 if memory allocation failed, * ERR_MPI_INVALID_PARAMETER if nbits is < 3 */ int mpi_gen_prime( mpi *X, int nbits, int dh_flag, int (*rng_f)(void *), void *rng_d ); /** * \brief Checkup routine * * \return 0 if successful, or 1 if the test failed */ int mpi_self_test( void ); #ifdef __cplusplus } #endif #endif /* bignum.h */