# bignum.h File Reference

## Detailed Description

Copyright (C) 2006-2009, Paul Bakker <polarssl_maintainer at polarssl.org> All rights reserved.

Joined copyright on original XySSL code with: Christophe Devine

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

Definition in file bignum.h.

`#include <stdio.h>`

Go to the source code of this file.

## Data Structures
struct | mpi
| MPI structure. More...
## Defines
#define | MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
#define | POLARSSL_ERR_MPI_BAD_INPUT_DATA 0x0004
#define | POLARSSL_ERR_MPI_BUFFER_TOO_SMALL 0x0008
#define | POLARSSL_ERR_MPI_DIVISION_BY_ZERO 0x000C
#define | POLARSSL_ERR_MPI_FILE_IO_ERROR 0x0002
#define | POLARSSL_ERR_MPI_INVALID_CHARACTER 0x0006
#define | POLARSSL_ERR_MPI_NEGATIVE_VALUE 0x000A
#define | POLARSSL_ERR_MPI_NOT_ACCEPTABLE 0x000E
## Typedefs
typedef unsigned long | t_int
## Functions
int | mpi_add_abs (mpi *X, mpi *A, mpi *B)
| Unsigned addition: X = |A| + |B|.
int | mpi_add_int (mpi *X, mpi *A, int b)
| Signed addition: X = A + b.
int | mpi_add_mpi (mpi *X, mpi *A, mpi *B)
| Signed addition: X = A + B.
int | mpi_cmp_abs (mpi *X, mpi *Y)
| Compare unsigned values.
int | mpi_cmp_int (mpi *X, int z)
| Compare signed values.
int | mpi_cmp_mpi (mpi *X, mpi *Y)
| Compare signed values.
int | mpi_copy (mpi *X, mpi *Y)
| Copy the contents of Y into X.
int | mpi_div_int (mpi *Q, mpi *R, mpi *A, int b)
| Division by int: A = Q * b + R.
int | mpi_div_mpi (mpi *Q, mpi *R, mpi *A, mpi *B)
| Division by mpi: A = Q * B + R.
int | mpi_exp_mod (mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR)
| Sliding-window exponentiation: X = A^E mod N.
void | mpi_free (mpi *X,...)
| Unallocate one or more mpi.
int | mpi_gcd (mpi *G, mpi *A, mpi *B)
| Greatest common divisor: G = gcd(A, B).
int | mpi_gen_prime (mpi *X, int nbits, int dh_flag, int(*f_rng)(void *), void *p_rng)
| Prime number generation.
int | mpi_grow (mpi *X, int nblimbs)
| Enlarge to the specified number of limbs.
void | mpi_init (mpi *X,...)
| Initialize one or more mpi.
int | mpi_inv_mod (mpi *X, mpi *A, mpi *N)
| Modular inverse: X = A^-1 mod N.
int | mpi_is_prime (mpi *X, int(*f_rng)(void *), void *p_rng)
| Miller-Rabin primality test.
int | mpi_lsb (mpi *X)
| Return the number of least significant bits.
int | mpi_lset (mpi *X, int z)
| Set value from integer.
int | mpi_mod_int (t_int *r, mpi *A, int b)
| Modulo: r = A mod b.
int | mpi_mod_mpi (mpi *R, mpi *A, mpi *B)
| Modulo: R = A mod B.
int | mpi_msb (mpi *X)
| Return the number of most significant bits.
int | mpi_mul_int (mpi *X, mpi *A, t_int b)
| Baseline multiplication: X = A * b Note: b is an unsigned integer type, thus Negative values of b are ignored.
int | mpi_mul_mpi (mpi *X, mpi *A, mpi *B)
| Baseline multiplication: X = A * B.
int | mpi_read_binary (mpi *X, unsigned char *buf, int buflen)
| Import X from unsigned binary data, big endian.
int | mpi_read_file (mpi *X, int radix, FILE *fin)
| Read X from an opened file.
int | mpi_read_string (mpi *X, int radix, char *s)
| Import from an ASCII string.
int | mpi_self_test (int verbose)
| Checkup routine.
int | mpi_shift_l (mpi *X, int count)
| Left-shift: X <<= count.
int | mpi_shift_r (mpi *X, int count)
| Right-shift: X >>= count.
int | mpi_size (mpi *X)
| Return the total size in bytes.
int | mpi_sub_abs (mpi *X, mpi *A, mpi *B)
| Unsigned substraction: X = |A| - |B|.
int | mpi_sub_int (mpi *X, mpi *A, int b)
| Signed substraction: X = A - b.
int | mpi_sub_mpi (mpi *X, mpi *A, mpi *B)
| Signed substraction: X = A - B.
void | mpi_swap (mpi *X, mpi *Y)
| Swap the contents of X and Y.
int | mpi_write_binary (mpi *X, unsigned char *buf, int buflen)
| Export X into unsigned binary data, big endian.
int | mpi_write_file (char *p, mpi *X, int radix, FILE *fout)
| Write X into an opened file, or stdout if fout is NULL.
int | mpi_write_string (mpi *X, int radix, char *s, int *slen)
| Export into an ASCII string.

