Unit Big Integer

From Ultibo.org
Revision as of 04:19, 19 April 2018 by Ultibo (Talk | contribs)

Jump to: navigation, search

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
Return A 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
Note None documented 


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
Note None documented 


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

Retrieved from "https://ultibo.org/mediawiki_ultibo_org/index.php?title=Unit_Big_Integer&oldid=3705"