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

Macros
#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

Functions
BI_CTX *	bi_initialize (void)
	Start a new bigint context. More...

void	bi_terminate (BI_CTX *ctx)
	Close the bigint context and free any resources. More...

void	bi_clear_cache (BI_CTX *ctx)
	Clear the memory cache.

bigint *	bi_copy (bigint *bi)
	Increment the number of references to this object. More...

void	bi_permanent (bigint *bi)
	Simply make a bigint object "unfreeable" if bi_free() is called on it. More...

void	bi_depermanent (bigint *bi)
	Take a permanent object and make it eligible for freedom. More...

void	bi_free (BI_CTX ctx, bigint bi)
	Free a bigint object so it can be used again. More...

bigint *	int_to_bi (BI_CTX *ctx, comp i)
	Convert an (unsigned) integer into a bigint. More...

bigint *	bi_clone (BI_CTX ctx, const bigint bi)
	Do a full copy of the bigint object. More...

bigint *	bi_add (BI_CTX ctx, bigint bia, bigint *bib)
	Perform an addition operation between two bigints. More...

bigint *	bi_subtract (BI_CTX ctx, bigint bia, bigint bib, int is_negative)
	Perform a subtraction operation between two bigints. More...

bigint *	bi_divide (BI_CTX ctx, bigint u, bigint *v, int is_mod)
	Does both division and modulo calculations. More...

bigint *	bi_import (BI_CTX ctx, const uint8_t data, int size)
	Allow a binary sequence to be imported as a bigint. More...

void	bi_export (BI_CTX ctx, bigint x, uint8_t *data, int size)
	Take a bigint and convert it into a byte sequence. More...

void	bi_set_mod (BI_CTX ctx, bigint bim, int mod_offset)
	Pre-calculate some of the expensive steps in reduction. More...

void	bi_free_mod (BI_CTX *ctx, int mod_offset)
	Used when cleaning various bigints at the end of a session. More...

bigint *	bi_multiply (BI_CTX ctx, bigint bia, bigint *bib)
	Perform a multiplication operation between two bigints. More...

int	bi_compare (bigint bia, bigint bib)
	Compare two bigints. More...

bigint *	bi_mod_power (BI_CTX ctx, bigint bi, bigint *biexp)
	Perform a modular exponentiation. More...

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

Function Documentation

◆ bi_add()

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.

◆ bi_clone()

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.

◆ bi_compare()

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.

◆ bi_copy()

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.

◆ bi_depermanent()

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.

◆ bi_divide()

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.

◆ bi_export()

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.

◆ bi_free()

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.

◆ bi_free_mod()

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().

◆ bi_import()

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.

◆ bi_initialize()

BI_CTX* bi_initialize ( void )

Start a new bigint context.

Returns: A bigint context.

◆ bi_mod_power()

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().

◆ bi_multiply()

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.

◆ bi_permanent()

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.

◆ bi_set_mod()

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().

◆ bi_subtract()

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.

◆ bi_terminate()

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.

◆ int_to_bi()

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.

Macros

Functions

Detailed Description

Function Documentation

◆ bi_add()

◆ bi_clone()

◆ bi_compare()

◆ bi_copy()

◆ bi_depermanent()

◆ bi_divide()

◆ bi_export()

◆ bi_free()

◆ bi_free_mod()

◆ bi_import()

◆ bi_initialize()

◆ bi_mod_power()

◆ bi_multiply()

◆ bi_permanent()

◆ bi_set_mod()

◆ bi_subtract()

◆ bi_terminate()

◆ int_to_bi()