bignum.h

00001 /**
00002  * \file bignum.h
00003  *
00004  * \brief  Multi-precision integer library
00005  *
00006  *  Copyright (C) 2006-2014, Brainspark B.V.
00007  *
00008  *  This file is part of PolarSSL (http://www.polarssl.org)
00009  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
00010  *
00011  *  All rights reserved.
00012  *
00013  *  This program is free software; you can redistribute it and/or modify
00014  *  it under the terms of the GNU General Public License as published by
00015  *  the Free Software Foundation; either version 2 of the License, or
00016  *  (at your option) any later version.
00017  *
00018  *  This program is distributed in the hope that it will be useful,
00019  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00020  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00021  *  GNU General Public License for more details.
00022  *
00023  *  You should have received a copy of the GNU General Public License along
00024  *  with this program; if not, write to the Free Software Foundation, Inc.,
00025  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00026  */
00027 #ifndef POLARSSL_BIGNUM_H
00028 #define POLARSSL_BIGNUM_H
00029 
00030 #include <stdio.h>
00031 #include <string.h>
00032 
00033 #if !defined(POLARSSL_CONFIG_FILE)
00034 #include "config.h"
00035 #else
00036 #include POLARSSL_CONFIG_FILE
00037 #endif
00038 
00039 #if defined(_MSC_VER) && !defined(EFIX64) && !defined(EFI32)
00040 #include <basetsd.h>
00041 #if (_MSC_VER <= 1200)
00042 typedef   signed short  int16_t;
00043 typedef unsigned short uint16_t;
00044 #else
00045 typedef  INT16  int16_t;
00046 typedef UINT16 uint16_t;
00047 #endif
00048 typedef  INT32  int32_t;
00049 typedef  INT64  int64_t;
00050 typedef UINT32 uint32_t;
00051 typedef UINT64 uint64_t;
00052 #else
00053 #include <inttypes.h>
00054 #endif /* _MSC_VER && !EFIX64 && !EFI32 */
00055 
00056 #define POLARSSL_ERR_MPI_FILE_IO_ERROR                     -0x0002  /**< An error occurred while reading from or writing to a file. */
00057 #define POLARSSL_ERR_MPI_BAD_INPUT_DATA                    -0x0004  /**< Bad input parameters to function. */
00058 #define POLARSSL_ERR_MPI_INVALID_CHARACTER                 -0x0006  /**< There is an invalid character in the digit string. */
00059 #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008  /**< The buffer is too small to write to. */
00060 #define POLARSSL_ERR_MPI_NEGATIVE_VALUE                    -0x000A  /**< The input arguments are negative or result in illegal output. */
00061 #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO                  -0x000C  /**< The input argument for division is zero, which is not allowed. */
00062 #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    -0x000E  /**< The input arguments are not acceptable. */
00063 #define POLARSSL_ERR_MPI_MALLOC_FAILED                     -0x0010  /**< Memory allocation failed. */
00064 
00065 #define MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
00066 
00067 /*
00068  * Maximum size MPIs are allowed to grow to in number of limbs.
00069  */
00070 #define POLARSSL_MPI_MAX_LIMBS                             10000
00071 
00072 #if !defined(POLARSSL_CONFIG_OPTIONS)
00073 /*
00074  * Maximum window size used for modular exponentiation. Default: 6
00075  * Minimum value: 1. Maximum value: 6.
00076  *
00077  * Result is an array of ( 2 << POLARSSL_MPI_WINDOW_SIZE ) MPIs used
00078  * for the sliding window calculation. (So 64 by default)
00079  *
00080  * Reduction in size, reduces speed.
00081  */
00082 #define POLARSSL_MPI_WINDOW_SIZE                           6        /**< Maximum windows size used. */
00083 
00084 /*
00085  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
00086  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
00087  *
00088  * Note: Calculations can results temporarily in larger MPIs. So the number
00089  * of limbs required (POLARSSL_MPI_MAX_LIMBS) is higher.
00090  */
00091 #define POLARSSL_MPI_MAX_SIZE                              512      /**< Maximum number of bytes for usable MPIs. */
00092 
00093 #endif /* !POLARSSL_CONFIG_OPTIONS */
00094 
00095 #define POLARSSL_MPI_MAX_BITS                              ( 8 * POLARSSL_MPI_MAX_SIZE )    /**< Maximum number of bits for usable MPIs. */
00096 
00097 /*
00098  * When reading from files with mpi_read_file() and writing to files with
00099  * mpi_write_file() the buffer should have space
00100  * for a (short) label, the MPI (in the provided radix), the newline
00101  * characters and the '\0'.
00102  *
00103  * By default we assume at least a 10 char label, a minimum radix of 10
00104  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
00105  * Autosized at compile time for at least a 10 char label, a minimum radix
00106  * of 10 (decimal) for a number of POLARSSL_MPI_MAX_BITS size.
00107  *
00108  * This used to be statically sized to 1250 for a maximum of 4096 bit
00109  * numbers (1234 decimal chars).
00110  *
00111  * Calculate using the formula:
00112  *  POLARSSL_MPI_RW_BUFFER_SIZE = ceil(POLARSSL_MPI_MAX_BITS / ln(10) * ln(2)) +
00113  *                                LabelSize + 6
00114  */
00115 #define POLARSSL_MPI_MAX_BITS_SCALE100          ( 100 * POLARSSL_MPI_MAX_BITS )
00116 #define LN_2_DIV_LN_10_SCALE100                 332
00117 #define POLARSSL_MPI_RW_BUFFER_SIZE             ( ((POLARSSL_MPI_MAX_BITS_SCALE100 + LN_2_DIV_LN_10_SCALE100 - 1) / LN_2_DIV_LN_10_SCALE100) + 10 + 6 )
00118 
00119 /*
00120  * Define the base integer type, architecture-wise
00121  */
00122 #if defined(POLARSSL_HAVE_INT8)
00123 typedef   signed char  t_sint;
00124 typedef unsigned char  t_uint;
00125 typedef uint16_t       t_udbl;
00126 #define POLARSSL_HAVE_UDBL
00127 #else
00128 #if defined(POLARSSL_HAVE_INT16)
00129 typedef  int16_t t_sint;
00130 typedef uint16_t t_uint;
00131 typedef uint32_t t_udbl;
00132 #define POLARSSL_HAVE_UDBL
00133 #else
00134   /*
00135    * 32-bit integers can be forced on 64-bit arches (eg. for testing purposes)
00136    * by defining POLARSSL_HAVE_INT32 and undefining POARSSL_HAVE_ASM
00137    */
00138   #if ( ! defined(POLARSSL_HAVE_INT32) && \
00139           defined(_MSC_VER) && defined(_M_AMD64) )
00140     #define POLARSSL_HAVE_INT64
00141     typedef  int64_t t_sint;
00142     typedef uint64_t t_uint;
00143   #else
00144     #if ( ! defined(POLARSSL_HAVE_INT32) &&               \
00145           defined(__GNUC__) && (                          \
00146           defined(__amd64__) || defined(__x86_64__)    || \
00147           defined(__ppc64__) || defined(__powerpc64__) || \
00148           defined(__ia64__)  || defined(__alpha__)     || \
00149           (defined(__sparc__) && defined(__arch64__))  || \
00150           defined(__s390x__) ) )
00151        #define POLARSSL_HAVE_INT64
00152        typedef  int64_t t_sint;
00153        typedef uint64_t t_uint;
00154        typedef unsigned int t_udbl __attribute__((mode(TI)));
00155        #define POLARSSL_HAVE_UDBL
00156     #else
00157        #define POLARSSL_HAVE_INT32
00158        typedef  int32_t t_sint;
00159        typedef uint32_t t_uint;
00160        #if ( defined(_MSC_VER) && defined(_M_IX86) )
00161          typedef uint64_t t_udbl;
00162          #define POLARSSL_HAVE_UDBL
00163        #else
00164          #if defined( POLARSSL_HAVE_LONGLONG )
00165            typedef unsigned long long t_udbl;
00166            #define POLARSSL_HAVE_UDBL
00167          #endif
00168        #endif
00169     #endif
00170   #endif
00171 #endif /* POLARSSL_HAVE_INT16 */
00172 #endif /* POLARSSL_HAVE_INT8  */
00173 
00174 #ifdef __cplusplus
00175 extern "C" {
00176 #endif
00177 
00178 /**
00179  * \brief          MPI structure
00180  */
00181 typedef struct
00182 {
00183     int s ;              /*!<  integer sign      */
00184     size_t n ;           /*!<  total # of limbs  */
00185     t_uint *p ;          /*!<  pointer to limbs  */
00186 }
00187 mpi;
00188 
00189 /**
00190  * \brief           Initialize one MPI
00191  *
00192  * \param X         One MPI to initialize.
00193  */
00194 void mpi_init( mpi *X );
00195 
00196 /**
00197  * \brief          Unallocate one MPI
00198  *
00199  * \param X        One MPI to unallocate.
00200  */
00201 void mpi_free( mpi *X );
00202 
00203 /**
00204  * \brief          Enlarge to the specified number of limbs
00205  *
00206  * \param X        MPI to grow
00207  * \param nblimbs  The target number of limbs
00208  *
00209  * \return         0 if successful,
00210  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00211  */
00212 int mpi_grow( mpi *X, size_t nblimbs );
00213 
00214 /**
00215  * \brief          Resize down, keeping at least the specified number of limbs
00216  *
00217  * \param X        MPI to shrink
00218  * \param nblimbs  The minimum number of limbs to keep
00219  *
00220  * \return         0 if successful,
00221  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00222  */
00223 int mpi_shrink( mpi *X, size_t nblimbs );
00224 
00225 /**
00226  * \brief          Copy the contents of Y into X
00227  *
00228  * \param X        Destination MPI
00229  * \param Y        Source MPI
00230  *
00231  * \return         0 if successful,
00232  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00233  */
00234 int mpi_copy( mpi *X, const mpi *Y );
00235 
00236 /**
00237  * \brief          Swap the contents of X and Y
00238  *
00239  * \param X        First MPI value
00240  * \param Y        Second MPI value
00241  */
00242 void mpi_swap( mpi *X, mpi *Y );
00243 
00244 /**
00245  * \brief          Safe conditional assignement X = Y if assign is 1
00246  *
00247  * \param X        MPI to conditionally assign to
00248  * \param Y        Value to be assigned
00249  * \param assign   1: perform the assignment, 0: keep X's original value
00250  *
00251  * \return         0 if successful,
00252  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00253  *
00254  * \note           This function is equivalent to
00255  *                      if( assign ) mpi_copy( X, Y );
00256  *                 except that it avoids leaking any information about whether
00257  *                 the assignment was done or not (the above code may leak
00258  *                 information through branch prediction and/or memory access
00259  *                 patterns analysis).
00260  */
00261 int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign );
00262 
00263 /**
00264  * \brief          Safe conditional swap X <-> Y if swap is 1
00265  *
00266  * \param X        First mpi value
00267  * \param Y        Second mpi value
00268  * \param assign   1: perform the swap, 0: keep X and Y's original values
00269  *
00270  * \return         0 if successful,
00271  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00272  *
00273  * \note           This function is equivalent to
00274  *                      if( assign ) mpi_swap( X, Y );
00275  *                 except that it avoids leaking any information about whether
00276  *                 the assignment was done or not (the above code may leak
00277  *                 information through branch prediction and/or memory access
00278  *                 patterns analysis).
00279  */
00280 int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char assign );
00281 
00282 /**
00283  * \brief          Set value from integer
00284  *
00285  * \param X        MPI to set
00286  * \param z        Value to use
00287  *
00288  * \return         0 if successful,
00289  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00290  */
00291 int mpi_lset( mpi *X, t_sint z );
00292 
00293 /**
00294  * \brief          Get a specific bit from X
00295  *
00296  * \param X        MPI to use
00297  * \param pos      Zero-based index of the bit in X
00298  *
00299  * \return         Either a 0 or a 1
00300  */
00301 int mpi_get_bit( const mpi *X, size_t pos );
00302 
00303 /**
00304  * \brief          Set a bit of X to a specific value of 0 or 1
00305  *
00306  * \note           Will grow X if necessary to set a bit to 1 in a not yet
00307  *                 existing limb. Will not grow if bit should be set to 0
00308  *
00309  * \param X        MPI to use
00310  * \param pos      Zero-based index of the bit in X
00311  * \param val      The value to set the bit to (0 or 1)
00312  *
00313  * \return         0 if successful,
00314  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00315  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1
00316  */
00317 int mpi_set_bit( mpi *X, size_t pos, unsigned char val );
00318 
00319 /**
00320  * \brief          Return the number of zero-bits before the least significant
00321  *                 '1' bit
00322  *
00323  * Note: Thus also the zero-based index of the least significant '1' bit
00324  *
00325  * \param X        MPI to use
00326  */
00327 size_t mpi_lsb( const mpi *X );
00328 
00329 /**
00330  * \brief          Return the number of bits up to and including the most
00331  *                 significant '1' bit'
00332  *
00333  * Note: Thus also the one-based index of the most significant '1' bit
00334  *
00335  * \param X        MPI to use
00336  */
00337 size_t mpi_msb( const mpi *X );
00338 
00339 /**
00340  * \brief          Return the total size in bytes
00341  *
00342  * \param X        MPI to use
00343  */
00344 size_t mpi_size( const mpi *X );
00345 
00346 /**
00347  * \brief          Import from an ASCII string
00348  *
00349  * \param X        Destination MPI
00350  * \param radix    Input numeric base
00351  * \param s        Null-terminated string buffer
00352  *
00353  * \return         0 if successful, or a POLARSSL_ERR_MPI_XXX error code
00354  */
00355 int mpi_read_string( mpi *X, int radix, const char *s );
00356 
00357 /**
00358  * \brief          Export into an ASCII string
00359  *
00360  * \param X        Source MPI
00361  * \param radix    Output numeric base
00362  * \param s        String buffer
00363  * \param slen     String buffer size
00364  *
00365  * \return         0 if successful, or a POLARSSL_ERR_MPI_XXX error code.
00366  *                 *slen is always updated to reflect the amount
00367  *                 of data that has (or would have) been written.
00368  *
00369  * \note           Call this function with *slen = 0 to obtain the
00370  *                 minimum required buffer size in *slen.
00371  */
00372 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen );
00373 
00374 #if defined(POLARSSL_FS_IO)
00375 /**
00376  * \brief          Read X from an opened file
00377  *
00378  * \param X        Destination MPI
00379  * \param radix    Input numeric base
00380  * \param fin      Input file handle
00381  *
00382  * \return         0 if successful, POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if
00383  *                 the file read buffer is too small or a
00384  *                 POLARSSL_ERR_MPI_XXX error code
00385  */
00386 int mpi_read_file( mpi *X, int radix, FILE *fin );
00387 
00388 /**
00389  * \brief          Write X into an opened file, or stdout if fout is NULL
00390  *
00391  * \param p        Prefix, can be NULL
00392  * \param X        Source MPI
00393  * \param radix    Output numeric base
00394  * \param fout     Output file handle (can be NULL)
00395  *
00396  * \return         0 if successful, or a POLARSSL_ERR_MPI_XXX error code
00397  *
00398  * \note           Set fout == NULL to print X on the console.
00399  */
00400 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
00401 #endif /* POLARSSL_FS_IO */
00402 
00403 /**
00404  * \brief          Import X from unsigned binary data, big endian
00405  *
00406  * \param X        Destination MPI
00407  * \param buf      Input buffer
00408  * \param buflen   Input buffer size
00409  *
00410  * \return         0 if successful,
00411  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00412  */
00413 int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen );
00414 
00415 /**
00416  * \brief          Export X into unsigned binary data, big endian
00417  *
00418  * \param X        Source MPI
00419  * \param buf      Output buffer
00420  * \param buflen   Output buffer size
00421  *
00422  * \return         0 if successful,
00423  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
00424  */
00425 int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen );
00426 
00427 /**
00428  * \brief          Left-shift: X <<= count
00429  *
00430  * \param X        MPI to shift
00431  * \param count    Amount to shift
00432  *
00433  * \return         0 if successful,
00434  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00435  */
00436 int mpi_shift_l( mpi *X, size_t count );
00437 
00438 /**
00439  * \brief          Right-shift: X >>= count
00440  *
00441  * \param X        MPI to shift
00442  * \param count    Amount to shift
00443  *
00444  * \return         0 if successful,
00445  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00446  */
00447 int mpi_shift_r( mpi *X, size_t count );
00448 
00449 /**
00450  * \brief          Compare unsigned values
00451  *
00452  * \param X        Left-hand MPI
00453  * \param Y        Right-hand MPI
00454  *
00455  * \return         1 if |X| is greater than |Y|,
00456  *                -1 if |X| is lesser  than |Y| or
00457  *                 0 if |X| is equal to |Y|
00458  */
00459 int mpi_cmp_abs( const mpi *X, const mpi *Y );
00460 
00461 /**
00462  * \brief          Compare signed values
00463  *
00464  * \param X        Left-hand MPI
00465  * \param Y        Right-hand MPI
00466  *
00467  * \return         1 if X is greater than Y,
00468  *                -1 if X is lesser  than Y or
00469  *                 0 if X is equal to Y
00470  */
00471 int mpi_cmp_mpi( const mpi *X, const mpi *Y );
00472 
00473 /**
00474  * \brief          Compare signed values
00475  *
00476  * \param X        Left-hand MPI
00477  * \param z        The integer value to compare to
00478  *
00479  * \return         1 if X is greater than z,
00480  *                -1 if X is lesser  than z or
00481  *                 0 if X is equal to z
00482  */
00483 int mpi_cmp_int( const mpi *X, t_sint z );
00484 
00485 /**
00486  * \brief          Unsigned addition: X = |A| + |B|
00487  *
00488  * \param X        Destination MPI
00489  * \param A        Left-hand MPI
00490  * \param B        Right-hand MPI
00491  *
00492  * \return         0 if successful,
00493  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00494  */
00495 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
00496 
00497 /**
00498  * \brief          Unsigned subtraction: X = |A| - |B|
00499  *
00500  * \param X        Destination MPI
00501  * \param A        Left-hand MPI
00502  * \param B        Right-hand MPI
00503  *
00504  * \return         0 if successful,
00505  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
00506  */
00507 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
00508 
00509 /**
00510  * \brief          Signed addition: X = A + B
00511  *
00512  * \param X        Destination MPI
00513  * \param A        Left-hand MPI
00514  * \param B        Right-hand MPI
00515  *
00516  * \return         0 if successful,
00517  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00518  */
00519 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
00520 
00521 /**
00522  * \brief          Signed subtraction: X = A - B
00523  *
00524  * \param X        Destination MPI
00525  * \param A        Left-hand MPI
00526  * \param B        Right-hand MPI
00527  *
00528  * \return         0 if successful,
00529  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00530  */
00531 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
00532 
00533 /**
00534  * \brief          Signed addition: X = A + b
00535  *
00536  * \param X        Destination MPI
00537  * \param A        Left-hand MPI
00538  * \param b        The integer value to add
00539  *
00540  * \return         0 if successful,
00541  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00542  */
00543 int mpi_add_int( mpi *X, const mpi *A, t_sint b );
00544 
00545 /**
00546  * \brief          Signed subtraction: X = A - b
00547  *
00548  * \param X        Destination MPI
00549  * \param A        Left-hand MPI
00550  * \param b        The integer value to subtract
00551  *
00552  * \return         0 if successful,
00553  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00554  */
00555 int mpi_sub_int( mpi *X, const mpi *A, t_sint b );
00556 
00557 /**
00558  * \brief          Baseline multiplication: X = A * B
00559  *
00560  * \param X        Destination MPI
00561  * \param A        Left-hand MPI
00562  * \param B        Right-hand MPI
00563  *
00564  * \return         0 if successful,
00565  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00566  */
00567 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
00568 
00569 /**
00570  * \brief          Baseline multiplication: X = A * b
00571  *                 Note: despite the functon signature, b is treated as a
00572  *                 t_uint.  Negative values of b are treated as large positive
00573  *                 values.
00574  *
00575  * \param X        Destination MPI
00576  * \param A        Left-hand MPI
00577  * \param b        The integer value to multiply with
00578  *
00579  * \return         0 if successful,
00580  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00581  */
00582 int mpi_mul_int( mpi *X, const mpi *A, t_sint b );
00583 
00584 /**
00585  * \brief          Division by mpi: A = Q * B + R
00586  *
00587  * \param Q        Destination MPI for the quotient
00588  * \param R        Destination MPI for the rest value
00589  * \param A        Left-hand MPI
00590  * \param B        Right-hand MPI
00591  *
00592  * \return         0 if successful,
00593  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00594  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
00595  *
00596  * \note           Either Q or R can be NULL.
00597  */
00598 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
00599 
00600 /**
00601  * \brief          Division by int: A = Q * b + R
00602  *
00603  * \param Q        Destination MPI for the quotient
00604  * \param R        Destination MPI for the rest value
00605  * \param A        Left-hand MPI
00606  * \param b        Integer to divide by
00607  *
00608  * \return         0 if successful,
00609  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00610  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
00611  *
00612  * \note           Either Q or R can be NULL.
00613  */
00614 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b );
00615 
00616 /**
00617  * \brief          Modulo: R = A mod B
00618  *
00619  * \param R        Destination MPI for the rest value
00620  * \param A        Left-hand MPI
00621  * \param B        Right-hand MPI
00622  *
00623  * \return         0 if successful,
00624  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00625  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0,
00626  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0
00627  */
00628 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
00629 
00630 /**
00631  * \brief          Modulo: r = A mod b
00632  *
00633  * \param r        Destination t_uint
00634  * \param A        Left-hand MPI
00635  * \param b        Integer to divide by
00636  *
00637  * \return         0 if successful,
00638  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00639  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0,
00640  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0
00641  */
00642 int mpi_mod_int( t_uint *r, const mpi *A, t_sint b );
00643 
00644 /**
00645  * \brief          Sliding-window exponentiation: X = A^E mod N
00646  *
00647  * \param X        Destination MPI
00648  * \param A        Left-hand MPI
00649  * \param E        Exponent MPI
00650  * \param N        Modular MPI
00651  * \param _RR      Speed-up MPI used for recalculations
00652  *
00653  * \return         0 if successful,
00654  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00655  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even or
00656  *                 if E is negative
00657  *
00658  * \note           _RR is used to avoid re-computing R*R mod N across
00659  *                 multiple calls, which speeds up things a bit. It can
00660  *                 be set to NULL if the extra performance is unneeded.
00661  */
00662 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
00663 
00664 /**
00665  * \brief          Fill an MPI X with size bytes of random
00666  *
00667  * \param X        Destination MPI
00668  * \param size     Size in bytes
00669  * \param f_rng    RNG function
00670  * \param p_rng    RNG parameter
00671  *
00672  * \return         0 if successful,
00673  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00674  */
00675 int mpi_fill_random( mpi *X, size_t size,
00676                      int (*f_rng)(void *, unsigned char *, size_t),
00677                      void *p_rng );
00678 
00679 /**
00680  * \brief          Greatest common divisor: G = gcd(A, B)
00681  *
00682  * \param G        Destination MPI
00683  * \param A        Left-hand MPI
00684  * \param B        Right-hand MPI
00685  *
00686  * \return         0 if successful,
00687  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
00688  */
00689 int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
00690 
00691 /**
00692  * \brief          Modular inverse: X = A^-1 mod N
00693  *
00694  * \param X        Destination MPI
00695  * \param A        Left-hand MPI
00696  * \param N        Right-hand MPI
00697  *
00698  * \return         0 if successful,
00699  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00700  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
00701                    POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
00702  */
00703 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
00704 
00705 /**
00706  * \brief          Miller-Rabin primality test
00707  *
00708  * \param X        MPI to check
00709  * \param f_rng    RNG function
00710  * \param p_rng    RNG parameter
00711  *
00712  * \return         0 if successful (probably prime),
00713  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00714  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
00715  */
00716 int mpi_is_prime( mpi *X,
00717                   int (*f_rng)(void *, unsigned char *, size_t),
00718                   void *p_rng );
00719 
00720 /**
00721  * \brief          Prime number generation
00722  *
00723  * \param X        Destination MPI
00724  * \param nbits    Required size of X in bits
00725  *                 ( 3 <= nbits <= POLARSSL_MPI_MAX_BITS )
00726  * \param dh_flag  If 1, then (X-1)/2 will be prime too
00727  * \param f_rng    RNG function
00728  * \param p_rng    RNG parameter
00729  *
00730  * \return         0 if successful (probably prime),
00731  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
00732  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
00733  */
00734 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
00735                    int (*f_rng)(void *, unsigned char *, size_t),
00736                    void *p_rng );
00737 
00738 /**
00739  * \brief          Checkup routine
00740  *
00741  * \return         0 if successful, or 1 if the test failed
00742  */
00743 int mpi_self_test( int verbose );
00744 
00745 #ifdef __cplusplus
00746 }
00747 #endif
00748 
00749 #endif /* bignum.h */
00750 
00751