## Define Documentation

#define MPI_CHK | ( | f |  | ) | if( ( ret = f ) != 0 ) goto cleanup

Definition at line 36 of file bignum.h.

#define POLARSSL_ERR_MPI_BAD_INPUT_DATA 0x0004

Definition at line 29 of file bignum.h.

#define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL 0x0008

Definition at line 31 of file bignum.h.

#define POLARSSL_ERR_MPI_DIVISION_BY_ZERO 0x000C

Definition at line 33 of file bignum.h.

#define POLARSSL_ERR_MPI_FILE_IO_ERROR 0x0002

Definition at line 28 of file bignum.h.

#define POLARSSL_ERR_MPI_INVALID_CHARACTER 0x0006

Definition at line 30 of file bignum.h.

#define POLARSSL_ERR_MPI_NEGATIVE_VALUE 0x000A

Definition at line 32 of file bignum.h.

#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE 0x000E

Definition at line 34 of file bignum.h.

## Typedef Documentation

typedef unsigned long t_int

Definition at line 49 of file bignum.h.

## Function Documentation

int mpi_add_abs | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Unsigned addition: X = |A| + |B|.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_add_int | ( | mpi * | X,
|  | mpi * | A,
|  | int | b |
| ) |  |  |

Signed addition: X = A + b.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | b | The integer value to add

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_add_mpi | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Signed addition: X = A + B.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_cmp_abs | ( | mpi * | X,
|  | mpi * | Y |
| ) |  |  |

Compare unsigned values.

Parameters:

  | X | Left-hand MPI
  | Y | Right-hand MPI

Returns:
  1 if |X| is greater than |Y|, -1 if |X| is lesser than |Y| or 0 if |X| is equal to |Y|

int mpi_cmp_int | ( | mpi * | X,
|  | int | z |
| ) |  |  |

Compare signed values.

Parameters:

  | X | Left-hand MPI
  | z | The integer value to compare to

Returns:
  1 if X is greater than z, -1 if X is lesser than z or 0 if X is equal to z

int mpi_cmp_mpi | ( | mpi * | X,
|  | mpi * | Y |
| ) |  |  |

Compare signed values.

Parameters:

  | X | Left-hand MPI
  | Y | Right-hand MPI

Returns:
  1 if X is greater than Y, -1 if X is lesser than Y or 0 if X is equal to Y

int mpi_copy | ( | mpi * | X,
|  | mpi * | Y |
| ) |  |  |

Copy the contents of Y into X.

Parameters:

  | X | Destination MPI
  | Y | Source MPI

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_div_int | ( | mpi * | Q,
|  | mpi * | R,
|  | mpi * | A,
|  | int | b |
| ) |  |  |

Division by int: A = Q * b + R.

