Re: [PATCH 6/8] Implement curve448 primitives
ni...@lysator.liu.se (Niels Möller) writes: > I'm considering rewriting the curve25519-case of eccdata, to also work > on the Edwards curve. I've spent most of the day doing this reorg of eccdata.c, together with a few smaller cleanups. Should make it easier to add curve448. Since it's going to take a few rounds before the SHAKE code is ready, I'd suggest that we aim to get curve448 in first, i.e., the DH functions, before doing eddsa448. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. ___ nettle-bugs mailing list nettle-bugs@lists.lysator.liu.se http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
Re: [PATCH 6/8] Implement curve448 primitives
Daiki Ueno 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
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
[PATCH 6/8] Implement curve448 primitives
From: Daiki Ueno
This patch adds the necessary primitives for "curve448": namely,
addition, doubling, scalar multiplication of the generator
or an arbitrary point, inversion, and square root.
Although the interface is similar to curve25519, the implementation is
slightly different. For curve25519, the Pippenger tables are
generated through the coordinates on the Montgomery curve. On the
other hand, for curve448 the tables are directly generated from the
coordinates on the corresponding Edwards curve ("edwards448").
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.
Signed-off-by: Daiki Ueno
---
.gitignore| 1 +
Makefile.in | 10 +-
curve448-eh-to-x.c| 73
curve448-mul-g.c | 74
curve448-mul.c| 148 +++
curve448.h| 58 +
ecc-448.c | 272 ++
ecc-add-eh.c | 74 +++-
ecc-add-ehh.c | 77 +++-
ecc-dup-eh.c | 55 -
ecc-eh-to-a.c | 2 +-
ecc-internal.h| 31 -
ecc-point-mul-g.c | 7 +-
ecc-point-mul.c | 2 +-
ecc-point.c | 15 +++
eccdata.c | 160 -
ecdsa-keygen.c| 4 +-
examples/ecc-benchmark.c | 1 +
nettle.texinfo| 59 +++--
testsuite/.test-rules.make| 3 +
testsuite/Makefile.in | 2 +-
testsuite/curve448-dh-test.c | 100
testsuite/ecc-add-test.c | 9 +-
testsuite/ecc-dup-test.c | 2 +-
testsuite/ecc-mul-a-test.c| 4 +-
testsuite/ecc-mul-g-test.c| 4 +-
testsuite/ecdh-test.c | 16 ++-
testsuite/ecdsa-keygen-test.c | 16 +++
testsuite/testutils.c | 14 ++-
29 files changed, 1248 insertions(+), 45 deletions(-)
create mode 100644 curve448-eh-to-x.c
create mode 100644 curve448-mul-g.c
create mode 100644 curve448-mul.c
create mode 100644 curve448.h
create mode 100644 ecc-448.c
create mode 100644 testsuite/curve448-dh-test.c
diff --git a/.gitignore b/.gitignore
index 1f3b92b9..92af6a46 100644
--- a/.gitignore
+++ b/.gitignore
@@ -50,6 +50,7 @@ core
/ecc-384.h
/ecc-521.h
/ecc-25519.h
+/ecc-448.h
/nettle.aux
/nettle.cp
/nettle.cps
diff --git a/Makefile.in b/Makefile.in
index 7e8f29c2..2cf44a31 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -168,7 +168,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
ecc-mod.c ecc-mod-inv.c \
ecc-mod-arith.c ecc-pp1-redc.c ecc-pm1-redc.c \
ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \
- ecc-25519.c \
+ ecc-25519.c ecc-448.c \
ecc-size.c ecc-j-to-a.c ecc-a-to-j.c \
ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \
ecc-eh-to-a.c \
@@ -179,6 +179,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
ecc-ecdsa-sign.c ecdsa-sign.c \
ecc-ecdsa-verify.c ecdsa-verify.c ecdsa-keygen.c \
curve25519-mul-g.c curve25519-mul.c curve25519-eh-to-x.c \
+ curve448-mul-g.c curve448-mul.c curve448-eh-to-x.c \
eddsa-compress.c eddsa-decompress.c eddsa-expand.c \
eddsa-hash.c eddsa-pubkey.c eddsa-sign.c eddsa-verify.c \
ed25519-sha512-pubkey.c \
@@ -189,7 +190,7 @@ OPT_SOURCES = fat-x86_64.c fat-arm.c mini-gmp.c
HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \
base16.h base64.h bignum.h buffer.h camellia.h cast128.h \
cbc.h ccm.h chacha.h chacha-poly1305.h ctr.h \
- curve25519.h des.h des-compat.h dsa.h dsa-compat.h eax.h \
+ curve25519.h curve448.h des.h des-compat.h dsa.h dsa-compat.h eax.h \
ecc-curve.h ecc.h ecdsa.h eddsa.h \
gcm.h gosthash94.h hmac.h \
knuth-lfib.h \
@@ -363,6 +364,9 @@ ecc-521.h: eccdata.stamp
ecc-25519.h: eccdata.stamp
./eccdata$(EXEEXT_FOR_BUILD) 255 14 6 $(GMP_NUMB_BITS) > $@T && mv $@T
$@
+ecc-448.h: eccdata.stamp
+ ./eccdata$(EXEEXT_FOR_BUILD) 448 64 6 $(GMP_NUMB_BITS) > $@T && mv $@T
$@
+
eccdata.stamp: eccdata.c
$(MAKE) eccdata$(EXEEXT_FOR_BUILD)
echo stamp > eccdata.stamp
@@ -373,6 +377,7 @@ ecc-256.$(OBJEXT): ecc-256.h
ecc-384.$(OBJEXT): ecc-384.h
ecc-521.$(OBJEXT): ecc-521.h
ecc-25519.$(OBJEXT): ecc-25519.h
+ecc-448.$(OBJEXT): ecc-448.h
.asm.$(OBJEXT): $(srcdir)/asm.m4 machine.m4 config.m4
$(M4) $(srcdir)/asm.m4 machine.m4 config.m4 $< >$*.s
@@ -626,6 +631,7 @@ distcheck: dist
clean-here:
-rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \
ecc-192.h ecc-224.h ecc-256.h ecc-384.h ecc-521.h e
