Cryostat is a Fits-in-Head minimal (~700 LOC, including comments) static library for adding safe and reliable persistent storage to Ada data structures. It makes use of memory-mapped disk I/O via the MMap() system call, present in Linux (kernel 2.4 and newer) and all compatible operating systems. This mechanism permits efficient work with persistent data structures substantially larger than a machine's physical RAM.

AdaCore offers their own implementation of MMap() support in GNATColl. However, IMHO their item is an atrocity, in many ways very similarly to their GNAT Sockets pile of garbage (the near-unusability of the latter is what prompted me to write Ada-UDP in 2018.) AdaCore's MMap library is not only a behemoth replete with e.g. special cases for MS-Win support, but its use is entirely incompatible with safety-restricted compilation profiles.

Cryostat, on the other hand, does NOT require enabling the use of pointerism, unchecked conversions, the secondary stack, heap allocators, or other bulky and objectionable GNAT features, in the calling program. It does however require finalization to be enabled. This is used to guarantee the safe sync-to-disk and closing of the backing MMap when the data structure it contains goes out of scope.

Let's proceed to building Cryostat and its included demo program.

You will need:

• A Keccak-based VTron (for this and all subsequent chapters.)
• GNAT.
• cryostat_genesis.kv.vpatch
• cryostat_genesis.kv.vpatch.asciilifeform.sig

Add the above vpatch and seal to your V-set, and press to cryostat_genesis.kv.vpatch.

Now compile the included CryoDemo:

cd demo
gprbuild

... this will build both the demo and the library.

But do not run it quite yet.

First, let's see what this demo consists of :

cryodemo.adb:

with Interfaces;  use Interfaces;
with ada.text_io; use  ada.text_io;
 
with Cryostat;
 
 
procedure CryoDemo is
 
   -- Path on disk for the example Cryostat backing file :
   File_Path : constant String := "cryotest.bin";
 
   -- Now, let's define an example data structure to place in a Cryostat :
 
   -- Example payload array's element type: byte.
   subtype ADatum is Unsigned_8;
 
   -- Let's make it 512MB - far bigger than a typical stack, to demonstrate
   -- that it will in fact reside in the Cryostat, rather than on the stack :
   A_MBytes : constant Unsigned_32 := 512;
 
   -- Example payload: an array.
   subtype ARange is Unsigned_32 range 0 .. (A_MBytes * 1024 * 1024) - 1;
 
   -- Complete the definition of the payload data structure :
   type TestArray is array(ARange) of ADatum;
 
   -- Declare a Cryostat which stores a TestArray :
   package Cryo is new Cryostat(Form     => TestArray,
                                Path     => File_Path,
                                Writable => True,  -- Permit writing
                                Create   => True); -- Create file if not exists
 
   -- Handy reference to the payload; no pointerisms needed !
   T : TestArray renames Cryo.Item;
 
   -- T can now be treated as if it lived on the stack :
 
begin
 
   Put_Line("T(0)    before :  " & ADatum'Image(T(0)));
   Put_Line("T(Last) before :  " & ADatum'Image(T(T'Last)));
 
   -- Increment each of the elements of T :
   for i in T'Range loop
      T(i) := T(i) + 1;
   end loop;
 
   Put_Line("T(0)    after  :  " & ADatum'Image(T(0)));
   Put_Line("T(Last) after  :  " & ADatum'Image(T(T'Last)));
 
   --- Optional, finalizer always syncs in this example
   --  Cryo.Sync;
 
   --- Test of Zap -- uncomment and get zeroized payload every time :
   --  Cryo.Zap;
 
   Put_Line("OK.");
 
end CryoDemo;

In the demo, we define TestArray -- a data structure consisting of a 512 megabyte array, and invoke Cryostat to create a persistent disk store for it. (When the program is first run, the array -- instantiated as T -- will contain only zeros.) After this, we increment each byte in T, and terminate. When, in the end, T goes out of scope, the finalizer kicks in and properly syncs the payload to disk. Thus, T behaves exactly like a stack-allocated variable, with the exception of the fact that its contents are loaded from disk upon its creation (on the second and subsequent runs of the program) and synced to disk upon its destruction (or if Sync were to be invoked.)

Observe that the calling code is not required to perform any file-related manipulations, or to juggle memory; all of the necessary mechanisms (including error handling) are contained in the Cryostat static library.

When we first execute the demo:

./bin/cryodemo

The following output will appear:

T(0)    before :   0
T(Last) before :   0
T(0)    after  :   1
T(Last) after  :   1
OK.

If we run it again, will see the following:

T(0)    before :   1
T(Last) before :   1
T(0)    after  :   2
T(Last) after  :   2
OK.

... and so forth. cryotest.bin, the backing file used by the Cryostat in the demo, will consist of 512 megabytes of byte value N, where N is the number of times the demo has executed. For example, after the first run, a hex dump:

hexdump -C cryotest.bin

... will yield:

