-- This program is free software; you can redistribute it and/or -- modify it under the terms of the GNU General Public License as -- published by the Free Software Foundation; either version 2 of the -- License, or (at your option) any later version. -- This program is distributed in the hope that it will be useful, -- but WITHOUT ANY WARRANTY; without even the implied warranty of -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -- General Public License for more details. -- You should have received a copy of the GNU General Public License -- along with this program; if not, write to the Free Software -- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA -- 02111-1307, USA. -- As a special exception, if other files instantiate generics from -- this unit, or you link this unit with other files to produce an -- executable, this unit does not by itself cause the resulting -- executable to be covered by the GNU General Public License. This -- exception does not however invalidate any other reasons why the -- executable file might be covered by the GNU Public License. -- With this packet you can generate (unsigned) n-Bit Numbers (Big_Unsigned). -- You can only create k*m Bit-Numbers where 1 < k < 2**32 and m is the -- size of a CPU-Word. For further informations read the ACL documentation. -- The look and feel is "borrowed" from J. Delcourt BIG_NUMBER package. -- First I want to use Delcourts package directly, but then I decided to -- rewrite it completly form scratch. ;-) with System; with Crypto.Types; use Crypto.Types; generic Size : Positive; package Crypto.Types.Big_Numbers is type Big_Unsigned is private; subtype Number_Base is Integer range 2 .. 16; -- Do not use this type. This one is only needed for internal purpose. type D_Big_Unsigned is private; --------------------------------------------------------------------------- ---------------------------Constants--------------------------------------- --------------------------------------------------------------------------- -- A few constants Big_Unsigned_Zero : constant Big_Unsigned; -- 0 Big_Unsigned_One : constant Big_Unsigned; -- 1 Big_Unsigned_Two : constant Big_Unsigned; -- 2 Big_Unsigned_Three : constant Big_Unsigned; -- 3 Big_Unsigned_Four : constant Big_Unsigned; -- 4 Big_Unsigned_Ten : constant Big_Unsigned; -- 10 Big_Unsigned_Sixteen : constant Big_Unsigned; -- 16 Big_Unsigned_First : constant Big_Unsigned; -- 0 Big_Unsigned_Last : constant Big_Unsigned; -- "Big_Unsigned'Last" --------------------------------------------------------------------------- ----------------------------Compare---------------------------------------- --------------------------------------------------------------------------- -- compare: Big Unsigned with Big_Unsigned function "="(Left, Right : Big_Unsigned) return Boolean; function "<"(Left, Right : Big_Unsigned) return Boolean; function ">"(Left, Right : Big_Unsigned) return Boolean; function "<="(Left, Right : Big_Unsigned) return Boolean; function ">="(Left, Right : Big_Unsigned) return Boolean; function Min(X, Y : in Big_Unsigned) return Big_Unsigned; function Max(X, Y : in Big_Unsigned) return Big_Unsigned; -- compare: Big Unsigned with Word function "="(Left : Big_Unsigned; Right : Word) return Boolean; function "="(Left : Word; Right : Big_Unsigned) return Boolean; function "<"(Left : Big_Unsigned; Right : Word) return Boolean; function "<"(Left : Word; Right : Big_Unsigned) return Boolean; function ">"(Left : Big_Unsigned; Right : Word) return Boolean; function ">"(Left : Word; Right : Big_Unsigned) return Boolean; function "<="(Left : Big_Unsigned; Right : Word) return Boolean; function "<="(Left : Word; Right : Big_Unsigned) return Boolean; function ">="(Left : Big_Unsigned; Right : Word) return Boolean; function ">="(Left : Word; Right : Big_Unsigned) return Boolean; --------------------------------------------------------------------------- -----------------------------Basic----------------------------------------- --------------------------------------------------------------------------- function "+"(Left, Right : Big_Unsigned) return Big_Unsigned; function "+"(Left : Big_Unsigned; Right : Word) return Big_Unsigned; function "+"(Left : Word; Right : Big_Unsigned) return Big_Unsigned; function "-"(Left, Right : Big_Unsigned) return Big_Unsigned; function "-"(Left : Big_Unsigned; Right : Word) return Big_Unsigned; function "-"(Left : Word; Right : Big_Unsigned) return Big_Unsigned; function "-"(X : Big_Unsigned) return Big_Unsigned; function "*"(Left, Right : Big_Unsigned) return Big_Unsigned; --============================================================================-- function Russ (Left, Right : Big_Unsigned) return Big_Unsigned; function Karatsuba (Left, Right : Big_Unsigned) return Big_Unsigned; function Karatsuba_P (Left, Right : Big_Unsigned) return Big_Unsigned; -- function Karatsuba_Prot (Left, Right : Big_Unsigned) return Big_Unsigned; function Toom_Cook (Left, Right : Big_Unsigned) return Big_Unsigned; function Toom_Cook_P (Left, Right : Big_Unsigned) return Big_Unsigned; --============================================================================-- function "*"(Left : Big_Unsigned; Right : Word) return Big_Unsigned; function "*"(Left : Word; Right : Big_Unsigned) return Big_Unsigned; function "/"(Left, Right : Big_Unsigned) return Big_Unsigned; function "/"(Left : Big_Unsigned; Right : Word) return Big_Unsigned; function "/"(Left : Word; Right : Big_Unsigned) return Big_Unsigned; function "xor"(Left, Right : Big_Unsigned) return Big_Unsigned; function "or" (Left, Right : Big_Unsigned) return Big_Unsigned; function "and"(Left, Right : Big_Unsigned) return Big_Unsigned; function "and"(Left: Big_Unsigned; Right: Word) return Big_Unsigned; function "and"(Left: Word; Right: Big_Unsigned) return Big_Unsigned; function "**"(Left, Right : Big_Unsigned) return Big_Unsigned; function "mod"(Left, Right : Big_Unsigned) return Big_Unsigned; function "mod"(Left : Big_Unsigned; Right : Word) return Big_Unsigned; --------------------------------------------------------------------------- ----------------------------Utils------------------------------------------ --------------------------------------------------------------------------- package Utils is procedure Swap(X, Y : in out Big_Unsigned); procedure Set_Least_Significant_Bit(X : in out Big_Unsigned); procedure Set_Most_Significant_Bit(X : in out Big_Unsigned); -- Returns true if X is odd . function Is_Odd(X : Big_Unsigned) return Boolean; -- Returns true if X is even. function Is_Even(X : Big_Unsigned) return Boolean; -- Caution: All operations are mod Big_unsigned_Last+1. -- X = Big_unsigned_Zero -- Inc(X) -- X = Big_Unsigned_Last -- Dec(X) -- X = Big_unsigned_Zero procedure Inc(X : in out Big_Unsigned); procedure Dec(X : in out Big_Unsigned); function To_Big_Unsigned(X : Word) return Big_Unsigned; function Shift_Left(Value : Big_Unsigned; Amount : Natural) return Big_Unsigned; function Shift_Right(Value : Big_Unsigned; Amount : Natural) return Big_Unsigned; function Rotate_Left(Value : Big_Unsigned; Amount : Natural) return Big_Unsigned; function Rotate_Right(Value : Big_Unsigned; Amount : Natural) return Big_Unsigned; function Get_Random return Big_Unsigned; function Bit_Length(X : Big_Unsigned) return Natural; function Lowest_Set_Bit(X : Big_Unsigned) return Natural; function Length_In_Bytes(X : Big_Unsigned) return Natural; function Gcd(Left, Right : Big_Unsigned) return Big_Unsigned; function To_Bytes(X : Big_Unsigned) return Bytes; function To_Big_Unsigned(X : Bytes) return Big_Unsigned; function To_Words(X : Big_Unsigned) return Words; function To_Big_Unsigned(X : Words) return Big_Unsigned; function To_String(Item : Big_Unsigned; Base : Number_Base := 10) return String; function To_Big_Unsigned(S : String) return Big_Unsigned; procedure Put(Item : in Big_Unsigned; Base : in Number_Base := 10); procedure Put_Line(Item : in Big_Unsigned; Base : in Number_Base := 10); procedure Big_Div(Dividend, Divisor : in Big_Unsigned; Quotient, Remainder : out Big_Unsigned); procedure Short_Div(Dividend : in Big_Unsigned; Divisor : in Word; Quotient : out Big_Unsigned; Remainder : out Word); end Utils; --------------------------------------------------------------------------- --------------------------Mod_Utils---------------------------------------- --------------------------------------------------------------------------- package Mod_Utils is -- All operations in this package are mod N function Add (Left, Right, N : Big_Unsigned) return Big_Unsigned; function Sub (Left, Right, N : Big_Unsigned) return Big_Unsigned; function Div (Left, Right, N : Big_Unsigned) return Big_Unsigned; function Mult(Left, Right, N : Big_Unsigned) return Big_Unsigned; -- function Barrett(Left, Right, M : Big_Unsigned) return Big_Unsigned; -- function Mult_School(Left, Right, N : Big_Unsigned) return Big_Unsigned; function Pow (Base, Exponent, N : Big_Unsigned) return Big_Unsigned; -- Returns a random Big_Unsigned mod N function Get_Random (N : Big_Unsigned) return Big_Unsigned; function Inverse (X, N : Big_Unsigned) return Big_Unsigned; -- This function returns with an overwhelming probability a prim function Get_Prime(N : Big_Unsigned) return Big_Unsigned; -- This function returns with an overwhelming probability a n-bit prim function Get_N_Bit_Prime(N : Positive) return Big_Unsigned; -- This function returns true if X is a prim and -- with an overwhelming probability false if X is not prime -- The change that a snowball survive one day in hell are greater that -- this function returns true if X is no prim. -- functionality: -- 1. Test if a one digit prime (2,3,5,7) divides X -- 2. Test if a two digit prime number divides X -- 3. Test if X is a "Lucas-Lehmer" prime -- 4. Test if a three digit prime number divides X -- 5. compute N random Big_Unsigneds and test if one -- of those is an Miller-Rabin wittness ( 1 < N < 51) -- (N depends on the Bit_Length of X). function Is_Prime(X : Big_Unsigned) return Boolean; -- a weaker but faster prime test function Looks_Like_A_Prime(X : Big_Unsigned) return Boolean; -- Returns only true if X passed n iterations of the -- Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS -- 186-2).The execution time of this function is proportional -- to the value of this parameter. -- The probability that a pseudoprim pass this test is < (1/(2**(2*S))) function Passed_Miller_Rabin_Test(X : Big_Unsigned; S : Positive) return Boolean; function Jacobi(X, N : Big_Unsigned) return Integer; -- internal functions for Binfield_Utils. Please, DON'T use them. function Shift_Left(Value : D_Big_Unsigned; Amount : Natural) return D_Big_Unsigned; function Bit_Length(X : D_Big_Unsigned) return Natural; end Mod_Utils; --------------------------------------------------------------------------- --------------------------------------------------------------------------- --------------------------------------------------------------------------- package Binfield_Utils is -- binary field operations -- F is the irreducible polynom with f(z)=2^m + r(z) -- Remember all operations are in GF(2^m) function B_Add(Left,Right : Big_Unsigned) return Big_Unsigned; function B_Sub(Left,Right : Big_Unsigned) return Big_Unsigned; function B_Mult(Left, Right, F : Big_Unsigned) return Big_Unsigned; function B_Div (Left, Right, F : Big_Unsigned) return Big_Unsigned; function B_Square(A, F : Big_Unsigned) return Big_Unsigned; function B_Mod(Left, Right : Big_Unsigned) return Big_Unsigned; function B_Inverse(X, F : Big_Unsigned) return Big_Unsigned; end Binfield_Utils; --------------------------------------------------------------------------- -----------------------------Exceptions------------------------------------ --------------------------------------------------------------------------- Constraint_Size_Error : exception; Division_By_Zero : exception; Conversion_Error : exception; Is_Zero_Error : exception; -- Big_Unsigned_Overflow : exception; -- Big_Unsigned_Negative : exception; --------------------------------------------------------------------------- --------------------------------PRIVATE------------------------------------ --------------------------------------------------------------------------- private type Largest_Unsigned is mod System.Max_Binary_Modulus; Max_Length : Natural := (Size/Word'Size)-1; D_Max_Length : Positive := 2*Max_Length+1; subtype Limbs is Words(0..Max_Length); subtype DLimbs is Words(0..D_Max_Length); subtype M_Len is Natural range Limbs'Range; -- This is our Big_Unsigned -- It represents a Size*Word'Size-bit number -- Last_Index is the Number of the last slice who -- contains the most significant bit of the current number. -- Ex.: -- Word'Size = 24 -- Our Big_Unsigned A is equal to 2**100-7 -- Big_Unsignesd_Last = 2**240-1 -- So only Slice 0-4 contains a part of the current 99-Bit number (2**100-7) -- In this case A.Last_Index = 4 because A.X(5)=...=A.X(9)=0 type Big_Unsigned is record Last_Index : Natural:=0; Number : Limbs:=(others => 0); end record; type D_Big_Unsigned is record Last_Index : Natural:=0; Number : DLimbs:=(others => 0); end record; -- prime test type Hardness is (Weak, Strong); -- Constants definitions Big_Unsigned_Zero : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (OTHERS => 0)); Big_Unsigned_One : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (0 => 1, OTHERS => 0)); Big_Unsigned_Two : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (0 => 2, OTHERS => 0)); Big_Unsigned_Three : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (0 => 3, OTHERS => 0)); Big_Unsigned_Four : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (0 => 4, OTHERS => 0)); Big_Unsigned_Ten : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (0 => 10, OTHERS => 0)); Big_Unsigned_Sixteen : CONSTANT Big_Unsigned := (Last_Index => 0, Number => (0 => 16, OTHERS => 0)); Big_Unsigned_First : CONSTANT Big_Unsigned := Big_Unsigned_Zero; Big_Unsigned_Last : CONSTANT Big_Unsigned := (Last_Index => Max_Length, Number => (OTHERS => Word'Last)); D_Big_Unsigned_Zero : CONSTANT D_Big_Unsigned := (Last_Index => 0, Number => (OTHERS => 0)); D_Big_Unsigned_One : CONSTANT D_Big_Unsigned := (Last_Index => 0, Number => (0 => 1, OTHERS => 0)); D_Big_Unsigned_Last : CONSTANT D_Big_Unsigned := (Last_Index => D_Max_Length, Number => (OTHERS => Word'Last)); -- Shifting function Shift_Left (Value : Largest_Unsigned; Amount : Natural) return Largest_Unsigned; function Shift_Right (Value : Largest_Unsigned; Amount : Natural) return Largest_Unsigned; --pragma Inline("-", "/", "**", "mod", "xor", "and", "or"); pragma Inline("=", "<", ">", "<=", ">=", Min, Max); pragma Import (Intrinsic, Shift_Left); pragma Import (Intrinsic, Shift_Right); pragma Optimize (Time); end Crypto.Types.Big_Numbers;