4 ms·

A Detailed Elliptic Curve Cryptography Tutorial

184 points by 68c12c16 9y ago

loup-vaillant 9y ago
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?
- 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.)
zmonx 9y ago
Thank you for sharing! Beware though: The scalar point multiplication method that is shown in the article is subject to side channel attacks such as timing attacks, since it depends on features of the secret key. Use Montgomery multiplication or similar methods to mitigate this.
runeks 9y ago
Certicom also has a good tutorial on ECC: https://www.certicom.com/content/certicom/en/ecc-tutorial.html https://www.certicom.com/content/certicom/en/ecc-tutorial.ht... Certicom authored the curve used by Bitcoin (secp256k1).
jerianasmith 9y ago
The scalar point multiplication method is vulnerable as it can be attacked as feature key in this case is very important

184 points by 68c12c16 9y ago

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?

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

zmonx 9y ago

Thank you for sharing! Beware though: The scalar point multiplication method that is shown in the article is subject to side channel attacks such as timing attacks, since it depends on features of the secret key. Use Montgomery multiplication or similar methods to mitigate this.

runeks 9y ago

Certicom also has a good tutorial on ECC: https://www.certicom.com/content/certicom/en/ecc-tutorial.html https://www.certicom.com/content/certicom/en/ecc-tutorial.ht... Certicom authored the curve used by Bitcoin (secp256k1).

jerianasmith 9y ago

The scalar point multiplication method is vulnerable as it can be attacked as feature key in this case is very important