Unit Big Integer - Ultibo.org
Return to Unit Reference
Description
Ultibo Big Integer Interface unit
This unit implements multiple precision integer arithmetic operations as well as multiple precision modular arithmetic including addition, subtraction, multiplication, division, square, modular reduction and modular exponentiation.
The unit is primarily intended to support the RSA functions within the Crypto unit as well as other cryptographic functionality.
Constants
BigInt specific constants BIGINT_*
| Maintain a number of precomputed variables when doing reduction | |
BIGINT_M_OFFSET = 0;
|
Normal modulo offset |
BIGINT_P_OFFSET = 1;
|
P modulo offset |
BIGINT_Q_OFFSET = 2;
|
Q modulo offset |
BIGINT_NUM_MODS = 3;
|
The number of modulus constants used |
BIGINT_COMP_RADIX = UInt64(4294967296);
|
Max component + 1 |
BIGINT_COMP_MAX = UInt64($FFFFFFFFFFFFFFFF);
|
Max dbl component - 1 |
BIGINT_COMP_BIT_SIZE = 32;
|
Number of bits in a component |
BIGINT_COMP_BYTE_SIZE = 4;
|
Number of bytes in a component |
BIGINT_COMP_NUM_NIBBLES = 8;
|
Used for diagnostics only |
BIGINT_PERMANENT = $7FFF55AA;
|
A magic number for permanents |
Type definitions
Component
PComponent = ^TComponent;
TComponent = LongWord;
| A single precision component | |
Long component
PLongComponent = ^TLongComponent;
TLongComponent = UInt64;
| A double precision component | |
Signed long component
PSignedLongComponent = ^TSignedLongComponent;
TSignedLongComponent = Int64;
| A signed double precision component | |
BigInt
PPBigInt = ^PBigInt;
PBigInt = ^TBigInt;
TBigInt = record
| A big integer basic object | |
Next:PBigInt;
|
The next bigint in the cache |
Size:Integer;
|
The number of components in this bigint |
MaxComponents:Integer;
|
The number of components allocated for this bigint |
References:Integer;
|
An internal reference count |
Components:PComponent;
|
A ptr to the actual component data |
procedure Zero;
|
|
procedure Clear;
|
|
function ToString:String;
|
|
BigInt context
PBigIntContext = ^TBigIntContext;
TBigIntContext = record
| Maintains the state of the cache, and a number of variables used in reduction. | |
ActiveList:PBigInt;
|
Bigints currently used |
FreeList:PBigInt;
|
Bigints not used |
BIRadix:PBigInt;
|
The radix used |
BIMod:array[0..BIGINT_NUM_MODS - 1] of PBigInt;
|
Modulus |
BImu:array[0..BIGINT_NUM_MODS - 1] of PBigInt;
|
Storage for mu |
BIbk1:array[0..BIGINT_NUM_MODS - 1] of PBigInt;
|
Storage for b(k+1) |
BINormalisedMod:array[0..BIGINT_NUM_MODS - 1] of PBigInt;
|
Normalised mod storage |
G:PPBigInt;
|
Used by sliding-window |
Window:Integer;
|
The size of the sliding window |
ActiveCount:Integer;
|
Number of active bigints |
FreeCount:Integer;
|
Number of free bigints |
ModOffset:Byte;
|
The mod offset we are using |
Public variables
None defined
Function declarations
BigInt functions
function BIInitialize:PBigIntContext;
Description: Start a new bigint context
procedure BITerminate(Context:PBigIntContext);
Description: Close the bigint context and free any resources
| Context | The bigint session context |
|---|
procedure BIPermanent(BI:PBigInt);
Description: Make a bigint object "unfreeable" if BIFree() is called on it
| BI | The bigint to be made permanent |
|---|
procedure BIDepermanent(BI:PBigInt);
Description: Take a permanent object and make it freeable
| BI | The bigint to be made freeable |
|---|
procedure BIClearCache(Context:PBigIntContext);
Description: Clear the memory cache
procedure BIFree(Context:PBigIntContext; BI:PBigInt);
Description: Free a bigint object so it can be used again
| Context | The bigint session context |
|---|---|
| BI | The bigint to be freed |
function BICopy(BI:PBigInt):PBigInt;
Description: Increment the number of references to this object
| BI | The bigint to copy |
|---|---|
| Return | A reference to the same bigint |
function BIClone(Context:PBigIntContext; const BI:TBigInt):PBigInt;
Description: Do a full copy of the bigint object
| Context | The bigint session context |
|---|---|
| BI | The bigint object to be copied |
| Return | A copy of the bigint object |
procedure BIExport(Context:PBigIntContext; BI:PBigInt; Data:PByte; Size:Integer);
Description: Take a bigint and convert it into a byte sequence
| Context | The bigint session context |
|---|---|
| BI | The bigint to be converted |
| Data | The converted data as a byte stream |
| Size | The maximum size of the byte stream. Unused bytes will be zeroed |
function BIImport(Context:PBigIntContext; Data:PByte; Size:Integer):PBigInt;
Description: Allow a binary sequence to be imported as a bigint
| Context | The bigint session context |
|---|---|
| Data | The data to be converted |
| Size | The number of bytes of data |
| Return | A bigint representing this data |
function IntToBI(Context:PBigIntContext; I:TComponent):PBigInt;
Description: Convert an (unsigned) integer into a bigint
| Context | The bigint session context |
|---|---|
| I | The (unsigned) integer to be converted |
function BIAdd(Context:PBigIntContext; BIA,BIB:PBigInt):PBigInt;
Description: Perform an addition operation between two bigints
| Context | The bigint session context |
|---|---|
| BIA | A bigint |
| BIB | Another bigint |
| Return | The result of the addition |
function BISubtract(Context:PBigIntContext; BIA,BIB:PBigInt; var IsNegative:Boolean):PBigInt;
Description: Perform a subtraction operation between two bigints
| Context | The bigint session context |
|---|---|
| BIA | A bigint |
| BIB | Another bigint |
| IsNegative | Indicates that the result was negative |
| Return | The result of the subtraction. The result is always positive. |
function BIDivide(Context:PBigIntContext; U,V:PBigInt; IsMod:Boolean):PBigInt;
Description: Does both division and modulo calculations
| Context | The bigint session context |
|---|---|
| U | A bigint which is the numerator |
| V | Either the denominator or the modulus depending on the mode |
| IsMod | Determines if this is a normal division (False) or a reduction (True) |
| Return | The result of the division/reduction |
function BIMultiply(Context:PBigIntContext; BIA,BIB:PBigInt):PBigInt;
Description: Perform a multiplication operation between two bigints
| Context | The bigint session context |
|---|---|
| BIA | A bigint |
| BIB | Another bigint |
| Return | The result of the multiplication |
function BIModPower(Context:PBigIntContext; BI,BIExp:PBigInt):PBigInt;
Description: Perform a modular exponentiation
| Context | The bigint session context |
|---|---|
| BI | The bigint on which to perform the mod power operation |
| BIExp | The bigint exponent |
| Return | The result of the mod exponentiation operation |
| Note | This function requires BISetMod() to have been called previously. This is one of the optimisations used for performance. |
function BIModPower2(Context:PBigIntContext; BI,BIM,BIExp:PBigInt):PBigInt;
Description: Perform a modular exponentiation using a temporary modulus
| Context | The bigint session context |
|---|---|
| BI | The bigint to perform the exp/mod |
| BIM | The temporary modulus |
| BIExp | The bigint exponent |
| Return | The result of the mod exponentiation operation |
| Note | We need this function to check the signatures of certificates. The modulus of this function is temporary as it's just used for authentication. |
function BICompare(BIA,BIB:PBigInt):Integer;
Description: Compare two bigints
| BIA | A bigint |
|---|---|
| BIB | Another bigint |
| Return | -1 if smaller, 1 if larger and 0 if equal |
procedure BISetMod(Context:PBigIntContext; BIM:PBigInt; ModOffset:Integer);
Description: Pre-calculate some of the expensive steps in reduction
| Context | The bigint session context |
|---|---|
| BIM | The bigint modulus that will be used |
| ModOffset | 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. |
| Note | This function should only be called once (normally when a session starts)
When the session is over, BIFreeMod() should be called. BIModPower() and BIMod() rely on this function being called. |
procedure BIFreeMod(Context:PBigIntContext; ModOffset:Integer);
Description: Used when cleaning various bigints at the end of a session
| Context | The bigint session context |
|---|---|
| ModOffset | The offset to use |
function BIMod(Context:PBigIntContext; BI:PBigInt):PBigInt; inline;
Description: Find the residue of BI
| Note | BISetMod() must be called beforehand |
|---|
function BIResidue(Context:PBigIntContext; BI:PBigInt):PBigInt; inline;
Description: BIResidue is simply an alias for BIBarrett
function BIBarrett(Context:PBigIntContext; BI:PBigInt):PBigInt;
Description: Perform a single Barrett reduction
| Context | The bigint session context |
|---|---|
| BI | A bigint |
| Return | The result of the Barrett reduction |
function BISquare(Context:PBigIntContext; BI:PBigInt):PBigInt;
Description: Perform a square operation on a bigint
| Context | The bigint session context |
|---|---|
| BI | A bigint |
| Return | The result of the multiplication |
function BICRT(Context:PBigIntContext; BI,DP,DQ,P,Q,QInv:PBigInt):PBigInt;
Description: Use the Chinese Remainder Theorem to quickly perform RSA decrypts
| Context | The bigint session context |
|---|---|
| BI | The bigint to perform the exp/mod |
| DP | CRT's dP bigint |
| DQ | CRT's dQ bigint |
| P | CRT's p bigint |
| Q | CRT's q bigint |
| QInv | CRT's qInv bigint |
| Return | The result of the CRT operation |
BigInt helper functions
function BIToString(BI:PBigInt):String;
Description: Convert a bigint to a string of hex characters
| BI | The bigint to convert |
|---|---|
| Return | A string representing the bigint |
function StringToBI(Context:PBigIntContext; const Value:String):PBigInt;
Description: Convert a string of hex characters to a bigint
| Context | The bigint session context |
|---|---|
| Value | A string consisting of hex characters |
| Return | A bigint representing this data |
Return to Unit Reference