00000000  01 01 01 01 01 01 01 01  01 01 01 01 01 01 01 01  |................|
*
20000000

Let's use the traditional strace tool to confirm that the demo behaves as specified:

strace ./bin/cryodemo

The following output will appear:

execve("./bin/cryodemo", ["./bin/cryodemo"], [/* 84 vars */]) = 0
arch_prctl(ARCH_SET_FS, 0x644798)       = 0
set_tid_address(0x6447d0)               = 3660
rt_sigprocmask(SIG_UNBLOCK, [RT_1 RT_2], NULL, 8) = 0
rt_sigaction(SIGABRT, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
rt_sigaction(SIGFPE, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
rt_sigaction(SIGILL, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
rt_sigaction(SIGBUS, {0x41c360, [], SA_RESTORER|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
sigaltstack({ss_sp=0x644a80, ss_flags=0, ss_size=16384}, NULL) = 0
rt_sigaction(SIGSEGV, {0x41c360, [], SA_RESTORER|SA_STACK|SA_RESTART|SA_NODEFER|SA_SIGINFO, 0x42498c}, NULL, 8) = 0
fstat(2, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 5), ...}) = 0
fstat(0, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 5), ...}) = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 5), ...}) = 0
open("cryotest.bin", O_RDWR|O_CREAT, 0666) = 3
ftruncate(3, 536870912)                 = 0
mmap(NULL, 536870912, PROT_READ|PROT_WRITE, MAP_SHARED, 3, 0) = 0x7f3bcc575000
writev(1, [{"", 0}, {"T(0)    before :   0\n", 21}], 2) = 21
writev(1, [{"", 0}, {"T(Last) before :   0\n", 21}], 2) = 21
writev(1, [{"", 0}, {"T(0)    after  :   1\n", 21}], 2) = 21
writev(1, [{"", 0}, {"T(Last) after  :   1\n", 21}], 2) = 21
writev(1, [{"", 0}, {"OK.\n", 4}], 2)   = 4
msync(0x7f3bcc575000, 536870912, MS_SYNC) = 0
munmap(0x7f3bcc575000, 536870912)       = 0
close(3)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++

There are a few minor knobs that still ought to be added to Cryostat (See README.TXT) but even as it presently stands, it is already sufficient for basic experimentation with clean and compact databases implemented wholly in Ada.

~ To Be Continued. ~

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)

You will need:

• All of the materials from the Chapters 1 through 15.
• There is no vpatch in Chapter 21A.
• For best results, please read this chapter on a colour display!

ACHTUNG: The subject of the Chapter 21 originally promised at the conclusion of Chapter 20 is postponed. That topic will be revisited later!

On account of the substantial heft of Chapter 21, I have cut it into three parts: 21A, 21B, and 21C. You are presently reading 21A, which consists strictly of an introduction to FFA's variant of the Extended GCD algorithm and its proof of correctness.

Recall that in Chapter 18C, we demonstrated the use of FFA and Peh to generate cryptographic primes, of the kind which are used in e.g. the RSA public key cryptosystem.

We also performed GPG-RSA signature verifications using Peh, and learned how to adapt traditional GPG public keys for use with it.

But why have we not yet seen how to generate a new RSA keypair ?

The still-missing mathematical ingredient is an operation known as the modular multiplicative inverse.

This is a process where, provided an integer N and a non-zero modulus M, we find (or fail to find -- its existence depends on the co-primality of the inputs) the integer X where:

NX ≡ 1 (mod M).

... or, in FFAistic terminology, where FFA_FZ_Modular_Multiply(N, X, M) would equal 1.

In RSA, this operation is used when deriving a public key corresponding to a given private key. (It is also used when ensuring that a selected pair of secret primes has certain properties.) The exact details of this process will be the subject of Chapter 22.

Typically, the modular multiplicative inverse is obtained via the Extended GCD algorithm. It differs from the ordinary GCD of Chapter 15 in that, when given inputs X, Y, it returns, in addition to their greatest common divisor, the Bezout coefficients: a pair of integers P, Q which satisfy the equation:

PX + QY = GCD(X,Y)

The modular multiplicative inverse of N modulo M exists strictly when GCD(N, M) = 1.

Therefore, in that case,

NX + MY = GCD(N,M) = 1

... which can be written as:

NX - 1 = (-Y)M

i.e.:

NX ≡ 1 (mod M).

The reader has probably already guessed that the typical heathen formulation of Extended GCD, i.e. one which uses a series of divisions with remainder, is unsuitable as a starting point for writing FFA's Extended GCD -- for the same reason as why the analogous Euclidean GCD was unsuitable (and rejected) for writing the ordinary GCD routine of Chapter 15. Division is the most expensive arithmetical operation, and it would have to be repeated a large number of times, while discarding many of the outputs (a la the old-style non-Barrettian modular exponentiation of Chapter 6.)

Fortunately, it is possible to write a much more efficient constant-spacetime algorithm for Extended GCD, rather closely similar to the one we used for ordinary GCD.

