41 ms·
The problem is, the following code doesn't work: sv ge_scalarmult(ge *p, const ge *q, const u8 scalar[32]) { // convert q to montgomery format
by loup-vaillant 9y ago
The problem is, the following code doesn't work:
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).
- lucb1e 9y agoSounds like something to ask on https://crypto.stackexchange.com 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 https://stackoverflow.com (if you think the mistake is in the syntax somewhere).
- loup-vaillant 9y agoI think my mistake is in the crypto, so… stack exchange it is.
- baby 9y agoplease report back!
- loup-vaillant 9y agoI 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.)
- pbsd 9y agoYour 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.
- loup-vaillant 9y agoThat 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.)
- loup-vaillant 9y agoOkay, 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? [1]: https://en.wikipedia.org/wiki/Montgomery_curve#Equivalence_with_twisted_Edwards_curves https://en.wikipedia.org/wiki/Montgomery_curve#Equivalence_w...
- pbsd 9y agosage: 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.
- loup-vaillant 9y agoExcellent, thank you. I'll get on it right away.