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

Macros
#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. 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. It does not do a full copy. 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_mont (BI_CTX ctx, bigint bixy)
	Perform a single montgomery reduction. More...

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

bigint *	bi_mod_power2 (BI_CTX ctx, bigint bi, bigint bim, bigint biexp)
	Perform a modular exponentiation using a temporary modulus. More...

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

Macro Definition Documentation

◆ V1

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

v1 for division

◆ V2

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

v2 for division

◆ U

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

uj for division

◆ Q

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

qj for division

◆ check

#define check ( A )

disappears in normal production mode

Function Documentation

◆ bi_initialize()

BI_CTX* bi_initialize ( void )

Start a new bigint context.

Returns: A bigint context.

Referenced by bi_mod_power2().

◆ 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.

References bi_clear_cache(), bi_depermanent(), and bi_free().

Referenced by bi_mod_power2().

◆ 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.

References check.

Referenced by bi_crt().

◆ 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.

References check.

Referenced by bi_set_mod().

◆ 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.

References check.

Referenced by bi_free_mod(), and bi_terminate().

◆ 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.

References check.

Referenced by bi_divide(), bi_export(), bi_free_mod(), bi_mod_power2(), and bi_terminate().

◆ 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.

◆ 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.

Referenced by bi_mod_power2().

◆ 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.

References check.

Referenced by bi_crt(), and bi_mont().

◆ 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.

References check.

Referenced by bi_crt().

◆ 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.

References bi_compare(), bi_free(), and check.

◆ 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_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.

References bi_free(), and check.

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

References bi_permanent().

Referenced by bi_mod_power2().

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

References bi_depermanent(), and bi_free().

Referenced by bi_mod_power2().

◆ 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.

References check.

Referenced by bi_crt().

◆ 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.

References check.

Referenced by bi_divide().

◆ bi_mont()

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.

References bi_add(), and check.

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

Referenced by bi_crt(), and bi_mod_power2().

◆ bi_mod_power2()

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

References bi_clone(), bi_free(), bi_free_mod(), bi_initialize(), bi_mod_power(), bi_set_mod(), and bi_terminate().

◆ bi_crt()

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

References bi_add(), bi_copy(), bi_mod_power(), bi_multiply(), and bi_subtract().

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ V1

◆ V2

◆ U

◆ Q

◆ check

Function Documentation

◆ bi_initialize()

◆ bi_terminate()

◆ bi_copy()

◆ bi_permanent()

◆ bi_depermanent()

◆ bi_free()

◆ int_to_bi()

◆ bi_clone()

◆ bi_add()

◆ bi_subtract()

◆ bi_divide()

◆ bi_import()

◆ bi_export()

◆ bi_set_mod()

◆ bi_free_mod()

◆ bi_multiply()

◆ bi_compare()

◆ bi_mont()

◆ bi_mod_power()

◆ bi_mod_power2()

◆ bi_crt()