7 ms·
Galois field instructions on 2021 CPUs
- k__ 4y agoDo such hardware enhancements help with ECC performance or does ECC on other fields?
- nullc 4y agoDo you mean Error Correcting Codes or Elliptic Curve Cryptography? In the former, yes, in the latter mostly* no-- as characteristic-2 field elliptic curve crypto isn't common these days due to a weaker and more complicated security story. *Mostly but not entirely, e.g. https://eprint.iacr.org/2022/1325 https://eprint.iacr.org/2022/1325
- k__ 4y agoI meant the latter, thanks.
- throwaway81523 4y agoElliptic curve cryptography is usually done with prime fields since there have been too many breaks against systems using binary fields, the ones that these cpu instructions operate on. Binary field arithmetic, as people have mentioned, are used widely for error correcting codes, and to a lesser extent in cryptography for modes like AES-GCM and inside of AES itself.
- nullc 4y agoThe by-a-constant trick using smaller lookup tables at the end can be done with pretty much arbitrary table sizes-- it's particularly helpful to fine tune the table size if you're building the table on the fly (e.g. because you perform many multiplications each with a dynamic value).
- NickM 4y agoCould someone with more knowledge than myself help explain what the practical applications of this are?
- greesil 4y agoI guess cryptography, but they're also used in GPS, and CDMA.
- karma_fountain 4y agoError correcting codes, specifically https://en.wikipedia.org/wiki/BCH_code https://en.wikipedia.org/wiki/BCH_code
- corsix 4y agoThe next article in blog order is one application: https://www.corsix.org/content/reed-solomon-for-software-raid https://www.corsix.org/content/reed-solomon-for-software-rai... Another application is crypto: the SubBytes step of AES maps very neatly onto gf2p8affineinvqb, so algorithms that are similar to AES but not exactly AES could make use of gf2p8affineinvqb
- salicideblock 4y agoExpanding on this,a very nice property of Galois Counter Mode (GCM) for AES is that encrypting one block does not require the previous block to be encrypted, like in AES-CBC. This means that AES-GCM can take advantage of data parallelism and there are big speedups in threaded and pipelined CPUs. In short, you can get big latency and throughout gains by using AES-GCM over AES-CBC.
- nwellnhof 4y ago> algorithms that are similar to AES but not exactly AES The SM4 cipher, for example: https://en.wikipedia.org/wiki/SM4_%28cipher%29 https://en.wikipedia.org/wiki/SM4_%28cipher%29
- Rebelgecko 4y agoI think these instructions can drastically speed up the GCM part of AES-GCM, which is used by a lot of https websites (not sure if it's the most popular TLS cipher, but it's almost definitely top 3). Part of why Salsa/Chaha become popular on phones and embedded devices is because for a while only x86 had specialized instructions for GCM
- baby 4y agoI was hopping this would be about larger fields. For zero-knowledge proofs we need to handle 255-bit field and operations are quite slow due to that (https://o1-labs.github.io/proof-systems/specs/pasta.html#pallas https://o1-labs.github.io/proof-systems/specs/pasta.html#pal...)
- tenebrisalietum 4y agoConverting arithmetic to things based on polynomials - when I was reading about the Atari 2600's TIA I recall some things about how polynomial counters were implemented internally to avoid having to deal with decimal->binary conversion in the chip (this is an 8-bit ASIC clocked at NTSC rate that generates a TV signal and must be manipulated in near real time by the CPU to generate graphics). Wondering how this could be related/applicable.
- DerekL 4y agoI don't see how decimal-to-binary conversion would have anything to do with the TIA chip. I suspect that it used a polynomial counter instead of a binary integer counter because it used fewer gates and had less delay. By the way, the CPU, like many others back then, could do addition and subtraction with binary-coded decimals.
- tenebrisalietum 4y agoTo position objects horizontally ideally you would have a register where you load a value between 0 and 160, but instead you have to strobe a register when the CRT beam is near the horizontal position you want, which will be +/- some pixels due to the CPU being 1/3 the clock of the TIA and 6502 instructions consuming 2 to 8 cycles. So then you have to "fine tune" using an additional register to shift it left/right -7 to 8 pixels.
- tmaly 4y agoA long time ago in my university days we implemented blowfish encryption on an FPGA using Galois fields.
- sbf501 4y agoWhy is 256 == 0 computer friendly and 251 == 0 reduction math friendly? Other than modulus bias, that initial assertion isn't clear to me. I mean, you can say "well, 251 isn't 2^N" which is abundantly obvious, but why does that matter? Is it because you can't create a bit polynomial for a non-power-of-two reduction?
- CuriousCosmic 4y ago`251 == 0` is maths friendly because 251 is a prime number. Like the article outlines, this means that for any given number x in the field, there exists some other y where `x * y == 1`. This isn't necessarily the case for non-primes. When that breaks down, you can no longer invert numbers in a reversible way. aka `1/(1/x) == x` no longer holds true. This means you can no longer easily manipulate values or equations using the common set of properties established for most mathematics, hence "not maths friendly".
- deleted 4y ago[deleted]
- sbf501 4y agoSo P=256 cannot define a field because it isn't prime?
- creata 4y agoThere is a field with 256 elements, because 256 is the power of a prime. But that field is not the integers mod 256: it has different rules for addition and multiplication.
- sbf501 4y agoAh, thanks! Fields are a lot less intimidating than I thought they would be! Well, I mean: the basic idea (after reading these replies + wikipedia).
- 4y ago
- ngcc_hk 4y agoMy intro take : for base 4 you have a set of number {1 2 3 4}. Imagine you start with 2. Can you use multiplication to get to 1. No. Because it goes to 2 then 4 then 2 … However if you do base 5 which is a prime. Then {1 2 3 4 5} meant start with any number you can reach the others by multiplication. (if you use 0…3 and 0…4 you have to mention except 0). We use 2*N as basis in computer which is non-prime though. The article tried to explain how to use polynomial and certain intel/arm feature to handle this …