“Finite Field Arithmetic.” Chapter 18C: Peh School: Generation of Cryptographic Primes.
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 18 consists of three parts, of which only the first (18A) includes a vpatch; the second (18B) -- completes the discussion of the mechanisms; while the third (18C) contains worked examples of practical use.
You are presently reading 18C.
You will need:
- A Keccak-based VTron (for this and all subsequent chapters.)
- All of the materials from Chapters 1 - 18B.
There is no vpatch in Chapter 18C. To run the examples given in this Chapter, please use the Peh you built in Chapter 18A, and refer to the Peh 251K Instruction Set Table as you read on.
First, the mail bag!
Reader bvt has given me to know that he has read and signed Chapters 10 and 11 :
He also published a report of his interesting experiment with an unrolled ASMistic AMD64 Comba multiplier.
Thank you, reader bvt!
Reader diana_coman has given me to know that she has read and signed Chapters 9, 10, and 11 :
- ffa_ch9_exodus.kv.vpatch.diana_coman.sig
- ffa_ch10_karatsuba.kv.vpatch.diana_coman.sig
- ffa_ch11_tuning_and_api.kv.vpatch.diana_coman.sig
She has also published an illustrated guide to Chapters 1 - 4.
Thank you, reader diana_coman!
Now, let's eat the meat of this Chapter.
Virtually all number-theoretical cryptosystems make use of prime numbers. In this Chapter, we will demonstrate how to use the Peh system, in conjunction with a TRNG, to produce primes of a particular desired form.
The reader may recall that the Miller-Rabin Test implemented in Chapter 16A, like all basic FFA operations, runs in constant time to avoid leaking secrets via timing side-channel. This means that it will consume the same number of CPU cycles for all possible candidate and witness inputs of a particular width, regardless of the "probable primality" or lack thereof of the candidate, or the value of the witness (which, recall, is always forced into the valid domain defined for the Miller-Rabin algorithm.)
Consequently, our Miller-Rabin operator P is to be considered "expensive" -- though, interestingly, in actual practice it is still faster than Koch's.
Likewise, Peh's division operator runs in constant time, and therefore the traditional "division by a series of small primes" litmus filter for Miller-Rabin inputs is undesirable. However, there is a simple alternative algorithm which makes use of the Greatest Common Divisor operator G defined in Chapter 15.
Prior to writing a Peh Tape which generates cryptographic primes, we will write one which computes the largest primorial (product of successive primes) which fits in a selected FZ Width:
(----------------------------------------------------------------------------) (----------------------------------------------------------------------------) (- Demo Tape for 'Peh'; produces the largest primorial that fits in Width. -) (- -) (- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) -) (- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html -) (- -) (- You do not have, nor can you ever acquire the right to use, copy or -) (- distribute this software ; Should you use this software for any purpose, -) (- or copy and distribute it to anyone or in any manner, you are breaking -) (- the laws of whatever soi-disant jurisdiction, and you promise to -) (- continue doing so for the indefinite future. In any case, please -) (- always : read and understand any software ; verify any PGP signatures -) (- that you use - for any purpose. -) (- -) (- See also http://trilema.com/2015/a-new-software-licensing-paradigm . -) (----------------------------------------------------------------------------) (----------------------------------------------------------------------------) (------------------------------ Main Program : ------------------------------) ( p is the 'primorial accumulator', and q is the current 'potential prime'. ) ( p is initialized to the product of the first two primes, 2 and 3 : ) .6 $p ( q is initialized to 5, i.e. the first prime that is not 2 or 3 :) .5 $q ( Begin a loop: ) : ( Determine GCD(p, q) : ) p q G ( If GCD(p, q) WAS equal to 1, we know that q is a new prime : ) .1 = { ( Find the product pq. The UPPER FZ of this product will land on top of stack, and the LOWER FZ will lie immediately under it : ) p q * ( If the UPPER FZ of the product pq was NOT equal to 0... ... then we have overflowed our Width, and must stop: ) { ( Drop the LOWER FZ of the product pq, because we have overflowed Width and cannot use it : ) _ ( Leave a 0 on the stack, to trigger termination : ) .0 ( At this point, we have the largest primorial that can fit in our FZ Width, and we are done. ) } ( If the UPPER FZ of the product pq WAS equal to 0... ... then we have NOT overflowed our Width, and continue: ) { ( Store the LOWER FZ of the product pq to p :) $p ( Leave a 1 on the stack, to trigger continuation : ) .1 ( At this point, pq is the primorial up to and inclusive of q, and we keep going. ) }_ } ( If GCD(p, q) WAS NOT equal to 1, we know that q is NOT a prime : ) { ( Leave a 1 on the stack, to signal continuation : ) .1 }_ ( After either of the above cases, we must: q := q + 2, given as any possible next prime after the current q must be odd : ) q .2 + $q ( If we have a 1, cycle the loop; otherwise, we have the Primorial, in p, and must output it and terminate the Tape : ) , ( Emit a Peh Tape which defines the constant 'Primorial' : ) [@Primorial@ ( Regs : none ) .] p# [; ] ( Now, terminate with a 'Yes' Verdict, as we have succeeded : ) QY (--------------------------------~~The End~~---------------------------------)
Chapter 18C, Exercise 1:
Prove the correctness of the algorithm offered above for generating the "max-Width" primorial.
Finished the exercise? Now let's execute this Tape in a Peh session with a FZ Width of 2048:
cat primorial.peh | ./ffa/ffacalc/bin/peh 2048 32 10000 0
... observe that we do not need the RNG for this Tape.
The expected output, re-indented for clarity :
@Primorial@ ( Regs : none ) .48CB4F7B0A023C393C0A4F253FFE4D1905DEFDF482D0C7754B59B612E3B741995 87DC933268A053E59F021733C80D558BF9CBBAD3A38E2FB5D4BA3157227E8ACA0 ACF379238AFA8DB31110AF0C566DC5DBC5C8E783E1566B3B44A4E35FFC2BFE481 C533A1609E99A1C9AF81C8F634F7400FBD1355D091FAB7B9AFF302AAC9D60C15C 29E3396A18523E177B1DA3898FF1F8BF74A2CC40032736A65B25B5908950863A8 019065A073EBF20164F14EA4338530C2818F208BAEEB2A810A9862A09B8ADE3BE BDD7CF7DC88ECB1722F7ED2DAD24FE5C4851F7D6681CA2B97306BAC70E37D177C 139E2688AF33E5CCEF102A2AE35276983DDCABA3720E5C165EB88C0FE ;
Observe that this is itself a valid Peh Tape. It defines a constant (the convention for constants in Peh is quite simple, they are simply subroutines which place one or more fixed numeric values on the data stack) which is equal to the largest primorial that is able to fit in the selected FZ Width.
We will make use of this primorial in our cryptographic prime generator Peh Tape. Candidate integers drawn from the RNG via the ? command will be logically OR'd with the given Bit Mask, which will specify that we wish to produce an odd integer having a bitness no less than the currently selected FZ Width (i.e. it will mandatorily have a 1 in the uppermost and lowermost positions.) If a given number is not coprime with the primorial, we therefore know that it has as a factor one of the small primes which went into the primorial, and this number is discarded.
When a candidate number which passes this "GCD litmus" is obtained, it will thereafter be subjected to a certain number of iterations of the Miller-Rabin test (in our example - 32), each time with a random Witness, and the test must fail to "find compositivity" each time. Recall that if the M-R test returns "found composite", the offered number is known to be composite. Therefore we stop short of the maximum number of shots if this takes place, and discard that candidate, thereafter invoking the RNG and the GCD litmus to produce a new candidate for yet another set of iterated M-R tests.
After we encounter a candidate integer which passes the specified number of M-R tests with random witnesses, we will report this candidate as a "probable prime", along with the total number of times the RNG was called upon via the ? command, and the number of these candidates which had passed the GCD litmus and were deemed worthy of the iterated Miller-Rabin test.
Without further delay, this Tape :
(----------------------------------------------------------------------------) (----------------------------------------------------------------------------) (- Demo Tape for 'Peh'; produces a random probable-prime of the given form. -) (- -) (- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) -) (- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html -) (- -) (- You do not have, nor can you ever acquire the right to use, copy or -) (- distribute this software ; Should you use this software for any purpose, -) (- or copy and distribute it to anyone or in any manner, you are breaking -) (- the laws of whatever soi-disant jurisdiction, and you promise to -) (- continue doing so for the indefinite future. In any case, please -) (- always : read and understand any software ; verify any PGP signatures -) (- that you use - for any purpose. -) (- -) (- See also http://trilema.com/2015/a-new-software-licensing-paradigm . -) (----------------------------------------------------------------------------) (----------------------------------------------------------------------------) (----------------------------------------------------------------------------) ( Largest Primorial which fits in a 2048-bit FZ : ) @Primorial@ ( Regs : none ) .48CB4F7B0A023C393C0A4F253FFE4D1905DEFDF482D0C7754B59B612E3B741995 87DC933268A053E59F021733C80D558BF9CBBAD3A38E2FB5D4BA3157227E8ACA0 ACF379238AFA8DB31110AF0C566DC5DBC5C8E783E1566B3B44A4E35FFC2BFE481 C533A1609E99A1C9AF81C8F634F7400FBD1355D091FAB7B9AFF302AAC9D60C15C 29E3396A18523E177B1DA3898FF1F8BF74A2CC40032736A65B25B5908950863A8 019065A073EBF20164F14EA4338530C2818F208BAEEB2A810A9862A09B8ADE3BE BDD7CF7DC88ECB1722F7ED2DAD24FE5C4851F7D6681CA2B97306BAC70E37D177C 139E2688AF33E5CCEF102A2AE35276983DDCABA3720E5C165EB88C0FE ; (----------------------------------------------------------------------------) ( Number of 'passing' M-R shots required before we will say that a candidate integer is a 'probable prime': 32. Can change this if you dare. ) @MR-Shots@ ( Regs : none ) .20 ; (----------------------------------------------------------------------------) ( Bitmask imposed, via logical OR, on the randomly-generated candidates. Consists of a 1 in the uppermost position for the current FZ width, and a 1 in the lowermost position, to give ODD integers of desired width. ) @Candidate-Bitmask@ ( Regs : none ) .1 .0 ~ W .1 - LS .1 | ; (----------------------------------------------------------------------------) ( Take an integer N from stack. N MUST BE > 1; assumed to be true, given that the Candidate Bitmask is odd. if N is Relatively Prime vs. Primorial: Return 0; else: return 1. ) @Primorial-Litmus@ ( Regs : none ) ( N is on the stack already. Now find GCD(N, Primorial) : ) @Primorial! G ( Was the GCD equal to 1 ? ) .1 = ( Invert the answer; i.e. a 'fail' will result in 1, a 'pass' -- 0 : ) .1 ^ ; (----------------------------------------------------------------------------) ( Take a Bitmask specifying the bits that must be set to 1, from the stack. Generate RANDOM integers, until obtains one that, when OR'd with Bitmask, passes the Primorial Litmus. ) @Make-Candidate@ ( Regs : u, m, z ) ( Get the Bitmask from the stack, and assign to m : ) $m ( Begin a loop: ) : ( u := u + 1 , i.e. increment the 'RNG shots' counter: ) u .1 + $u ( Generate a random FZ of the current FZ width : ) ? ( Take the mandatory-ones Bitmask, and OR it into the random FZ from above, then store this to z: ) m | $z ( Run z through the Primorial Litmus: ) z @Primorial-Litmus! ( If 1, i.e. Litmus failed, cycle the loop; otherwise we're done: ) , ( Return the z which passed the Primorial Litmus: ) z ; (----------------------------------------------------------------------------) ( Take integers N and I from stack (I is on the top of stack, followed by N) ; Fire up to I shots of Miller-Rabin Test on N, each with a RANDOM witness; If ALL I shots PASSED, i.e. M-R did NOT 'find composite' in any of them : Return 0; else (i.e. if any shot FAILED) : Return 1 IMMEDIATELY. ) @Iterated-MR-Test@ ( Regs : i, n, r ) ( i := Maximum number of Miller-Rabin shots that we will perform : ) $i ( n := N, i.e. store a copy of N: ) $n ( Begin a loop: ) : ( Put n on the stack: ) n ( Generate a random Witness for this shot: ) ? ( Recall that it will always be brought into the valid range, automatically, in constant time. See also Ch. 16A. ) ( Run a M-R test; outputs 1 if FOUND composite, and 0 if NOT: ) P ( r := result ) $r ( i := i - 1 , i.e. decrement the shots counter: ) i .1 - $i ( If any shots still remain... ) i .0 > ( Invert the M-R result: if 'NOT found composite', give a 1 : ) r .1 ^ ( ...shots remain, AND current one did not 'find composite' : ) & ( ... then have a 1, and we cycle the loop, for the next shot; Otherwise, we're done: ) , ( At this point, N has failed a M-R shot, or passed all of the shots; In either case, we return r, which will be 0 IFF all shots passed, and otherwise 1 : ) r ; (------------------------------ Main Program : ------------------------------) ( Regs: u, t, k, x ) ( Initialize u, 'RNG' counter, i.e. how many random FZ were needed : ) .0 $u ( Initialize t, 'tries' counter, i.e. how many GCD-filtered candidates tried: ) .0 $t ( Initialize k to the Bitmask that is to be imposed on candidates : ) @Candidate-Bitmask! $k ( Begin the main loop: ) : ( t := t + 1 , i.e. increment the 'tries' counter: ) t .1 + $t ( Get a candidate x, using Bitmask k, which passes Primorial Litmus: ) k @Make-Candidate! $x ( Perform MR-Shots of the Miller-Rabin Test: ) x @MR-Shots! @Iterated-MR-Test! ( If not yet found a candidate which passed both the initial Primorial Litmus and then the full number of M-R shots, then cycle the loop : ) , ( At this point, we have found a 'probable prime' candidate, and will print: ) ( ... the Bitmask used : ) [Bitmask Imposed on Candidates : ] k # ( ... the number of 'passing' M-R shots required for termination : ) [Number of Mandated M-R Shots : ] @MR-Shots! # ( ... the 'RNG shots' counter : ) [Total Number of Random FZ Used : ] u # ( ... the 'tries' counter, i.e. how many passed Primorial Litmus : ) [GCD-Filtered Candidates Tested : ] t # ( ... finally, the candidate which passed all of the requested tests : ) [Probable Prime Integer : ] x # ( Now, terminate with a 'Yes' Verdict, as we have succeeded : ) QY (--------------------------------~~The End~~---------------------------------)
Let's execute this Tape in a Peh session with a FZ Width of 2048:
cat 2048_rng_prime.peh | ./ffa/ffacalc/bin/peh 2048 32 10000 0 /dev/ttyUSB0
... the above presumes that the reader has a properly-initialized FG device connected on /dev/ttyUSB0. If this is not the case, for this didactic example you may substitute e.g. /dev/random or whatever sad TRNG substitute you may happen to have available.
One possible output of this Peh Tape, re-indented for clarity :
Bitmask Imposed on Candidates : 80000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000001 Number of Mandated M-R Shots : 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000020 Total Number of Random FZ Used : 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000063 GCD-Filtered Candidates Tested : 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000016 Probable Prime Integer : C355B3D2F3FBC7EE6F6FA56D367A22026ADBAE7F8FD63C60805BB23F018F3E84B 0AFB2E965D635F9E886F9A17DFD853FC6DF5C813F5C6D0CC690470A0DC70D716D 10245353341754E379092702B8026CD4E79AC41336D1F854B3C76FB86590B4B26 2F951DA64B7F7AF58FDD23EAF8200C0D755F0276416654B93241DF86F7E8896D4 D58BDC83F1760E82BAE5B03A464F8CEB3E813E8312E5F2251736AFAAA20D72D65 9006D334E81B926C4F4216E02A1B651043E26880AF90A6C756065675DF196DB83 0E81D8856FFFA82D3668B3796B3AAF8C54C75445B36CB5956385DBC3E4F52A9A7 1C2ABC4E35B69B38AC0682DC55F0561067CEB07B67736B81BC618D285
Now... stop! It's time for some more homework...
Chapter 18C, Exercise 2:
Produce a hundred outputs using the supplied Peh Tape. Verify their "probable primality" using your favourite computer algebra system.
Chapter 18C, Exercise 3:
Does the algorithm offered above for cryptographic prime generation leak secrets via a timing or other side-channel? Prove your conjecture. Assume that all operations offered in Peh as constant time actually provide this guarantee on your irons.
Chapter 18C, Exercise 4:
Suppose you were to "economize" on RNG entropy and iterate over successive odd integers in search of a prime, starting from a random integer, as e.g. OpenSSL and Koch's GPG do, rather than discarding every RNG output that was rejected by either litmus. What effect would this have on side-channel leakage of secrets? Suppose you were able to time an opponent's Koch-style prime generator in such a way that you know the total number of rejected candidates prior to the discovery of a "probable prime". How many bits of your opponent's cryptographic prime can you derive from this information?
Chapter 18C, Exercise 5:
Produce a hundred outputs using the supplied Peh Tape. Given what you know about the distribution of primes, do the statistics for pre- and post- GCD-litmus candidate counts conform to your expectation?
Chapter 18C, Exercise 6:
Modify the supplied prime generator Peh Tape to report the counts of candidates which passed a particular number of Miller-Rabin shots prior to failure, for all counts ranging from 1 to the maximum allotted number of shots. Do the counts conform to what you would expect based on your understanding of the Miller-Rabin algorithm?
Chapter 18C, Exercise 7:
Suppose you were generating the secret primes P and Q for use with the RSA cryptosystem. How many bits of "uncertainty" of the product P × Q are lost by forcing the uppermost bit of P and Q to equal one? Describe a practical algorithm for maximizing the entropy of P × Q. Implement it as a Peh Tape.
In Chapter 19, we will begin to tie up the remaining "loose ends" which stand in the way of battlefield use of the Peh system.
