6 ms·

> Wait, what? So many articles and journals I read on the topic just talk about prime fields, modular reduction and blah blah blah like it’s asking someone to b

> Wait, what? So many articles and journals I read on the topic just talk about prime fields, modular reduction and blah blah blah like it’s asking someone to buy milk and eggs at the grocery store. No kidding, it's so frustrating! I have to read some articles/ papers like 20x and open a bunch of wikipedia tabs to understand wtf they're talking about. If they gave a simple, high level explanation it would save tons of time - while a wikipedia article is going to be very in depth, it's not tailored to the context of what I'm reading, so I often have to look at a whole bunch of things to start to build a good model in my head for wtf they're trying to convey. This post, on the other hand, is perfect for me. Thank you so much for writing it I'm learning a ton.

bunnie 5y ago
Thanks! It's good to know I'm not alone in feeling this way. This is actually an abridged version, if you click into the link for the "datasheet" (https://ci.betrusted.io/betrusted-soc/doc/engine.html https://ci.betrusted.io/betrusted-soc/doc/engine.html) you can find all the gory details down to the register level...
- amirhirsch 5y ago
  I liked your struggle with the corner-case :)
- staticassertion 5y ago
  Awesome, much appreciated, I'll dig into it. I was actually just using the dalek crate myself quite heavily this week, so this is great timing.
dragontamer 5y ago
https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller), but GF2 and GF3 are too small to really see where the beauty of all this math lies. ------ GF5 (which is simply "arithmetic modulo 5") has all the properties of Real-numbers "we care about", and none of the hassles of decimals or partial numbers. GF5 is simply arithmetic modulo 5. Its really easy to do. 4 + 2 == 1. (Aka: 4 + 2 mod 5 == 6 mod 5 == 1). Addition and multiplication are easily proven to be the same. The fun starts when you start doing roots, exponents and logarithms (!!!). Take the definition of addition / multiplication above (aka: addition / multiplication modulo 5) and redefine square-root, exponents, and logarithms to be consistent with it. That is to say: 2 * 3 == 1. Which means that 3 == (1/2) (yes, "one half" is now 3 in GF5). Which means 3 is 2^(-1). * 2^2 == 4. * 2^2 * (2^-1) == 4 * 3 == 12 mod 5 == 2. Which means 2^2 * 2^-1 == 2^(2-1) and look, exponents work as expected. Feel free to play around with all the numbers: you'll find that exponents work once you match this new "definition" of exponents. --------- Because exponents work, logarithms work. Because everything works, we can have complicated ellipical curves defined over the numbers {0, 1, 2, 3, 4} (aka: the numbers mod 5) and have everything work out mathematically. -------- The hard part is proving that all of this works in GF(5^2) aka GF25. It turns out that you can't just "mod 25" the stuff, you need to do an extension field (and basically make a complex number out of things). Once you understand GF25 extension fields and its relationship with GF5, then it becomes easy to generalize that to GF2 and its extension fields GF(2^8) (aka: binary numbers of 8 bits) or GF(2^32) (aka: 32-bit numbers). Turns out for extension fields (like GF(5^2) aka GF25) you need to redefine multiplication and addition as well and then rebuild all the math from the ground up off of this new definition of addition and new definition of multiplication. And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers. Bonus points: GF(2^32)'s new addition operator is just an xor. Only multiplication is difficult. But once you do that, it all __JUST WORKS__ and is amazing. ---------- Galois Fields are a way to "cheat" a definition of logarithm, exponents, square roots, multiplication, division, and addition (by redefining these operations). It turns out that these operations continue to work "as expected" in the Galois Field... as long as you're cool with the new definitions of them. ------ EDIT: I'm slightly wrong. Seems like Curve25519 is a prime field and not an extension field. So this is more similar to GF5 than it is to GF(2^32). Still, other elliptical curves are in GF(2^32) or other extension fields, so the study of extension fields is useful for other curves. Curve25519 can be understood with just the GF(5) description I gave earlier in this post. Prime fields are really simple: just mod(the prime number) and you're set. There's some weird properties that can accelerate speed (Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster).
- fogof 5y ago
  > GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller) There is also a field of 4 elements, since 4 is a power of a prime.
  - dragontamer 5y ago
    Fair. I guess I was implicitly staying away from extension fields because people's attention span will start drifing away the minute I start to attempt to explain how to perform modulo polynomial arithmetic over irreducible polynomials. Prime fields (GF2, GF3, GF5...) are just easier to explain than extension fields (GF (2^2), GF(3^2), GF(5^2)... GF(2^8)...)
