Timeline for Why is multiplication uncommon in cryptographic primitives?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2022 at 18:27 | comment | added | Sam Ginrich | Wonder, whether there are asymmetric cryptosystems without finite field models. | |
| Sep 29, 2017 at 4:42 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Allude to how issuses 3 and 5 can be taken care of, by example of IDEA
|
| Sep 28, 2017 at 13:19 | comment | added | otus | @Fanael most ciphers and such have some parallelism by design. E.g. if you look at argon2's permutation in appendix 2 of the specification, you can see that 16 64-bit words are mixed in sets of 4 so that computations from different $G$ can also be interleaved. | |
| Sep 28, 2017 at 5:50 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Add 5 per comment
|
| Sep 28, 2017 at 5:38 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Link to x64 source
|
| Sep 28, 2017 at 5:11 | comment | added | otus | As for a source, I recommend agner.org/optimize/instruction_tables.pdf | |
| Sep 28, 2017 at 5:09 | comment | added | otus | @Fanael, like fgrieu basically wrote it depends on whether you mean reciprocal throughput or latency. Modern x86 execution units typically have 1 cycle reciprocal throughput for multiplication, but e.g. Ryzen has 3-cycle latency. That is, if you are doing independent multiplies you get a similar throughput as with simpler ops, but if the next instruction needs the result you are slowed down. Anyway, with truly fast ciphers you need to also consider vectorization and things get more complicated. | |
| Sep 28, 2017 at 5:03 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
"extremely uncommon"
|
| Sep 28, 2017 at 4:58 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 28, 2017 at 4:52 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 28, 2017 at 4:46 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Latency
|
| Sep 27, 2017 at 20:26 | vote | accept | EPICI | ||
| Sep 27, 2017 at 17:06 | comment | added | Ella Rose | (+1) There's also the matter of the existence of the modular inverse: If you want to have an inverse permutation, you require multiplication by the modular inverse. Since the multiplier operates modulo machine sized words, multiplication via a number that possesses 2 as a factor is not efficiently invertible. The words of the state cannot be guaranteed to not possess 2 as a factor (and almost certainly will at some point), and so using words of the state as inputs to the multiplier is not as straightforward as just using addition or xor. | |
| Sep 27, 2017 at 11:42 | comment | added | Samuel Neves | Two AES finalists used multiplications not by constants: RC6 and MARS. The eSTREAM finalist Rabbit does as well. Today, Lyra2 and Argon2 use multiplications in their BLAKE2-derived round function BlakMka. Multiplication as a primitive gives a nice amount of 'mixing', but it makes the cipher harder to analyze. | |
| Sep 27, 2017 at 7:33 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Add reference
|
| Sep 27, 2017 at 7:08 | history | answered | fgrieu♦ | CC BY-SA 3.0 |