“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.

You will need:

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!~

This entry was written by Stanislav , posted on Saturday January 20 2018 , filed under Ada, Bitcoin, Cold Air, Computation, Cryptography, FFA, Friends, Mathematics, ShouldersGiants, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

5 Responses to ““Finite Field Arithmetic.” Chapter 8: Interlude: Randomism.”

  • DangerNorm says:

    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.

    • Stanislav says:

      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

      • DangerNorm says:

        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.

  • DangerNorm says:

    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.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre lang="" line="" escaped="" highlight="">


MANDATORY: Please prove that you are human:

17 xor 53 = ?

What is the serial baud rate of the FG device ?


Answer the riddle correctly before clicking "Submit", or comment will NOT appear! Not in moderation queue, NOWHERE!