Skip to content

CryptAda.Big_Naturals

Jump to bottom
Antonio edited this page Jun 14, 2017 · 39 revisions

Contents

Overview

Cryptography is mostly a practical application of number theory, this package provides the core implementation of the numeric primitives that will be used by most of the cryptographic algorithms in CryptAda. This package provides an implementation of multiprecission natural number arithmetic.

CryptAda big natural numbers, as any other number, consist of a sequence of digits. In this case, in order to provide the capabilities required for cryptography aplications, each digit has a size of 32 bit so a single digit could represent values in the range 0 .. (2 ** 32) - 1 or, in decimal from 0 to 4,294,967,295.

CryptAda.Big_Naturals is a generic package that must be instantiated providing a positive generic argument which is the maximum number of digits a Big_Natural number could have. So, for example, if instantiated used the value 256, the Big_Natural type could represent values in the range 0 .. (2 ** 8196) - 1 or 8,196-bit values (which, by the way, could be insanely big numbers, you could check it out by using this calculator).

The name Big_Natural was provided by historical reasons and could be misleading because Big_Natural values could act as naturals and as modular values depending on the operations performed.

Taxonomy of operations on Big_Naturals

Operations provided in this package could be classified in the following way.

  1. Conversions from/to external representations. These operations provide functionality to set Big_Natural values for convenient external representations (Digit_Sequence, Byte_Array or Digit) and to get such a convenient representation from a Big_Natural value.
  2. Getting information of Big_Natural values. Obtaining the number of significant digits or the number of significant bits a Big_Natural value has.
  3. Comparison operators. That allow to compare two Big_Natural values, are implemented as the usual relational operators "=", ">", ">=", "<", and "<=".
  4. Arithmetic operations. Usual arithmetic operations: addition, subtraction, multiplication, squaring, division and remainder which are provided as procedures or as functions using the usual arithmetic operators ("+", "-", "*", "/", and "mod"). The set of operations is extended to allow for mixed operations among Big_Natural and Digit values.

Generic parameters

Max_Digits

generic
   Max_Digits                    : Positive;
package CryptAda.Big_Naturals is
   ...
end CryptAda.Big_Naturals;

Max_Digits is a positive value that specifies the maximum number of digits a Big_Natural value can have.

Next example instantiate Big_Naturals with Max_Digits set to 256 to handle 8,196-bit values.

with CryptAda.Big_Naturals;

...

declare
   package BN_8196 is new CryptAda.Big_Naturals(Max_Digits => 256);
   use BN_8196;

   Big_One     : Big_Natural;
begin
   ...
end;

Constants

Big_Natural sizing constants

The package declares the next public constants that set the number of bits a Big_Natural digit has and the maximum number of bits a Big_Natural value has for an specific instantiation:

Digit_Bits                    : constant Positive := 32;
Max_Bits                      : constant Positive := Digit_Bits * Max_Digits;

Big_Natural special values

Next constants represent special values for Big_Naturals. Zero, One and Two represent the three first values (0, 1, and 2) and Last represents the largest Big_Natural for a particular package instantiation.

Zero                          : constant Big_Natural;
One                           : constant Big_Natural;
Two                           : constant Big_Natural;
Last                          : constant Big_Natural;

Types

Digit

The type that represent the digits that conform a Big_Natural value.

subtype Digit is CryptAda.Pragmatics.Four_Bytes;

Digit_Sequence

Constrained array of Digit values that represent the sequence of digits of a Big_Natural value. This type is used as an external representation of Big_Natural values. In Digit_Sequences the order of the digits follows the Little_Endian convention that means the lowest the index the lesser the significance of the bytes.

subtype Digit_Sequence is CryptAda.Pragmatics.Four_Bytes_Array(1 .. Max_Digits);

Significant_Digits

Type whose values are used to represent the number of significant digits that Big_Natural values have.

subtype Significant_Digits is Natural range 0 .. Max_Digits;

Significant_Bits

Type whose values are used to represent the number of significant bits that Big_Natural values have.

subtype Significant_Bits is Natural range 0 .. Max_Bits;

Jacobi

Type for representing Jacobi symbols (Wikipedia).

subtype Jacobi is Integer range -1 .. 1;

Prime_Test_Result

Enumeration whose values represent the result returned by primality tests (Wikipedia). Composite indicates that the number object of test is composite and Prime indicates that the number is probably prime.

type Prime_Test_Result is (Composite, Prime);

Big_Natural

Private type that represent the Big_Natural values handled by this package.

type Big_Natural is private;

Subprograms

To_Big_Natural

Specification

function    To_Big_Natural(
               From           : in     CryptAda.Pragmatics.Byte_Array;
               Order          : in     CryptAda.Pragmatics.Byte_Order := CryptAda.Pragmatics.Little_Endian)
   return   Big_Natural;
      
function    To_Big_Natural(
               From           : in     Digit_Sequence)
   return   Big_Natural;
      
function    To_Big_Natural(
               From           : in     Digit)
   return   Big_Natural;

Purpose

These subprograms allow to create Big_Natural values from other external representations. Three overloaded forms are provided which allow to create Big_Natural values from Byte_Array, Digit_Sequence, and Digit values.

Arguments

  • From. Depending on the overloaded form either a Byte_Array, a Digit_Sequence, or a Digit value which will be converted to the Big_Natural value.
  • Order. In the first overloaded form, Byte_Order value that specifies the order of significance of bytes in the byte array From.

Returned value

