[HN Gopher] Galois field instructions on 2021 CPUs
___________________________________________________________________
Galois field instructions on 2021 CPUs
Author : 082349872349872
Score : 126 points
Date : 2022-11-06 14:07 UTC (8 hours ago)
(HTM) web link (www.corsix.org)
(TXT) w3m dump (www.corsix.org)
| nullc wrote:
| The 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).
| sbf501 wrote:
| Why 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?
| AlotOfReading wrote:
| All modern computers are implemented with binary digital logic.
| If you build the hardware the obvious, computing mod 256 is
| just masking the lower 8 bits or nothing at all if it's an 8
| bit register. Computing mod arbitrary N is equivalent to doing
| integer division, which is an inherently complex operation
| that's typically anywhere from 10-100x slower. It also scales
| much worse for very large operands.
| [deleted]
| jacoblambda wrote:
| `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]
| sbf501 wrote:
| So P=256 cannot define a field because it isn't prime?
| creata wrote:
| There 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 wrote:
| Ah, thanks! Fields are a lot less intimidating than I
| thought they would be! Well, I mean: the basic idea
| (after reading these replies + wikipedia).
| vmilner wrote:
| There is a finite field (or Galois field GF(p)) of size p
| for any prime p. This can be exhibited by integers mod p.
|
| There are also finite (Galois) fields GF(p^n) of size p^n
| (positive integer powers of p)
|
| These can be exhibited by polynomials with coefficients
| in the GF(p) field with up to n terms.
|
| Eg for p = 2 and n = 3
|
| 0
|
| 1
|
| x
|
| 1 + x
|
| 1 + x + x^2
|
| 1 + x^2
|
| x + x^2
|
| x^2
| chriswarbo wrote:
| It's mentioned later, but the "math friendly" versions satisfy
| the axioms of a group and a field, which only works if the
| modulus is a prime.
|
| In particular, all non-zero values have a unique inverse:
|
| > As 251 is prime, this reduction rule is math-friendly. By
| that, I mean that for any x other than zero, there is some y
| such that x * y == 1. For example, taking x of 16, we have 16 *
| 204 == 1. This property is not true for the 256 == 0 reduction
| rule; with that rule, there is no y such that 16 * y == 1.
| Where it exists, this y can be called inv(x) or 1/x.
| kccqzy wrote:
| The article is trying to get to the concept of a group inverse
| without using too much jargon. If you don't mind jargon, as
| usual you'll want to go to Wikipedia to learn more.
|
| https://en.wikipedia.org/wiki/Multiplicative_group_of_intege...
| wging wrote:
| I'd suggest https://en.wikipedia.org/wiki/Finite_field -
| they'd probably get to the page you linked in trying to
| understand finite fields, but finite fields (AKA Galois
| fields) are _exactly_ what the post is about.
| tenebrisalietum wrote:
| Converting 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.
| k__ wrote:
| Do such hardware enhancements help with ECC performance or does
| ECC on other fields?
| nullc wrote:
| Do 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
| k__ wrote:
| I meant the latter, thanks.
| baby wrote:
| I 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#pal...)
| NickM wrote:
| Could someone with more knowledge than myself help explain what
| the practical applications of this are?
| greesil wrote:
| I guess cryptography, but they're also used in GPS, and CDMA.
| karma_fountain wrote:
| Error correcting codes, specifically
| https://en.wikipedia.org/wiki/BCH_code
| corsix wrote:
| The next article in blog order is one application:
| 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
| nwellnhof wrote:
| > algorithms that are similar to AES but not exactly AES
|
| The SM4 cipher, for example:
| https://en.wikipedia.org/wiki/SM4_%28cipher%29
| salicideblock wrote:
| Expanding 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.
| Rebelgecko wrote:
| I 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
| adonovan wrote:
| You can think of a Galois field as a specially chosen
| permutation of a set of numbers such as 0-255 and a
| redefinition or remapping of the arithmetic operators + - * /
| such that each one is reversible: if a op b = c, then given c
| and b you can find a by applying the inverse of op. (In normal
| arithmetic of course, multiplication and division aren't
| reversible because of zero.) The actual operators aren't ADD
| SUB MUL DIV, but they are like them in the sense that they are
| easy to implement in a hardware ALU as functions over bit
| patterns.
|
| This unlocks all kinds of clever techniques. For example, it
| lets you efficiently compute a "rolling" hash of every n-byte
| substring of a document, by simply sliding an n-byte window
| across the document one byte at a time, multiplying the
| previous hash by the incoming byte and dividing by the outgoing
| byte. This has lots of applications in cryptography,
| compression, searching, and so on.
| superjan wrote:
| Thanks for the explanation. Are addition/ multiplication
| still linked the same was as for normal integers? Like 2*a ==
| a + a? Edit: I do get that '2' in GF might not be the same as
| integer 2.
| gizmo686 wrote:
| Pretty much. Fields are generally considered to be the
| structure that links the common notion addition and
| multiplication. In particular, you need 3 things to qualify
| as a field:
|
| 1) Multiplication behaves as expected (without reference to
| addition)
|
| 2) Addition behaves as expected (without reference to
| multiplication)
|
| 3) a(b+c) = ab + bc
|
| The third requirement is the only part of fields that links
| multiplication to addition. In particular, if we assume
| that 2=1+1, then we have: 2a = (1+1)a = a(1+1) = a+a
| tmaly wrote:
| A long time ago in my university days we implemented blowfish
| encryption on an FPGA using Galois fields.
___________________________________________________________________
(page generated 2022-11-06 23:00 UTC)