Hacker News new | comments | show | ask | jobs | submit login

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.

[1] https://link.springer.com/chapter/10.1007/3-540-44709-1_12

[2] https://eprint.iacr.org/2017/212

[3] https://eprint.iacr.org/2008/013


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).


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?

[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.


Excellent, thank you. I'll get on it right away.


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 think my mistake is in the crypto, so… stack exchange it is.


please report back!


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.)




Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: