Daiki Ueno <[email protected]> writes: > The motivation behind this is that the formula converting the Edwards > curve coordinates to the Montgomery curve coordinates is simpler than > the other way around for curve448/edwards448.
After a quick look at RFC7748, I see what you mean. I'm considering rewriting the curve25519-case of eccdata, to also work on the Edwards curve. It's a bit silly to have three different curve formulas there. Some other comments of this change below: > --- a/Makefile.in > +++ b/Makefile.in [...] > +ecc-448.h: eccdata.stamp > + ./eccdata$(EXEEXT_FOR_BUILD) 448 64 6 $(GMP_NUMB_BITS) > $@T && mv $@T > $@ > + How did you select the table size? I have forgotten some of the details, but for the other curves, I aimed for table size around 16 KB, and looked at the examples/ecc-benchmark numbers for mul_g to select the organization. My notes are here: https://git.lysator.liu.se/nettle/se-nettle-2013/blob/master/doc/ecc-multiplication.tex > +void > +curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, mp_limb_t *scratch) [...] > + ecc->p.invert (&ecc->p, t0, p, t1 + ecc->p.size); > + ecc_modp_mul (ecc, t1, t0, vp); > + ecc_modp_mul (ecc, t2, t1, t1); Micro-optimization: Replace secong ecc_modp_mul by ecc_modp_sqr. > --- /dev/null > +++ b/curve448-mul-g.c > @@ -0,0 +1,74 @@ [...] > +/* Intended to be compatible with NaCl's crypto_scalarmult_base. */ Is this true? > --- /dev/null > +++ b/curve448-mul.c [...] > + for (i = 446; i >= 2; i--) > + { > + int bit = (n[i/8] >> (i & 7)) & 1; > + > + cnd_swap (bit, x2, x3, 2*ecc->p.size); > + > + /* Formulas from RFC 7748. We compute new coordinates in > + memory-address order, since mul and sqr clobbers higher > + limbs. */ > + ecc_modp_add (ecc, A, x2, z2); > + ecc_modp_sub (ecc, B, x2, z2); > + ecc_modp_sqr (ecc, AA, A); > + ecc_modp_sqr (ecc, BB, B); > + ecc_modp_mul (ecc, x2, AA, BB); > + ecc_modp_sub (ecc, E, AA, BB); /* Last use of BB */ > + ecc_modp_addmul_1 (ecc, AA, E, a24); > + ecc_modp_add (ecc, C, x3, z3); > + ecc_modp_sub (ecc, D, x3, z3); > + ecc_modp_mul (ecc, z2, E, AA); /* Last use of E and AA */ > + ecc_modp_mul (ecc, DA, D, A); /* Last use of D, A. FIXME: could > + let CB overlap. */ > + ecc_modp_mul (ecc, CB, C, B); > + > + ecc_modp_add (ecc, C, DA, CB); > + ecc_modp_sqr (ecc, x3, C); > + ecc_modp_sub (ecc, C, DA, CB); > + ecc_modp_sqr (ecc, DA, C); > + ecc_modp_mul (ecc, z3, DA, x1); > + > + /* FIXME: Could be combined with the loop's initial cnd_swap. */ > + cnd_swap (bit, x2, x3, 2*ecc->p.size); > + } The formulas are the same RFC7748 formulas as for curve25519, right? We should be able to share most of this code. > --- a/ecc-dup-eh.c > +++ b/ecc-dup-eh.c > @@ -36,7 +36,7 @@ > #include "ecc.h" > #include "ecc-internal.h" > > -/* Double a point on an Edwards curve, in homogeneous coordinates */ > +/* Double a point on a twisted Edwards curve, in homogeneous coordinates */ As for naming, I'm considering renaming this file and function to use the _teh suffix or so, and leave "_eh" for the untwisted functions. > --- a/eccdata.c > +++ b/eccdata.c > + /* x' = (p_x q_y + q_x p_y) / (1 + t) */ > + mpz_mul (x, p->x, q->y); > + mpz_mod (x, x, ecc->p); > + mpz_addmul (x, q->x, p->y); > + mpz_mod (x, x, ecc->p); > + mpz_add_ui (s, t, 1); > + mpz_invert (s, s, ecc->p); ^ > + mpz_mul (x, x, s); > + mpz_mod (x, x, ecc->p); > + > + /* y' = (p_y q_y - p_x q_x) / (1 - t) */ > + mpz_mul (y, p->y, q->y); > + mpz_mod (y, y, ecc->p); > + mpz_submul (y, p->x, q->x); > + mpz_mod (y, y, ecc->p); > + mpz_set_ui (s, 1); > + mpz_sub (s, s, t); > + mpz_invert (s, s, ecc->p); ^ > + mpz_mul (y, y, s); > + mpz_mod (y, y, ecc->p); Could consider rewriting the formulas to have only a single inversion, of the common denominator (1-t) (1+t) = (1-t^2). Worthwhile only if it brings a large speed improvement. mpz_invert here uses mini-gmp, and is implemented as binary algorithm for extended gcd, with a couple of bignum shifts and adds for each bit. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
