asciilifeform: bvt: possibly the bolix machines also ( they did it in vertical microcode, iirc, tho, and in nonconstant time unsurprisingly )

asciilifeform: ( ada standard btw trivially allows for types where this holds true automatically , i.e. throws exception for overflow. but this is not only massively unconstanttime but the overhead is gigantic )

asciilifeform: chances are that it wouldn't, tho, given how the table still has to be indexed via fz_mux in order to prevent variant (i.e. nonconstanttime) memory indexing

asciilifeform: i prolly oughta add to the http://btcbase.org/log/2019-01-20#1888508 thing : 1 of the items which seemed like a speedup, but in actual practice sucked, was the use of (constant-time) 2 (ditto 4) -bit windows for modexp ( iirc apeloyee suggested ) ☝︎

asciilifeform: ( the 64x64 iron multer in amd/intel, possibly surprisingly, is in fact constant time, in all boxes i've tested to date )

asciilifeform: mircea_popescu: it is conceivable that the ones currently sold are constant time , i simply haven't tried'em.

asciilifeform: mircea_popescu: that wouldn't be constant-time...

asciilifeform: i saw. and imho would be interesting to have a constant-spacetime, no-floats fft

asciilifeform: i take a kind of perverse entomological interest in sad rsatrons. ( e.g.: bolix, interestingly, had a -- nonconstant time, of course -- bignum stack, but at least it was reasonably compact.. )

asciilifeform: this allows 'P' to be a constant-spacetime operation, and hands the decision of 'just how important to constant-time the whole prime generation' to the author of the tape.

asciilifeform: btw per asciilifeform's chalkboard, the physical cost of constanttime m-r is ~equal to that of (2 modexps of the given width) x (number of witnesses) . ☟︎

asciilifeform: which means ugh, for e.g. 2048bit candidate being tested for primality in constant time, ~each~ witness needs 1 modexp and 2047 modsquares !

asciilifeform: http://p.bvulpes.com/pastes/TkmoM/?raw=true << sneak peek of constant-time stein. ( afaik there isn't one anywhere else on the net, funnily enuff. )

asciilifeform: if primality test ( which consists of GCD ~and~ m-r, in order to constant-time ) does not exceed 0.0356sec, then on machine with 1 FG it can be considered that the FG is the limiting reactant.

asciilifeform: ( afaik nobody ever proved that you couldn't, and the nonconstanttime lehmer and variations run in ~O(n) for ~all inputs )

asciilifeform: in other noose, constant-time stein-gcd aint so bad, 1msec (2048bit operands) , 6msec (4096bit) , 21msec (8192bit), 81msec (16384bit) ☟︎

asciilifeform: http://btcbase.org/log/2019-01-06#1884935 << i actually considered to have 'if low bit is 0 - i.e. N is even -- then montgomery, otherwise barrett' but what this does is break constanttimeism of modexp -- nao you broadcast the parity of N for whole planet, cuz entirely diff execution profiles for the 2 algos. and montgomery is at the very most a 10% revvup over barrett. ☝︎

asciilifeform: orig q was whether it is possible to improve the constant factor of stein.

asciilifeform: this much is correct, and why i have gcd to begin with. right nao i have a modified stein that goes in constanttime.

asciilifeform: this isnt catastrophic (or surprising, apeloyee warned about it yr+ ago) , and the only place where need gcd is the pre-millerrabin primorial 'divisible by small primes?' litmus. but would still be good to cut the constant down.

asciilifeform: so anyffin we do for gcd is gonna be quadratic, q is strictly re the constant factor.

asciilifeform: it is interesting to note, i did an exhaustive dig re gcd algos; and found that there are half a dozen sub-quadratic ones, but none of those can be made constant-time.

asciilifeform: otherwise can wait for asciilifeform's constant-time m-r ( or not, depending on what's in eulora war room chalkboard, i cannot presume to know what the priority is )

asciilifeform: what remains is 1) prime-baking 2) rsa (and similar cryptosystems, tho c-s dun need it) padtron -- requires constant-spacetime keccak 3) optional asmistic speedups.

asciilifeform: ( in orig timeline also did not include problem of constant-time keccak, which i presently do not have, and neither anyone else, but is necessary to fill mircea_popescu's spec for the final product )

asciilifeform: ( recall how constanttimeization is done, when converged, you set the stopper and fz_mux outputs the answer , after that algo runs however many shots remain but without affecting the output )

asciilifeform: ~without~ the 3 separate full-width subtractions that e.g. constanttimeized stein's gcd needs.

asciilifeform: mircea_popescu: i won't know whether the 'constanttimeism litmus' actuallyworx, until i dredge up an iron where it outputs negative

asciilifeform: i've actually found decent (not constant time, but didn't need, it only checked sigs) rsatrons in malware samples -- kB or so of asm. it aint exactly mystery, how to bake

