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:

Classical
Barrett
Montgomery

It also implements the following:

Karatsuba multiplication
Squaring
Sliding window exponentiation
Chinese Remainder Theorem (implemented in rsa.c).

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 ( j ) tmp_u->comps[tmp_u->size-j-1]

uj for division

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

qj for division

#define check ( A )

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

Big Integer API

Defines

Functions

Detailed Description

Define Documentation

Function Documentation