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.
Dependents: blinky_max32630fthr
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 14:21:31 by
1.7.2