bignum.h

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