Our algorithm of choice for a properly FFAtronic Extended GCD will be very similar to the Binary Extended GCD pictured in Vanstone's Applied Cryptography.

However, in addition to constant-spacetime operation, our algorithm will differ from the traditional one by avoiding any internal use of signed arithmetic, and will produce outputs having the form :

PX - QY = GCD(X,Y)

Because the Extended GCD algorithm chosen for FFA is not wholly identical to any previously-published one, on account of having to satisfy the familiar requirements, I decided that a full proof of correctness for it ought to be given prior to publishing Chapter 21's Vpatch.

Let's proceed with deriving this algorithm and its correctness proof.

As a starting point, let's take the traditional non-constant-time Stein's GCD given as Algorithm 2 at the start of Chapter 15:

Iterative Quasi-Stein GCD from Chapter 15.

For integers A ≥ 0 and B ≥ 0:

1. Twos := 0
2. Iterate until B = 0:
3.    A_e, B_e := IsEven(A), IsEven(B)
4.    A      := A >> A_e
5.    B      := B >> B_e
6.    Twos   := Twos + (A_e AND B_e)
7.    B_next   := Min(A, B)
8.    A_next   := |A - B|
9.    A, B   := A_next, B_next
10. A := A × 2^Twos
11. A contains the GCD.

Now, suppose that Twos -- the common power-of-two factor of A and B -- were known at the start of the algorithm, and that it were to be divided out of both numbers prior to entering the loop. The rewritten algorithm could look like this:

Algorithm 1: Quasi-Stein GCD with "Twos" Removal.

For integers X ≥ 0 and Y ≥ 0:

1. Twos := Find_Common_Power_Of_Two_Factor(X, Y)
2. X    := X >> Twos
3. Y    := Y >> Twos
4. A    := X
5. B    := Y
6. Iterate until B = 0:
7.    A      := A >> IsEven(A)
8.    B      := B >> IsEven(B)
9.    B_next   := Min(A, B)
10.    A_next   := |A - B|
11.    A, B   := A_next, B_next
12. A := A << Twos
13. A contains GCD(X,Y).

