Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /**
  2.  * \file bignum.h
  3.  *
  4.  * \brief  Multi-precision integer library
  5.  *
  6.  *  Copyright (C) 2006-2010, Brainspark B.V.
  7.  *
  8.  *  This file is part of PolarSSL (http://www.polarssl.org)
  9.  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
  10.  *
  11.  *  All rights reserved.
  12.  *
  13.  *  This program is free software; you can redistribute it and/or modify
  14.  *  it under the terms of the GNU General Public License as published by
  15.  *  the Free Software Foundation; either version 2 of the License, or
  16.  *  (at your option) any later version.
  17.  *
  18.  *  This program is distributed in the hope that it will be useful,
  19.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21.  *  GNU General Public License for more details.
  22.  *
  23.  *  You should have received a copy of the GNU General Public License along
  24.  *  with this program; if not, write to the Free Software Foundation, Inc.,
  25.  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  26.  */
  27. #ifndef POLARSSL_BIGNUM_H
  28. #define POLARSSL_BIGNUM_H
  29.  
  30. #include <stdio.h>
  31. #include <string.h>
  32.  
  33. #include "config.h"
  34.  
  35. #ifdef _MSC_VER
  36. #include <basetsd.h>
  37. #if (_MSC_VER <= 1200)
  38. typedef   signed short  int16_t;
  39. typedef unsigned short uint16_t;
  40. #else
  41. typedef  INT16  int16_t;
  42. typedef UINT16 uint16_t;
  43. #endif
  44. typedef  INT32  int32_t;
  45. typedef  INT64  int64_t;
  46. typedef UINT32 uint32_t;
  47. typedef UINT64 uint64_t;
  48. #else
  49. #include <inttypes.h>
  50. #endif
  51.  
  52. #define POLARSSL_ERR_MPI_FILE_IO_ERROR                     -0x0002  /**< An error occurred while reading from or writing to a file. */
  53. #define POLARSSL_ERR_MPI_BAD_INPUT_DATA                    -0x0004  /**< Bad input parameters to function. */
  54. #define POLARSSL_ERR_MPI_INVALID_CHARACTER                 -0x0006  /**< There is an invalid character in the digit string. */
  55. #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008  /**< The buffer is too small to write to. */
  56. #define POLARSSL_ERR_MPI_NEGATIVE_VALUE                    -0x000A  /**< The input arguments are negative or result in illegal output. */
  57. #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO                  -0x000C  /**< The input argument for division is zero, which is not allowed. */
  58. #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    -0x000E  /**< The input arguments are not acceptable. */
  59. #define POLARSSL_ERR_MPI_MALLOC_FAILED                     -0x0010  /**< Memory allocation failed. */
  60.  
  61. #define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
  62.  
  63. /*
  64.  * Maximum size MPIs are allowed to grow to in number of limbs.
  65.  */
  66. #define POLARSSL_MPI_MAX_LIMBS                             10000
  67.  
  68. /*
  69.  * Maximum window size used for modular exponentiation. Default: 6
  70.  * Minimum value: 1. Maximum value: 6.
  71.  *
  72.  * Result is an array of ( 2 << POLARSSL_MPI_WINDOW_SIZE ) MPIs used
  73.  * for the sliding window calculation. (So 64 by default)
  74.  *
  75.  * Reduction in size, reduces speed.
  76.  */
  77. #define POLARSSL_MPI_WINDOW_SIZE                           6        /**< Maximum windows size used. */
  78.  
  79. /*
  80.  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
  81.  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
  82.  *
  83.  * Note: Calculations can results temporarily in larger MPIs. So the number
  84.  * of limbs required (POLARSSL_MPI_MAX_LIMBS) is higher.
  85.  */
  86. #define POLARSSL_MPI_MAX_SIZE                              512      /**< Maximum number of bytes for usable MPIs. */
  87. #define POLARSSL_MPI_MAX_BITS                              ( 8 * POLARSSL_MPI_MAX_SIZE )    /**< Maximum number of bits for usable MPIs. */
  88.  
  89. /*
  90.  * When reading from files with mpi_read_file() and writing to files with
  91.  * mpi_write_file() the buffer should have space
  92.  * for a (short) label, the MPI (in the provided radix), the newline
  93.  * characters and the '\0'.
  94.  *
  95.  * By default we assume at least a 10 char label, a minimum radix of 10
  96.  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
  97.  * Autosized at compile time for at least a 10 char label, a minimum radix
  98.  * of 10 (decimal) for a number of POLARSSL_MPI_MAX_BITS size.
  99.  *
  100.  * This used to be statically sized to 1250 for a maximum of 4096 bit
  101.  * numbers (1234 decimal chars).
  102.  *
  103.  * Calculate using the formula:
  104.  *  POLARSSL_MPI_RW_BUFFER_SIZE = ceil(POLARSSL_MPI_MAX_BITS / ln(10) * ln(2)) +
  105.  *                                LabelSize + 6
  106.  */
  107. #define POLARSSL_MPI_MAX_BITS_SCALE100          ( 100 * POLARSSL_MPI_MAX_BITS )
  108. #define LN_2_DIV_LN_10_SCALE100                 332
  109. #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 )
  110.  
  111. /*
  112.  * Define the base integer type, architecture-wise
  113.  */
  114. #if defined(POLARSSL_HAVE_INT8)
  115. typedef   signed char  t_sint;
  116. typedef unsigned char  t_uint;
  117. typedef uint16_t       t_udbl;
  118. #define POLARSSL_HAVE_UDBL
  119. #else
  120. #if defined(POLARSSL_HAVE_INT16)
  121. typedef  int16_t t_sint;
  122. typedef uint16_t t_uint;
  123. typedef uint32_t t_udbl;
  124. #define POLARSSL_HAVE_UDBL
  125. #else
  126.   #if ( defined(_MSC_VER) && defined(_M_AMD64) )
  127.     typedef  int64_t t_sint;
  128.     typedef uint64_t t_uint;
  129.   #else
  130.     #if ( defined(__GNUC__) && (                          \
  131.           defined(__amd64__) || defined(__x86_64__)    || \
  132.           defined(__ppc64__) || defined(__powerpc64__) || \
  133.           defined(__ia64__)  || defined(__alpha__)     || \
  134.           (defined(__sparc__) && defined(__arch64__))  || \
  135.           defined(__s390x__) ) )
  136.        typedef  int64_t t_sint;
  137.        typedef uint64_t t_uint;
  138.        typedef unsigned int t_udbl __attribute__((mode(TI)));
  139.        #define POLARSSL_HAVE_UDBL
  140.     #else
  141.        typedef  int32_t t_sint;
  142.        typedef uint32_t t_uint;
  143.        #if ( defined(_MSC_VER) && defined(_M_IX86) )
  144.          typedef uint64_t t_udbl;
  145.          #define POLARSSL_HAVE_UDBL
  146.        #else
  147.          #if defined( POLARSSL_HAVE_LONGLONG )
  148.            typedef unsigned long long t_udbl;
  149.            #define POLARSSL_HAVE_UDBL
  150.          #endif
  151.        #endif
  152.     #endif
  153.   #endif
  154. #endif /* POLARSSL_HAVE_INT16 */
  155. #endif /* POLARSSL_HAVE_INT8  */
  156.  
  157. /**
  158.  * \brief          MPI structure
  159.  */
  160. typedef struct
  161. {
  162.     int s;              /*!<  integer sign      */
  163.     size_t n;           /*!<  total # of limbs  */
  164.     t_uint *p;          /*!<  pointer to limbs  */
  165. }
  166. mpi;
  167.  
  168. #ifdef __cplusplus
  169. extern "C" {
  170. #endif
  171.  
  172. /**
  173.  * \brief           Initialize one MPI
  174.  *
  175.  * \param X         One MPI to initialize.
  176.  */
  177. void mpi_init( mpi *X );
  178.  
  179. /**
  180.  * \brief          Unallocate one MPI
  181.  *
  182.  * \param X        One MPI to unallocate.
  183.  */
  184. void mpi_free( mpi *X );
  185.  
  186. /**
  187.  * \brief          Enlarge to the specified number of limbs
  188.  *
  189.  * \param X        MPI to grow
  190.  * \param nblimbs  The target number of limbs
  191.  *
  192.  * \return         0 if successful,
  193.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  194.  */
  195. int mpi_grow( mpi *X, size_t nblimbs );
  196.  
  197. /**
  198.  * \brief          Copy the contents of Y into X
  199.  *
  200.  * \param X        Destination MPI
  201.  * \param Y        Source MPI
  202.  *
  203.  * \return         0 if successful,
  204.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  205.  */
  206. int mpi_copy( mpi *X, const mpi *Y );
  207.  
  208. /**
  209.  * \brief          Swap the contents of X and Y
  210.  *
  211.  * \param X        First MPI value
  212.  * \param Y        Second MPI value
  213.  */
  214. void mpi_swap( mpi *X, mpi *Y );
  215.  
  216. /**
  217.  * \brief          Set value from integer
  218.  *
  219.  * \param X        MPI to set
  220.  * \param z        Value to use
  221.  *
  222.  * \return         0 if successful,
  223.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  224.  */
  225. int mpi_lset( mpi *X, t_sint z );
  226.  
  227. /**
  228.  * \brief          Get a specific bit from X
  229.  *
  230.  * \param X        MPI to use
  231.  * \param pos      Zero-based index of the bit in X
  232.  *
  233.  * \return         Either a 0 or a 1
  234.  */
  235. int mpi_get_bit( const mpi *X, size_t pos );
  236.  
  237. /**
  238.  * \brief          Set a bit of X to a specific value of 0 or 1
  239.  *
  240.  * \note           Will grow X if necessary to set a bit to 1 in a not yet
  241.  *                 existing limb. Will not grow if bit should be set to 0
  242.  *
  243.  * \param X        MPI to use
  244.  * \param pos      Zero-based index of the bit in X
  245.  * \param val      The value to set the bit to (0 or 1)
  246.  *
  247.  * \return         0 if successful,
  248.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  249.  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1
  250.  */
  251. int mpi_set_bit( mpi *X, size_t pos, unsigned char val );
  252.  
  253. /**
  254.  * \brief          Return the number of zero-bits before the least significant
  255.  *                 '1' bit
  256.  *
  257.  * Note: Thus also the zero-based index of the least significant '1' bit
  258.  *
  259.  * \param X        MPI to use
  260.  */
  261. size_t mpi_lsb( const mpi *X );
  262.  
  263. /**
  264.  * \brief          Return the number of bits up to and including the most
  265.  *                 significant '1' bit'
  266.  *
  267.  * Note: Thus also the one-based index of the most significant '1' bit
  268.  *
  269.  * \param X        MPI to use
  270.  */
  271. size_t mpi_msb( const mpi *X );
  272.  
  273. /**
  274.  * \brief          Return the total size in bytes
  275.  *
  276.  * \param X        MPI to use
  277.  */
  278. size_t mpi_size( const mpi *X );
  279.  
  280. /**
  281.  * \brief          Import from an ASCII string
  282.  *
  283.  * \param X        Destination MPI
  284.  * \param radix    Input numeric base
  285.  * \param s        Null-terminated string buffer
  286.  *
  287.  * \return         0 if successful, or a POLARSSL_ERR_MPI_XXX error code
  288.  */
  289. int mpi_read_string( mpi *X, int radix, const char *s );
  290.  
  291. /**
  292.  * \brief          Export into an ASCII string
  293.  *
  294.  * \param X        Source MPI
  295.  * \param radix    Output numeric base
  296.  * \param s        String buffer
  297.  * \param slen     String buffer size
  298.  *
  299.  * \return         0 if successful, or a POLARSSL_ERR_MPI_XXX error code.
  300.  *                 *slen is always updated to reflect the amount
  301.  *                 of data that has (or would have) been written.
  302.  *
  303.  * \note           Call this function with *slen = 0 to obtain the
  304.  *                 minimum required buffer size in *slen.
  305.  */
  306. int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen );
  307.  
  308. #if defined(POLARSSL_FS_IO)
  309. /**
  310.  * \brief          Read X from an opened file
  311.  *
  312.  * \param X        Destination MPI
  313.  * \param radix    Input numeric base
  314.  * \param fin      Input file handle
  315.  *
  316.  * \return         0 if successful, POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if
  317.  *                 the file read buffer is too small or a
  318.  *                 POLARSSL_ERR_MPI_XXX error code
  319.  */
  320. int mpi_read_file( mpi *X, int radix, FILE *fin );
  321.  
  322. /**
  323.  * \brief          Write X into an opened file, or stdout if fout is NULL
  324.  *
  325.  * \param p        Prefix, can be NULL
  326.  * \param X        Source MPI
  327.  * \param radix    Output numeric base
  328.  * \param fout     Output file handle (can be NULL)
  329.  *
  330.  * \return         0 if successful, or a POLARSSL_ERR_MPI_XXX error code
  331.  *
  332.  * \note           Set fout == NULL to print X on the console.
  333.  */
  334. int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
  335. #endif /* POLARSSL_FS_IO */
  336.  
  337. /**
  338.  * \brief          Import X from unsigned binary data, big endian
  339.  *
  340.  * \param X        Destination MPI
  341.  * \param buf      Input buffer
  342.  * \param buflen   Input buffer size
  343.  *
  344.  * \return         0 if successful,
  345.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  346.  */
  347. int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen );
  348.  
  349. /**
  350.  * \brief          Export X into unsigned binary data, big endian
  351.  *
  352.  * \param X        Source MPI
  353.  * \param buf      Output buffer
  354.  * \param buflen   Output buffer size
  355.  *
  356.  * \return         0 if successful,
  357.  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
  358.  */
  359. int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen );
  360.  
  361. /**
  362.  * \brief          Left-shift: X <<= count
  363.  *
  364.  * \param X        MPI to shift
  365.  * \param count    Amount to shift
  366.  *
  367.  * \return         0 if successful,
  368.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  369.  */
  370. int mpi_shift_l( mpi *X, size_t count );
  371.  
  372. /**
  373.  * \brief          Right-shift: X >>= count
  374.  *
  375.  * \param X        MPI to shift
  376.  * \param count    Amount to shift
  377.  *
  378.  * \return         0 if successful,
  379.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  380.  */
  381. int mpi_shift_r( mpi *X, size_t count );
  382.  
  383. /**
  384.  * \brief          Compare unsigned values
  385.  *
  386.  * \param X        Left-hand MPI
  387.  * \param Y        Right-hand MPI
  388.  *
  389.  * \return         1 if |X| is greater than |Y|,
  390.  *                -1 if |X| is lesser  than |Y| or
  391.  *                 0 if |X| is equal to |Y|
  392.  */
  393. int mpi_cmp_abs( const mpi *X, const mpi *Y );
  394.  
  395. /**
  396.  * \brief          Compare signed values
  397.  *
  398.  * \param X        Left-hand MPI
  399.  * \param Y        Right-hand MPI
  400.  *
  401.  * \return         1 if X is greater than Y,
  402.  *                -1 if X is lesser  than Y or
  403.  *                 0 if X is equal to Y
  404.  */
  405. int mpi_cmp_mpi( const mpi *X, const mpi *Y );
  406.  
  407. /**
  408.  * \brief          Compare signed values
  409.  *
  410.  * \param X        Left-hand MPI
  411.  * \param z        The integer value to compare to
  412.  *
  413.  * \return         1 if X is greater than z,
  414.  *                -1 if X is lesser  than z or
  415.  *                 0 if X is equal to z
  416.  */
  417. int mpi_cmp_int( const mpi *X, t_sint z );
  418.  
  419. /**
  420.  * \brief          Unsigned addition: X = |A| + |B|
  421.  *
  422.  * \param X        Destination MPI
  423.  * \param A        Left-hand MPI
  424.  * \param B        Right-hand MPI
  425.  *
  426.  * \return         0 if successful,
  427.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  428.  */
  429. int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
  430.  
  431. /**
  432.  * \brief          Unsigned substraction: X = |A| - |B|
  433.  *
  434.  * \param X        Destination MPI
  435.  * \param A        Left-hand MPI
  436.  * \param B        Right-hand MPI
  437.  *
  438.  * \return         0 if successful,
  439.  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
  440.  */
  441. int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
  442.  
  443. /**
  444.  * \brief          Signed addition: X = A + B
  445.  *
  446.  * \param X        Destination MPI
  447.  * \param A        Left-hand MPI
  448.  * \param B        Right-hand MPI
  449.  *
  450.  * \return         0 if successful,
  451.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  452.  */
  453. int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
  454.  
  455. /**
  456.  * \brief          Signed substraction: X = A - B
  457.  *
  458.  * \param X        Destination MPI
  459.  * \param A        Left-hand MPI
  460.  * \param B        Right-hand MPI
  461.  *
  462.  * \return         0 if successful,
  463.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  464.  */
  465. int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
  466.  
  467. /**
  468.  * \brief          Signed addition: X = A + b
  469.  *
  470.  * \param X        Destination MPI
  471.  * \param A        Left-hand MPI
  472.  * \param b        The integer value to add
  473.  *
  474.  * \return         0 if successful,
  475.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  476.  */
  477. int mpi_add_int( mpi *X, const mpi *A, t_sint b );
  478.  
  479. /**
  480.  * \brief          Signed substraction: X = A - b
  481.  *
  482.  * \param X        Destination MPI
  483.  * \param A        Left-hand MPI
  484.  * \param b        The integer value to subtract
  485.  *
  486.  * \return         0 if successful,
  487.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  488.  */
  489. int mpi_sub_int( mpi *X, const mpi *A, t_sint b );
  490.  
  491. /**
  492.  * \brief          Baseline multiplication: X = A * B
  493.  *
  494.  * \param X        Destination MPI
  495.  * \param A        Left-hand MPI
  496.  * \param B        Right-hand MPI
  497.  *
  498.  * \return         0 if successful,
  499.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  500.  */
  501. int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
  502.  
  503. /**
  504.  * \brief          Baseline multiplication: X = A * b
  505.  *                 Note: b is an unsigned integer type, thus
  506.  *                 Negative values of b are ignored.
  507.  *
  508.  * \param X        Destination MPI
  509.  * \param A        Left-hand MPI
  510.  * \param b        The integer value to multiply with
  511.  *
  512.  * \return         0 if successful,
  513.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  514.  */
  515. int mpi_mul_int( mpi *X, const mpi *A, t_sint b );
  516.  
  517. /**
  518.  * \brief          Division by mpi: A = Q * B + R
  519.  *
  520.  * \param Q        Destination MPI for the quotient
  521.  * \param R        Destination MPI for the rest value
  522.  * \param A        Left-hand MPI
  523.  * \param B        Right-hand MPI
  524.  *
  525.  * \return         0 if successful,
  526.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  527.  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
  528.  *
  529.  * \note           Either Q or R can be NULL.
  530.  */
  531. int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
  532.  
  533. /**
  534.  * \brief          Division by int: A = Q * b + R
  535.  *
  536.  * \param Q        Destination MPI for the quotient
  537.  * \param R        Destination MPI for the rest value
  538.  * \param A        Left-hand MPI
  539.  * \param b        Integer to divide by
  540.  *
  541.  * \return         0 if successful,
  542.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  543.  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
  544.  *
  545.  * \note           Either Q or R can be NULL.
  546.  */
  547. int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b );
  548.  
  549. /**
  550.  * \brief          Modulo: R = A mod B
  551.  *
  552.  * \param R        Destination MPI for the rest value
  553.  * \param A        Left-hand MPI
  554.  * \param B        Right-hand MPI
  555.  *
  556.  * \return         0 if successful,
  557.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  558.  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0,
  559.  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0
  560.  */
  561. int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
  562.  
  563. /**
  564.  * \brief          Modulo: r = A mod b
  565.  *
  566.  * \param r        Destination t_uint
  567.  * \param A        Left-hand MPI
  568.  * \param b        Integer to divide by
  569.  *
  570.  * \return         0 if successful,
  571.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  572.  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0,
  573.  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0
  574.  */
  575. int mpi_mod_int( t_uint *r, const mpi *A, t_sint b );
  576.  
  577. /**
  578.  * \brief          Sliding-window exponentiation: X = A^E mod N
  579.  *
  580.  * \param X        Destination MPI
  581.  * \param A        Left-hand MPI
  582.  * \param E        Exponent MPI
  583.  * \param N        Modular MPI
  584.  * \param _RR      Speed-up MPI used for recalculations
  585.  *
  586.  * \return         0 if successful,
  587.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  588.  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even or if
  589.  *                 E is negative
  590.  *
  591.  * \note           _RR is used to avoid re-computing R*R mod N across
  592.  *                 multiple calls, which speeds up things a bit. It can
  593.  *                 be set to NULL if the extra performance is unneeded.
  594.  */
  595. int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
  596.  
  597. /**
  598.  * \brief          Fill an MPI X with size bytes of random
  599.  *
  600.  * \param X        Destination MPI
  601.  * \param size     Size in bytes
  602.  * \param f_rng    RNG function
  603.  * \param p_rng    RNG parameter
  604.  *
  605.  * \return         0 if successful,
  606.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  607.  */
  608. int mpi_fill_random( mpi *X, size_t size,
  609.                      int (*f_rng)(void *, unsigned char *, size_t),
  610.                      void *p_rng );
  611.  
  612. /**
  613.  * \brief          Greatest common divisor: G = gcd(A, B)
  614.  *
  615.  * \param G        Destination MPI
  616.  * \param A        Left-hand MPI
  617.  * \param B        Right-hand MPI
  618.  *
  619.  * \return         0 if successful,
  620.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
  621.  */
  622. int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
  623.  
  624. /**
  625.  * \brief          Modular inverse: X = A^-1 mod N
  626.  *
  627.  * \param X        Destination MPI
  628.  * \param A        Left-hand MPI
  629.  * \param N        Right-hand MPI
  630.  *
  631.  * \return         0 if successful,
  632.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  633.  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
  634.                    POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
  635.  */
  636. int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
  637.  
  638. /**
  639.  * \brief          Miller-Rabin primality test
  640.  *
  641.  * \param X        MPI to check
  642.  * \param f_rng    RNG function
  643.  * \param p_rng    RNG parameter
  644.  *
  645.  * \return         0 if successful (probably prime),
  646.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  647.  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
  648.  */
  649. int mpi_is_prime( mpi *X,
  650.                   int (*f_rng)(void *, unsigned char *, size_t),
  651.                   void *p_rng );
  652.  
  653. /**
  654.  * \brief          Prime number generation
  655.  *
  656.  * \param X        Destination MPI
  657.  * \param nbits    Required size of X in bits ( 3 <= nbits <= POLARSSL_MPI_MAX_BITS )
  658.  * \param dh_flag  If 1, then (X-1)/2 will be prime too
  659.  * \param f_rng    RNG function
  660.  * \param p_rng    RNG parameter
  661.  *
  662.  * \return         0 if successful (probably prime),
  663.  *                 POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
  664.  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
  665.  */
  666. int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
  667.                    int (*f_rng)(void *, unsigned char *, size_t),
  668.                    void *p_rng );
  669.  
  670. /**
  671.  * \brief          Checkup routine
  672.  *
  673.  * \return         0 if successful, or 1 if the test failed
  674.  */
  675. int mpi_self_test( int verbose );
  676.  
  677. #ifdef __cplusplus
  678. }
  679. #endif
  680.  
  681. #endif /* bignum.h */
  682.