git.zerfleddert.de Git - proxmark3-svn/blob - common/mbedtls/bignum.h

   1 /**
   2  * \file bignum.h
   3  *
   4  * \brief Multi-precision integer library
   5  */
   6 /*
   7  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
   8  *  SPDX-License-Identifier: GPL-2.0
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License along
  21  *  with this program; if not, write to the Free Software Foundation, Inc.,
  22  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  23  *
  24  *  This file is part of mbed TLS (https://tls.mbed.org)
  25  */
  26 #ifndef MBEDTLS_BIGNUM_H
  27 #define MBEDTLS_BIGNUM_H
  28
  29 #if !defined(MBEDTLS_CONFIG_FILE)
  30 #include "config.h"
  31 #else
  32 #include MBEDTLS_CONFIG_FILE
  33 #endif
  34
  35 #include <stddef.h>
  36 #include <stdint.h>
  37
  38 #if defined(MBEDTLS_FS_IO)
  39 #include <stdio.h>
  40 #endif
  41
  42 #define MBEDTLS_ERR_MPI_FILE_IO_ERROR                     -0x0002  /**< An error occurred while reading from or writing to a file. */
  43 #define MBEDTLS_ERR_MPI_BAD_INPUT_DATA                    -0x0004  /**< Bad input parameters to function. */
  44 #define MBEDTLS_ERR_MPI_INVALID_CHARACTER                 -0x0006  /**< There is an invalid character in the digit string. */
  45 #define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008  /**< The buffer is too small to write to. */
  46 #define MBEDTLS_ERR_MPI_NEGATIVE_VALUE                    -0x000A  /**< The input arguments are negative or result in illegal output. */
  47 #define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO                  -0x000C  /**< The input argument for division is zero, which is not allowed. */
  48 #define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE                    -0x000E  /**< The input arguments are not acceptable. */
  49 #define MBEDTLS_ERR_MPI_ALLOC_FAILED                      -0x0010  /**< Memory allocation failed. */
  50
  51 #define MBEDTLS_MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
  52
  53 /*
  54  * Maximum size MPIs are allowed to grow to in number of limbs.
  55  */
  56 #define MBEDTLS_MPI_MAX_LIMBS                             10000
  57
  58 #if !defined(MBEDTLS_MPI_WINDOW_SIZE)
  59 /*
  60  * Maximum window size used for modular exponentiation. Default: 6
  61  * Minimum value: 1. Maximum value: 6.
  62  *
  63  * Result is an array of ( 2 << MBEDTLS_MPI_WINDOW_SIZE ) MPIs used
  64  * for the sliding window calculation. (So 64 by default)
  65  *
  66  * Reduction in size, reduces speed.
  67  */
  68 #define MBEDTLS_MPI_WINDOW_SIZE                           6        /**< Maximum windows size used. */
  69 #endif /* !MBEDTLS_MPI_WINDOW_SIZE */
  70
  71 #if !defined(MBEDTLS_MPI_MAX_SIZE)
  72 /*
  73  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
  74  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
  75  *
  76  * Note: Calculations can temporarily result in larger MPIs. So the number
  77  * of limbs required (MBEDTLS_MPI_MAX_LIMBS) is higher.
  78  */
  79 #define MBEDTLS_MPI_MAX_SIZE                              1024     /**< Maximum number of bytes for usable MPIs. */
  80 #endif /* !MBEDTLS_MPI_MAX_SIZE */
  81
  82 #define MBEDTLS_MPI_MAX_BITS                              ( 8 * MBEDTLS_MPI_MAX_SIZE )    /**< Maximum number of bits for usable MPIs. */
  83
  84 /*
  85  * When reading from files with mbedtls_mpi_read_file() and writing to files with
  86  * mbedtls_mpi_write_file() the buffer should have space
  87  * for a (short) label, the MPI (in the provided radix), the newline
  88  * characters and the '\0'.
  89  *
  90  * By default we assume at least a 10 char label, a minimum radix of 10
  91  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
  92  * Autosized at compile time for at least a 10 char label, a minimum radix
  93  * of 10 (decimal) for a number of MBEDTLS_MPI_MAX_BITS size.
  94  *
  95  * This used to be statically sized to 1250 for a maximum of 4096 bit
  96  * numbers (1234 decimal chars).
  97  *
  98  * Calculate using the formula:
  99  *  MBEDTLS_MPI_RW_BUFFER_SIZE = ceil(MBEDTLS_MPI_MAX_BITS / ln(10) * ln(2)) +
 100  *                                LabelSize + 6
 101  */
 102 #define MBEDTLS_MPI_MAX_BITS_SCALE100          ( 100 * MBEDTLS_MPI_MAX_BITS )
 103 #define MBEDTLS_LN_2_DIV_LN_10_SCALE100                 332
 104 #define MBEDTLS_MPI_RW_BUFFER_SIZE             ( ((MBEDTLS_MPI_MAX_BITS_SCALE100 + MBEDTLS_LN_2_DIV_LN_10_SCALE100 - 1) / MBEDTLS_LN_2_DIV_LN_10_SCALE100) + 10 + 6 )
 105
 106 /*
 107  * Define the base integer type, architecture-wise.
 108  *
 109  * 32 or 64-bit integer types can be forced regardless of the underlying
 110  * architecture by defining MBEDTLS_HAVE_INT32 or MBEDTLS_HAVE_INT64
 111  * respectively and undefining MBEDTLS_HAVE_ASM.
 112  *
 113  * Double-width integers (e.g. 128-bit in 64-bit architectures) can be
 114  * disabled by defining MBEDTLS_NO_UDBL_DIVISION.
 115  */
 116 #if !defined(MBEDTLS_HAVE_INT32)
 117     #if defined(_MSC_VER) && defined(_M_AMD64)
 118         /* Always choose 64-bit when using MSC */
 119         #if !defined(MBEDTLS_HAVE_INT64)
 120             #define MBEDTLS_HAVE_INT64
 121         #endif /* !MBEDTLS_HAVE_INT64 */
 122         typedef  int64_t mbedtls_mpi_sint;
 123         typedef uint64_t mbedtls_mpi_uint;
 124     #elif defined(__GNUC__) && (                         \
 125         defined(__amd64__) || defined(__x86_64__)     || \
 126         defined(__ppc64__) || defined(__powerpc64__)  || \
 127         defined(__ia64__)  || defined(__alpha__)      || \
 128         ( defined(__sparc__) && defined(__arch64__) ) || \
 129         defined(__s390x__) || defined(__mips64) )
 130         #if !defined(MBEDTLS_HAVE_INT64)
 131             #define MBEDTLS_HAVE_INT64
 132         #endif /* MBEDTLS_HAVE_INT64 */
 133         typedef  int64_t mbedtls_mpi_sint;
 134         typedef uint64_t mbedtls_mpi_uint;
 135         #if !defined(MBEDTLS_NO_UDBL_DIVISION)
 136             /* mbedtls_t_udbl defined as 128-bit unsigned int */
 137             typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI)));
 138             #define MBEDTLS_HAVE_UDBL
 139         #endif /* !MBEDTLS_NO_UDBL_DIVISION */
 140     #elif defined(__ARMCC_VERSION) && defined(__aarch64__)
 141         /*
 142          * __ARMCC_VERSION is defined for both armcc and armclang and
 143          * __aarch64__ is only defined by armclang when compiling 64-bit code
 144          */
 145         #if !defined(MBEDTLS_HAVE_INT64)
 146             #define MBEDTLS_HAVE_INT64
 147         #endif /* !MBEDTLS_HAVE_INT64 */
 148         typedef  int64_t mbedtls_mpi_sint;
 149         typedef uint64_t mbedtls_mpi_uint;
 150         #if !defined(MBEDTLS_NO_UDBL_DIVISION)
 151             /* mbedtls_t_udbl defined as 128-bit unsigned int */
 152             typedef __uint128_t mbedtls_t_udbl;
 153             #define MBEDTLS_HAVE_UDBL
 154         #endif /* !MBEDTLS_NO_UDBL_DIVISION */
 155     #elif defined(MBEDTLS_HAVE_INT64)
 156         /* Force 64-bit integers with unknown compiler */
 157         typedef  int64_t mbedtls_mpi_sint;
 158         typedef uint64_t mbedtls_mpi_uint;
 159     #endif
 160 #endif /* !MBEDTLS_HAVE_INT32 */
 161
 162 #if !defined(MBEDTLS_HAVE_INT64)
 163     /* Default to 32-bit compilation */
 164     #if !defined(MBEDTLS_HAVE_INT32)
 165         #define MBEDTLS_HAVE_INT32
 166     #endif /* !MBEDTLS_HAVE_INT32 */
 167     typedef  int32_t mbedtls_mpi_sint;
 168     typedef uint32_t mbedtls_mpi_uint;
 169     #if !defined(MBEDTLS_NO_UDBL_DIVISION)
 170         typedef uint64_t mbedtls_t_udbl;
 171         #define MBEDTLS_HAVE_UDBL
 172     #endif /* !MBEDTLS_NO_UDBL_DIVISION */
 173 #endif /* !MBEDTLS_HAVE_INT64 */
 174
 175 #ifdef __cplusplus
 176 extern "C" {
 177 #endif
 178
 179 /**
 180  * \brief          MPI structure
 181  */
 182 typedef struct mbedtls_mpi
 183 {
 184     int s;              /*!<  integer sign      */
 185     size_t n;           /*!<  total # of limbs  */
 186     mbedtls_mpi_uint *p;          /*!<  pointer to limbs  */
 187 }
 188 mbedtls_mpi;
 189
 190 /**
 191  * \brief           Initialize one MPI (make internal references valid)
 192  *                  This just makes it ready to be set or freed,
 193  *                  but does not define a value for the MPI.
 194  *
 195  * \param X         One MPI to initialize.
 196  */
 197 void mbedtls_mpi_init( mbedtls_mpi *X );
 198
 199 /**
 200  * \brief          Unallocate one MPI
 201  *
 202  * \param X        One MPI to unallocate.
 203  */
 204 void mbedtls_mpi_free( mbedtls_mpi *X );
 205
 206 /**
 207  * \brief          Enlarge to the specified number of limbs
 208  *
 209  *                 This function does nothing if the MPI is already large enough.
 210  *
 211  * \param X        MPI to grow
 212  * \param nblimbs  The target number of limbs
 213  *
 214  * \return         0 if successful,
 215  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 216  */
 217 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs );
 218
 219 /**
 220  * \brief          Resize down, keeping at least the specified number of limbs
 221  *
 222  *                 If \c X is smaller than \c nblimbs, it is resized up
 223  *                 instead.
 224  *
 225  * \param X        MPI to shrink
 226  * \param nblimbs  The minimum number of limbs to keep
 227  *
 228  * \return         0 if successful,
 229  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 230  *                 (this can only happen when resizing up).
 231  */
 232 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs );
 233
 234 /**
 235  * \brief          Copy the contents of Y into X
 236  *
 237  * \param X        Destination MPI. It is enlarged if necessary.
 238  * \param Y        Source MPI.
 239  *
 240  * \return         0 if successful,
 241  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 242  */
 243 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y );
 244
 245 /**
 246  * \brief          Swap the contents of X and Y
 247  *
 248  * \param X        First MPI value
 249  * \param Y        Second MPI value
 250  */
 251 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y );
 252
 253 /**
 254  * \brief          Safe conditional assignement X = Y if assign is 1
 255  *
 256  * \param X        MPI to conditionally assign to
 257  * \param Y        Value to be assigned
 258  * \param assign   1: perform the assignment, 0: keep X's original value
 259  *
 260  * \return         0 if successful,
 261  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 262  *
 263  * \note           This function is equivalent to
 264  *                      if( assign ) mbedtls_mpi_copy( X, Y );
 265  *                 except that it avoids leaking any information about whether
 266  *                 the assignment was done or not (the above code may leak
 267  *                 information through branch prediction and/or memory access
 268  *                 patterns analysis).
 269  */
 270 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign );
 271
 272 /**
 273  * \brief          Safe conditional swap X <-> Y if swap is 1
 274  *
 275  * \param X        First mbedtls_mpi value
 276  * \param Y        Second mbedtls_mpi value
 277  * \param assign   1: perform the swap, 0: keep X and Y's original values
 278  *
 279  * \return         0 if successful,
 280  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 281  *
 282  * \note           This function is equivalent to
 283  *                      if( assign ) mbedtls_mpi_swap( X, Y );
 284  *                 except that it avoids leaking any information about whether
 285  *                 the assignment was done or not (the above code may leak
 286  *                 information through branch prediction and/or memory access
 287  *                 patterns analysis).
 288  */
 289 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign );
 290
 291 /**
 292  * \brief          Set value from integer
 293  *
 294  * \param X        MPI to set
 295  * \param z        Value to use
 296  *
 297  * \return         0 if successful,
 298  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 299  */
 300 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z );
 301
 302 /**
 303  * \brief          Get a specific bit from X
 304  *
 305  * \param X        MPI to use
 306  * \param pos      Zero-based index of the bit in X
 307  *
 308  * \return         Either a 0 or a 1
 309  */
 310 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos );
 311
 312 /**
 313  * \brief          Set a bit of X to a specific value of 0 or 1
 314  *
 315  * \note           Will grow X if necessary to set a bit to 1 in a not yet
 316  *                 existing limb. Will not grow if bit should be set to 0
 317  *
 318  * \param X        MPI to use
 319  * \param pos      Zero-based index of the bit in X
 320  * \param val      The value to set the bit to (0 or 1)
 321  *
 322  * \return         0 if successful,
 323  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 324  *                 MBEDTLS_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1
 325  */
 326 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val );
 327
 328 /**
 329  * \brief          Return the number of zero-bits before the least significant
 330  *                 '1' bit
 331  *
 332  * Note: Thus also the zero-based index of the least significant '1' bit
 333  *
 334  * \param X        MPI to use
 335  */
 336 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X );
 337
 338 /**
 339  * \brief          Return the number of bits up to and including the most
 340  *                 significant '1' bit'
 341  *
 342  * Note: Thus also the one-based index of the most significant '1' bit
 343  *
 344  * \param X        MPI to use
 345  */
 346 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X );
 347
 348 /**
 349  * \brief          Return the total size in bytes
 350  *
 351  * \param X        MPI to use
 352  */
 353 size_t mbedtls_mpi_size( const mbedtls_mpi *X );
 354
 355 /**
 356  * \brief          Import from an ASCII string
 357  *
 358  * \param X        Destination MPI
 359  * \param radix    Input numeric base
 360  * \param s        Null-terminated string buffer
 361  *
 362  * \return         0 if successful, or a MBEDTLS_ERR_MPI_XXX error code
 363  */
 364 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s );
 365
 366 /**
 367  * \brief          Export into an ASCII string
 368  *
 369  * \param X        Source MPI
 370  * \param radix    Output numeric base
 371  * \param buf      Buffer to write the string to
 372  * \param buflen   Length of buf
 373  * \param olen     Length of the string written, including final NUL byte
 374  *
 375  * \return         0 if successful, or a MBEDTLS_ERR_MPI_XXX error code.
 376  *                 *olen is always updated to reflect the amount
 377  *                 of data that has (or would have) been written.
 378  *
 379  * \note           Call this function with buflen = 0 to obtain the
 380  *                 minimum required buffer size in *olen.
 381  */
 382 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
 383                               char *buf, size_t buflen, size_t *olen );
 384
 385 #if defined(MBEDTLS_FS_IO)
 386 /**
 387  * \brief          Read MPI from a line in an opened file
 388  *
 389  * \param X        Destination MPI
 390  * \param radix    Input numeric base
 391  * \param fin      Input file handle
 392  *
 393  * \return         0 if successful, MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if
 394  *                 the file read buffer is too small or a
 395  *                 MBEDTLS_ERR_MPI_XXX error code
 396  *
 397  * \note           On success, this function advances the file stream
 398  *                 to the end of the current line or to EOF.
 399  *
 400  *                 The function returns 0 on an empty line.
 401  *
 402  *                 Leading whitespaces are ignored, as is a
 403  *                 '0x' prefix for radix 16.
 404  *
 405  */
 406 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin );
 407
 408 /**
 409  * \brief          Write X into an opened file, or stdout if fout is NULL
 410  *
 411  * \param p        Prefix, can be NULL
 412  * \param X        Source MPI
 413  * \param radix    Output numeric base
 414  * \param fout     Output file handle (can be NULL)
 415  *
 416  * \return         0 if successful, or a MBEDTLS_ERR_MPI_XXX error code
 417  *
 418  * \note           Set fout == NULL to print X on the console.
 419  */
 420 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout );
 421 #endif /* MBEDTLS_FS_IO */
 422
 423 /**
 424  * \brief          Import X from unsigned binary data, big endian
 425  *
 426  * \param X        Destination MPI
 427  * \param buf      Input buffer
 428  * \param buflen   Input buffer size
 429  *
 430  * \return         0 if successful,
 431  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 432  */
 433 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen );
 434
 435 /**
 436  * \brief          Export X into unsigned binary data, big endian.
 437  *                 Always fills the whole buffer, which will start with zeros
 438  *                 if the number is smaller.
 439  *
 440  * \param X        Source MPI
 441  * \param buf      Output buffer
 442  * \param buflen   Output buffer size
 443  *
 444  * \return         0 if successful,
 445  *                 MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
 446  */
 447 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen );
 448
 449 /**
 450  * \brief          Left-shift: X <<= count
 451  *
 452  * \param X        MPI to shift
 453  * \param count    Amount to shift
 454  *
 455  * \return         0 if successful,
 456  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 457  */
 458 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count );
 459
 460 /**
 461  * \brief          Right-shift: X >>= count
 462  *
 463  * \param X        MPI to shift
 464  * \param count    Amount to shift
 465  *
 466  * \return         0 if successful,
 467  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 468  */
 469 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count );
 470
 471 /**
 472  * \brief          Compare unsigned values
 473  *
 474  * \param X        Left-hand MPI
 475  * \param Y        Right-hand MPI
 476  *
 477  * \return         1 if |X| is greater than |Y|,
 478  *                -1 if |X| is lesser  than |Y| or
 479  *                 0 if |X| is equal to |Y|
 480  */
 481 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y );
 482
 483 /**
 484  * \brief          Compare signed values
 485  *
 486  * \param X        Left-hand MPI
 487  * \param Y        Right-hand MPI
 488  *
 489  * \return         1 if X is greater than Y,
 490  *                -1 if X is lesser  than Y or
 491  *                 0 if X is equal to Y
 492  */
 493 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y );
 494
 495 /**
 496  * \brief          Compare signed values
 497  *
 498  * \param X        Left-hand MPI
 499  * \param z        The integer value to compare to
 500  *
 501  * \return         1 if X is greater than z,
 502  *                -1 if X is lesser  than z or
 503  *                 0 if X is equal to z
 504  */
 505 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z );
 506
 507 /**
 508  * \brief          Unsigned addition: X = |A| + |B|
 509  *
 510  * \param X        Destination MPI
 511  * \param A        Left-hand MPI
 512  * \param B        Right-hand MPI
 513  *
 514  * \return         0 if successful,
 515  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 516  */
 517 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
 518
 519 /**
 520  * \brief          Unsigned subtraction: X = |A| - |B|
 521  *
 522  * \param X        Destination MPI
 523  * \param A        Left-hand MPI
 524  * \param B        Right-hand MPI
 525  *
 526  * \return         0 if successful,
 527  *                 MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B is greater than A
 528  */
 529 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
 530
 531 /**
 532  * \brief          Signed addition: X = A + B
 533  *
 534  * \param X        Destination MPI
 535  * \param A        Left-hand MPI
 536  * \param B        Right-hand MPI
 537  *
 538  * \return         0 if successful,
 539  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 540  */
 541 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
 542
 543 /**
 544  * \brief          Signed subtraction: X = A - B
 545  *
 546  * \param X        Destination MPI
 547  * \param A        Left-hand MPI
 548  * \param B        Right-hand MPI
 549  *
 550  * \return         0 if successful,
 551  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 552  */
 553 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
 554
 555 /**
 556  * \brief          Signed addition: X = A + b
 557  *
 558  * \param X        Destination MPI
 559  * \param A        Left-hand MPI
 560  * \param b        The integer value to add
 561  *
 562  * \return         0 if successful,
 563  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 564  */
 565 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b );
 566
 567 /**
 568  * \brief          Signed subtraction: X = A - b
 569  *
 570  * \param X        Destination MPI
 571  * \param A        Left-hand MPI
 572  * \param b        The integer value to subtract
 573  *
 574  * \return         0 if successful,
 575  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 576  */
 577 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b );
 578
 579 /**
 580  * \brief          Baseline multiplication: X = A * B
 581  *
 582  * \param X        Destination MPI
 583  * \param A        Left-hand MPI
 584  * \param B        Right-hand MPI
 585  *
 586  * \return         0 if successful,
 587  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 588  */
 589 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
 590
 591 /**
 592  * \brief          Baseline multiplication: X = A * b
 593  *
 594  * \param X        Destination MPI
 595  * \param A        Left-hand MPI
 596  * \param b        The unsigned integer value to multiply with
 597  *
 598  * \note           b is unsigned
 599  *
 600  * \return         0 if successful,
 601  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 602  */
 603 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b );
 604
 605 /**
 606  * \brief          Division by mbedtls_mpi: A = Q * B + R
 607  *
 608  * \param Q        Destination MPI for the quotient
 609  * \param R        Destination MPI for the rest value
 610  * \param A        Left-hand MPI
 611  * \param B        Right-hand MPI
 612  *
 613  * \return         0 if successful,
 614  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 615  *                 MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0
 616  *
 617  * \note           Either Q or R can be NULL.
 618  */
 619 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B );
 620
 621 /**
 622  * \brief          Division by int: A = Q * b + R
 623  *
 624  * \param Q        Destination MPI for the quotient
 625  * \param R        Destination MPI for the rest value
 626  * \param A        Left-hand MPI
 627  * \param b        Integer to divide by
 628  *
 629  * \return         0 if successful,
 630  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 631  *                 MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0
 632  *
 633  * \note           Either Q or R can be NULL.
 634  */
 635 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b );
 636
 637 /**
 638  * \brief          Modulo: R = A mod B
 639  *
 640  * \param R        Destination MPI for the rest value
 641  * \param A        Left-hand MPI
 642  * \param B        Right-hand MPI
 643  *
 644  * \return         0 if successful,
 645  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 646  *                 MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0,
 647  *                 MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B < 0
 648  */
 649 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B );
 650
 651 /**
 652  * \brief          Modulo: r = A mod b
 653  *
 654  * \param r        Destination mbedtls_mpi_uint
 655  * \param A        Left-hand MPI
 656  * \param b        Integer to divide by
 657  *
 658  * \return         0 if successful,
 659  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 660  *                 MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0,
 661  *                 MBEDTLS_ERR_MPI_NEGATIVE_VALUE if b < 0
 662  */
 663 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b );
 664
 665 /**
 666  * \brief          Sliding-window exponentiation: X = A^E mod N
 667  *
 668  * \param X        Destination MPI
 669  * \param A        Left-hand MPI
 670  * \param E        Exponent MPI
 671  * \param N        Modular MPI
 672  * \param _RR      Speed-up MPI used for recalculations
 673  *
 674  * \return         0 if successful,
 675  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 676  *                 MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is negative or even or
 677  *                 if E is negative
 678  *
 679  * \note           _RR is used to avoid re-computing R*R mod N across
 680  *                 multiple calls, which speeds up things a bit. It can
 681  *                 be set to NULL if the extra performance is unneeded.
 682  */
 683 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR );
 684
 685 /**
 686  * \brief          Fill an MPI X with size bytes of random
 687  *
 688  * \param X        Destination MPI
 689  * \param size     Size in bytes
 690  * \param f_rng    RNG function
 691  * \param p_rng    RNG parameter
 692  *
 693  * \return         0 if successful,
 694  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 695  *
 696  * \note           The bytes obtained from the PRNG are interpreted
 697  *                 as a big-endian representation of an MPI; this can
 698  *                 be relevant in applications like deterministic ECDSA.
 699  */
 700 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
 701                      int (*f_rng)(void *, unsigned char *, size_t),
 702                      void *p_rng );
 703
 704 /**
 705  * \brief          Greatest common divisor: G = gcd(A, B)
 706  *
 707  * \param G        Destination MPI
 708  * \param A        Left-hand MPI
 709  * \param B        Right-hand MPI
 710  *
 711  * \return         0 if successful,
 712  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
 713  */
 714 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B );
 715
 716 /**
 717  * \brief          Modular inverse: X = A^-1 mod N
 718  *
 719  * \param X        Destination MPI
 720  * \param A        Left-hand MPI
 721  * \param N        Right-hand MPI
 722  *
 723  * \return         0 if successful,
 724  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 725  *                 MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is <= 1,
 726                    MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N.
 727  */
 728 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N );
 729
 730 /**
 731  * \brief          Miller-Rabin primality test
 732  *
 733  * \param X        MPI to check
 734  * \param f_rng    RNG function
 735  * \param p_rng    RNG parameter
 736  *
 737  * \return         0 if successful (probably prime),
 738  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 739  *                 MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime
 740  */
 741 int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
 742                   int (*f_rng)(void *, unsigned char *, size_t),
 743                   void *p_rng );
 744
 745 /**
 746  * \brief          Prime number generation
 747  *
 748  * \param X        Destination MPI
 749  * \param nbits    Required size of X in bits
 750  *                 ( 3 <= nbits <= MBEDTLS_MPI_MAX_BITS )
 751  * \param dh_flag  If 1, then (X-1)/2 will be prime too
 752  * \param f_rng    RNG function
 753  * \param p_rng    RNG parameter
 754  *
 755  * \return         0 if successful (probably prime),
 756  *                 MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
 757  *                 MBEDTLS_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
 758  */
 759 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
 760                    int (*f_rng)(void *, unsigned char *, size_t),
 761                    void *p_rng );
 762
 763 /**
 764  * \brief          Checkup routine
 765  *
 766  * \return         0 if successful, or 1 if the test failed
 767  */
 768 int mbedtls_mpi_self_test( int verbose );
 769
 770 #ifdef __cplusplus
 771 }
 772 #endif
 773
 774 #endif /* bignum.h */