Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Big Integer API
The bigint implementation as used by the axTLS project. More...
Functions | |
| static bigint * | bi_int_multiply (BI_CTX *ctx, bigint *bia, comp b) |
| Perform a multiply between a bigint an an (unsigned) integer. | |
| static bigint * | comp_right_shift (bigint *biR, int num_shifts) |
| Take each component and shift down (in terms of components) | |
| static bigint * | comp_left_shift (bigint *biR, int num_shifts) |
| Take each component and shift it up (in terms of components) | |
| 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. | |
| 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. | |
| static comp | modular_inverse (bigint *bim) |
| There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1, where B^-1(B-1) mod N=1. | |
| bigint * | bi_import (BI_CTX *ctx, const uint8_t *data, int size) |
| Allow a binary sequence to be imported as a bigint. | |
| bigint * | bi_str_import (BI_CTX *ctx, const char *data) |
| The testharness uses this code to import text hex-streams and convert them into bigints. | |
| 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. | |
| static bigint * | regular_multiply (BI_CTX *ctx, bigint *bia, bigint *bib, int inner_partial, int outer_partial) |
| Perform a standard multiplication between two bigints. | |
| bigint * | bi_multiply (BI_CTX *ctx, bigint *bia, bigint *bib) |
| Perform a multiplication operation between two bigints. | |
| bigint * | bi_square (BI_CTX *ctx, bigint *bia) |
| Perform a square operation on a bigint. | |
| 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_barrett (BI_CTX *ctx, bigint *bi) |
| Perform a single Barrett 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>
Function Documentation
| void bi_clear_cache | ( | BI_CTX * | ctx ) |
| 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
| void bi_depermanent | ( | bigint * | bi ) |
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.
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_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_CTX* bi_initialize | ( | void | ) |
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().
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().
| 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.
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().
The testharness uses this code to import text hex-streams and convert them into bigints.
- Parameters:
-
ctx [in] The bigint session context. data [in] A string consisting of hex characters. The characters must be in upper case.
- Returns:
- A bigint representing this data.
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.
| void bi_terminate | ( | BI_CTX * | ctx ) |
| static comp modular_inverse | ( | bigint * | bim ) | [static] |
There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1, where B^-1(B-1) mod N=1.
Actually, only the least significant part of N' is needed, hence the definition N0'=N' mod b. We reproduce below the simple algorithm from an article by Dusse and Kaliski to efficiently find N0' from N0 and b
Generated on Tue Jul 12 2022 12:58:50 by
1.7.2