Parameters:

  | Q | Destination MPI for the quotient
  | R | Destination MPI for the rest value
  | A | Left-hand MPI
  | b | Integer to divide by

Returns:
  0 if successful, 1 if memory allocation failed, POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0

Note:
  Either Q or R can be NULL.

int mpi_div_mpi | ( | mpi * | Q,
|  | mpi * | R,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Division by mpi: A = Q * B + R.

Parameters:

  | Q | Destination MPI for the quotient
  | R | Destination MPI for the rest value
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed, POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0

Note:
  Either Q or R can be NULL.

int mpi_exp_mod | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | E,
|  | mpi * | N,
|  | mpi * | _RR |
| ) |  |  |

Sliding-window exponentiation: X = A^E mod N.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | E | Exponent MPI
  | N | Modular MPI
  | _RR | Speed-up MPI used for recalculations

Returns:
  0 if successful, 1 if memory allocation failed, POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even

Note:
  _RR is used to avoid re-computing R*R mod N across multiple calls, which speeds up things a bit. It can be set to NULL if the extra performance is unneeded.

void mpi_free | ( | mpi * | X,
|  |  | ... |
| ) |  |  |

Unallocate one or more mpi.

int mpi_gcd | ( | mpi * | G,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Greatest common divisor: G = gcd(A, B).

Parameters:

  | G | Destination MPI
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_gen_prime | ( | mpi * | X,
|  | int | nbits,
|  | int | dh_flag,
|  | int(*)(void *) | f_rng,
|  | void * | p_rng |
| ) |  |  |

Prime number generation.

Parameters:

  | X | Destination MPI
  | nbits | Required size of X in bits
  | dh_flag | If 1, then (X-1)/2 will be prime too
  | f_rng | RNG function
  | p_rng | RNG parameter

Returns:
  0 if successful (probably prime), 1 if memory allocation failed, POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3

int mpi_grow | ( | mpi * | X,
|  | int | nblimbs |
| ) |  |  |

Enlarge to the specified number of limbs.

Parameters:

  | X | MPI to grow
  | nblimbs | The target number of limbs

Returns:
  0 if successful, 1 if memory allocation failed

void mpi_init | ( | mpi * | X,
|  |  | ... |
| ) |  |  |

Initialize one or more mpi.

int mpi_inv_mod | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | N |
| ) |  |  |

Modular inverse: X = A^-1 mod N.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | N | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed, POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N

int mpi_is_prime | ( | mpi * | X,
|  | int(*)(void *) | f_rng,
|  | void * | p_rng |
| ) |  |  |

Miller-Rabin primality test.

Parameters:

  | X | MPI to check
  | f_rng | RNG function
  | p_rng | RNG parameter

Returns:
  0 if successful (probably prime), 1 if memory allocation failed, POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime

int mpi_lsb | ( | mpi * | X | ) |

Return the number of least significant bits.

Parameters:

  | X | MPI to use

int mpi_lset | ( | mpi * | X,
|  | int | z |
| ) |  |  |

Set value from integer.

Parameters:

  | X | MPI to set
  | z | Value to use

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_mod_int | ( | t_int * | r,
|  | mpi * | A,
|  | int | b |
| ) |  |  |

Modulo: r = A mod b.

Parameters:

  | a | Destination t_int
  | A | Left-hand MPI
  | b | Integer to divide by

Returns:
  0 if successful, 1 if memory allocation failed, POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0, POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0

