cvs.zerfleddert.de Git - proxmark3-svn/blob - common/polarssl/bignum.h

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