Difference between revisions of "Unit Big Integer"

From Ultibo.org
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
----
 
----
  
−
'''Ultibo Big Integer interface unit'''
+
'''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.
 
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.
Line 14: Line 14:
 
----
 
----
  
−
''To be documented''
+
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 20px; padding-bottom: 15px;">
 +
<div style="font-size: 14px; padding-left: 12px;">'''BigInt specific constants''' <code> BIGINT_* </code></div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
|colspan="2"|Maintain a number of precomputed variables when doing reduction
 +
|-
 +
| <code>BIGINT_M_OFFSET = 0;</code>
 +
| Normal modulo offset
 +
|-
 +
| <code>BIGINT_P_OFFSET = 1;</code>
 +
| P modulo offset
 +
|-
 +
| <code>BIGINT_Q_OFFSET = 2;</code>
 +
| Q modulo offset
 +
|-
 +
| <code>BIGINT_NUM_MODS = 3;</code>
 +
| The number of modulus constants used
 +
|-
 +
|colspan="2"|&nbsp;
 +
|-
 +
| <code>BIGINT_COMP_RADIX = UInt64(4294967296);</code>
 +
| Max component + 1
 +
|-
 +
| <code>BIGINT_COMP_MAX = UInt64($FFFFFFFFFFFFFFFF);</code>
 +
| Max dbl component - 1
 +
|-
 +
| <code>BIGINT_COMP_BIT_SIZE = 32;</code>
 +
| Number of bits in a component
 +
|-
 +
| <code>BIGINT_COMP_BYTE_SIZE = 4;</code>
 +
| Number of bytes in a component
 +
|-
 +
| <code>BIGINT_COMP_NUM_NIBBLES = 8;</code>
 +
| Used for diagnostics only
 +
|-
 +
|colspan="2"|&nbsp;
 +
|-
 +
| <code>BIGINT_PERMANENT = $7FFF55AA;</code>
 +
| A magic number for permanents
 +
|-
 +
|}
 +
</div></div>
 +
<br />
  
 
=== Type definitions ===
 
=== Type definitions ===
 
----
 
----
  
−
''To be documented''
+
 
 +
'''Component'''
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial;">
 +
<code>PComponent = ^TComponent;</code>
 +
 
 +
<code>TComponent = LongWord;</code>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
|colspan="2"|A single precision component
 +
|-
 +
| &nbsp;
 +
| style="width: 50%;"|&nbsp;
 +
|-
 +
|}
 +
</div></div>
 +
 
 +
'''Long component'''
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial;">
 +
<code>PLongComponent = ^TLongComponent;</code>
 +
 
 +
<code>TLongComponent = UInt64;</code>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
|colspan="2"|A double precision component
 +
|-
 +
| &nbsp;
 +
| style="width: 50%;"|&nbsp;
 +
|-
 +
|}
 +
</div></div>
 +
 +
'''Signed long component'''
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial;">
 +
<code>PSignedLongComponent = ^TSignedLongComponent;</code>
 +
 
 +
<code>TSignedLongComponent = Int64;</code>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
|colspan="2"|A signed double precision component
 +
|-
 +
| &nbsp;
 +
| style="width: 50%;"|&nbsp;
 +
|-
 +
|}
 +
</div></div>
 +
 
 +
'''BigInt'''
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial;">
 +
<code>PPBigInt = ^PBigInt;</code>
 +
 
 +
<code>PBigInt = ^TBigInt;</code>
 +
 
 +
<code>TBigInt = record</code>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
|colspan="2"|A big integer basic object
 +
|-
 +
| <code>Next:PBigInt;</code>
 +
| The next bigint in the cache
 +
|-
 +
| <code>Size:Integer;</code>
 +
| The number of components in this bigint
 +
|-
 +
| <code>MaxComponents:Integer;</code>
 +
| The number of components allocated for this bigint
 +
|-
 +
| <code>References:Integer;</code>
 +
| An internal reference count
 +
|-
 +
| <code>Components:PComponent;</code>
 +
| A ptr to the actual component data
 +
|-
 +
|colspan="2"|&nbsp;
 +
|-
 +
| <code>procedure Zero;</code>
 +
| &nbsp;
 +
|-
 +
| <code>procedure Clear;</code>
 +
| &nbsp;
 +
|-
 +
|colspan="2"|&nbsp;
 +
|-
 +
| <code>function ToString:String;</code>
 +
| &nbsp;
 +
|-
 +
|}
 +
</div></div>
 +
 
 +
'''BigInt context'''
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial;">
 +
<code>PBigIntContext = ^TBigIntContext;</code>
 +
 
 +
<code>TBigIntContext = record</code>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
|colspan="2"|Maintains the state of the cache, and a number of variables used in reduction.
 +
|-
 +
| <code>ActiveList:PBigInt;</code>
 +
| Bigints currently used
 +
|-
 +
| <code>FreeList:PBigInt;</code>
 +
| Bigints not used
 +
|-
 +
| <code>BIRadix:PBigInt;</code>
 +
| The radix used
 +
|-
 +
| <code>BIMod:array[0..BIGINT_NUM_MODS - 1] of PBigInt;</code>
 +
| Modulus
 +
|-
 +
|colspan="2"|&nbsp;
 +
|-
 +
| <code>BImu:array[0..BIGINT_NUM_MODS - 1] of PBigInt;</code>
 +
| Storage for mu
 +
|-
 +
| <code>BIbk1:array[0..BIGINT_NUM_MODS - 1] of PBigInt;</code>
 +
| Storage for b(k+1)
 +
|-
 +
| <code>BINormalisedMod:array[0..BIGINT_NUM_MODS - 1] of PBigInt;</code>
 +
| Normalised mod storage
 +
|-
 +
| <code>G:PPBigInt;</code>
 +
| Used by sliding-window
 +
|-
 +
| <code>Window:Integer;</code>
 +
| The size of the sliding window
 +
|-
 +
| <code>ActiveCount:Integer;</code>
 +
| Number of active bigints
 +
|-
 +
| <code>FreeCount:Integer;</code>
 +
| Number of free bigints
 +
|-
 +
|colspan="2"|&nbsp;
 +
|-
 +
| <code>ModOffset:Byte;</code>
 +
| The mod offset we are using
 +
|-
 +
|}
 +
</div></div>
 +
<br />
  
 
=== Public variables ===
 
=== Public variables ===
 
----
 
----
  
−
''To be documented''
+
''None defined''
  
 
=== Function declarations ===
 
=== Function declarations ===
 
----
 
----
  
−
''To be documented''
 
  
 +
'''BigInt functions'''
 +
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIInitialize:PBigIntContext;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Start a new bigint context</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Return
 +
| A bigint context
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BITerminate(Context:PBigIntContext);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Close the bigint context and free any resources</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BIPermanent(BI:PBigInt);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Make a bigint object "unfreeable" if BIFree() is called on it</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! BI
 +
| The bigint to be made permanent
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BIDepermanent(BI:PBigInt);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Take a permanent object and make it freeable</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! BI
 +
| The bigint to be made freeable
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BIClearCache(Context:PBigIntContext);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Clear the memory cache</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Note
 +
| None documented
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BIFree(Context:PBigIntContext; BI:PBigInt);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Free a bigint object so it can be used again</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! BI
 +
| The bigint to be freed
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BICopy(BI:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Increment the number of references to this object</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! BI
 +
| The bigint to copy
 +
|-
 +
! Return
 +
| A reference to the same bigint
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIClone(Context:PBigIntContext; const BI:TBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Do a full copy of the bigint object</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! BI
 +
| The bigint object to be copied
 +
|-
 +
! Return
 +
| A copy of the bigint object
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BIExport(Context:PBigIntContext; BI:PBigInt; Data:PByte; Size:Integer);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Take a bigint and convert it into a byte sequence</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIImport(Context:PBigIntContext; Data:PByte; Size:Integer):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Allow a binary sequence to be imported as a bigint</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! Data
 +
| The data to be converted
 +
|-
 +
! Size
 +
| The number of bytes of data
 +
|-
 +
! Return
 +
| A bigint representing this data
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function IntToBI(Context:PBigIntContext; I:TComponent):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Convert an (unsigned) integer into a bigint</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! I
 +
| The (unsigned) integer to be converted
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIAdd(Context:PBigIntContext; BIA,BIB:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform an addition operation between two bigints</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! BIA
 +
| A bigint
 +
|-
 +
! BIB
 +
| Another bigint
 +
|-
 +
! Return
 +
| The result of the addition
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BISubtract(Context:PBigIntContext; BIA,BIB:PBigInt; var IsNegative:Boolean):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform a subtraction operation between two bigints</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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.
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIDivide(Context:PBigIntContext; U,V:PBigInt; IsMod:Boolean):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Does both division and modulo calculations</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIMultiply(Context:PBigIntContext; BIA,BIB:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform a multiplication operation between two bigints</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! BIA
 +
| A bigint
 +
|-
 +
! BIB
 +
| Another bigint
 +
|-
 +
! Return
 +
| The result of the multiplication
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIModPower(Context:PBigIntContext; BI,BIExp:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform a modular exponentiation</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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.
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIModPower2(Context:PBigIntContext; BI,BIM,BIExp:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform a modular exponentiation using a temporary modulus</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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.
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BICompare(BIA,BIB:PBigInt):Integer;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Compare two bigints</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! BIA
 +
| A bigint
 +
|-
 +
! BIB
 +
| Another bigint
 +
|-
 +
! Return
 +
| -1 if smaller, 1 if larger and 0 if equal
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BISetMod(Context:PBigIntContext; BIM:PBigInt; ModOffset:Integer);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Pre-calculate some of the expensive steps in reduction</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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.
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">procedure BIFreeMod(Context:PBigIntContext; ModOffset:Integer);</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Used when cleaning various bigints at the end of a session</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! ModOffset
 +
| The offset to use
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIMod(Context:PBigIntContext; BI:PBigInt):PBigInt; inline;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Find the residue of BI</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Note
 +
| BISetMod() must be called beforehand
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIResidue(Context:PBigIntContext; BI:PBigInt):PBigInt; inline;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' BIResidue is simply an alias for BIBarrett</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Note
 +
| None documented
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIBarrett(Context:PBigIntContext; BI:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform a single Barrett reduction</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! BI
 +
| A bigint
 +
|-
 +
! Return
 +
| The result of the Barrett reduction
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BISquare(Context:PBigIntContext; BI:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Perform a square operation on a bigint</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! BI
 +
| A bigint
 +
|-
 +
! Return
 +
| The result of the multiplication
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BICRT(Context:PBigIntContext; BI,DP,DQ,P,Q,QInv:PBigInt):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Use the Chinese Remainder Theorem to quickly perform RSA decrypts</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! 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
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
 +
'''BigInt helper functions'''
 +
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function BIToString(BI:PBigInt):String;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Convert a bigint to a string of hex characters</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! BI
 +
| The bigint to convert
 +
|-
 +
! Return
 +
| A string representing the bigint
 +
|-
 +
|}
 +
</div></div>
 +
<br />
 +
<div class="toccolours mw-collapsible mw-collapsed" style="border: 1; font-family: arial; padding-top: 0px; padding-bottom: 15px;">
 +
<pre style="border: 0; padding-bottom:0px;">function StringToBI(Context:PBigIntContext; const Value:String):PBigInt;</pre>
 +
<div style="font-size: 14px; padding-left: 12px;">'''Description:''' Convert a string of hex characters to a bigint</div>
 +
<div class="mw-collapsible-content" style="text-align: left; padding-left: 5px;">
 +
{| class="wikitable" style="font-size: 14px; background: white;"
 +
|-
 +
! Context
 +
| The bigint session context
 +
|-
 +
! Value
 +
| A string consisting of hex characters
 +
|-
 +
! Return
 +
| A bigint representing this data
 +
|-
 +
|}
 +
</div></div>
 +
<br />
  
 
Return to [[Unit_Reference|Unit Reference]]
 
Return to [[Unit_Reference|Unit Reference]]

Latest revision as of 04:40, 31 August 2021

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=5052"