11. MPI library

Public key cryptography is based on mathematics with large numbers. To implement the public key functions, a library for handling these large numbers is required. Because of the general usefulness of such a library, its interface is exposed by Libgcrypt. The implementation is based on an old release of GNU Multi-Precision Library (GMP) but in the meantime heavily modified and stripped down to what is required for cryptography. For a lot of CPUs, high performance assembler implementations of some very low level functions are used to gain much better performance than with the standard C implementation.

In the context of Libgcrypt and in most other applications, these large numbers are called MPIs (multi-precision-integers).

11.1 Data types

Data type: gcry_mpi_t

The gcry_mpi_t type represents an object to hold an MPI.

11.2 Basic functions

To work with MPIs, storage must be allocated and released for the numbers. This can be done with one of these functions:

Function: gcry_mpi_t gcry_mpi_new (unsigned int nbits)

Allocate a new MPI object, initialize it to 0 and initially allocate enough memory for a number of at least nbits. This pre-allocation is only a small performance issue and not actually necessary because Libgcrypt automatically re-allocates the required memory.

Function: gcry_mpi_t gcry_mpi_snew (unsigned int nbits)

This is identical to gcry_mpi_new but allocates the MPI in the so called "secure memory" which in turn will take care that all derived values will also be stored in this "secure memory". Use this for highly confidential data like private key parameters.

Function: gcry_mpi_t gcry_mpi_copy (const gcry_mpi_t a)

Create a new MPI as the exact copy of a.

Function: void gcry_mpi_release (gcry_mpi_t a)

Release the MPI a and free all associated resources. Passing NULL is allowed and ignored. When a MPI stored in the "secure memory" is released, that memory gets wiped out immediately.

The simplest operations are used to assign a new value to an MPI:

Function: gcry_mpi_t gcry_mpi_set (gcry_mpi_t w, const gcry_mpi_t u)

Assign the value of u to w and return w. If NULL is passed for w, a new MPI is allocated, set to the value of u and returned.

Function: gcry_mpi_t gcry_mpi_set_ui (gcry_mpi_t w, unsigned long u)

Assign the value of u to w and return w. If NULL is passed for w, a new MPI is allocated, set to the value of u and returned. This function takes an unsigned int as type for u and thus it is only possible to set w to small values (usually up to the word size of the CPU).

Function: void gcry_mpi_swap (gcry_mpi_t a, gcry_mpi_t b)

Swap the values of a and b.

11.3 MPI formats

The following functions are used to convert between an external representation of an MPI and the internal one of Libgcrypt.

Function: gcry_error_t gcry_mpi_scan (gcry_mpi_t *r_mpi, enum gcry_mpi_format format, const unsigned char *buffer, size_t buflen, size_t *nscanned)

Convert the external representation of an integer stored in buffer with a length of buflen into a newly created MPI returned which will be stored at the address of r_mpi. For certain formats the length argument is not required and may be passed as 0. After a successful operation the variable nscanned receives the number of bytes actually scanned unless nscanned was given as NULL. format describes the format of the MPI as stored in buffer:

GCRYMPI_FMT_STD

2-complement stored without a length header.

GCRYMPI_FMT_PGP

As used by OpenPGP (only defined as unsigned). This is basically GCRYMPI_FMT_STD with a 2 byte big endian length header.

GCRYMPI_FMT_SSH

As used in the Secure Shell protocol. This is GCRYMPI_FMT_STD with a 4 byte big endian header.

GCRYMPI_FMT_HEX

Stored as a C style string with each byte of the MPI encoded as 2 hex digits. When using this format, buflen must be zero.

GCRYMPI_FMT_USG

Simple unsigned integer.

Note that all of the above formats store the integer in big-endian format (MSB first).

Function: gcry_error_t gcry_mpi_print (enum gcry_mpi_format format, unsigned char *buffer, size_t buflen, size_t *nwritten, const gcry_mpi_t a)

Convert the MPI a into an external representation described by format (see above) and store it in the provided buffer which has a usable length of at least the buflen bytes. If nwritten is not NULL, it will receive the number of bytes actually stored in buffer after a successful operation.

Function: gcry_error_t gcry_mpi_aprint (enum gcry_mpi_format format, unsigned char **buffer, size_t *nbytes, const gcry_mpi_t a)

Convert the MPI a into an external representation described by format (see above) and store it in a newly allocated buffer which address will be stored in the variable buffer points to. The number of bytes stored in this buffer will be stored in the variable nbytes points to, unless nbytes is NULL.

Function: void gcry_mpi_dump (const gcry_mpi_t a)

Dump the value of a in a format suitable for debugging to Libgcrypt's logging stream. Note that one leading space but no trailing space or linefeed will be printed. It is okay to pass NULL for a.

11.4 Calculations

Basic arithmetic operations:

Function: void gcry_mpi_add (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v)

w = u + v.

Function: void gcry_mpi_add_ui (gcry_mpi_t w, gcry_mpi_t u, unsigned long v)

