axTLS
|
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... | |
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 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
BI_CTX* bi_initialize | ( | void | ) |
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.
ctx | [in] The bigint session context. |
References bi_clear_cache(), bi_depermanent(), and bi_free().
Referenced by bi_mod_power2().
bigint* bi_copy | ( | bigint * | bi | ) |
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.
bi | [in] The bigint to be made permanent. |
References check.
Referenced by bi_set_mod().
void bi_depermanent | ( | bigint * | bi | ) |
Take a permanent object and make it eligible for freedom.
bi | [in] The bigint to be made back to temporary. |
References check.
Referenced by bi_free_mod(), and bi_terminate().
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
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().
bigint* int_to_bi | ( | BI_CTX * | ctx, |
comp | i | ||
) |
Convert an (unsigned) integer into a bigint.
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.
ctx | [in] The bigint session context. |
bi | [in] The bigint object to be copied. |
Referenced by bi_mod_power2().
bigint* bi_add | ( | BI_CTX * | ctx, |
bigint * | bia, | ||
bigint * | bib | ||
) |
bigint* bi_subtract | ( | BI_CTX * | ctx, |
bigint * | bia, | ||
bigint * | bib, | ||
int * | is_negative | ||
) |
Perform a subtraction operation between two bigints.
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. |
References check.
Referenced by bi_crt().
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.
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). |
References bi_compare(), bi_free(), and check.
bigint* bi_import | ( | BI_CTX * | ctx, |
const uint8_t * | data, | ||
int | size | ||
) |
Allow a binary sequence to be imported as a bigint.
ctx | [in] The bigint session context. |
data | [in] The data to be converted. |
size | [in] The number of bytes of 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.
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.
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. |
References bi_permanent().
Referenced by bi_mod_power2().
void bi_free_mod | ( | BI_CTX * | ctx, |
int | mod_offset | ||
) |
Used when cleaning various bigints at the end of a session.
ctx | [in] The bigint session context. |
mod_offset | [in] The offset to use. |
References bi_depermanent(), and bi_free().
Referenced by bi_mod_power2().
bigint* bi_multiply | ( | BI_CTX * | ctx, |
bigint * | bia, | ||
bigint * | bib | ||
) |
int bi_compare | ( | bigint * | bia, |
bigint * | bib | ||
) |
Compare two bigints.
bia | [in] A bigint. |
bib | [in] Another bigint. |
References check.
Referenced by bi_divide().
bigint* bi_mont | ( | BI_CTX * | ctx, |
bigint * | bixy | ||
) |
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.
ctx | [in] The bigint session context. |
bi | [in] The bigint on which to perform the mod power operation. |
biexp | [in] The bigint exponent. |
Referenced by bi_crt(), and 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.
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. |
References bi_clone(), bi_free(), bi_free_mod(), bi_initialize(), bi_mod_power(), bi_set_mod(), and bi_terminate().
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.
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 |
References bi_add(), bi_copy(), bi_mod_power(), bi_multiply(), and bi_subtract().