tmsr - Search: modular "exp"

asciilifeform: ( modular exponentiation is , in all operations which feature it )

asciilifeform: BingoBoingo: to nitpick, s/in Barrett's Modular Reduction/in modular exponentiation/ , koch dun use barrett ( he uses montgomery, which dies on even numbers, lol )

asciilifeform: user of pcode never has to manually consider memory, so long as he knows how much stack to instantiate it with ( e.g. for modular exponentiation, you need 3 FZ worth of stack ) , and it properly eggogs if you mismeasure.

mircea_popescu: Turns out, Koch’s pile of shit, despite eschewing constant time arithmetic, and being implemented in Overflowandcrashlang… loses the footrace, when given a full-width modular exponentiation (i.e. one where it cannot cheat by skipping over leading zeroes.)

asciilifeform: hey NoSatoshisHear -- you say you read the ffa series ? in what order of complexity does modular exponentiation run ?

asciilifeform: modular exp is intrinsically costlier , at least on pc iron, than the idjit rotorization used in symmetrics

asciilifeform: diana_coman: ffa arithmetic stack is theoretically available. however until i have barrett reduction going, it's a ~30 second modular exponentiation ( i.e. per rsa op )

mircea_popescu: is it or is it not true a modular exponentiation in current gpg takes, on your chosen machine, 0.26 seconds.

a111: Logged on 2017-09-16 15:31 asciilifeform: in other olds ( i dun think i posted this measurement ) the NAIVE modular exponentiator takes 51.3 seconds per 4096b a*b mod m , on the 'standard' test box

asciilifeform: when bitness is B, a modular exponentiation takes B mod-muls and B mod-squares, each of which produces a 2B-wide item that gets div'd . that's 2B 2B-wide divisions.

asciilifeform: in other olds ( i dun think i posted this measurement ) the NAIVE modular exponentiator takes 51.3 seconds per 4096b a*b mod m , on the 'standard' test box ☟︎

asciilifeform: mircea_popescu: the classical ffa exponentiator, for reference, looks like http://wotpaste.cascadianhacker.com/pastes/S4dWM/?raw=true . the ~modular~ exponentiator must look like http://wotpaste.cascadianhacker.com/pastes/AiB9t/?raw=true . however it needs 'first, steal the chicken', i.e. FZ_Mod_Mul and FZ_Mod_Square .

asciilifeform: and it is not only O(N^3), but when you modularly exponentiate it actually gets done B times, and not to B-sized inputs, but 2B ( because we have a multiply and then also a square, in each step of the B-step modular exponentiation bitwise )

asciilifeform: ( the rsa operation, the one and only, is modular exponentiation. but it is made trivially from modular multiplication . )

mircea_popescu: asciilifeform amusingly, the guy complains about the modular exponentiation not being constant time. maybe write to him ask where he ever saw a sane algo ?

asciilifeform: meanwhile from literature search, every article ever, apparently, written re 'constant time modular exponentiation' proposes... tables

asciilifeform: aite, nao all asciilifeform needs is a constantspacetime MODULAR exp algo that can be expressed with the mux primitive

asciilifeform: the 'release modular exponentiation result after time T' is an armoured propeller.

sina: also: Complete break of RSA-1024 as implemented in Libgcrypt https://eprint.iacr.org/2017/627.pdf, "And 13% of RSA-2048 keys. Whoopsie!", "The new bit is showing that LtR sliding windows are a Very Bad Choice for modular exponentiation. Very nice."

asciilifeform: this means ALL ciphertext is the output of rsa modular exponentiations.

mircea_popescu: asciilifeform i imagine he means that it overflow between the exp and the modular steps.

asciilifeform: other thing: ~modular~ exp can't oveflow !

asciilifeform: what i don't yet have is a fixed-time modular exponentiator.

asciilifeform: does anybody have a favourite constant-time modular-exp ??

asciilifeform: for some peculiar reason, everybody else (afaik) who implemented a bignumtron, only did this (or claimed, at any rate) for modular exponentiation -- but not for its subcomponent ops

mircea_popescu: the thing is called modular exponentiation you know :D

asciilifeform: this comes with the territory of 'naked' register. in ada you have to explicitly ask for this horror, it is called 'modular type'. all c types are it.

asciilifeform: modular exponentiation

asciilifeform: btw rsa only needs 1 op, modular exp

asciilifeform: 'If one tries to calculate a modular exponentiation with the base equal to the modulus (a^b mod a, code) it would return an error. If one tries to calculate a modular exponentiation with the base zero (0^b mod a, code) it would crash with an invalid free operation, potentially leading to memory corruption.'

asciilifeform: when done correctly - no. we don't sit here and argue about how the modular exponentiations came out.

asciilifeform: tx-making - modular exp.

assbot: Logged on 23-12-2015 22:29:00; ascii_field: thestringpuller: be grateful that you don't have to modular-exponentiate by hand.

ascii_field: thestringpuller: be grateful that you don't have to modular-exponentiate by hand. ☟︎

asciilifeform: sane people understand enough to wish for their rsa modular exponentiations to NOT HAPPEN UNDER WINBLOWZ

asciilifeform: prototype is essentially an 'rpn calculator' where you can push bignums on the stack and instruction 0x01 --> 'pop two, multiply, push back' or 0x70 --> modular-exponentiate, etc.

asciilifeform: it is, in principle, possible for dr. evil's cpu to recognize when, e.g, given version of gpg is in the process of taking the modular exponentiation.

kakobrekla: good thing my mattress is modular, i can easily expand to bed more women

mike_c: cancellations deep inside GnuPG’s modular exponentiation algorithm. This causes the special value