Suppose that we have a correct definition of Find_Common_Power_Of_Two_Factor. (For now, let's merely suppose.)

Algorithm 1 will do precisely the same job as Iterative Quasi-Stein GCD. However, it has one new property -- presently useless -- of which we will later take advantage: because 2^Twos (which could be 1, i.e. 2⁰, if either input were odd to begin with) was divided out of X and Y in steps 2 and 3 -- upon entering the loop at step 7, at least one of X, Y can be now relied upon to be odd. (If X and Y were both equal to zero at the start, step 7 is never reached, and the algorithm terminates immediately.)

Now we want to extend Algorithm 1 to carry out Extended GCD.

First, let's introduce two pairs of additional variables. Each pair will represent the coefficients in an equation which states A or B in terms of multiples of X and Y: A_x, A_y for A; and B_x, B_y for B :

Elementarily, if we were to give these coefficients the following values:

... both equations will hold true, regardless of the particular values of A and B.

Of course, this alone does not give us anything useful.

However, if we assign these base-case values to the coefficients at the start of the algorithm, and correctly adjust them every time we make a change to A or B, the equations will likewise hold true after the completion of the loop, and, in the end, it will necessarily be true that:

... and, importantly, also true that :

When A or B is divided by two, we will divide each of the coefficients in the corresponding pair (A_x, A_y or B_x, B_y respectively) likewise by two. When A and B switch roles, the pairs of coefficients will likewise switch roles. When A is subtracted from B, or vice-versa, the respective pairs will be likewise subtracted from one another, keeping the invariant.

In order to keep the invariant at all times, it will be necessary to apply certain transformations. The mechanics of these transformations will account for most of the moving parts of our Extended GCD algorithm.

To make it clear where we will want to put the new variables and the mechanisms for keeping the invariant, let's rewrite Algorithm 1 in traditional branched-logic form:

Algorithm 2. Quasi-Stein with Branched Logic.

1. Twos := Find_Common_Power_Of_Two_Factor(X, Y)
2. X    := X >> Twos
3. Y    := Y >> Twos
4. A    := X
5. B    := Y
6. Iterate until B = 0:
7.    If IsOdd(A) and IsOdd(B) :
8.       If B < A :
9.          A := A - B
10.       Else :
11.          B := B - A
12.    If IsEven(A) :
13.       A := A >> 1
14.    If IsEven(B) :
15.       B := B >> 1
16. A := A << Twos
17. A contains GCD(X,Y).

Now, let's work out what must be done to the coefficients A_x, A_y and B_x, B_y when we carry out the operations A - B and B - A (steps 9 and 11, respectively) to keep the invariant :

If we write these simplified expressions side-by-side with the original invariant equations :

... it becomes quite obvious. In both the A - B and the B - A cases, we only need to compute the sums A_x + B_x and A_y + B_y ; the only difference will consist of whether they must be assigned, respectively, to A_x, A_y or B_x, B_y.

Now, suppose we introduce these new parts into Algorithm 2, and end up with :

Algorithm 3. A naive attempt at Extended GCD.

1. Twos := Find_Common_Power_Of_Two_Factor(X, Y)
2. X    := X >> Twos
3. Y    := Y >> Twos
4. A    := X
5. B    := Y
6. A_x   := 1
7. A_y   := 0
8. B_x   := 0
9. B_y   := 1
10. Iterate until B = 0:
11.    If IsOdd(A) and IsOdd(B) :
12.       If B < A :
13.          A  := A - B
14.          A_x := A_x + B_x
15.          A_y := A_y + B_y
16.       Else :
17.          B  := B - A
18.          B_x := B_x + A_x
19.          B_y := B_y + A_y
20.    If IsEven(A) :
21.       A  := A  >> 1
22.       A_x := A_x >> 1
23.       A_y := A_y >> 1
24.    If IsEven(B) :
25.       B  := B  >> 1
26.       B_x := B_x >> 1
27.       B_y := B_y >> 1
28. A := A << Twos
29. A contains GCD(X,Y).
30. A_xX - A_yY = GCD(X,Y).

Unfortunately, Algorithm 3 will not work; the equation at step 30 will not hold true. And the attentive reader probably knows why.

For the inattentive: the erroneous logic is marked in red.

The problem is that we have no guarantee that A_x, A_y or B_x, B_y are in fact even at steps 22,23 and 26,27 where they are being divided by two. An entire bit of information "walks away into /dev/null" every time one of these coefficients turns out to have been odd. And then, the invariant no longer holds. Instead of correct coefficients A_x, A_y at step 30, we will end up with rubbish.

The pill needed here is known (according to D. Knuth) as Penk's Method. (I have not succeeded in discovering who, when, or where, Penk was. Do you know? Tell me! A reader found the works of Penk.)

This method, as it happens, is not complicated. And it looks like this:

Algorithm 4. Extended GCD with Penk's Method.

1. Twos := Find_Common_Power_Of_Two_Factor(X, Y)
2. X    := X >> Twos
3. Y    := Y >> Twos
4. A    := X
5. B    := Y
6. A_x   := 1
7. A_y   := 0
8. B_x   := 0
9. B_y   := 1
10. Iterate until B = 0:
11.    If IsOdd(A) and IsOdd(B) :
12.       If B < A :
13.          A  := A - B
14.          A_x := A_x + B_x
15.          A_y := A_y + B_y
16.       Else :
17.          B  := B - A
18.          B_x := B_x + A_x
19.          B_y := B_y + A_y
20.    If IsEven(A) :
21.       A  := A  >> 1
22.       If IsOdd(Ax) or IsOdd(Ay) :
23.          Ax := Ax + Y
24.          Ay := Ay + X
25.       A_x := A_x >> 1
26.       A_y := A_y >> 1
27.    If IsEven(B) :
28.       B  := B  >> 1
29.       If IsOdd(Bx) or IsOdd(By) :
30.          Bx := Bx + Y
31.          By := By + X
32.       B_x := B_x >> 1
33.       B_y := B_y >> 1
34. A := A << Twos
35. A contains GCD(X,Y).
36. A_xX - A_yY = GCD(X,Y).

Of course, for our purposes, it does not suffice to merely know what it looks like; we must also understand precisely why it is guaranteed to work !

At this point, the reader should be satisfied with the logic of the Odd-A-Odd-B case; and therefore knows that the invariant in fact holds when we first reach either of the two places where Penk's Method is applied.

Let's start by proving that what Penk does to A_x, A_y (in steps 22..24) and B_x, B_y (in steps 29..31) does not itself break the invariant.

Review the invariant again:

... and see that in the first case,

22.       If IsOdd(Ax) or IsOdd(Ay) :
23.          Ax := Ax + Y
24.          Ay := Ay + X

... the A invariant equation holds :

And in the second case,

29.       If IsOdd(Bx) or IsOdd(By) :
30.          Bx := Bx + Y
31.          By := By + X

... the B invariant equation holds :

The added X and Y terms simply cancel out in both cases.

However, it remains to be proven that Penk's Method actually resolves our problem, rather than merely avoids creating a new one; i.e. that these operations in fact guarantee the evenness of the coefficients prior to their division by two.

Let's demonstrate this for the Even-A case first; later, it will become apparent that the same approach works likewise in the Even-B case.

At the start of step 21, we know that A is even :

20.    If IsEven(A) :
21.       A  := A  >> 1
22.       If IsOdd(Ax) or IsOdd(Ay) :
23.          Ax := Ax + Y
24.          Ay := Ay + X

And, at all times, we know that X and Y cannot be even simultaneously (because we have divided out 2^Twos from each of them.)

On top of all of this: since we graduated from kindergarten, we also know about the following properties of arithmetic operations upon odd and even numbers:

Parity of Addition and Subtraction:

Parity of Multiplication:

So, what then do we know about the parities of the working variables at step 21? Let's illustrate all possible combinations of parities, using the above colour scheme; and observe that we only need the A invariant equation for this. As it happens, there are exactly two possible combinations of parities for its terms :

Elementarily, given that A is even at this step, both terms of its invariant equation must have the same parity.

Let's produce a table where all possible combinations of parities of the variables having an unknown parity (A_x, A_y) are organized by the known parities of the variables having a known parity (X, Y, A).

In yellow, we will mark variables which could be either odd or even in a particular combination; in red, those which are known to be odd; in green, those known to be even; and in grey, those for which neither of the possible parities would make the known parities of X, Y, and A in that combination possible, and therefore imply a logical impossibility :

Now, let's remove the two impossible entries from the above table:

And now suppose that we have reached step 23. Therefore we already know that at least one of A_x and A_y is odd. Let's remove from the table the only entry where this is not true; and, finally, in all of the remaining entries, indicate the deduced parity of the variables whose parity was previously indeterminate :

All of the parities are now determined.

We are left with only three possible combinations of parities of the terms of A which could exist at step 23. So let's list what happens to each of them when Penk's Method is applied, i.e. Y is added to A_x and X is added to A_y :

In the Even-A case, Penk's Method works, QED. It is difficult to think of how this could be made more obvious. The parities on both sides of the + sign always match, and so we have forced both A_x and A_y to be even, without breaking the invariant equation for A.

And now, how about the Even-B case ? Suppose that we have reached step 30. Let's do the same thing as we have done for the Even-A case:

... does this remind you of anything you've seen before?

Instead of telling the nearly-same and rather tedious story twice, let's leave step 30 as an...

Chapter 21A, Exercise #1: Prove that Penk's Method is correct in the Even-B case.

Chapter 21A, Exercise #2: Why are simultaneously-even X and Y forbidden in this algorithm?

Now, we are ready to rewrite Algorithm 4, this time grouping any repeating terms together, as follows:

Algorithm 5. Extended GCD with Penk's Method and Unified Terms.

For integers X ≥ 1 and Y ≥ 0:

1. Twos := Find_Common_Power_Of_Two_Factor(X, Y)
2. X    := X >> Twos
3. Y    := Y >> Twos
4. A    := X
5. B    := Y
6. A_x   := 1
7. A_y   := 0
8. B_x   := 0
9. B_y   := 1
10. Iterate until B = 0:
11.    If IsOdd(A) and IsOdd(B) :
12.       D  := |B - A|
13.       S_x :=  A_x + B_x
14.       S_y :=  A_y + B_y
15.       If B < A :
16.          A  := D
17.          A_x := S_x
18.          A_y := S_y
19.       Else :
20.          B  := D
21.          B_x := S_x
22.          B_y := S_y
23.    If IsEven(A) :
24.       A  := A  >> 1
25.       If IsOdd(Ax) or IsOdd(Ay) :
26.          Ax := Ax + Y
27.          Ay := Ay + X
28.       A_x := A_x >> 1
29.       A_y := A_y >> 1
30.    If IsEven(B) :
31.       B  := B  >> 1
32.       If IsOdd(Bx) or IsOdd(By) :
33.          Bx := Bx + Y
34.          By := By + X
35.       B_x := B_x >> 1
36.       B_y := B_y >> 1
37. A := A << Twos
38. A contains GCD(X,Y).
39. A_xX - A_yY = GCD(X,Y).

At this point, we have something which closely resembles commonly-used traditional variants of the Binary Extended GCD algorithm. With the not-unimportant difference that all of the working variables stay positive throughout. This way, we will avoid the need to introduce signed arithmetic into the internals of FFA.

Should we proceed with rewriting Algorithm 5 using constant-time operations? ...or is something important still missing? What is it ?

Chapter 21A, Exercise #3: What, other than the use of FFA-style constant-time arithmetic, is missing in Algorithm 5 ?

~To be continued in Chapter 21B.~

I have recently built two new WWW mirrors containing certain publicly-available software:

1. Historic Gentoo Distfiles.

I have been using Gentoo for nearly all Linux-related work since 2007. It was "the lesser of evils": to my knowledge, no other Linux variant ever offered a comparable level of rodenticidal control, while at the same time providing an adequate means of automatically cutting through "dependency hell".

This uniqueness made Gentoo a target for concerted attack by the Enemy, on a variety of fronts. Through creeping Poetteringism, the cancerous blight of GCC 5+, and the eventual decay -- fostered by corrupt maintainers -- of the portage system into unusability, it became nearly impossible to set up a hygienic Gentoo system from scratch.

The minute you try emerge --sync, you will be force-fed a boiling ocean of liquid shit under the name of "progress". And the machine will have to be scrubbed and re-OSed, if you wish to continue with civilized life on it.

Eventually I resorted to creating "canned" Gentoos using bitwise copies of old installations. (E.g. this system for ARM-64, and this one for AMD-64, are provided for my ISP service customers.)

One obvious problem with the "canned" approach is the decay of the official Gentoo distfiles mirrors. At one time these operated purely by accretion, i.e. added new packages while preserving the old. At a certain point this changed, and the servants of "progress" began to sabotage the ecosystem by deliberately removing "ungodly" packages. Mirror operators which refused to participate in this "cultural revolution" were delisted and you will not find them via the Gentoo WWW -- even supposing their mirrors are still standing (many have simply given up.)

Until and unless a cultural "reset" takes place, and something like what Gentoo tried to be in 2007 again exists as a living entity, I intend to continue the use of my hand-curated "fossilized" variants. And to make this easier for others, I have put together a public distfiles mirror:

http://dulap.xyz/gentoo/distfiles

... using the contents of my backup tapes from a multitude of Gentoo systems I have operated.

Gentoo users may add this URL to their GENTOO_MIRRORS list in /etc/portage/make.conf; or download any necessary tarballs into their local /usr/portage/distfiles by hand; this is a matter of taste.

WARNING: this repository is offered with no warranty or endorsement of any kind, and certainly contains software with dangerous flaws. It does not necessarily reflect the current configuration of any of the Gentoo machines I presently use (although packages from both the RK and the "Dulap" variant's default distfiles directories are all present.) I have trimmed some -- but by no means all! -- of the obvious garbage. It goes without saying that I am not responsible for the contents of the tarballs, or even their integrity. Please do not use tarballs for which you do not have an authoritative signature for safety-critical work! From this -- or any other public repository.

Any and all questions regarding the above -- I prefer to answer here.

People from my L1 WoT who wish to contribute specimens to this collection, are invited to contact me.

At this time, the Gentoo collection weighs ~16GB.

2. GNAT.

The following mirror now contains a multitude of GNAT and miscellaneous Ada-related packages/dependencies, obtained on April 10, 2020 via JFW's method:

http://dulap.xyz/ada

READMEs, as well as MS-Win and Apple binaries have been omitted. Packages with duplicate names are stored in the "dupes" subdirectories (1, 2, 3, 4, 5, 6, 7)

The same warning as given for the Gentoo repository applies to this collection.

At this time, the Ada collection weighs ~17GB. Aside from the binaries removal, this set was not curated in any way.

Readers are encouraged to mirror the mirrors. Anyone who has done this, is encouraged to leave a comment here, with the URL of the new mirror.

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.

You will need:

• A Keccak-based VTron (for this and all subsequent chapters.)
• All of the materials from Chapters 1 - 20C.
• ffa_ch20d_litmus_nested_fix.kv.vpatch
• ffa_ch20d_litmus_nested_fix.kv.vpatch.asciilifeform.sig

Add the above vpatches and seals to your V-set, and press to ffa_ch20d_litmus_nested_fix.kv.vpatch.

As of Chapter 20D, the versions of Peh and FFA are 250 and 253, respectively. FFA and Peh themselves have not changed from Chapter 19.

Compile Peh:

cd ffacalc
gprbuild

... and install it to a path visible in your shell (e.g. /usr/bin.)

Litmus as given in the previous chapter would choke (failing safe, i.e. rejecting the signature) when fed "nested" clearsigned texts. This bug has been fixed:

litmus.sh:

# 'ASCII-Armoured' PGP signatures have mandatory start and end markers:
START_MARKER="^\-\-\-\-\-BEGIN PGP SIGNATURE\-\-\-\-\-"
END_MARKER="^\-\-\-\-\-END PGP SIGNATURE\-\-\-\-\-"
 
.......
 
CLEAR_MARKER="^\-\-\-\-\-BEGIN PGP SIGNED MESSAGE\-\-\-\-\-"
 
.......

To test, invoke Litmus with two arguments: the public key, followed by the input file:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
 
- -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
 
This is a test-fire GPG 'clearsigned' document written for
FFA Chapter 20C.
- -----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
 
iQEcBAEBCgAGBQJeGimSAAoJELmCKKABq//HfgsH/1bg0zpL1PoApHE5BMNXmJ7U
7vWKQJ3ZCsGvkUSIgIZESTp6EpGDclBQqvBsdBZ9KVnBpGiIbmKbNjDNlZU5YcWt
WQ7FO+r4LiUZOJRiPADWMM7tpI3azXelPyuge7hFe6o3UG0aErSceKXcoFGKFDO2
MCZXkR6Lfd3rYKHcySOEvkoCMQ4ytbEQM4IBE57AqQIpmnI7Mo1033TnDgL2KdXd
PHLtedNyaKwzVJw08BtKjzole130GvElSMmxilrHZ0w+2J4uHRuBELyZbJ55vu+x
Bx+Q5OpMwz0ZG4vjz8ncZE/nCvK/sZv/RXsdNow95fETH5DKC9HfIP279kKlBRg=
=3ozu
- -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
 
iQEcBAEBCgAGBQJeHgg9AAoJELmCKKABq//HHywH/3cfUfV8SH2yuxHNBPmk3Yha
Nw/40YK52/DJ/H+RUY6Zei2X3tJPYe3vDN2P3iRqKBycpUPtNnCDaF3BAvg7cyRQ
PghpykoSeERxIQZaIQWTUyMQRBwoMF90wiQpcgCEXRH3xZo/p0M3M6zPrqKElXf4
essZmM3jsvfU9T8JGho0RPyK1J42fTBCiRb0Y++ZQGWVEwJugtVnQOL76fYmSUpW
vDBKgNJfvGOMNTCTLemqD2nn6DZzLN9TOrRlmLvfr0lbzu9rSGAMtRKqozhZeCXf
LiTWWVZkCUGr/SEk5olhbHQnfoYMH1V071qJnpv1/5QqIiZ1z2KbP65Ba/i3i0A=
=o/9T
-----END PGP SIGNATURE-----

./litmus.sh asciilifeform.peh asciilifeform-clearsigned-twice.txt

... which will yield the output:

VALID GPG RSA signature from asciilifeform <[email protected]>

Naturally, no verification is performed on the embedded clearsigned text (just as in traditional GPG. If you want to operate on the embedded text, you must extract it.)

~To be continued!~

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

You will need:

• A Keccak-based VTron (for this and all subsequent chapters.)
• All of the materials from Chapters 1 - 20B.
• ffa_ch20c_litmus_clearsigned.kv.vpatch
• ffa_ch20c_litmus_clearsigned.kv.vpatch.asciilifeform.sig

Add the above vpatches and seals to your V-set, and press to ffa_ch20c_litmus_clearsigned.kv.vpatch.

As of Chapter 20C, the versions of Peh and FFA are 250 and 253, respectively. FFA and Peh themselves have not changed from Chapter 19.

Compile Peh:

cd ffacalc
gprbuild

... and install it to a path visible in your shell (e.g. /usr/bin.)

Litmus now supports GPG "clearsigned" texts. Compatibility with the program given in the previous chapter is retained. The "clearsigned" mode of operation is selected simply by invoking the script with two arguments instead of the usual three:

litmus.sh:

.......
 
# Whether we are working on a 'clearsigned text'
CLEARSIGN_MODE=false
 
# Set up in the selected mode:
case $ARGCOUNT in
    2) # If given two arguments, verify a 'clearsigned' text file:
        CLEARSIGN_MODE=true
        # The processed payload will end up in a temporary file:
        DATAFILE=$(mktemp) || { echo "Failed to create temp file!" >&2; \
            exit $RET_EGGOG; }
        # On exit, if in 'clearsign' mode, remove temporary file with payload:
        trap remove_temp_file EXIT
        # Expect 'Canonical Text Signature' in GPG sig packet turd
        expect_sig_class=1
        ;;
    3) # Verify Detached Signature on given Data File (third argument is path):
        # The given Data file to be verified against the Signature
        DATAFILE=$3 # i.e. path given on command line
        # Expect 'Detached Binary Signature' in GPG sig packet turd
        expect_sig_class=0
        ;;
    *) # If invalid arg count -- print usage and abort:
        echo "Usage: $0 publickey.peh signature.sig datafile"
        echo "   or: $0 publickey.peh clearsigned.txt"
        exit $RET_EGGOG
        ;;
