3 ms·
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
by pbsd 9y ago
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.
- 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.