- nullc 5y ago
  Nice comment! Some nits. > Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster that's not just a weird property you can use for performance, standard grade-school division doesn't work in fields because the results are outside of the field. So division is redefined using the modular inverse-- which has a natural definition the modular inverse a of element x is the value that makes the product ax equal the identity. The "cool optimization" though is that since modular inverses are kinda expensive, you can rewrite your arithmetic to keep things in fractional form as long as possible and get a big speed-up. [This also applies to ordinary numbers with division: E.g. use newton's method to compute square roots but don't do any division, keep everything as fractions -- with that trick you can compute pretty accurate square roots in your head! ... seems people don't get taught this kind of thing any more because of access to calculator :) ] > And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers. This makes it sound like you're saying that regular computer arithmetic is GF(2^32). :) In my experience GF(2^32) arithmetic is fairly uncommon! Work in GF(2^8) is extremely common, e.g. it's used all over in error correcting codes. The field size is common because it's perfectly reasonable to implement multiplication using a log and inverse log table. For 2^32 you really want a CLMUL instruction if you want high performance. Though once you have one you can easily go to 64-bits if it's useful for your application. You won't find a lot of binary extension field (GF(2^n)) stuff in crypto these days except sometimes hidden deep inside a block cipher (like the AES sbox) because the extensions create a lot of additional and surprising algebraic structure. E.g. in these fields (x + y)^2 == (x^2 + y^2)! ( https://en.wikipedia.org/wiki/Freshman%27s_dream https://en.wikipedia.org/wiki/Freshman%27s_dream ) Unless you're doing something where the structure is useful, it's better to not have it. Error correcting codes, CRCs, hashes, and related stuff-- however, has lots of it.
Kalium 5y ago
This feels, to me, like the complaint of someone with a general technical grounding going into a narrow specialization and discovering they understand none of the terminology. This is exactly how I felt when I was learning Haskell and hearing about eta conversions and pointfreeness and so on. Each new bit of terminology had a precise definition, but specialists writing primarily for one another were not inclined to offer definitions each time. They didn't need them and neither did their anticipated audience. I had to learn the terminology and jargon so I could understand what they were talking about, and high-level abstracted explanations were not going to be enough to participate usefully. I had to learn the basics. Similarly, Watson & Crick's seminal paper might not have been the best of all possible times to stop and define an X-ray or how crystallography worked. So yes, just instantiate the metaclass, implement the interface, and go buy milk. Easy. You just have to learn what each of those things actually means, especially if the details might be important (and in cryptography, that's always the case).

bunnie 5y ago

Thanks! It's good to know I'm not alone in feeling this way. This is actually an abridged version, if you click into the link for the "datasheet" (https://ci.betrusted.io/betrusted-soc/doc/engine.html https://ci.betrusted.io/betrusted-soc/doc/engine.html) you can find all the gory details down to the register level...

amirhirsch 5y ago
I liked your struggle with the corner-case :)
staticassertion 5y ago
Awesome, much appreciated, I'll dig into it. I was actually just using the dalek crate myself quite heavily this week, so this is great timing.

dragontamer 5y ago

https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller), but GF2 and GF3 are too small to really see where the beauty of all this math lies. ------ GF5 (which is simply "arithmetic modulo 5") has all the properties of Real-numbers "we care about", and none of the hassles of decimals or partial numbers. GF5 is simply arithmetic modulo 5. Its really easy to do. 4 + 2 == 1. (Aka: 4 + 2 mod 5 == 6 mod 5 == 1). Addition and multiplication are easily proven to be the same. The fun starts when you start doing roots, exponents and logarithms (!!!). Take the definition of addition / multiplication above (aka: addition / multiplication modulo 5) and redefine square-root, exponents, and logarithms to be consistent with it. That is to say: 2 * 3 == 1. Which means that 3 == (1/2) (yes, "one half" is now 3 in GF5). Which means 3 is 2^(-1). * 2^2 == 4. * 2^2 * (2^-1) == 4 * 3 == 12 mod 5 == 2. Which means 2^2 * 2^-1 == 2^(2-1) and look, exponents work as expected. Feel free to play around with all the numbers: you'll find that exponents work once you match this new "definition" of exponents. --------- Because exponents work, logarithms work. Because everything works, we can have complicated ellipical curves defined over the numbers {0, 1, 2, 3, 4} (aka: the numbers mod 5) and have everything work out mathematically. -------- The hard part is proving that all of this works in GF(5^2) aka GF25. It turns out that you can't just "mod 25" the stuff, you need to do an extension field (and basically make a complex number out of things). Once you understand GF25 extension fields and its relationship with GF5, then it becomes easy to generalize that to GF2 and its extension fields GF(2^8) (aka: binary numbers of 8 bits) or GF(2^32) (aka: 32-bit numbers). Turns out for extension fields (like GF(5^2) aka GF25) you need to redefine multiplication and addition as well and then rebuild all the math from the ground up off of this new definition of addition and new definition of multiplication. And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers. Bonus points: GF(2^32)'s new addition operator is just an xor. Only multiplication is difficult. But once you do that, it all __JUST WORKS__ and is amazing. ---------- Galois Fields are a way to "cheat" a definition of logarithm, exponents, square roots, multiplication, division, and addition (by redefining these operations). It turns out that these operations continue to work "as expected" in the Galois Field... as long as you're cool with the new definitions of them. ------ EDIT: I'm slightly wrong. Seems like Curve25519 is a prime field and not an extension field. So this is more similar to GF5 than it is to GF(2^32). Still, other elliptical curves are in GF(2^32) or other extension fields, so the study of extension fields is useful for other curves. Curve25519 can be understood with just the GF(5) description I gave earlier in this post. Prime fields are really simple: just mod(the prime number) and you're set. There's some weird properties that can accelerate speed (Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster).

fogof 5y ago
> GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller) There is also a field of 4 elements, since 4 is a power of a prime.
- dragontamer 5y ago
  Fair. I guess I was implicitly staying away from extension fields because people's attention span will start drifing away the minute I start to attempt to explain how to perform modulo polynomial arithmetic over irreducible polynomials. Prime fields (GF2, GF3, GF5...) are just easier to explain than extension fields (GF (2^2), GF(3^2), GF(5^2)... GF(2^8)...)
