Rename add and dup functions for Edwards curves.

13 files changed, 390 insertions, 251 deletions

diff --git a/ChangeLog b/ChangeLog
index e3fc8542..f463c5f7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,25 @@
 2019-12-18  Niels Möller  <nisse@lysator.liu.se>
 
+	Rename add and dup functions for Edwards curves.
+	* ecc-dup-th.c (ecc_dup_th): New file, move and rename ecc_dup_eh.
+	* ecc-add-th.c (ecc_add_th): New file, move and rename ecc_add_eh.
+	* ecc-add-thh.c (ecc_add_thh): New file, move and rename
+	ecc_add_ehh.
+	* ecc-dup-eh.c (ecc_dup_eh_untwisted): Rename to just ecc_dup_eh.
+	* ecc-add-eh.c (ecc_add_ehh_untwisted): Rename to just ecc_add_eh.
+	* ecc-add-ehh.c (ecc_add_ehh_untwisted): Rename to just ecc_add_ehh.
+	* ecc-internal.h (ecc_dup_th, ecc_add_th, ecc_add_thh): Declare
+	new functions, delete declarations of ecc_*_untwisted variants.
+	(ECC_DUP_TH_ITCH, ECC_ADD_TH_ITCH, ECC_ADD_THH_ITCH): New macros.
+	* ecc-25519.c (_nettle_curve25519): Update, use ecc_dup_th and
+	friends.
+	* ecc-448.c (_nettle_curve448): Update for rename, without
+	_untwisted suffix.
+	* Makefile.in (hogweed_SOURCES): Added ecc-dup-th.c, ecc-add-th.c,
+	and ecc-add-thh.c
+	* testsuite/ecc-dup-test.c (test_main): Update asserts.
+	* testsuite/ecc-add-test.c (test_main): Likewise.
+
 	* eddsa-verify.c (_eddsa_verify): Use function pointer rather than
 	calling ecc_add_eh directly. Preparation for eddsa over curve448.
 
diff --git a/Makefile.in b/Makefile.in
index 8d06149f..9c67c778 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -180,6 +180,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \
 		  ecc-eh-to-a.c \
 		  ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c \
+		  ecc-dup-th.c ecc-add-th.c ecc-add-thh.c \
 		  ecc-mul-g-eh.c ecc-mul-a-eh.c ecc-mul-m.c \
 		  ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \
 		  ecc-point.c ecc-scalar.c ecc-point-mul.c ecc-point-mul-g.c \
diff --git a/ecc-25519.c b/ecc-25519.c
index 105ce0f4..7eacc780 100644
--- a/ecc-25519.c
+++ b/ecc-25519.c
@@ -335,16 +335,16 @@ const struct ecc_curve _nettle_curve25519 =
   ECC_PIPPENGER_K,
   ECC_PIPPENGER_C,
 
-  ECC_ADD_EH_ITCH (ECC_LIMB_SIZE),
-  ECC_ADD_EHH_ITCH (ECC_LIMB_SIZE),
-  ECC_DUP_EH_ITCH (ECC_LIMB_SIZE),
+  ECC_ADD_TH_ITCH (ECC_LIMB_SIZE),
+  ECC_ADD_THH_ITCH (ECC_LIMB_SIZE),
+  ECC_DUP_TH_ITCH (ECC_LIMB_SIZE),
   ECC_MUL_A_EH_ITCH (ECC_LIMB_SIZE),
   ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE),
   ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_25519_INV_ITCH),
 
-  ecc_add_eh,
-  ecc_add_ehh,
-  ecc_dup_eh,
+  ecc_add_th,
+  ecc_add_thh,
+  ecc_dup_th,
   ecc_mul_a_eh,
   ecc_mul_g_eh,
   ecc_eh_to_a,
diff --git a/ecc-448.c b/ecc-448.c
index 429bb8ff..6a957bb4 100644
--- a/ecc-448.c
+++ b/ecc-448.c
@@ -310,9 +310,9 @@ const struct ecc_curve _nettle_curve448 =
   ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE),
   ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_448_INV_ITCH),
 
-  ecc_add_eh_untwisted,
-  ecc_add_ehh_untwisted,
-  ecc_dup_eh_untwisted,
+  ecc_add_eh,
+  ecc_add_ehh,
+  ecc_dup_eh,
   ecc_mul_a_eh,
   ecc_mul_g_eh,
   ecc_eh_to_a,
