From 2b8b55de4a18757e8d6769e458c84f7c1df1e261 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Mon, 13 Feb 2017 18:27:13 +1100 Subject: Swapped out crypto package for something smaller, revised other code and readme/notes slightly --- src/crypto-types-big_numbers-binfield_utils.adb | 319 ------------------------ 1 file changed, 319 deletions(-) delete mode 100644 src/crypto-types-big_numbers-binfield_utils.adb (limited to 'src/crypto-types-big_numbers-binfield_utils.adb') diff --git a/src/crypto-types-big_numbers-binfield_utils.adb b/src/crypto-types-big_numbers-binfield_utils.adb deleted file mode 100644 index 5835b6d..0000000 --- a/src/crypto-types-big_numbers-binfield_utils.adb +++ /dev/null @@ -1,319 +0,0 @@ --- 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. - - --- Most algorithms based on Kankerson, Menezes and Vanstones --- "Guide to Elliptic Curve Cryptograpyh" (ISBN: 0-387-95273-x) - - --- f(z) = 2^m + r(z) --- R is the binary representation of r(z) - -with Crypto.Asymmetric.Prime_Tables; - - -separate(Crypto.Types.Big_Numbers) - -package body Binfield_Utils is - - function B_Mod(Left : D_Big_Unsigned; Right : Big_Unsigned) - return Big_Unsigned; - - function "xor"(Left, Right: D_Big_Unsigned) return D_Big_Unsigned; - - procedure Set_Last_Index(X : in out D_Big_Unsigned); - - --------------------------------------------------------------------------- - - pragma Optimize (Time); - use Crypto.Asymmetric.Prime_Tables; - - -- compute: a(z) + b(z) mod f(z) - function B_Add(Left,Right : Big_Unsigned) return Big_Unsigned is - N : constant Natural := Natural'Max(Left.Last_Index, Right.Last_Index); - C : Big_Unsigned; - begin - for I in 0..N loop - C.Number(I) := Left.Number(i) xor Right.Number(I); - end loop; - - for I in reverse 0..N loop - if C.Number(I) /= 0 then - C.Last_Index :=I; - exit; - end if; - end loop; - - return C; - end B_Add; - - --------------------------------------------------------------------------- - - - -- compute: a(z) - b(z) mod f(z) - -- in binary field is -a = a. so a - b = a + (-b) = a + b - function B_Sub(Left,Right : Big_Unsigned) return Big_Unsigned is - begin - return B_Add(Left,Right); - end B_Sub; - - - --------------------------------------------------------------------------- - - -- compute: a(z)* z mod f(Z) - function B_Mult(A, F : Big_Unsigned) - return Big_Unsigned is - C : Big_Unsigned; - M : constant Positive := Bit_Length(F)-1; - N : Natural:= M/Word'Size; - begin - C := Shift_Left(A,1); - - if C.Last_Index = N then - N:=M mod Word'Size; - - if (Shift_Right(C.Number(C.Last_Index),N)) = 1 then - C := B_Add(C,F); - end if; - end if; - return C; - - end B_Mult; - - --------------------------------------------------------------------------- - - - --Algorithm 2.34: Right to left comb method for polynominal multiplication - -- compute: a(z)*b(z) mod f(Z) - function B_Mult(Left, Right, F : Big_Unsigned) return Big_Unsigned is - C : D_Big_Unsigned; - B : Big_Unsigned := Right; - -- N : constant Natural := Bit_Length(F); - begin - for K in 0..Word'Size-1 loop - for J in 0..Left.Last_Index loop - if (Shift_Right(Left.Number(J),K) and 1) = 1 then - -- add B to C{i} - for I in J..(J+B.Last_Index) loop - C.Number(I) := C.Number(I) xor B.Number(I-J); - end loop; - end if; - end loop; - if K /= Word'Size-1 then - B:=B_Mult(B,F); - end if; - end loop; - - Set_Last_Index(C); - - return B_Mod(C,F); - - end B_Mult; - - --------------------------------------------------------------------------- - - -- Algorithm 2.39: Polynominal squaring (with wordlength W=8) - -- compute a(z)**2 mod f(z) on a 8 bit processor - -- function B_Square8(A, F : Big_Unsigned) return Big_Unsigned is - -- C : D_Big_Unsigned; - -- L : Natural; - -- begin - -- for I in 0..A.Last_Index loop - -- L := 2*I; - -- C.Number(L) := Word(T8(Natural(A.Number(I) and 15))); - -- L:= L+1; - -- C.Number(L) := - -- Word(T8(Natural(Shift_Right(A.Number(I),4) and 15))); - -- end loop; - - -- Set_Last_Index(C); - - -- return B_Mod(C,F); - -- end B_Square8; - - ------------------------------------------------------------------------- - - -- Algorithm 2.39: Polynominal squaring (with word length W=n*8 for n=>0) - -- compute a(z)**2 mod f(z) - function B_Square(A, F : Big_Unsigned) return Big_Unsigned is - K : constant Natural := Word'Size/8; - N : constant Natural := K/2-1; - --M : constant Natural := Bit_Length(F); - L : Natural; - C : D_Big_Unsigned; - begin - for I in 0..A.Last_Index loop - L := 2*I; - for J in reverse 0..N loop - C.Number(L) := Shift_Left(C.Number(L),16) xor - Word(T16(Byte(Shift_Right(A.Number(I),8*J) and 255))); - end loop; - L:= L+1; - for J in reverse K/2..K-1 loop - C.Number(L) := Shift_Left(C.Number(L),16) xor - Word(T16(Byte(Shift_Right(A.Number(I),8*J) and 255))); - end loop; - end loop; - Set_Last_Index(C); - - return B_Mod(C,F); - end B_Square; - --------------------------------------------------------------------------- - - -- It' my own secret "blow and cut" technic. ;-) - -- compute left(z) mod right(z) - function B_Mod(Left, Right : Big_Unsigned) return Big_Unsigned is - A : Natural := Bit_Length(Left); - B : constant Natural := Bit_Length(Right); - Result : Big_Unsigned; - begin - if A < B or B=0 then - Result.Last_Index := Left.Last_Index; - Result.Number(0..Left.Last_Index) := Left.Number(0..Left.Last_Index); - else - while A >= B loop - Result := Shift_Left(Right,A-B) xor Right; - A := Bit_Length(Result); - end loop; - end if; - return Result; - end B_Mod; - - - - -------------------------------------------------------------------------- - - -- Algorithm 2.49: Binary algorithm for inversion in F_{2^m} - -- computes a(z)^{-1} - function B_Inverse(X, F : Big_Unsigned) return Big_Unsigned is - U : Big_Unsigned := X; - V : Big_Unsigned := F; - G1 : Big_Unsigned := Big_Unsigned_One; - G2 : Big_Unsigned; - begin - if X = Big_Unsigned_Zero or F = Big_Unsigned_Zero then - return F; - end if; - - while U /= Big_Unsigned_One and V /= Big_Unsigned_One loop - - while Is_Even(U) loop - U := Shift_Right(U,1); - if Is_Even(G1) then - G1 := Shift_Right(G1,1); - else - G1 := Shift_Right(B_Add(G1,F),1); - end if; - end loop; - - while Is_Even(V) loop - V := Shift_Right(V,1); - if Is_Even(G2) then - G2 := Shift_Right(G2,1); - else - G2 := Shift_Right(B_Add(G2,F),1); - end if; - end loop; - - if Bit_Length(U) > Bit_Length(V) then - U := B_Add(U,V); - G1 := B_Add(G1,G2); - else - V := B_Add(V,U); - G2 := B_Add(G2,G1); - end if; - end loop; - if U = Big_Unsigned_One then - return G1; - else - return G2; - end if; - end B_Inverse; - - -------------------------------------------------------------------------- - - function B_Div(Left, Right, F : Big_Unsigned) return Big_Unsigned is - R : constant Big_Unsigned := B_Inverse(Right, F); - begin - return B_Mult(Left,R,F); - end B_Div; - - -------------------------------------------------------------------------- - -------------------------------------------------------------------------- - - function B_Mod(Left : D_Big_Unsigned; Right : Big_Unsigned) - return Big_Unsigned is - A : Natural := Bit_Length(Left); - B : constant Natural := Bit_Length(Right); - Result : Big_Unsigned; - begin - if A < B or B=0 then - Result.Last_Index := Left.Last_Index; - Result.Number(0..Left.Last_Index) := Left.Number(0..Left.Last_Index); - else - declare - T : D_Big_Unsigned := Left; - Z : D_Big_Unsigned; - begin - Z.Last_Index := Right.Last_Index; - Z.Number(0..Right.Last_Index) := Right.Number(0..Right.Last_Index); - while A >= B loop - T := Shift_Left(Z,A-B) xor T; - A := Bit_Length(T); - end loop; - Result.Last_Index := T.Last_Index; - Result.Number(0..T.Last_Index) := T.Number(0..T.Last_Index); - end; - end if; - return Result; - end B_Mod; - - - -------------------------------------------------------------------------- - - function "xor"(Left, Right: D_Big_Unsigned) return D_Big_Unsigned is - Result : D_Big_Unsigned; - M : constant Natural:= Natural'Max(Left.Last_Index, Right.Last_Index); - begin - for I in 0..M loop - Result.Number(I) := Left.Number(I) xor Right.Number(I); - end loop; - Set_Last_Index(Result); - - return Result; - end "xor"; - - - -------------------------------------------------------------------------- - - procedure Set_Last_Index(X : in out D_Big_Unsigned) is - begin - for I in reverse 0..D_Max_Length loop - if X.Number(I) /= 0 then - X.Last_Index :=I; - exit; - end if; - end loop; - end Set_Last_Index; pragma Inline(Set_Last_Index); - -end Binfield_Utils; -- cgit