Follow

Curve25519 implementation is both the most blessed and cursed code in the world.

On one hand, it has the cleanest math and attracted the best minds to work on it. Now the code deployed in most projects have been fully optimized, and formally verified to be mathematically correct and secure. One of the biggest accomplishment in crypto applications in recent years.

On the other hand, the monstrous, machine-generated assembly or C code will give any unsuspected programmer a heart attack.

Seriously, "you are not expected to understand this."

git.kernel.org/pub/scm/linux/k

BTW, human-understandable implementations do exist...

Curve25519 in 18 tweets
cs.ru.nl/bachelors-theses/2014

/me now trying to implement it in PDP-11 assembly...

This paper is even better, fully annotated commentary of TweetNaCl's X25519 code. martin.kleppmann.com/papers/cu

Now I need to find a way to do carry propagation on smaller limbs. Two papers all "cheated" by representing 256-bit bignum using 16 x 64-bit integers to ensure they never overflow, avoiding the need to carry completely, but it would be too slow on the PDP-11..

Michael Hutter & Peter Schwabe's code for 8-bit Atmel chips look like a good start, but it also features multi-thousand lines of fully-unrolled and semi-machine generated code. No macros, the same thing just repeats over and over again, not the easiest thing to read... 🙈

Just figured out the One Weird Trick to add numbers mod 2^255 - 19 for Curve25519. The actual normalization is only needed at the last moment, meanwhile, during the many calculations, you don't reduce results to mod 2^255 - 19, but to mod 2^256 - 38. Now the computer can calculate mod 2^256 automatically due to integer overflow. The only problem is the result is off by 38, so you simply add 38 if the most significant byte has overflowed. Neat.

I was staring at the screen for an entire afternoon and trying to understand why the carry propagation is performed twice in Curve25519 modular additions, no idea at all... Why is the second carry necessary?

Later, after a web search, I found a historical OpenSSL bug caused by not doing the second carry... Okay, I'm glad I'm not the only one who doesn't understand it. :doge:

github.com/openssl/openssl/iss

PDP-11's (optional) multiplier can only perform SIGNED multiplication, to do unsigned multiplication in branchless, constant-time cryptography code, I need to do this convoluted sequence of adjustments... Totally a brain teaser.

Unsigned multiplication is just terrible on the . I wonder whether switching from 16-bit to 15-bit integers for bignum is a feasible workaround - multiplication is easier, but difficult to do carry propagation...

Bignum with 15-bit integers work surprisingly well. It only takes 2 instructions to simulate a carry. And coincidentally, Curve25519 works on a 255-bit finite field, not 256-bit, so a field element is representable in exactly 17 words and the fast modular reduction trick still works. It's also naturally represented in octal, PDP-11's preferred number system.

@niconiconi Gotta be honest, I just like Elliptic Curve algorithms because my ssh keys are shorter.

@rune Don't get me wrong. ECC, especially Curve25519/448 is the best public-key crypto you can use today. I'm just saying how much indescribable magic is there under the hood.

@niconiconi Oh that was my understanding too.

I've given up on trying to understand them, so I just expect and hope someone dedicated enough validates it..

@niconiconi somewhere there must exist a tower exactly like this in picture 2 if you tilt your head by 90 degrees

@fakefred It's a shame that they didn't submit it to IOCCC.

@niconiconi I've gotta ask, why is this implementation appropriate?

@Lofenyy This implementation is a project from MIT CSAIL with a full paper: adam.chlipala.net/papers/FiatC Basically the actual code is written in a high-level programming language they invented with formal proofs of correctness in Coq, the unreadable C code can be seen as a form of portable assembly.

@niconiconi Is the original source code available somewhere? Is it reproducible?

@niconiconi Of course I do! Theo De Raadt is a proud Calgarian. As someone living in Calgary, I know exactly how questionable Calgarians are. The answer is a lot more than you may think!

I hope to meet him one day, but I dread knowing that I probably will. I tend to hang around people who are vaguely in his social circle. Well, I used to...

@niconiconi I meant like a copy of the higher level language source code that was used to generate the C source code.

@Lofenyy The entire project is the generator. It's not a programming language by itself, more like a general-purpose elliptic curve crypto code synthesizer/compiler. Internally it implements operations such as arithmetic over a finite field, or point addition formulas, and implementation techniques. You just pass a set of parameters that defines your elliptic curve into the compiler, and the compiler gives you an implementation.

Sign in to participate in the conversation
Cybrespace

cybrespace: the social hub of the information superhighway jack in to the mastodon fediverse today and surf the dataflow through our cybrepunk, slightly glitchy web portal support us on patreon or liberapay!