diff --git a/ecc-add-eh.c b/ecc-add-eh.c
index 85e06648..8e6b82ab 100644
--- a/ecc-add-eh.c
+++ b/ecc-add-eh.c
@@ -55,80 +55,6 @@ ecc_add_eh (const struct ecc_curve *ecc,
 #define z3 (r + 2*ecc->p.size)
 
   /* Formulas (from djb,
-     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#addition-madd-2008-bbjlp
-
-     Computation	Operation	Live variables
-
-     C = x1*x2		mul		C
-     D = y1*y2		mul		C, D
-     T = (x1+y1)*(x2+y2) mul		C, D, T
-         - C - D
-     E = b*C*D          2 mul		C, E, T  (Replace C <-- D+C)
-     B = z1^2		sqr		B, C, E, T
-     F = B - E				B, C, E, F, T
-     G = B + E     			C, F, G, T
-     x3 = z1 * F * T    2 mul		C, F, G, T
-     y3 = z1*G*(D+C)	2 mul		F, G
-     z3 = F*G		mul
-
-     10M + 1S
-
-     We have different sign for E, hence swapping F and G, because our
-     ecc->b corresponds to -b above.
-  */
-#define C (scratch)
-#define D (scratch + 1*ecc->p.size)
-#define T (scratch + 2*ecc->p.size)
-#define E (scratch + 3*ecc->p.size)
-#define B (scratch + 4*ecc->p.size)
-#define F D
-#define G E
-
-  ecc_modp_mul (ecc, C, x1, x2);
-  ecc_modp_mul (ecc, D, y1, y2);
-  ecc_modp_add (ecc, x3, x1, y1);
-  ecc_modp_add (ecc, y3, x2, y2);
-  ecc_modp_mul (ecc, T, x3, y3);
-  ecc_modp_sub (ecc, T, T, C);
-  ecc_modp_sub (ecc, T, T, D);
-  ecc_modp_mul (ecc, x3, C, D);
-  ecc_modp_mul (ecc, E, x3, ecc->b);
-
-  ecc_modp_add (ecc, C, D, C);
-  ecc_modp_sqr (ecc, B, z1);
-  ecc_modp_sub (ecc, F, B, E);
-  ecc_modp_add (ecc, G, B, E);
-
-  /* x3 */
-  ecc_modp_mul (ecc, B, G, T);
-  ecc_modp_mul (ecc, x3, B, z1);
-
-  /* y3 */
-  ecc_modp_mul (ecc, B, F, z1);
-  ecc_modp_mul (ecc, y3, B, C); /* Clobbers z1 in case r == p. */
-
-  /* z3 */
-  ecc_modp_mul (ecc, B, F, G);
-  mpn_copyi (z3, B, ecc->p.size);
-}
-
-void
-ecc_add_eh_untwisted (const struct ecc_curve *ecc,
-		      mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
-		      mp_limb_t *scratch)
-{
-#define x1 p
-#define y1 (p + ecc->p.size)
-#define z1 (p + 2*ecc->p.size)
-
-#define x2 q
-#define y2 (q + ecc->p.size)
-
-#define x3 r
-#define y3 (r + ecc->p.size)
-#define z3 (r + 2*ecc->p.size)
-
-  /* Formulas (from djb,
      http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):
 
      Computation	Operation	Live variables
diff --git a/ecc-add-ehh.c b/ecc-add-ehh.c
index ee8f9cb0..bdd827ba 100644
--- a/ecc-add-ehh.c
+++ b/ecc-add-ehh.c
@@ -55,84 +55,6 @@ ecc_add_ehh (const struct ecc_curve *ecc,
 #define z3 (r + 2*ecc->p.size)
 
   /* Formulas (from djb,
-     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#addition-add-2008-bbjlp):
-
-     Computation	Operation	Live variables
-
-     C = x1*x2		mul		C
-     D = y1*y2		mul		C, D
-     T = (x1+y1)(x2+y2) - C - D, mul	C, D, T
-     E = b*C*D		2 mul		C, E, T (Replace C <-- D - C)
-     A = z1*z2		mul		A, C, E, T
-     B = A^2		sqr		A, B, C, E, T
-     F = B - E				A, B, C, E, F, T
-     G = B + E     			A, C, F, G, T
-     x3 = A*F*T		2 mul		A, C, G
-     y3 = A*G*(D+C)	2 mul		F, G
-     z3 = F*G		mul
-
-     11M + S
-
-     We have different sign for E, hence swapping F and G, because our
-     ecc->b corresponds to -b above.
-  */
-#define C scratch
-#define D (scratch + ecc->p.size)
-#define T (scratch + 2*ecc->p.size)
-#define E (scratch + 3*ecc->p.size)
-#define A (scratch + 4*ecc->p.size)
-#define B (scratch + 5*ecc->p.size)
-#define F D
-#define G E
-
-  ecc_modp_mul (ecc, C, x1, x2);
-  ecc_modp_mul (ecc, D, y1, y2);
-  ecc_modp_add (ecc, A, x1, y1);
-  ecc_modp_add (ecc, B, x2, y2);
-  ecc_modp_mul (ecc, T, A, B);
-  ecc_modp_sub (ecc, T, T, C);
-  ecc_modp_sub (ecc, T, T, D);
-  ecc_modp_mul (ecc, x3, C, D);
-  ecc_modp_mul (ecc, E, x3, ecc->b);
-  ecc_modp_add (ecc, C, D, C);
-
-  ecc_modp_mul (ecc, A, z1, z2);
-  ecc_modp_sqr (ecc, B, A);
-
-  ecc_modp_sub (ecc, F, B, E);
-  ecc_modp_add (ecc, G, B, E);
-
-  /* x3 */
-  ecc_modp_mul (ecc, B, G, T);
-  ecc_modp_mul (ecc, x3, B, A);
-
-  /* y3 */
-  ecc_modp_mul (ecc, B, F, C);
-  ecc_modp_mul (ecc, y3, B, A);
-
-  /* z3 */
-  ecc_modp_mul (ecc, B, F, G);
-  mpn_copyi (z3, B, ecc->p.size);
-}
-
-void
-ecc_add_ehh_untwisted (const struct ecc_curve *ecc,
-		       mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
-		       mp_limb_t *scratch)
-{
-#define x1 p
-#define y1 (p + ecc->p.size)
-#define z1 (p + 2*ecc->p.size)
-
-#define x2 q
-#define y2 (q + ecc->p.size)
-#define z2 (q + 2*ecc->p.size)
-
-#define x3 r
-#define y3 (r + ecc->p.size)
-#define z3 (r + 2*ecc->p.size)
-
-  /* Formulas (from djb,
      http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#addition-add-2007-bl):
 
      Computation	Operation	Live variables
diff --git a/ecc-add-th.c b/ecc-add-th.c
new file mode 100644
index 00000000..c19afbb5
--- /dev/null
+++ b/ecc-add-th.c
@@ -0,0 +1,113 @@
+/* ecc-add-th.c
+
+   Copyright (C) 2014, 2017 Niels Möller
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+/* Add two points on a twisted Edwards curve, with result and first point in
+   homogeneous coordinates. */
+void
+ecc_add_th (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	    mp_limb_t *scratch)
+{
+#define x1 p
+#define y1 (p + ecc->p.size)
+#define z1 (p + 2*ecc->p.size)
+
+#define x2 q
+#define y2 (q + ecc->p.size)
+
+#define x3 r
+#define y3 (r + ecc->p.size)
+#define z3 (r + 2*ecc->p.size)
+
+  /* Formulas (from djb,
+     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#addition-madd-2008-bbjlp
+
+     Computation	Operation	Live variables
+
+     C = x1*x2		mul		C
+     D = y1*y2		mul		C, D
+     T = (x1+y1)*(x2+y2) mul		C, D, T
+         - C - D
+     E = b*C*D          2 mul		C, E, T  (Replace C <-- D+C)
+     B = z1^2		sqr		B, C, E, T
+     F = B - E				B, C, E, F, T
+     G = B + E     			C, F, G, T
+     x3 = z1 * F * T    2 mul		C, F, G, T
+     y3 = z1*G*(D+C)	2 mul		F, G
+     z3 = F*G		mul
+
+     10M + 1S
+
+     We have different sign for E, hence swapping F and G, because our
+     ecc->b corresponds to -b above.
+  */
+#define C (scratch)
+#define D (scratch + 1*ecc->p.size)
+#define T (scratch + 2*ecc->p.size)
+#define E (scratch + 3*ecc->p.size)
+#define B (scratch + 4*ecc->p.size)
+#define F D
+#define G E
+
+  ecc_modp_mul (ecc, C, x1, x2);
+  ecc_modp_mul (ecc, D, y1, y2);
+  ecc_modp_add (ecc, x3, x1, y1);
+  ecc_modp_add (ecc, y3, x2, y2);
+  ecc_modp_mul (ecc, T, x3, y3);
+  ecc_modp_sub (ecc, T, T, C);
+  ecc_modp_sub (ecc, T, T, D);
+  ecc_modp_mul (ecc, x3, C, D);
+  ecc_modp_mul (ecc, E, x3, ecc->b);
+
+  ecc_modp_add (ecc, C, D, C);
+  ecc_modp_sqr (ecc, B, z1);
+  ecc_modp_sub (ecc, F, B, E);
+  ecc_modp_add (ecc, G, B, E);
+
+  /* x3 */
+  ecc_modp_mul (ecc, B, G, T);
+  ecc_modp_mul (ecc, x3, B, z1);
+
+  /* y3 */
+  ecc_modp_mul (ecc, B, F, z1);
+  ecc_modp_mul (ecc, y3, B, C); /* Clobbers z1 in case r == p. */
+
+  /* z3 */
+  ecc_modp_mul (ecc, B, F, G);
+  mpn_copyi (z3, B, ecc->p.size);
+}
diff --git a/ecc-add-thh.c b/ecc-add-thh.c
new file mode 100644
index 00000000..03bb761f
--- /dev/null
+++ b/ecc-add-thh.c
@@ -0,0 +1,116 @@
+/* ecc-add-thh.c
+
+   Copyright (C) 2014 Niels Möller
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+/* Add two points on an Edwards curve, in homogeneous coordinates */
+void
+ecc_add_thh (const struct ecc_curve *ecc,
+	     mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	     mp_limb_t *scratch)
+{
+#define x1 p
+#define y1 (p + ecc->p.size)
+#define z1 (p + 2*ecc->p.size)
+
+#define x2 q
+#define y2 (q + ecc->p.size)
+#define z2 (q + 2*ecc->p.size)
+
+#define x3 r
+#define y3 (r + ecc->p.size)
+#define z3 (r + 2*ecc->p.size)
+
+  /* Formulas (from djb,
+     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#addition-add-2008-bbjlp):
+
+     Computation	Operation	Live variables
+
+     C = x1*x2		mul		C
+     D = y1*y2		mul		C, D
+     T = (x1+y1)(x2+y2) - C - D, mul	C, D, T
+     E = b*C*D		2 mul		C, E, T (Replace C <-- D - C)
+     A = z1*z2		mul		A, C, E, T
+     B = A^2		sqr		A, B, C, E, T
+     F = B - E				A, B, C, E, F, T
+     G = B + E     			A, C, F, G, T
+     x3 = A*F*T		2 mul		A, C, G
+     y3 = A*G*(D+C)	2 mul		F, G
+     z3 = F*G		mul
+
+     11M + S
+
+     We have different sign for E, hence swapping F and G, because our
+     ecc->b corresponds to -b above.
+  */
+#define C scratch
+#define D (scratch + ecc->p.size)
+#define T (scratch + 2*ecc->p.size)
+#define E (scratch + 3*ecc->p.size)
+#define A (scratch + 4*ecc->p.size)
+#define B (scratch + 5*ecc->p.size)
+#define F D
+#define G E
+
+  ecc_modp_mul (ecc, C, x1, x2);
+  ecc_modp_mul (ecc, D, y1, y2);
+  ecc_modp_add (ecc, A, x1, y1);
+  ecc_modp_add (ecc, B, x2, y2);
+  ecc_modp_mul (ecc, T, A, B);
+  ecc_modp_sub (ecc, T, T, C);
+  ecc_modp_sub (ecc, T, T, D);
+  ecc_modp_mul (ecc, x3, C, D);
+  ecc_modp_mul (ecc, E, x3, ecc->b);
+  ecc_modp_add (ecc, C, D, C);
+
+  ecc_modp_mul (ecc, A, z1, z2);
+  ecc_modp_sqr (ecc, B, A);
+
+  ecc_modp_sub (ecc, F, B, E);
+  ecc_modp_add (ecc, G, B, E);
+
+  /* x3 */
+  ecc_modp_mul (ecc, B, G, T);
+  ecc_modp_mul (ecc, x3, B, A);
+
+  /* y3 */
+  ecc_modp_mul (ecc, B, F, C);
+  ecc_modp_mul (ecc, y3, B, A);
+
+  /* z3 */
+  ecc_modp_mul (ecc, B, F, G);
+  mpn_copyi (z3, B, ecc->p.size);
+}
diff --git a/ecc-dup-eh.c b/ecc-dup-eh.c
index 6b678a40..f7b46eef 100644
--- a/ecc-dup-eh.c
+++ b/ecc-dup-eh.c
@@ -36,84 +36,13 @@
 #include "ecc.h"
 #include "ecc-internal.h"
 
-/* Double a point on a twisted Edwards curve, in homogeneous coordinates */
+/* Double a point on an Edwards curve, in homogeneous coordinates */
 void
 ecc_dup_eh (const struct ecc_curve *ecc,
 	    mp_limb_t *r, const mp_limb_t *p,
 	    mp_limb_t *scratch)
 {
   /* Formulas (from djb,
-     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp):
-
-     B = (X1+Y1)^2
-     C = X1^2
-     D = Y1^2
-     (E = a*C = -C)
-     F = E+D
-     H = Z1^2
-     J = F-2*H
-     X3 = (B-C-D)*J
-     Y3 = F*(E-D)
-     Z3 = F*J         (-C+D)*(-C+D - 2Z1^2)
-
-     In the formula for Y3, we have E - D = -(C+D). To avoid explicit
-     negation, negate all of X3, Y3, Z3, and use
-
-     Computation	Operation	Live variables
-
-     B = (X1+Y1)^2	sqr		B
-     C = X1^2		sqr		B, C
-     D = Y1^2		sqr		B, C, D
-     F = -C+D				B, C, D, F
-     H = Z1^2		sqr		B, C, D, F, H
-     J = 2*H - F			B, C, D, F, J
-     X3 = (B-C-D)*J	mul		C, F, J  (Replace C <-- C+D)
-     Y3 = F*(C+D)	mul		F, J
-     Z3 = F*J		mul
-
-     3M+4S
-  */
-  /* FIXME: Could reduce scratch need by reusing D storage. */
-#define B scratch
-#define C (scratch  + ecc->p.size)
-#define D (scratch  + 2*ecc->p.size)
-#define F (scratch  + 3*ecc->p.size)
-#define J (scratch  + 4*ecc->p.size)
-
-  /* B */
-  ecc_modp_add (ecc, F, p, p + ecc->p.size);
-  ecc_modp_sqr (ecc, B, F);
-
-  /* C */
-  ecc_modp_sqr (ecc, C, p);
-  /* D */
-  ecc_modp_sqr (ecc, D, p + ecc->p.size);
-  /* Can use r as scratch, even for in-place operation. */
-  ecc_modp_sqr (ecc, r, p + 2*ecc->p.size);
-  /* F, */
-  ecc_modp_sub (ecc, F, D, C);
-  /* B - C - D */
-  ecc_modp_add (ecc, C, C, D);
-  ecc_modp_sub (ecc, B, B, C);
-  /* J */
-  ecc_modp_add (ecc, r, r, r);
-  ecc_modp_sub (ecc, J, r, F);
-
-  /* x' */
-  ecc_modp_mul (ecc, r, B, J);
-  /* y' */
-  ecc_modp_mul (ecc, r + ecc->p.size, F, C);
-  /* z' */
-  ecc_modp_mul (ecc, B, F, J);
-  mpn_copyi (r + 2*ecc->p.size, B, ecc->p.size);
-}
-
-void
-ecc_dup_eh_untwisted (const struct ecc_curve *ecc,
-		      mp_limb_t *r, const mp_limb_t *p,
-		      mp_limb_t *scratch)
-{
-  /* Formulas (from djb,
      http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):
 
      Computation	Operation	Live variables
diff --git a/ecc-dup-th.c b/ecc-dup-th.c
new file mode 100644
index 00000000..b4ce95c9
--- /dev/null
+++ b/ecc-dup-th.c
@@ -0,0 +1,109 @@
+/* ecc-dup-th.c
+
+   Copyright (C) 2014, 2019 Niels Möller
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+/* Double a point on a twisted Edwards curve, in homogeneous coordinates */
+void
+ecc_dup_th (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch)
+{
+  /* Formulas (from djb,
+     http://www.hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp):
+
+     B = (X1+Y1)^2
+     C = X1^2
+     D = Y1^2
+     (E = a*C = -C)
+     F = E+D
+     H = Z1^2
+     J = F-2*H
+     X3 = (B-C-D)*J
+     Y3 = F*(E-D)
+     Z3 = F*J         (-C+D)*(-C+D - 2Z1^2)
+
+     In the formula for Y3, we have E - D = -(C+D). To avoid explicit
+     negation, negate all of X3, Y3, Z3, and use
+
+     Computation	Operation	Live variables
+
+     B = (X1+Y1)^2	sqr		B
+     C = X1^2		sqr		B, C
+     D = Y1^2		sqr		B, C, D
+     F = -C+D				B, C, D, F
+     H = Z1^2		sqr		B, C, D, F, H
+     J = 2*H - F			B, C, D, F, J
+     X3 = (B-C-D)*J	mul		C, F, J  (Replace C <-- C+D)
+     Y3 = F*(C+D)	mul		F, J
+     Z3 = F*J		mul
+
+     3M+4S
+  */
+  /* FIXME: Could reduce scratch need by reusing D storage. */
+#define B scratch
+#define C (scratch  + ecc->p.size)
+#define D (scratch  + 2*ecc->p.size)
+#define F (scratch  + 3*ecc->p.size)
+#define J (scratch  + 4*ecc->p.size)
+
+  /* B */
+  ecc_modp_add (ecc, F, p, p + ecc->p.size);
+  ecc_modp_sqr (ecc, B, F);
+
+  /* C */
+  ecc_modp_sqr (ecc, C, p);
+  /* D */
+  ecc_modp_sqr (ecc, D, p + ecc->p.size);
+  /* Can use r as scratch, even for in-place operation. */
+  ecc_modp_sqr (ecc, r, p + 2*ecc->p.size);
+  /* F, */
+  ecc_modp_sub (ecc, F, D, C);
+  /* B - C - D */
+  ecc_modp_add (ecc, C, C, D);
+  ecc_modp_sub (ecc, B, B, C);
+  /* J */
+  ecc_modp_add (ecc, r, r, r);
+  ecc_modp_sub (ecc, J, r, F);
+
+  /* x' */
+  ecc_modp_mul (ecc, r, B, J);
+  /* y' */
+  ecc_modp_mul (ecc, r + ecc->p.size, F, C);
+  /* z' */
+  ecc_modp_mul (ecc, B, F, J);
+  mpn_copyi (r + 2*ecc->p.size, B, ecc->p.size);
+}
diff --git a/ecc-internal.h b/ecc-internal.h
index cd1a1573..000b812e 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -62,9 +62,9 @@
 #define ecc_dup_eh _nettle_ecc_dup_eh
 #define ecc_add_eh _nettle_ecc_add_eh
 #define ecc_add_ehh _nettle_ecc_add_ehh
-#define ecc_dup_eh_untwisted _nettle_ecc_dup_eh_untwisted
-#define ecc_add_eh_untwisted _nettle_ecc_add_eh_untwisted
-#define ecc_add_ehh_untwisted _nettle_ecc_add_ehh_untwisted
+#define ecc_dup_th _nettle_ecc_dup_th
+#define ecc_add_th _nettle_ecc_add_th
+#define ecc_add_thh _nettle_ecc_add_thh
 #define ecc_mul_g _nettle_ecc_mul_g
 #define ecc_mul_a _nettle_ecc_mul_a
 #define ecc_mul_g_eh _nettle_ecc_mul_g_eh
@@ -353,19 +353,19 @@ ecc_add_ehh (const struct ecc_curve *ecc,
 	     mp_limb_t *scratch);
 
 void
-ecc_dup_eh_untwisted (const struct ecc_curve *ecc,
-		      mp_limb_t *r, const mp_limb_t *p,
-		      mp_limb_t *scratch);
+ecc_dup_th (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch);
 
 void
-ecc_add_eh_untwisted (const struct ecc_curve *ecc,
-		      mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
-		      mp_limb_t *scratch);
+ecc_add_th (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	    mp_limb_t *scratch);
 
 void
-ecc_add_ehh_untwisted (const struct ecc_curve *ecc,
-		       mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
-		       mp_limb_t *scratch);
+ecc_add_thh (const struct ecc_curve *ecc,
+	     mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	     mp_limb_t *scratch);
 
 /* Computes N * the group generator. N is an array of ecc_size()
    limbs. It must be in the range 0 < N < group order, then R != 0,
@@ -429,10 +429,13 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p,
 #define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv))
 #define ECC_DUP_JJ_ITCH(size) (5*(size))
 #define ECC_DUP_EH_ITCH(size) (5*(size))
+#define ECC_DUP_TH_ITCH(size) (5*(size))
 #define ECC_ADD_JJA_ITCH(size) (6*(size))
 #define ECC_ADD_JJJ_ITCH(size) (8*(size))
 #define ECC_ADD_EH_ITCH(size) (6*(size))
 #define ECC_ADD_EHH_ITCH(size) (7*(size))
+#define ECC_ADD_TH_ITCH(size) (6*(size))
+#define ECC_ADD_THH_ITCH(size) (7*(size))
 #define ECC_MUL_G_ITCH(size) (9*(size))
 #define ECC_MUL_G_EH_ITCH(size) (9*(size))
 #if ECC_MUL_A_WBITS == 0
diff --git a/testsuite/ecc-add-test.c b/testsuite/ecc-add-test.c
index ed4eed57..84e4aaa6 100644
--- a/testsuite/ecc-add-test.c
+++ b/testsuite/ecc-add-test.c
@@ -23,10 +23,10 @@ test_main (void)
 	{
 	  mp_limb_t *z = xalloc_limbs (ecc_size_j (ecc));
 
-	  ASSERT ((ecc->p.bit_size == 255 && ecc->add_hh == ecc_add_eh)
-		  || (ecc->p.bit_size == 448 && ecc->add_hh == ecc_add_eh_untwisted));
-	  ASSERT ((ecc->p.bit_size == 255 && ecc->add_hhh == ecc_add_ehh)
-		  || (ecc->p.bit_size == 448 && ecc->add_hhh == ecc_add_ehh_untwisted));
+	  ASSERT ((ecc->p.bit_size == 255 && ecc->add_hh == ecc_add_th)
+		  || (ecc->p.bit_size == 448 && ecc->add_hh == ecc_add_eh));
+	  ASSERT ((ecc->p.bit_size == 255 && ecc->add_hhh == ecc_add_thh)
+		  || (ecc->p.bit_size == 448 && ecc->add_hhh == ecc_add_ehh));
 	  ASSERT (ecc->add_hh_itch <= ecc->add_hhh_itch);
 
 	  /* Zero point has x = 0, y = 1, z = 1 */
diff --git a/testsuite/ecc-dup-test.c b/testsuite/ecc-dup-test.c
index 2499c130..2a2179ac 100644
--- a/testsuite/ecc-dup-test.c
+++ b/testsuite/ecc-dup-test.c
@@ -18,8 +18,8 @@ test_main (void)
 	{
 	  mp_limb_t *z = xalloc_limbs (ecc_size_j (ecc));
 
-	  ASSERT ((ecc->p.bit_size == 255 && ecc->dup == ecc_dup_eh)
-		  || (ecc->p.bit_size == 448 && ecc->dup == ecc_dup_eh_untwisted));
+	  ASSERT ((ecc->p.bit_size == 255 && ecc->dup == ecc_dup_th)
+		  || (ecc->p.bit_size == 448 && ecc->dup == ecc_dup_eh));
 
 	  /* Zero point has x = 0, y = 1, z = 1 */
 	  mpn_zero (z, 3*ecc->p.size);