esac
.......

RFC4880 (the document GPG nominally conforms to) specifies certain transformations required to obtain the hashable payload from the document (e.g. imposition of MSDOS-style line endings) which were implemented as follows:

litmus.sh:

.......
 
# If we are operating on a 'clearsigned' text file, $DATAFILE will be
# an empty temporary file, and the payload is to be extracted to it,
 
.......
 
if [ $CLEARSIGN_MODE == true ]
then
    # Find position of 'clearsign' payload start marker:
    CLEAR_MARKER="\-\-\-\-\-BEGIN PGP SIGNED MESSAGE\-\-\-\-\-"
    start_clr=$(grep -m 1 -n "$CLEAR_MARKER" $SIGFILE | cut -d ':' -f1)
 
    # If payload start marker was not found:
    if [ "$start_clr" == "" ]
    then
        eggog_broken_clearsigned
    fi
 
    # Discard the start marker:
    start_clr=$(($start_clr + 1))
 
    # The payload ends with the line preceding the sig start:
    end_clr=$((start_ln - 2))
 
    # Find any 'Hash:' headers:
    start_body=$(tail -n "+$start_clr" $SIGFILE | \
        grep -v -n -m 1 "^Hash:" | cut -d ':' -f1)
 
    # Skip the above headers and mandatory empty line:
    start_clr=$(($start_clr + $start_body))
 
    # If there is no payload, or the markers are misplaced, abort:
    if [ $start_clr -ge $end_clr ]
    then
        eggog_broken_clearsigned
    fi
 
    # Extract the 'clearsign' payload to the temporary file:
    cat $SIGFILE | sed -n "$start_clr,$end_clr p" | \
        sed 's/[ \t]*$//; s/^- //' | \
        awk '{printf("%s\r\n",$0)}' \
            > $DATAFILE
 
    # Remove the trailing CR,LF ending:
    truncate -s -2 $DATAFILE
 
    # After this, proceed exactly like with 'detached' sigs, but
    # with the expected 'class' being 1 rather than 0.
