A Detailed Elliptic Curve Cryptography Tutorial
johannes-bauer.com
johannes-bauer.com
Certicom authored the curve used by Bitcoin (secp256k1).
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?
[1] https://link.springer.com/chapter/10.1007/3-540-44709-1_12
sv ge_scalarmult(ge *p, const ge *q, const u8 scalar[32])
{
// convert q to montgomery format
fe x1, y1, z1, x2, z2, x3, z3, t1, t2, t3, t4;
fe_sub(z1, q->Z, q->Y);
fe_mul(z1, z1, q->X);
fe_invert(z1, z1);
fe_add(t1, q->Z, q->Y);
fe_mul(x1, q->X, t1 );
fe_mul(x1, x1, z1);
fe_mul(y1, q->Z, t1 );
fe_mul(y1, y1, z1);
fe_1(z1); // coherence
// montgomery scalarmult
x25519_ladder(x1, x2, z2, x3, z3, scalar);
// recover the y1 coordinate
fe_mul(t1, x1, z2); // t1 = x1 * z2
fe_add(t2, x2, t1); // t2 = x2 + t1
fe_sub(t3, x2, t1); // t3 = x2 − t1
fe_sq (t3, t3); // t3 = t3^2
fe_mul(t3, t3, x3); // t3 = t3 * x3
fe_mul973324(t1, z2);// t1 = 2a * z2
fe_add(t2, t2, t1); // t2 = t2 + t1
fe_mul(t4, x1, x2); // t4 = x1 * x2
fe_add(t4, t4, z2); // t4 = t4 + z2
fe_mul(t2, t2, t4); // t2 = t2 * t4
fe_mul(t1, t1, z2); // t1 = t1 * z2
fe_sub(t2, t2, t1); // t2 = t2 − t1
fe_mul(t2, t2, z3); // t2 = t2 * z3
fe_add(t1, y1, y1); // t1 = y1 + y1
fe_mul(t1, t1, z2); // t1 = t1 * z2
fe_mul(t1, t1, z3); // t1 = t1 * z3
fe_mul(x1, t1, x2); // x1 = t1 * x2
fe_sub(y1, t2, t3); // y1 = t2 − t3
fe_mul(z1, t1, z2); // z1 = t1 * z2
// convert back to twisted edwards
fe_sub(t1 , x1, z1);
fe_add(t2 , x1, z1);
fe_mul(p->X, x1, t2);
fe_mul(p->Y, y1, t1);
fe_mul(p->Z, y1, t2);
fe_mul(p->T, x1, t1);
}
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).
I have a problem however: how do I find the modular square root of -486664?
[1]: https://en.wikipedia.org/wiki/Montgomery_curve#Equivalence_w...
sage: p=2^255-19
sage: sqrt(GF(p)(-486664))
6853475219497561581579357271197624642482790079785650197046958215289687604742
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.(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.)
(Note: another commenter saw an error in my conversion code, it might be exactly what I needed to hear.)