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

You should end up with the same directory structure as previously.

Now compile ffacalc:

cd ffacalc

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:


   -- 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);
      -- 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 :


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:


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
         -- Open the RNG at the offered path:
         Word_IO.Open(File => RNG.F,
                      Mode => Word_IO.In_File,
                      Name => RNG_Unix_Path);
         when others =>
            Eggog("Could not open RNG at : " & RNG_Unix_Path & "!");
   end Init_RNG;
   -- Fill a FZ from RNG
   procedure FZ_Random(RNG : in RNG_Device;
                       N   : out FZ) is
         -- Fill the destination FZ from this RNG:
         for i in N'Range loop
            Word_IO.Read(RNG.F, N(i));
         end loop;
         when others =>
            Eggog("Could not read from RNG!");
   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 incorrectlyfutile.

The RNG initialization will look like this:


-- 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.
   if Arg_Count < 3 or Arg_Count > 4 then
      Eggog("Usage: ./ffa_calc WIDTH HEIGHT [/dev/rng]");
   end if;
      Arg1 : CmdLineArg;
      Arg2 : CmdLineArg;
      -- Get commandline args:
      Get_Argument(1, Arg1); -- First arg
      Get_Argument(2, Arg2); -- Second arg
      if Arg_Count = 4 then
         -- RNG was specified:
            Arg3 : CmdLineArg;
            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)));
         -- 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:


               -- Push a FZ of RNGolade onto the stack
            when '?' =>
               FZ_Random(RNG, Stack(SP));

Now let’s try it:

echo "?#" | ./bin/ffa_calc 4096 32

And one possible result:



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


      • 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=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">