int mpi_mod_mpi | ( | mpi * | R,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Modulo: R = A mod B.

Parameters:

  | R | Destination MPI for the rest value
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed, POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0, POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0

int mpi_msb | ( | mpi * | X | ) |

Return the number of most significant bits.

Parameters:

  | X | MPI to use

Referenced by d2i_RSA_PUBKEY().

int mpi_mul_int | ( | mpi * | X,
|  | mpi * | A,
|  | t_int | b |
| ) |  |  |

Baseline multiplication: X = A * b Note: b is an unsigned integer type, thus Negative values of b are ignored.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | b | The integer value to multiply with

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_mul_mpi | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Baseline multiplication: X = A * B.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_read_binary | ( | mpi * | X,
|  | unsigned char * | buf,
|  | int | buflen |
| ) |  |  |

Import X from unsigned binary data, big endian.

Parameters:

  | X | Destination MPI
  | buf | Input buffer
  | buflen | Input buffer size

Returns:
  0 if successful, 1 if memory allocation failed

Referenced by d2i_RSA_PUBKEY().

int mpi_read_file | ( | mpi * | X,
|  | int | radix,
|  | FILE * | fin |
| ) |  |  |

Read X from an opened file.

Parameters:

  | X | Destination MPI
  | radix | Input numeric base
  | fin | Input file handle

Returns:
  0 if successful, or an POLARSSL_ERR_MPI_XXX error code

int mpi_read_string | ( | mpi * | X,
|  | int | radix,
|  | char * | s |
| ) |  |  |

Import from an ASCII string.

Parameters:

  | X | Destination MPI
  | radix | Input numeric base
  | s | Null-terminated string buffer

Returns:
  0 if successful, or an POLARSSL_ERR_MPI_XXX error code

int mpi_self_test | ( | int | verbose | ) |

Checkup routine.

Returns:
  0 if successful, or 1 if the test failed

int mpi_shift_l | ( | mpi * | X,
|  | int | count |
| ) |  |  |

Left-shift: X <<= count.

Parameters:

  | X | MPI to shift
  | count | Amount to shift

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_shift_r | ( | mpi * | X,
|  | int | count |
| ) |  |  |

Right-shift: X >>= count.

Parameters:

  | X | MPI to shift
  | count | Amount to shift

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_size | ( | mpi * | X | ) |

Return the total size in bytes.

Parameters:

  | X | MPI to use

int mpi_sub_abs | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Unsigned substraction: X = |A| - |B|.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A

int mpi_sub_int | ( | mpi * | X,
|  | mpi * | A,
|  | int | b |
| ) |  |  |

Signed substraction: X = A - b.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | b | The integer value to subtract

Returns:
  0 if successful, 1 if memory allocation failed

int mpi_sub_mpi | ( | mpi * | X,
|  | mpi * | A,
|  | mpi * | B |
| ) |  |  |

Signed substraction: X = A - B.

Parameters:

  | X | Destination MPI
  | A | Left-hand MPI
  | B | Right-hand MPI

Returns:
  0 if successful, 1 if memory allocation failed

void mpi_swap | ( | mpi * | X,
|  | mpi * | Y |
| ) |  |  |

Swap the contents of X and Y.

Parameters:

  | X | First MPI value
  | Y | Second MPI value

int mpi_write_binary | ( | mpi * | X,
|  | unsigned char * | buf,
|  | int | buflen |
| ) |  |  |

Export X into unsigned binary data, big endian.

Parameters:

  | X | Source MPI
  | buf | Output buffer
  | buflen | Output buffer size

Returns:
  0 if successful, POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough

int mpi_write_file | ( | char * | p,
|  | mpi * | X,
|  | int | radix,
|  | FILE * | fout |
| ) |  |  |

Write X into an opened file, or stdout if fout is NULL.

Parameters:

  | p | Prefix, can be NULL
  | X | Source MPI
  | radix | Output numeric base
  | fout | Output file handle (can be NULL)

Returns:
  0 if successful, or an POLARSSL_ERR_MPI_XXX error code

Note:
  Set fout == NULL to print X on the console.

int mpi_write_string | ( | mpi * | X,
|  | int | radix,
|  | char * | s,
|  | int * | slen |
| ) |  |  |

Export into an ASCII string.

Parameters:

  | X | Source MPI
  | radix | Output numeric base
  | s | String buffer
  | slen | String buffer size

Returns:
  0 if successful, or an POLARSSL_ERR_MPI_XXX error code

Note:
  Call this function with *slen = 0 to obtain the minimum required buffer size in *slen.