“Finite Field Arithmetic.” Chapter 8: Interlude: Randomism.
This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical "Open Sores" abomination, in that -- rather than trusting the author blindly with their lives -- prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.
- Chapter 1: Genesis.
- Chapter 2: Logical and Bitwise Operations.
- Chapter 3: Shifts.
- Chapter 4: Interlude: FFACalc.
- Chapter 5: "Egyptological" Multiplication and Division.
- Chapter 6: "Geological" RSA.
- Chapter 7: "Turbo Egyptians."
- Chapter 8: Interlude: Randomism.
You will need:
- All of the materials from Chapters 1 - 7.
ffa_ch8_randomism.vpatch(see here)ffa_ch8_randomism.vpatch.asciilifeform.sig- ffa_ch8_randomism.kv.vpatch
- ffa_ch8_randomism.kv.vpatch.asciilifeform.sig
Add the above vpatch and seal to your V-set, and press to ffa_ch8_randomism.kv.vpatch.
You should end up with the same directory structure as previously.
Now compile ffacalc:
cd ffacalc gprbuild
But do not run it quite yet.
The "mail bag" from Chapter 7... is empty.
Well, not entirely empty: reader Apeloyee observed that FZ_Mod_Exp would produce the wrong answer in a hypothetical scenario where its output Result is permitted to overwrite the location containing the Modulus input operand. A revised variant is therefore as follows:
FZ_ModEx.adb:
-- Modular Exponent: Result := Base^Exponent mod Modulus procedure FZ_Mod_Exp(Base : in FZ; Exponent : in FZ; Modulus : in FZ; Result : out FZ) is -- Working register for the squaring; initially is copy of Base B : FZ(Base'Range) := Base; -- Copy of Exponent, for cycling through its bits E : FZ(Exponent'Range) := Exponent; -- Register for the Mux operation T : FZ(Result'Range); -- Buffer register for the Result R : FZ(Result'Range); begin -- Result := 1 WBool_To_FZ(1, R); -- For each bit of R width: for i in 1 .. FZ_Bitness(R) loop -- T := Result * B mod Modulus FZ_Mod_Mul(X => R, Y => B, Modulus => Modulus, Product => T); -- Sel is the current low bit of E; -- When Sel=0 -> Result := Result; -- When Sel=1 -> Result := T FZ_Mux(X => R, Y => T, Result => R, Sel => FZ_OddP(E)); -- Advance to the next bit of E FZ_ShiftRight(E, E, 1); -- B := B*B mod Modulus FZ_Mod_Mul(X => B, Y => B, Modulus => Modulus, Product => B); end loop; -- Output the Result: Result := R; end FZ_Mod_Exp; pragma Inline_Always(FZ_Mod_Exp);
The ultimate aim of FFA is not merely correctness, but obvious correctness. In that vein, any reasonably inexpensive (from complexity and speed POVs) "cushion" which increases rodent resistance -- i.e. cuts down the phase space of possible abuses -- is of interest.
As always, I would like to thank my eagle-eyed readers for their sweat. And anyone who observes a similar thing, I encourage to write in, and receive credit in the next Chapter.
In this Chapter, we will be taking a break from the intricacies of Modular Exponentiation. And in fact from FFA per se. (We will return to the subject in Chapter 9.) Instead, we will be introducing an important knob previously missing from FFACalc: random number generation :
FFA_RNG.ads:
with Ada.Sequential_IO; with Words; use Words; with FZ_Type; use FZ_Type; package FFA_RNG is Default_RNG_Path : constant String := "/dev/random"; -- For reading from RNGs: package Word_IO is new Ada.Sequential_IO(Element_Type => Word); -- Represents an RNG Device: type RNG_Device is record F : Word_IO.File_Type; end record; -- Prepare an RNG for use; at given path, or will use default procedure Init_RNG(RNG : out RNG_Device; RNG_Unix_Path : in String := Default_RNG_Path); -- Fill a FZ from RNG procedure FZ_Random(RNG : in RNG_Device; N : out FZ); end FFA_RNG;
Do you have an auditable hardware True Random Number Generator? If so, you will be able to use it with FFACalc. (Note: if your RNG is on, e.g., a serial port, the port must be already initialized prior to using FFACalc.)
Alternatively, it is possible to specify an ordinary file as an "RNG", for deterministic testing.
The mechanism itself is not complicated:
FFA_RNG.adb:
with OS; use OS; with FZ_Type; use FZ_Type; package body FFA_RNG is -- Prepare an RNG for use; at given path, or will use default procedure Init_RNG(RNG : out RNG_Device; RNG_Unix_Path : in String := Default_RNG_Path) is begin begin -- Open the RNG at the offered path: Word_IO.Open(File => RNG.F, Mode => Word_IO.In_File, Name => RNG_Unix_Path); exception when others => Eggog("Could not open RNG at : " & RNG_Unix_Path & "!"); end; end Init_RNG; -- Fill a FZ from RNG procedure FZ_Random(RNG : in RNG_Device; N : out FZ) is begin begin -- Fill the destination FZ from this RNG: for i in N'Range loop Word_IO.Read(RNG.F, N(i)); end loop; exception when others => Eggog("Could not read from RNG!"); end; end FZ_Random; end FFA_RNG;
Observe that we make no attempt to "massage" the RNG device's output in any way whatsoever. If your RNG is correctly designed, it is unnecessary; if incorrectly -- futile.
The RNG initialization will look like this:
ffa_calc.adb:
-- For RNG: with FFA_RNG; use FFA_RNG; procedure FFA_Calc is Width : Positive; -- Desired FFA Width Height : Positive; -- Desired Height of Stack RNG : RNG_Device; -- The active RNG device. begin if Arg_Count < 3 or Arg_Count > 4 then Eggog("Usage: ./ffa_calc WIDTH HEIGHT [/dev/rng]"); end if; declare Arg1 : CmdLineArg; Arg2 : CmdLineArg; begin -- Get commandline args: Get_Argument(1, Arg1); -- First arg Get_Argument(2, Arg2); -- Second arg if Arg_Count = 4 then -- RNG was specified: declare Arg3 : CmdLineArg; begin Get_Argument(3, Arg3); -- Third arg (optional) -- Ada.Sequential_IO chokes on paths with trailing whitespace! -- So we have to give it a trimmed path. But we can't use -- Ada.Strings.Fixed.Trim, because it suffers from -- SecondaryStackism-syphilis. Instead we are stuck doing this: Init_RNG(RNG, Arg3(Arg3'First .. Len_Arg(3))); end; else -- RNG was NOT specified: Init_RNG(RNG); -- Use the machine default then end if; -- .......snipped.......
To satisfy the Unix insanity of Ada.Sequential_IO, it was necessary to make the Len_Arg function accessible.
FFACalc is invoked quite like before; but now it can take an optional third argument, consisting of the RNG device path. If this optional argument is not given, the default RNG (presently /dev/random. And pointedly not /dev/urandom, which only even exists in Linux because rats gotta rat around.)
And now for the new op itself:
ffa_calc.adb:
-- Push a FZ of RNGolade onto the stack when '?' => Push; FZ_Clear(Stack(SP)); FZ_Random(RNG, Stack(SP));
Now let's try it:
echo "?#" | ./bin/ffa_calc 4096 32
And one possible result:
A331FBE217BC77C7C6AD90C1BABB18C9C95B5A420650AE30876102ECF3FB47667BC5C3 38857C058ED15554724F71321D950A41CB95E86B7894B73BC61BDBAE8B9E0F24EF400D B71742B96A2D46F64D24C57304423D13F5C3EBE7DC62D1A72A33B424F8C3920905BCD6 D1AAB6868D2350D82F73A4583C695B9D46D1D4CFCC46E8487AFBE55DAA53865084D261 B32880A337AFD5A567E1CBA475B3215F18A625E0343031F153F46070F15A159DCBE628 4FC6E624DE42AE31CE086502419777DDC9133BC07D21930D3B87DE124F8E5B282629C3 95DC240033C8E0EF1790F95FBC4C21E8346ECF335B9F4D0DC9A26D5B05218A03C742DA 2D03667A16FB01BBCC2B4CF29169D0CE02E750265BBA4F568C5EE35103440A54B9D6E6 098490DF7E587BD220D01EA396524DAC92812E417BD79248AD3D4480E3AD9CA76DF2B2 405D79F689830C4101D52AEC26311324D529661F286E90DCBB973B371114102971BFF6 FA2EA2460D6733D2C893AFAC0A81FFA0B39C3F67DE04CF9E56AE82B9C659BC8A8470DE EFE5908C16CC1168F1F0AD00DBF6AEFD08B402B9E742817475DDFF273E99641360B62A 3CCB5CC9343BC936CCECAF4FA926B4BF69D96D286C8308448A17B0FF4342AECD0F84CC 5CD43D7DF5D8A343FABEE3CDD4126B3E7DB94C35ECD111824CA288051C269CBEDBAB2F 368627DDD2D4E8CAFD1E3E00001F88FF4E9E5E5DD94C
Homework:
1. Write an automatic generator of arithmetical statements, e.g. multiplications, which are valid programs in your favourite scripting language, and will print "True" supposing that FFACalc had performed the computation correctly, and "False" otherwise.
2. Observe what you get when invoking the RNG when a file is used as the entropy source. Do the contents of the resulting FZ depend on the machine "endianness" ? What happens if there are insufficiently many bytes in the file to supply the demand of your FFACalc tape?
~To be continued!~
I have a copy of the first edition of Applied Cryptography from a used book store. Is there anything in particular you think should be more widely available?
I hope to follow this project soon, time permitting. But I'm thinking maybe I shouldn't make a crypto product literally the first thing I do with Ada. I had also noticed the potential issue with the xor swap, but thinking that the fact that it doesn't work with targets at the same address was something that was learned when one learns of the technique itself, I figured that something in the semantics of this language I didn't know how to read prohibited that kind of misuse, and so held off until I learned more Ada. I'll make more noise if something like that happens in the future. I used to work in nuclear power, so that's the level of pedantry and noise-making I'm trained for, if I just stay in the right mindset.
Edit: You're gonna make me accept scripts from Google to post here? Well, I will, since I'm not fully migrated off of Google yet anyway, but it seems uncharacteristic.
Dear DangerNorm,
The XOR-swap was abolished in Chapter 2.
Schneier's book is of largely historical interest; you may find the "adult" books on the subject more interesting.
As for the Google Captcha crapola, it is loathesome but currently I do not have a working alternative:
If you can suggest a mechanism for spam control that is similarly airtight and still works my dynamically-IP'd web host, I'm all ears.
Yours,
-S
I was going to see if I could get a copy of that from a friend that I know to have a non-trivial CS library, but there's currently a full (non-scanned!) pdf of it as the 4th result from the top on a Google search for "Handbook of Applied Cryptography". So, grab that before it's gone if you want a digital copy and don't have one already.
I must be misremembering who said it, but I know someone adjacent to these parts has said to get the first edition of Applied Cryptography, because the second edition took out "the good stuff". What I'm actually studying right not is Cryptography Engineering, on recommendations that it's a good place to start.
I'll be working on the same captcha problem in getting my site up. I'll let you know what I come up with.
Dear DangerNorm,
See here.
Yours,
-S