Big Integer API

The bigint implementation as used by the axTLS project. More...

Defines

#define V1   v->comps[v->size-1]
#define V2   v->comps[v->size-2]
#define U(j)   tmp_u->comps[tmp_u->size-j-1]
#define Q(j)   quotient->comps[quotient->size-j-1]
#define check(A)

Functions

BI_CTX * bi_initialize (void)
 Start a new bigint context.
void bi_terminate (BI_CTX *ctx)
 Close the bigint context and free any resources.
void bi_clear_cache (BI_CTX *ctx)
 Clear the memory cache.
bigint * bi_copy (bigint *bi)
 Increment the number of references to this object. It does not do a full copy.
void bi_permanent (bigint *bi)
 Simply make a bigint object "unfreeable" if bi_free() is called on it.
void bi_depermanent (bigint *bi)
 Take a permanent object and make it eligible for freedom.
void bi_free (BI_CTX *ctx, bigint *bi)
 Free a bigint object so it can be used again.
bigint * int_to_bi (BI_CTX *ctx, comp i)
 Convert an (unsigned) integer into a bigint.
bigint * bi_clone (BI_CTX *ctx, const bigint *bi)
 Do a full copy of the bigint object.
bigint * bi_add (BI_CTX *ctx, bigint *bia, bigint *bib)
 Perform an addition operation between two bigints.
bigint * bi_subtract (BI_CTX *ctx, bigint *bia, bigint *bib, int *is_negative)
 Perform a subtraction operation between two bigints.
bigint * bi_divide (BI_CTX *ctx, bigint *u, bigint *v, int is_mod)
 Does both division and modulo calculations.
bigint * bi_import (BI_CTX *ctx, const uint8_t *data, int size)
 Allow a binary sequence to be imported as a bigint.
void bi_export (BI_CTX *ctx, bigint *x, uint8_t *data, int size)
 Take a bigint and convert it into a byte sequence.
void bi_set_mod (BI_CTX *ctx, bigint *bim, int mod_offset)
 Pre-calculate some of the expensive steps in reduction.
void bi_free_mod (BI_CTX *ctx, int mod_offset)
 Used when cleaning various bigints at the end of a session.
bigint * bi_multiply (BI_CTX *ctx, bigint *bia, bigint *bib)
 Perform a multiplication operation between two bigints.
int bi_compare (bigint *bia, bigint *bib)
 Compare two bigints.
bigint * bi_mont (BI_CTX *ctx, bigint *bixy)
 Perform a single montgomery reduction.
bigint * bi_mod_power (BI_CTX *ctx, bigint *bi, bigint *biexp)
 Perform a modular exponentiation.
bigint * bi_mod_power2 (BI_CTX *ctx, bigint *bi, bigint *bim, bigint *biexp)
 Perform a modular exponentiation using a temporary modulus.
bigint * bi_crt (BI_CTX *ctx, bigint *bi, bigint *dP, bigint *dQ, bigint *p, bigint *q, bigint *qInv)
 Use the Chinese Remainder Theorem to quickly perform RSA decrypts.

Detailed Description

The bigint implementation as used by the axTLS project.

The bigint library is for RSA encryption/decryption as well as signing. This code tries to minimise use of malloc/free by maintaining a small cache. A bigint context may maintain state by being made "permanent". It be be later released with a bi_depermanent() and bi_free() call.

It supports the following reduction techniques:

It also implements the following:

All the algorithms used are pretty standard, and designed for different data bus sizes. Negative numbers are not dealt with at all, so a subtraction may need to be tested for negativity.

This library steals some ideas from Jef Poskanzer <http://cs.marlboro.edu/term/cs-fall02/algorithms/crypto/RSA/bigint> and GMP <http://www.swox.com/gmp>. It gets most of its implementation detail from "The Handbook of Applied Cryptography" <http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf>


Define Documentation

#define V1   v->comps[v->size-1]

v1 for division

#define V2   v->comps[v->size-2]

v2 for division

#define U (  )     tmp_u->comps[tmp_u->size-j-1]

uj for division

#define Q (  )     quotient->comps[quotient->size-j-1]

qj for division

#define check (  ) 

disappears in normal production mode


Function Documentation

BI_CTX* bi_initialize ( void   ) 

Start a new bigint context.

Returns:
A bigint context.
void bi_terminate ( BI_CTX *  ctx  ) 

Close the bigint context and free any resources.

Free up any used memory - a check is done if all objects were not properly freed.

Parameters:
ctx [in] The bigint session context.
bigint* bi_copy ( bigint *  bi  ) 

Increment the number of references to this object. It does not do a full copy.

Parameters:
bi [in] The bigint to copy.
Returns:
A reference to the same bigint.
void bi_permanent ( bigint *  bi  ) 

Simply make a bigint object "unfreeable" if bi_free() is called on it.

For this object to be freed, bi_depermanent() must be called.

Parameters:
bi [in] The bigint to be made permanent.
void bi_depermanent ( bigint *  bi  ) 

Take a permanent object and make it eligible for freedom.

Parameters:
bi [in] The bigint to be made back to temporary.
void bi_free ( BI_CTX *  ctx,
bigint *  bi 
)

Free a bigint object so it can be used again.

The memory itself it not actually freed, just tagged as being available

Parameters:
ctx [in] The bigint session context.
bi [in] The bigint to be freed.
bigint* int_to_bi ( BI_CTX *  ctx,
comp  i 
)

Convert an (unsigned) integer into a bigint.

