"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.
- 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.
- Chapter 9: "Exodus from Egypt" with Comba's Algorithm.
- Chapter 10: Introducing Karatsuba's Multiplication.
- Chapter 11: Tuning and Unified API.
- Chapter 12A: Karatsuba Redux. (Part 1 of 2)
- Chapter 12B: Karatsuba Redux. (Part 2 of 2)
- Chapter 13: "Width-Measure" and "Quiet Shifts."
- Chapter 14A: Barrett's Modular Reduction. (Part 1 of 2)
- Chapter 14A-Bis: Barrett's Modular Reduction. (Physical Bounds Proof.)
- Chapter 14B: Barrett's Modular Reduction. (Part 2 of 2.)
- Chapter 15: Greatest Common Divisor.
- Chapter 16A: The Miller-Rabin Test.
- Chapter 17: Introduction to Peh.
- Chapter 18A: Subroutines in Peh.
- Chapter 18B: "Cutouts" in Peh.
- Chapter 18C: Peh School: Generation of Cryptographic Primes.
- Chapter 19: Peh Tuning and Demo Tapes.
- Chapter 20: "Litmus", a Peh-Powered Verifier for GPG Signatures.
- Chapter 20B: Support for Selected Ancient Hash Algos in "Litmus."
- Chapter 20C: Support for 'Clearsigned' GPG texts in "Litmus."
- Chapter 20D: "Litmus" Errata: Support for Nested Clearsigned Texts.
- Chapter 21A: Extended GCD and Modular Multiplicative Inverse. (Part 1 of 3).
- Chapter 21A-Bis: Fix for Lethal Flaw in Ch.15's Greatest Common Divisor.
- Chapter 21A-Ter: Fix for a False Alarm in Ch.14; "Litmus" Errata.
You will need:
- A Keccak-based VTron (for this and all subsequent chapters.)
- All of the materials from Chapters 1 - 21A-Bis.
- ffa_ch21a_ter_ch14_ch20_errata.kv.vpatch
- ffa_ch21a_ter_ch14_ch20_errata.kv.vpatch.asciilifeform.sig
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:
- X_{s} := X >> J_{M}
- Z := X_{s} × B_{M}
- Z_{s} := Z >> S_{M}
- Q := Z_{s} × M
- R := X - Q
- R := R - M, C := Borrow
- R := R + (M × C)
- R := R - M, C := Borrow
- R := R + (M × C)
- R := R - (R × D_{M})
- R is now equal to X mod M.
... and its optimization, as suggested by the physical bounds proof of Ch.14A-Bis :
←2W_{M}→ | ||
Ignore | X | |
←W_{M} - L→ | ←W_{M} + L→ | |
←2W_{M}→ | ||
- | Ignore | Q |
←W_{M} - L→ | ←W_{M} + L→ | |
= | R | |
←W_{M} + L→ |
... and finally, its implementation in Chapter 14B :
-- 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:
-- 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 :
.................. # 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. ~