asciilifeform: mircea_popescu: i didnt try patching out the test ( given as it's got montgomery, the answer will be soup ) but did try for odd exp, got ~same~ as for the nonconstanttime gmp knob ( which is pretty hilarious, means that they dun do anything differently for 'constant time' variant, evidently )

asciilifeform: fwiw ordinary (no attempt at constanttime on their end) mpz_powm() , gives 0.005s . (so the asm does help'em.)

asciilifeform: ( implication , naturally, is that even if the sig coad were to be replaced with constanttimeism, it would not appreciably change the cpu cost of noad.. )

asciilifeform: on defective (i.e. non-constanttime iron mul, or any other similar defect) they will give variant runtimes.

asciilifeform: on proper (i.e. constanttimeistic iron mul) irons, 'uniform' and 'slid' test vectors will give same (to within timer jitter) runtimes when fed to ffa (of either ch13 or ch14 variety.) ☟︎

asciilifeform: also will double as platform litmus for constanttimeitude of iron mul etc.

asciilifeform: ( the reason why worked, is that barrett is ( as shown in ch 14a ) 'too forgiving' of wrong choice of constant J . )

asciilifeform: http://btcbase.org/log/2018-12-18#1881465 << will add to this : on any hypothetical iron where add and sub aint constant-time ( i know of none , but could hypothetically exist in fyooyoor ) the overall 'is modexp constant-time' litmus will ring alarm. ☝︎

asciilifeform: !#s plus constant

asciilifeform: again -- impossible to authenticate 'did he ? or donation of constantine' w/out time machine.

asciilifeform: at 1 time, was used in the constant entry ( nibble inserter ) routine, then the latter was replaced with rewritten http://www.loper-os.org/pub/ffa/hypertext/ch13/fz_io__adb.htm#29_14 , nao sole remaining use is in the knuth divider.

asciilifeform: ( the only guarantee i can offer in good conscience is that nuffin can be broken by operating the ~external~ controls -- but even there user is required to see whether his cpu has barrel shifter (see ch13 discussion) , constant-time mul ( see ch9 discussion ) )

asciilifeform: ( bonus is that the ~output printing~ itself is constant-time, ha )

asciilifeform realized that he's gonna need a constant-time keccak for the final chapters, dun have 1 yet

asciilifeform: hardwarizable ( in the manner discussed by mircea_popescu ) also, as 'phree' side effect of the constant-spacetime. but this is yet embryonic.

asciilifeform: keep in mind that horsecocks has hardcoded constants in it that may or may not work on arm ( per bvt's dig )

asciilifeform: tldr : yet-another nonconstanttime , notfitinhead piece of shit, valuable exhibit for kunstkammer of 'how not to ada'

asciilifeform: the other is that on iron such as certain ARM ( i have not yet investigated ~which~ ) , and ppc, and certain others, there does not even exist a constant-time MUL, and one is stuck with some variant of http://www.loper-os.org/pub/ffa/hypertext/ch11/w_mul__adb.htm#33_13 -- which really begs to be asmed, is riotously inefficient

asciilifeform: mircea_popescu: serpent's constanttime tho

asciilifeform: ( the width of the constants pictured in http://ossasepia.com/2018/11/04/smg-comms-chapter-6-packing-and-unpacking-rsa/#selection-121.192-121.4240 )

asciilifeform: ( bake it in ECL, then get 'for phree' not only constant-time, but constant-current.

asciilifeform: diana_coman: they aint; recall that the square-bracketed items on right hand side are constants

asciilifeform: diana_coman: unlike, e.g., haskellists, we only do things if they make sense : as you pointed out, 'bit-vectorized' keccak aint constant time, no matter what, so no particular reason to bother with the massage

asciilifeform: ( if, btw, somebody else has the time/inclination to do the latter, i'll only say 'thx'. thing is already in xor-sat form, roll the constant term into the eqn's, set $known-schedule as the output values, and gaussian-reduce... )

asciilifeform: last col. is the constant term of the row.

asciilifeform: implicit conditionals aint evil per se , tho ; i banned them in ffa specifically as they get in the way of constanttimeism, is all ☟︎

asciilifeform: ada treats any statement that divides by anything other than an immediate constant ( incl. / or mod by a named constant ) as potentially div0-barfing

asciilifeform: Keccak_L: constant := 6; Z_Length: constant := 2**Keccak_L; << so it's 64

asciilifeform: really, 1) flatten the tree 2) group the constants together 3) xor the constants into one 4) eliminate duplicate terms

asciilifeform: diana_coman et al : http://p.bvulpes.com/pastes/uX1BM/?raw=true << for convenience, the recurrence eqs rewritten 1) as sexpr 2) with the orig constant-xors included

asciilifeform: ( dun forget to acct for the constants )

asciilifeform: so, continuing: we throw out the constants, and:

asciilifeform: there are exactly as many possible outputs as inputs, and if you xor with the constant again, you get the input back.

asciilifeform: with the tools in the actual box, however, afaik there is no headache of this kind, xor-with-constant is reversible and conserves.

asciilifeform: and the two xor's-with-constants, just the same reversible.

asciilifeform: ( for anybody who wants to take a stab at this in parallel with asciilifeform , hint : xor-with-constant is injective , can be factored out of equation; ditto sboxes )

asciilifeform: and .c is not the only os liquishit, tables of platform constants that one ends up with from avoidance of .c, is also liquishit.

asciilifeform: imho, segregating as much as possible of unix liquishit in a short .c, is cleaner than buncha Import() and hardcoded flag constants derived by guesswork

asciilifeform: if could afford asic with ~100k transistors -- could have 256x256 multiplier, have 4096bit constant-spacetime rsa in coupla millisecond...

asciilifeform: was speaking of where it recalculates what is by all rights a 100% constant value, 9000 times/hr, eternally ☟︎