Daiki Ueno ueno@gnu.org 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-multipl...
+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 inmemory-address order, since mul and sqr clobbers higherlimbs. */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: couldlet 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