1 ------------------------------------------------------------------------------ 2 ------------------------------------------------------------------------------ 3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. -- 4 -- -- 5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) -- 6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html -- 7 -- -- 8 -- You do not have, nor can you ever acquire the right to use, copy or -- 9 -- distribute this software ; Should you use this software for any purpose, -- 10 -- or copy and distribute it to anyone or in any manner, you are breaking -- 11 -- the laws of whatever soi-disant jurisdiction, and you promise to -- 12 -- continue doing so for the indefinite future. In any case, please -- 13 -- always : read and understand any software ; verify any PGP signatures -- 14 -- that you use - for any purpose. -- 15 -- -- 16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . -- 17 ------------------------------------------------------------------------------ 18 ------------------------------------------------------------------------------ 19 20 with Words; use Words; 21 with W_Shifts; use W_Shifts; 22 with FZ_Basic; use FZ_Basic; 23 with FZ_Mul; use FZ_Mul; 24 with FZ_Sqr; use FZ_Sqr; 25 with FZ_Divis; use FZ_Divis; 26 27 28 package body FZ_ModEx is 29 30 -- (Conventional) Modular Multiply: Product := X*Y mod Modulus 31 procedure FZ_Mod_Mul(X : in FZ; 32 Y : in FZ; 33 Modulus : in FZ; 34 Product : out FZ) is 35 36 -- The wordness of all three operands is equal: 37 L : constant Indices := X'Length; 38 39 -- Double-width register for multiplication and modulus operations 40 XY : FZ(1 .. L * 2); 41 42 -- To refer to the lower and upper halves of the working register: 43 XY_Lo : FZ renames XY(1 .. L); 44 XY_Hi : FZ renames XY(L + 1 .. XY'Last); 45 46 begin 47 48 -- XY_Lo:XY_Hi := X * Y 49 FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi); 50 51 -- Product := XY mod M 52 FZ_Mod(XY, Modulus, Product); 53 54 end FZ_Mod_Mul; 55 56 57 -- (Conventional) Modular Squaring: Product := X*X mod Modulus 58 procedure FZ_Mod_Sqr(X : in FZ; 59 Modulus : in FZ; 60 Product : out FZ) is 61 62 -- The wordness of both operands is equal: 63 L : constant Indices := X'Length; 64 65 -- Double-width register for squaring and modulus operations 66 XX : FZ(1 .. L * 2); 67 68 -- To refer to the lower and upper halves of the working register: 69 XX_Lo : FZ renames XX(1 .. L); 70 XX_Hi : FZ renames XX(L + 1 .. XX'Last); 71 72 begin 73 74 -- XX_Lo:XX_Hi := X^2 75 FZ_Square_Buffered(X, XX_Lo, XX_Hi); 76 77 -- Product := XX mod M 78 FZ_Mod(XX, Modulus, Product); 79 80 end FZ_Mod_Sqr; 81 82 83 -- (Barrettronic) Modular Squaring, using given Barrettoid 84 procedure FZ_Mod_Sqr_Barrett(X : in FZ; 85 Bar : in Barretoid; 86 Product : out FZ) is 87 88 -- The wordness of both operands is equal: 89 L : constant Indices := X'Length; 90 91 -- Double-width register for squaring and modulus operations 92 XX : FZ(1 .. L * 2); 93 94 -- To refer to the lower and upper halves of the working register: 95 XX_Lo : FZ renames XX(1 .. L); 96 XX_Hi : FZ renames XX(L + 1 .. XX'Last); 97 98 begin 99 100 -- XX_Lo:XX_Hi := X^2 101 FZ_Square_Buffered(X, XX_Lo, XX_Hi); 102 103 -- Product := XX mod M 104 FZ_Barrett_Reduce(X => XX, Bar => Bar, XReduced => Product); 105 106 end FZ_Mod_Sqr_Barrett; 107 108 109 -- Barrettronic Modular Exponent, using given Barrettoid 110 procedure FZ_Mod_Exp_Barrett(Base : in FZ; 111 Exponent : in FZ; 112 Bar : in Barretoid; 113 Result : out FZ) is 114 115 -- Double-width scratch buffer for the modular operations 116 D : FZ(1 .. Base'Length * 2); 117 118 -- Working register for the squaring; initially is copy of Base 119 B : FZ(Base'Range) := Base; 120 121 -- Register for the Mux operation 122 T : FZ(Result'Range); 123 124 -- Buffer register for the Result 125 R : FZ(Result'Range); 126 127 begin 128 129 -- Result := 1 130 WBool_To_FZ(1, R); 131 132 -- For each Word of the Exponent: 133 for i in Exponent'Range loop 134 135 declare 136 137 -- The current Word of the Exponent 138 Wi : Word := Exponent(i); 139 140 begin 141 142 -- For each bit of Wi: 143 for j in 1 .. Bitness loop 144 145 -- T := Result * B mod Modulus 146 FZ_Multiply_Unbuffered(X => R, Y => B, XY => D); 147 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T); 148 149 -- Sel is the current bit of Exponent; 150 -- When Sel=0 -> Result := Result; 151 -- When Sel=1 -> Result := T 152 FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1); 153 154 -- Advance to the next bit of Wi (i.e. next bit of Exponent) 155 Wi := Shift_Right(Wi, 1); 156 157 -- B := B^2 mod Modulus 158 FZ_Square_Unbuffered(X => B, XX => D); 159 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B); 160 161 end loop; 162 163 end; 164 165 end loop; 166 167 -- Output the Result: 168 Result := R; 169 170 end FZ_Mod_Exp_Barrett; 171 172 173 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus 174 procedure FZ_Mod_Exp(Base : in FZ; 175 Exponent : in FZ; 176 Modulus : in FZ; 177 Result : out FZ) is 178 179 -- Space for Barrettoid 180 Bar : Barretoid(ZXMLength => Modulus'Length + 1, 181 BarretoidLength => 2 * Base'Length); 182 183 begin 184 185 -- First, pre-compute the Barretoid for the given Modulus: 186 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar); 187 188 -- Compute the modular exponentiation using the above Barrettoid: 189 FZ_Mod_Exp_Barrett(Base => Base, 190 Exponent => Exponent, 191 Bar => Bar, 192 Result => Result); 193 194 end FZ_Mod_Exp; 195 196 end FZ_ModEx;