All three forms return the Big_Natural value corresponding to the external representation.

Exceptions

  • CryptAda_Overflow_Error could be raised in the first overloaded form if the From Byte_Array could not be represented as a Big_Natural value.

Get_Digit_Sequence

Specification

function    Get_Digit_Sequence(
               From           : in     Big_Natural)
   return   Digit_Sequence;

Purpose

Returns the Digit_Sequence corresponding to a Big_Natural value.

Arguments

  • From. Big_Natural value to obtain its Digit_Sequence from.

Returned value

Digit_Sequence value representing the Big_Natural value. The returned sequence is padded with (unsignificant) 0 digits up to Max_Digits length.

Exceptions

None.

Get_Bytes

Specification

   function    Get_Bytes(
                  From           : in     Big_Natural;
                  Order          : in     CryptAda.Pragmatics.Byte_Order := CryptAda.Pragmatics.Little_Endian)
      return   CryptAda.Pragmatics.Byte_Array;

Purpose

Returns a Byte_Array value with the representation of a Big_Natural value.

Arguments

  • From. Big_Natural value to obtain its Bytes from.
  • Order. Byte_Order value that specifies the byte ordering in the returning Byte_Array.

Returned value

Byte_Array value corresponding to From in the specified Order. The byte array returned is unpadded.

Exceptions

None.

Get_Significant_Digits

Specification

   function    Get_Significant_Digits(
                  From           : in     Big_Natural)
      return   Significant_Digits;

Purpose

Returns the number of significant digits a Big_Natural value has.

Arguments

  • From. Big_Natural value to obtain its significant digits.

Returned value

Significant_Digits value with the number of significant digits in From. 0 if From = Zero.

Exceptions

None.

Get_Significant_Bits

Specification

   function    Get_Significant_Bits(
                  From           : in     Big_Natural)
      return   Significant_Bits;

Purpose

Returns the number of significant bits a Big_Natural value has.

Arguments

  • From. Big_Natural value to obtain its significant bits.

Returned value

Significant_Bits value with the number of significant bits in From. 0 if From = Zero.

Exceptions

None.

Comparision operators

Specification

   function    "="(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Boolean;
      
   function    ">"(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Boolean;

   function    ">="(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Boolean;
      
   function    "<"(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Boolean;

   function    "<="(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Boolean;

Purpose

These functions provide the full set of comparision operators for Big_Natural value. Their meaning is the usual meaning for those operators so no additional remarks are required.

Arguments

  • Left. First Big_Natural to compare.
  • Right. Second Big_Natural to compare.

Returned value

Boolean value with the result of comparision.

Exceptions

None.

Add

Specification

   procedure   Add(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural;
                  Sum            :    out Big_Natural);

   procedure   Add(
                  Left           : in     Big_Natural;
                  Right          : in     Digit;
                  Sum            :    out Big_Natural);

Purpose

These procedures implement arithmetic addition of Big_Natural values and the addition of a Big_Natural and a Digit value returning, as a Big_Natural, the result of addition.

Arguments

  • Left. Big_Natural summand.
  • Right. Either a Big_Natural or a Digit summad to add to Left.
  • Sum. Big_Natural value that, on procedure return, will contain addition result.

Exceptions

  • CryptAda_Overflow_Error will be raised if addition result could not be represented by a Big_Natural value.

Addition operator

Specification

   function    "+"(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Big_Natural;

   function    "+"(
                  Left           : in     Digit;
                  Right          : in     Big_Natural)
      return   Big_Natural;

   function    "+"(
                  Left           : in     Big_Natural;
                  Right          : in     Digit)
      return   Big_Natural;

Purpose

These functions provide the full set of addition operators for Big_Natural values and Digit values.

Arguments

  • Left. First summand, either a Big_Natural or a Digit depending on the overloaded form.
  • Right. Second summand either a Big_Natural or a Digit depending on the overloaded form.

Returned value

Big_Natural value with the result of addition.

Exceptions

  • CryptAda_Overflow_Error will be raised if addition result could not be represented by a Big_Natural value.

Subtract

Specification

   procedure   Subtract(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural;
                  Subt           :    out Big_Natural);

   procedure   Subtract(
                  Left           : in     Big_Natural;
                  Right          : in     Digit;
                  Subt           :    out Big_Natural);

Purpose

These procedures implement arithmetic subtraction of Big_Natural values and the subtration of a Digit value from a Big_Natural value. The procedures return subtraction result as an out Big_Natural argument.

Arguments

  • Left. Big_Natural minuend of subtraction.
  • Right. Either a Big_Natural or a Digit, subtrahend of subtraction.
  • Subt. Big_Natural value that, on procedure return, will contain subtraction result.

Exceptions

  • CryptAda_Underflow_Error will be raised if Right > Left.

Subtraction operator

Specification

   function    "-"(
                  Left           : in     Big_Natural;
                  Right          : in     Big_Natural)
      return   Big_Natural;

   function    "-"(
                  Left           : in     Big_Natural;
                  Right          : in     Digit)
      return   Big_Natural;

Purpose

Subtract either a Big_Natural value or a Digit value from a Big_Natural value and return subtraction result.

Arguments

  • Left. Minuend, a Big_Natural value.
  • Right. Subtrahend, either a Big_Natural or a Digit depending on the overloaded form.

Returned value

Big_Natural value with the result of subtraction.

Exceptions

  • CryptAda_Underflow_Error will be raised if Right > Left.
Clone this wiki locally