fi
 
.......

To verify a "clearsigned" message, invoke Litmus with two arguments: the public key, followed by the input file, e.g.:

./litmus.sh asciilifeform.peh asciilifeform-clearsigned.txt

... which will yield the output:

VALID GPG RSA signature from asciilifeform <[email protected]>

~To be continued!~

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

You will need:

• A Keccak-based VTron (for this and all subsequent chapters.)
• All of the materials from Chapters 1 - 20.
• ffa_ch20b_litmus_legacy_hashes.kv.vpatch
• ffa_ch20b_litmus_legacy_hashes.kv.vpatch.asciilifeform.sig

Add the above vpatches and seals to your V-set, and press to ffa_ch20b_litmus_legacy_hashes.kv.vpatch.

As of Chapter 20B, the versions of Peh and FFA are 250 and 253, respectively. FFA and Peh themselves have not changed from Chapter 19.

Compile Peh:

cd ffacalc
gprbuild

... and install it to a path visible in your shell (e.g. /usr/bin.)

In the course of experimenting with the subject of the previous Chapter, I found that a number of current and past Vtronicists had misconfigured their GPG, and emit suboptimal signatures (i.e. not SHA-512, the strongest of the ancient hashes supported by that utility). And so I added support for these. (Litmus will emit a warning if such a signature is encountered.)

