3 ms·

> Arbitrary bigint math - how do you do Exp/Sqrt with arbitrary sized ints? (I'm familiar with two crypto libs that do this, and MPIs & branches confuse me). I

> Arbitrary bigint math - how do you do Exp/Sqrt with arbitrary sized ints? (I'm familiar with two crypto libs that do this, and MPIs & branches confuse me). I solve that problem by using Common Lisp. Because arbitrary bigints are built-in, that's a big chunk of the problem you don't need to worry about. You still need to write a Montgomery multiplier (because otherwise you'd fill available RAM or the divisions would slow everything to a crawl) but that's straightforward. Common Lisp makes exploring crypto algorithms easy.

sbf501 4y ago
Great, but that's not an explanation that adds knowledge to the discussion. I mean, Python and JavaScript both have BigInt libraries and are trivial to use. I want to know HOW they work, especially in C, since that's what the majority of popular crypto libraries are written in.
- syncsynchalt 4y ago
  I've cobbled together a few. It's half interesting, and half boring. The boring half is all carry-the-one manual operations that are very much like the addition, multi-digit multiplication, and long division that you learned at a classroom chalkboard. The more interesting is things like modular exponentiation: there's a trick to computing n^e%p for large values, https://en.wikipedia.org/wiki/Modular_exponentiation https://en.wikipedia.org/wiki/Modular_exponentiation goes into some detail. It's an operation used in both RSA and public curve cryptography.
  - sbf501 4y ago
    > It's half interesting, and half boring. I once emailed Grant from 3b1b and asked if he could explain convolution. Not neural-net convolution, but transfer convolution you learn in linear systems: e.g. f * g where you flip and slide g over f. His short response: "That's too boring." I was a little miffed. Well, yeah, ECC is boring too, until someone like you makes cool graphics. Anyway, thanks again!
syncsynchalt 4y ago
Note that it's not usually safe to use a language's built-in bigint for crypto like this because it's not time constant - for performance reasons smaller numbers will compute more quickly than larger numbers. Instead you'll need a fixed-size bigint lib with constant time guarantees.
- sbf501 4y ago
  ^^^ This person cryptos. ;-)
- dreamcompiler 4y ago
  Completely agree. For deployment I'd strongly prefer a well-tested library with good side-channel protection rather than rolling my own. I use Common Lisp for researching and understanding algorithms. Very nice page BTW. I've written C25519 code and I now understand my own code better because of your logical, step-by-step presentation.

sbf501 4y ago

Great, but that's not an explanation that adds knowledge to the discussion. I mean, Python and JavaScript both have BigInt libraries and are trivial to use. I want to know HOW they work, especially in C, since that's what the majority of popular crypto libraries are written in.

syncsynchalt 4y ago
I've cobbled together a few. It's half interesting, and half boring. The boring half is all carry-the-one manual operations that are very much like the addition, multi-digit multiplication, and long division that you learned at a classroom chalkboard. The more interesting is things like modular exponentiation: there's a trick to computing n^e%p for large values, https://en.wikipedia.org/wiki/Modular_exponentiation https://en.wikipedia.org/wiki/Modular_exponentiation goes into some detail. It's an operation used in both RSA and public curve cryptography.
- sbf501 4y ago
  > It's half interesting, and half boring. I once emailed Grant from 3b1b and asked if he could explain convolution. Not neural-net convolution, but transfer convolution you learn in linear systems: e.g. f * g where you flip and slide g over f. His short response: "That's too boring." I was a little miffed. Well, yeah, ECC is boring too, until someone like you makes cool graphics. Anyway, thanks again!

syncsynchalt 4y ago

Note that it's not usually safe to use a language's built-in bigint for crypto like this because it's not time constant - for performance reasons smaller numbers will compute more quickly than larger numbers. Instead you'll need a fixed-size bigint lib with constant time guarantees.

sbf501 4y ago
^^^ This person cryptos. ;-)
dreamcompiler 4y ago
Completely agree. For deployment I'd strongly prefer a well-tested library with good side-channel protection rather than rolling my own. I use Common Lisp for researching and understanding algorithms. Very nice page BTW. I've written C25519 code and I now understand my own code better because of your logical, step-by-step presentation.