w = u + v. Note that v is an unsigned integer.

Function: void gcry_mpi_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)

w = u + v \bmod m.

Function: void gcry_mpi_sub (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v)

w = u - v.

Function: void gcry_mpi_sub_ui (gcry_mpi_t w, gcry_mpi_t u, unsigned long v)

w = u - v. v is an unsigned integer.

Function: void gcry_mpi_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)

w = u - v \bmod m.

Function: void gcry_mpi_mul (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v)

w = u * v.

Function: void gcry_mpi_mul_ui (gcry_mpi_t w, gcry_mpi_t u, unsigned long v)

w = u * v. v is an unsigned integer.

Function: void gcry_mpi_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)

w = u * v \bmod m.

Function: void gcry_mpi_mul_2exp (gcry_mpi_t w, gcry_mpi_t u, unsigned long e)

w = u * 2^e.

Function: void gcry_mpi_div (gcry_mpi_t q, gcry_mpi_t r, gcry_mpi_t dividend, gcry_mpi_t divisor, int round)

q = dividend / divisor, r = dividend \bmod divisor. q and r may be passed as NULL. round should be negative or 0.

Function: void gcry_mpi_mod (gcry_mpi_t r, gcry_mpi_t dividend, gcry_mpi_t divisor)

r = dividend \bmod divisor.

Function: void gcry_mpi_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e, const gcry_mpi_t m)

w = b^e \bmod m.

Function: int gcry_mpi_gcd (gcry_mpi_t g, gcry_mpi_t a, gcry_mpi_t b)

Set g to the greatest common divisor of a and b. Return true if the g is 1.

Function: int gcry_mpi_invm (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t m)

Set x to the multiplicative inverse of a \bmod m. Return true if the inverse exists.

11.5 Comparisons

The next 2 functions are used to compare MPIs:

Function: int gcry_mpi_cmp (const gcry_mpi_t u, const gcry_mpi_t v)

Compare the big integer number u and v returning 0 for equality, a positive value for u > v and a negative for u < v.

Function: int gcry_mpi_cmp_ui (const gcry_mpi_t u, unsigned long v)

Compare the big integer number u with the unsigned integer v returning 0 for equality, a positive value for u > v and a negative for u < v.

11.6 Bit manipulations

There are a couple of functions to get information on arbitrary bits in an MPI and to set or clear them:

Function: unsigned int gcry_mpi_get_nbits (gcry_mpi_t a)

Return the number of bits required to represent a.

Function: int gcry_mpi_test_bit (gcry_mpi_t a, unsigned int n)

Return true if bit number n (counting from 0) is set in a.

Function: void gcry_mpi_set_bit (gcry_mpi_t a, unsigned int n)

Set bit number n in a.

Function: void gcry_mpi_clear_bit (gcry_mpi_t a, unsigned int n)

Clear bit number n in a.

Function: void gcry_mpi_set_highbit (gcry_mpi_t a, unsigned int n)

Set bit number n in a and clear all bits greater than n.

Function: void gcry_mpi_clear_highbit (gcry_mpi_t a, unsigned int n)

Clear bit number n in a and all bits greater than n.

Function: void gcry_mpi_rshift (gcry_mpi_t x, gcry_mpi_t a, unsigned int n)

Shift the value of a by n bits to the right and store the result in x.

11.7 Miscellaneous

Function: gcry_mpi_t gcry_mpi_set_opaque (gcry_mpi_t a, void *p, unsigned int nbits)

Store nbits of the value p points to in a and mark a as an opaque value (i.e. an value that can't be used for any math calculation and is only used to store an arbitrary bit pattern in a).

WARNING: Never use an opaque MPI for actual math operations. The only valid functions are gcry_mpi_get_opaque and gcry_mpi_release. Use gcry_mpi_scan to convert a string of arbitrary bytes into an MPI.

Function: void * gcry_mpi_get_opaque (gcry_mpi_t a, unsigned int *nbits)

Return a pointer to an opaque value stored in a and return its size in nbits. Note that the returned pointer is still owned by a and that the function should never be used for an non-opaque MPI.

Function: void gcry_mpi_set_flag (gcry_mpi_t a, enum gcry_mpi_flag flag)

Set the flag for the MPI a. Currently only the flag GCRYMPI_FLAG_SECURE is allowed to convert a into an MPI stored in "secure memory".

Function: void gcry_mpi_clear_flag (gcry_mpi_t a, enum gcry_mpi_flag flag)

Clear flag for the big integer a. Note that this function is currently useless as no flags are allowed.

Function: int gcry_mpi_get_flag (gcry_mpi_t a, enum gcry_mpi_flag flag)

Return true when the flag is set for a.

Function: void gcry_mpi_randomize (gcry_mpi_t w, unsigned int nbits, enum gcry_random_level level)

Set the big integer w to a random value of nbits, using random data quality of level level. In case nbits is not a multiple of a byte, nbits is rounded up to the next byte boundary.

This document was generated by root on August, 10 2009 using texi2html 1.78.