The following routine has been added to Litmus:

litmus.sh:

# If Sig was made with an unsupported hash algo:
eggog_unsupported_hash() {
    algo=$1
    echo "This sig uses an unsupported Digest Algo: $1 !" >&2
    exit $RET_EGGOG
}
 
.......
 
# Warnings:
achtung() {
    echo "WARNING: $1" >&2
}
 
.......
 
# Digest Algo (only certain hash algos are supported)
get_sig_bytes 1
turd+=$r
hex_to_int
sig_digest_algo=$r
 
# If hash algo is supported, get ASN turd and MD_LEN; and if not, eggog:
case $sig_digest_algo in
    1)  ## MD5 -- NOT SUPPORTED ##
        eggog_unsupported_hash "MD5"
        ;;
 
    2)  ## SHA1 ##
        achtung "This sig was made with SHA-1, which is cheaply breakable!"
        achtung "Please contact the signer ($pubkey_owner) !"
        HASHER="shasum -a 1 -b"
        ASN="3021300906052b0e03021a05000414"
        MD_LEN=20
        ;;
 
    3)  ## RIPE-MD/160 -- NOT SUPPORTED ##
        eggog_unsupported_hash "RIPE-MD/160"
        ;;
 
    8)  ## SHA256 ##
        achtung "This sig was made with SHA-256; GPG supports SHA-512."
        achtung "Please contact the signer ($pubkey_owner) !"
        HASHER="shasum -a 256 -b"
        ASN="3031300d060960864801650304020105000420"
        MD_LEN=32
        ;;
 
    9)  ## SHA384 ##
        achtung "This sig was made with SHA-384; GPG supports SHA-512."
        achtung "Please contact the signer ($pubkey_owner) !"
        HASHER="shasum -a 384 -b"
        ASN="3041300d060960864801650304020205000430"
        MD_LEN=48
        ;;
 
    10) ## SHA512 ##
        HASHER="shasum -a 512 -b"
        ASN="3051300D060960864801650304020305000440"
        MD_LEN=64 # 512 / 8 == 64 bytes
        ;;
 
    11) ## SHA224 ##
        achtung "This sig was made with SHA-224; GPG supports SHA-512."
        achtung "Please contact the signer ($pubkey_owner) !"
        HASHER="shasum -a 224 -b"
        ASN="302D300d06096086480165030402040500041C"
        MD_LEN=28
        ;;
 
    *)  ## Unknown Digest Type ##
        eggog_unsupported_hash "UNKNOWN (type $sig_digest_algo)"
        ;;
esac
 
# Calculate length (bytes) of the ASN turd for the digest used in the sig:
ASN_LEN=$((${#ASN} / 2))
 
.......

To test, for instance, verification of SHA-1 signatures (please stop using SHA-1, people! see e.g. here), download this Litmus-converted GPG public key of former contributor Diana Coman, and verify her signature of Chapter 1:

./litmus.sh diana_coman.peh ffa_ch1_genesis.kv.vpatch.diana_coman.sig ffa_ch1_genesis.kv.vpatch

... which will yield the output:

WARNING: This sig was made with SHA-1, which is cheaply breakable!
WARNING: Please contact the signer (Diana Coman <[email protected]>) !
VALID GPG RSA signature from Diana Coman <[email protected]>

~To be continued!~