4 ms·

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 descr

by pbsd 9y ago

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. [1] https://link.springer.com/chapter/10.1007/3-540-44709-1_12 https://link.springer.com/chapter/10.1007/3-540-44709-1_12 [2] https://eprint.iacr.org/2017/212 https://eprint.iacr.org/2017/212 [3] https://eprint.iacr.org/2008/013 https://eprint.iacr.org/2008/013

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 ago
  Sounds 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 ago
    I think my mistake is in the crypto, so… stack exchange it is.
    - baby 9y ago
      please report back!
      - loup-vaillant 9y ago
        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.)
- 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 ago
    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.)

by pbsd 9y ago

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 ago
Sounds 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 ago
  I think my mistake is in the crypto, so… stack exchange it is.
  - baby 9y ago
    please report back!
    - loup-vaillant 9y ago
      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.)
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 ago
  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.)