Parameters:
ctx [in] The bigint session context.
i [in] The (unsigned) integer to be converted.
bigint* bi_clone ( BI_CTX *  ctx,
const bigint *  bi 
)

Do a full copy of the bigint object.

Parameters:
ctx [in] The bigint session context.
bi [in] The bigint object to be copied.
bigint* bi_add ( BI_CTX *  ctx,
bigint *  bia,
bigint *  bib 
)

Perform an addition operation between two bigints.

Parameters:
ctx [in] The bigint session context.
bia [in] A bigint.
bib [in] Another bigint.
Returns:
The result of the addition.
bigint* bi_subtract ( BI_CTX *  ctx,
bigint *  bia,
bigint *  bib,
int *  is_negative 
)

Perform a subtraction operation between two bigints.

Parameters:
ctx [in] The bigint session context.
bia [in] A bigint.
bib [in] Another bigint.
is_negative [out] If defined, indicates that the result was negative. is_negative may be null.
Returns:
The result of the subtraction. The result is always positive.
bigint* bi_divide ( BI_CTX *  ctx,
bigint *  u,
bigint *  v,
int  is_mod 
)

Does both division and modulo calculations.

Used extensively when doing classical reduction.

Parameters:
ctx [in] The bigint session context.
u [in] A bigint which is the numerator.
v [in] Either the denominator or the modulus depending on the mode.
is_mod [n] Determines if this is a normal division (0) or a reduction (1).
Returns:
The result of the division/reduction.
bigint* bi_import ( BI_CTX *  ctx,
const uint8_t *  data,
int  size 
)

Allow a binary sequence to be imported as a bigint.

Parameters:
ctx [in] The bigint session context.
data [in] The data to be converted.
size [in] The number of bytes of data.
Returns:
A bigint representing this data.
void bi_export ( BI_CTX *  ctx,
bigint *  x,
uint8_t *  data,
int  size 
)

Take a bigint and convert it into a byte sequence.

This is useful after a decrypt operation.

Parameters:
ctx [in] The bigint session context.
x [in] The bigint to be converted.
data [out] The converted data as a byte stream.
size [in] The maximum size of the byte stream. Unused bytes will be zeroed.
void bi_set_mod ( BI_CTX *  ctx,
bigint *  bim,
int  mod_offset 
)

Pre-calculate some of the expensive steps in reduction.

This function should only be called once (normally when a session starts). When the session is over, bi_free_mod() should be called. bi_mod_power() relies on this function being called.

Parameters:
ctx [in] The bigint session context.
bim [in] The bigint modulus that will be used.
mod_offset [in] There are three moduluii that can be stored - the standard modulus, and its two primes p and q. This offset refers to which modulus we are referring to.
See also:
bi_free_mod(), bi_mod_power().
void bi_free_mod ( BI_CTX *  ctx,
int  mod_offset 
)

Used when cleaning various bigints at the end of a session.

Parameters:
ctx [in] The bigint session context.
mod_offset [in] The offset to use.
See also:
bi_set_mod().
bigint* bi_multiply ( BI_CTX *  ctx,
bigint *  bia,
bigint *  bib 
)

Perform a multiplication operation between two bigints.

Parameters:
ctx [in] The bigint session context.
bia [in] A bigint.
bib [in] Another bigint.
Returns:
The result of the multiplication.
int bi_compare ( bigint *  bia,
bigint *  bib 
)

Compare two bigints.

Parameters:
bia [in] A bigint.
bib [in] Another bigint.
Returns:
-1 if smaller, 1 if larger and 0 if equal.
bigint* bi_mont ( BI_CTX *  ctx,
bigint *  bixy 
)

Perform a single montgomery reduction.

Parameters:
ctx [in] The bigint session context.
bixy [in] A bigint.
Returns:
The result of the montgomery reduction.
bigint* bi_mod_power ( BI_CTX *  ctx,
bigint *  bi,
bigint *  biexp 
)

Perform a modular exponentiation.

This function requires bi_set_mod() to have been called previously. This is one of the optimisations used for performance.

Parameters:
ctx [in] The bigint session context.
bi [in] The bigint on which to perform the mod power operation.
biexp [in] The bigint exponent.
Returns:
The result of the mod exponentiation operation
See also:
bi_set_mod().
bigint* bi_mod_power2 ( BI_CTX *  ctx,
bigint *  bi,
bigint *  bim,
bigint *  biexp 
)

Perform a modular exponentiation using a temporary modulus.

We need this function to check the signatures of certificates. The modulus of this function is temporary as it's just used for authentication.

Parameters:
ctx [in] The bigint session context.
bi [in] The bigint to perform the exp/mod.
bim [in] The temporary modulus.
biexp [in] The bigint exponent.
Returns:
The result of the mod exponentiation operation
See also:
bi_set_mod().
bigint* bi_crt ( BI_CTX *  ctx,
bigint *  bi,
bigint *  dP,
bigint *  dQ,
bigint *  p,
bigint *  q,
bigint *  qInv 
)

Use the Chinese Remainder Theorem to quickly perform RSA decrypts.

Parameters:
ctx [in] The bigint session context.
bi [in] The bigint to perform the exp/mod.
dP [in] CRT's dP bigint
dQ [in] CRT's dQ bigint
p [in] CRT's p bigint
q [in] CRT's q bigint
qInv [in] CRT's qInv bigint
Returns:
The result of the CRT operation

Copyright 2007 Cameron Rich