nullc 5y ago
Nice comment! Some nits. > Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster that's not just a weird property you can use for performance, standard grade-school division doesn't work in fields because the results are outside of the field. So division is redefined using the modular inverse-- which has a natural definition the modular inverse a of element x is the value that makes the product ax equal the identity. The "cool optimization" though is that since modular inverses are kinda expensive, you can rewrite your arithmetic to keep things in fractional form as long as possible and get a big speed-up. [This also applies to ordinary numbers with division: E.g. use newton's method to compute square roots but don't do any division, keep everything as fractions -- with that trick you can compute pretty accurate square roots in your head! ... seems people don't get taught this kind of thing any more because of access to calculator :) ] > And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers. This makes it sound like you're saying that regular computer arithmetic is GF(2^32). :) In my experience GF(2^32) arithmetic is fairly uncommon! Work in GF(2^8) is extremely common, e.g. it's used all over in error correcting codes. The field size is common because it's perfectly reasonable to implement multiplication using a log and inverse log table. For 2^32 you really want a CLMUL instruction if you want high performance. Though once you have one you can easily go to 64-bits if it's useful for your application. You won't find a lot of binary extension field (GF(2^n)) stuff in crypto these days except sometimes hidden deep inside a block cipher (like the AES sbox) because the extensions create a lot of additional and surprising algebraic structure. E.g. in these fields (x + y)^2 == (x^2 + y^2)! ( https://en.wikipedia.org/wiki/Freshman%27s_dream https://en.wikipedia.org/wiki/Freshman%27s_dream ) Unless you're doing something where the structure is useful, it's better to not have it. Error correcting codes, CRCs, hashes, and related stuff-- however, has lots of it.

Kalium 5y ago

This feels, to me, like the complaint of someone with a general technical grounding going into a narrow specialization and discovering they understand none of the terminology. This is exactly how I felt when I was learning Haskell and hearing about eta conversions and pointfreeness and so on. Each new bit of terminology had a precise definition, but specialists writing primarily for one another were not inclined to offer definitions each time. They didn't need them and neither did their anticipated audience. I had to learn the terminology and jargon so I could understand what they were talking about, and high-level abstracted explanations were not going to be enough to participate usefully. I had to learn the basics. Similarly, Watson & Crick's seminal paper might not have been the best of all possible times to stop and define an X-ray or how crystallography worked. So yes, just instantiate the metaclass, implement the interface, and go buy milk. Easy. You just have to learn what each of those things actually means, especially if the details might be important (and in cryptography, that's always the case).