"Finite Field Arithmetic." Chapter 21A-Ter: Fix for a False Alarm in Ch.14; "Litmus" Errata.

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 vpatches and seals to your V-set, and press to ffa_ch21a_ter_ch14_ch20_errata.kv.vpatch.

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

As of Chapter 21A-Ter, the versions of Peh and FFA are 250 and 199, respectively.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.


This Chapter concerns fixes for several flaws recently reported by a careful Finnish reader known only as cgra. Thank you, cgra!

Let's begin with his first find: a false alarm bug in Chapter 14B's implementation of Barrett's Modular Reduction. (Note that the proofs given in Ch.14A and Ch.14A-Bis presently stand; the bug exists strictly in the Ada program.)

Recall Step 5 of the algorithm given in Ch.14A :

For each new input X, to compute the reduction R := X mod M:

  1. Xs := X >> JM
  2. Z  := Xs × BM
  3. Zs := Z >> SM
  4. Q  := Zs × M
  5. R  := X - Q
  6. R  := R - M, C := Borrow
  7. R  := R + (M × C)
  8. R  := R - M, C := Borrow
  9. R  := R + (M × C)
  10. R  := R - (R × DM)
  11. R is now equal to X mod M.

... and its optimization, as suggested by the physical bounds proof of Ch.14A-Bis :

2WM
Ignore X
WM - L WM + L
2WM
- Ignore Q
WM - L WM + L
= R
WM + L

... and finally, its implementation in Chapter 14B :

fz_barr.adb:

   -- Reduce X using the given precomputed Barrettoid.
   procedure FZ_Barrett_Reduce(X          : in     FZ;
                               Bar        : in     Barretoid;
                               XReduced   : in out FZ) is
 
   ..............................
 
      -- R is made one Word longer than Modulus (see proof re: why)
      Rl      : constant Indices := Ml + 1;
 
   ..............................
 
      -- Barring cosmic ray, no underflow can take place in (4) and (5)
      NoCarry : WZeroOrDie := 0;
 
   begin
 
   ..............................
 
      -- (5) R  := X - Q (we only need Rl-sized segments of X and Q here)
      FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
             Difference => R, Underflow => NoCarry);
 
   ..............................

Even though we had demonstrated that Q ≤ X, the prohibition of a nonzero subtraction borrow in (5) is fallacious.

To illustrate: this Tape, on a 256-bit run of Peh :

  .1 .FF LS .1 .3 MX # QY

... will not print the expected answer to the given modular exponentiation, i.e.:

  0000000000000000000000000000000000000000000000000000000000000002

... with a Verdict of Yes; but instead will print nothing, and yield a Verdict of EGGOG. Specifically, Peh will halt at (5) via a Constraint_Error (range check failed), when the range of NoCarry's WZeroOrDie type is violated by an assignment of 1.

This is because -- early in this modular exponentiation's sequence of Barrett reductions -- and immediately prior to (5) :

X == 0x40000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 
Q == 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

... but what will be actually computed in (5) is X(1 .. Rl) - Q(1 .. Rl), i.e.:

  0x00000000000000000000000000000000000000000000000000000000000000000000000000000000 -
  0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 
=
 
  1 (Underflow == 1)

... that is, the borrow bit is legitimately 1, in this and in a number of other readily-constructed cases. The constraints we have demonstrated for X, Q, and R do not imply that a borrow will never occur in the subtraction at (5). Therefore, the intended cosmic ray detector is strictly a source of false alarms, and we will remove it:

fz_barr.adb:

   -- Reduce X using the given precomputed Barrettoid.
   procedure FZ_Barrett_Reduce(X          : in     FZ;
                               Bar        : in     Barretoid;
                               XReduced   : in out FZ) is
 
   ..............................
 
      -- Borrow from Subtraction in (5) is meaningless, and is discarded
      IgnoreC : WBool;
      pragma Unreferenced(IgnoreC);
 
   begin
 
   ..............................
 
      -- (5) R  := X - Q (we only need Rl-sized segments of X and Q here)
      FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
             Difference => R, Underflow => IgnoreC); -- Borrow is discarded
 
   ..............................

... and that's it.


Cgra's second find concerned the Ch.20 demo script, Litmus. He had discovered that two mutually-canceling bugs exist in the program. Specifically, in :

litmus.sh:

 
..................
 
# Hashed Section Length
get_sig_bytes 2
turd+=$r
hex_to_int
sig_hashed_len=$r
 
# Hashed Section (typically: timestamp)
get_sig_bytes $sig_hashed_len
turd+=$r
sig_hashed=$r
 
# Unhashed Section Length
get_sig_bytes 1
hex_to_int
sig_unhashed_len=$r
 
# Unhashed Section (discard)
get_sig_bytes $sig_unhashed_len
 
..................
..................
 
# RSA Packet Length (how many bytes to read)
get_sig_bytes 1
hex_to_int
rsa_packet_len=$r
 
# The RSA Packet itself
get_sig_bytes $rsa_packet_len
rsa_packet=$r
 
# Digest Prefix (2 bytes)
get_sig_bytes 2
digest_prefix=$r
 
..................

... the Unhashed Section Length is erroneously treated as a 1-byte field, whereas in reality the GPG format gives 2 bytes. The script only worked (on all inputs tested to date) on account of the presence of the superfluous routine (RSA Packet reader, which remained from an early version of the demo!); in all of the test cases to date, the second byte of the Unhashed Section Length (and the unhashed section in its entirety, for so long as it does not exceed 255 bytes in length -- which it appears to never do) are consumed by get_sig_bytes $rsa_packet_len.

I am almost pleased that I had made this mistake; it is in fact a better illustration of programs which operate correctly despite erroneous logic -- as well as the unsuitability of shell script as a language for nontrivial tasks -- than anything I could readily unearth in the open literature.

And the fix is readily obvious :

 
..................
 
# Hashed Section Length
get_sig_bytes 2
turd+=$r
hex_to_int
sig_hashed_len=$r
 
# Hashed Section (typically: timestamp)
get_sig_bytes $sig_hashed_len
turd+=$r
sig_hashed=$r
 
# Unhashed Section Length
get_sig_bytes 2
hex_to_int
sig_unhashed_len=$r
 
# Unhashed Section (discard)
get_sig_bytes $sig_unhashed_len
 
..................
..................
 
# Digest Prefix (2 bytes)
get_sig_bytes 2
digest_prefix=$r
 
..................

I also incorporated cgra's earlier suggestion regarding error checking. Thank you again, cgra!

And that's it for Litmus, presently.


~ The next Chapter, 21B, will (yes!) continue the Extended-GCD sequence of Chapter 21A. ~
This entry was written by Stanislav , posted on Friday December 04 2020 , filed under Ada, Bitcoin, Cold Air, Computation, Cryptography, FFA, Mathematics, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

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:

60 xor 39 = ?

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!