Thank you for sharing! Beware though: The scalar point multiplication method that is shown in the article is subject to side channel attacks such as timing attacks, since it depends on features of the secret key. Use Montgomery multiplication or similar methods to mitigate this.
This looks nice. Too bad I care more about Montgomery and Twisted Edwards curves (everyone say curve255129 and edDSA are great, and I believe them).
I'm looking for one thing, which I hope should speed up signature and verification speed with very little bloat: converting a Twisted Edwards point to Montgomery space, then back (with that sign recovery trick after the Montgomery ladder).
Reading (and trying to apply) the relevant papers has been frustrating so far (I get wrong results), and I can't find code (or pseudo-code) I can use. Have someone implemented this?
What exactly is the problem? Converting between Montgomery and twisted Edwards is well documented by now, for example in [3, Theorem 3.2] or RFC 7748. The descriptions in, e.g., [1, §3.2] or [2, §4.3] for the Montgomery y-recovery trick are pretty straightforward.
This is supposed to be a straightforward application of the first link you provided. I have no freaking idea what I did wrong. I can only say thef x25519_ladder() function is correct, because it gives the correct results for Diffie-Hellman.
I'm not sure your Last 2 links contain the information I want. RFC 7748 is of no help whatsoever (I already have a correct curve25519 implementation).
Your conversion between Edwards and Montgomery is not quite correct. I suspect that is why you're getting different results (though I didn't really go over the whole thing). RFC 7748 does include the correct conversion routines in page 4: ((1+y)/(1-y), sqrt(-486664) * ((1+y)/(1-y))/x) to go from ed25519 to x25519, and (sqrt(-486664) * u/v, (u-1)/(u+1)) to go back. So with some luck, you're only missing 2 multiplications by a constant.
Okay, I went through my sources, and remembered I got my conversion from Wikipedia¹. Strangely, Wikipedia gives a different map than the RFC. (One DJB paper agrees with the RFC, so either the Wikipedia is wrong, or I'm missing something.) That's why I didn't multiply by any constant.
I have a problem however: how do I find the modular square root of -486664?
The formula in Wikipedia is not wrong, but note that it maps E_{a,d} to M_{A, B} with B = 4/(a - d) = -486664. curve25519, and pretty much every Montgomery curve, is defined with B = 1, so you need some extra twisting to get there.
That would be terrific! I'll check that out, thanks.
(Come to think of it, I should have tested the conversion by adding a useless round trip to the old algorithm. It would most probably have detected the problem.)
Sounds like something to ask on https://crypto.stackexchange.com (if you think your mistake is in the crypto, and you don't care about the particular programming/scripting language syntax), or on https://stackoverflow.com (if you think the mistake is in the syntax somewhere).
I will, promise. When version 1.0 of Monocypher is out (probably before the end of next week), I'll write how it all happened. I think I can make it entertaining as well as useful.
(Note: another commenter saw an error in my conversion code, it might be exactly what I needed to hear.)
Certicom authored the curve used by Bitcoin (secp256k1).