Implemented ecc_add_eh.

6 files changed, 145 insertions, 4 deletions

diff --git a/ChangeLog b/ChangeLog
index 7280e91b..48e295bf 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,7 +1,12 @@
 2014-07-15  Niels Möller  <nisse@lysator.liu.se>
 
-	* testsuite/curve25519-add-test.c (test_main): Additonal test for
-	g2+g2. Free allocated storage.
+	* ecc-add-eh.c (ecc_add_eh, ecc_add_eh_itch): New file, new
+	functions.
+	* ecc.h: Declare new functions.
+	* ecc-internal.h (ECC_ADD_EH_ITCH): New macro.
+	* Makefile.in (hogweed_SOURCES): Added ecc-add-eh.c.
+	* testsuite/curve25519-add-test.c (test_main): Test ecc_add_eh.
+	Additional test for g2+g2. Free allocated storage.
 
 2014-07-14  Niels Möller  <nisse@lysator.liu.se>
 
diff --git a/Makefile.in b/Makefile.in
index 6831cc4a..9a91aec3 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -167,7 +167,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  ecc-25519.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-dup-eh.c ecc-add-ehh.c ecc-eh-to-a.c \
+		  ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c ecc-eh-to-a.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 \
 		  ecc-ecdsa-sign.c ecdsa-sign.c \
diff --git a/ecc-add-eh.c b/ecc-add-eh.c
new file mode 100644
index 00000000..05c2188e
--- /dev/null
+++ b/ecc-add-eh.c
@@ -0,0 +1,111 @@
+/* ecc-add-eh.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"
+
+mp_size_t
+ecc_add_eh_itch (const struct ecc_curve *ecc)
+{
+  return ECC_ADD_EH_ITCH (ecc->size);
+}
+
+/* Add two points on an Edwards curve, with result and first point in
+   homogeneous coordinates. */
+void
+ecc_add_eh (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->size)
+#define z1 (p + 2*ecc->size)
+
+#define x2 q
+#define y2 (q + ecc->size)
+
+#define x3 r
+#define y3 (r + ecc->size)
+#define z3 (r + 2*ecc->size)
+
+  /* Formulas (from djb,
+     http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):
+
+     Computation	Operation	Live variables
+
+     B = z1^2		sqr		B
+     C = x1*x2		mul		B, C
+     D = y1*y2		mul		B, C, D
+     E = b*C*D		2 mul		B, C, D, E
+     F = B - E				B, C, D, E, F
+     G = B + E     			C, D, F, G
+     x3 = z1*F*[(x1+y1)(x2+y2) - C - D] 3 mul	C, D, G
+     y3 = z1*G*(D-C)	2 mul		F, G
+     z3 = F*G		mul
+  */
+#define B (scratch)
+#define C (scratch + 1*ecc->size)
+#define D (scratch + 2*ecc->size)
+#define E (scratch + 3*ecc->size) 
+#define F (scratch + 4*ecc->size)
+#define G (scratch + 5*ecc->size)
+#define T (scratch + 6*ecc->size)
+
+  ecc_modp_sqr (ecc, B, z1);
+  ecc_modp_mul (ecc, C, x1, x2);
+  ecc_modp_mul (ecc, D, y1, y2);
+  ecc_modp_mul (ecc, T, C, D);
+  ecc_modp_mul (ecc, E, T, ecc->b);
+  ecc_modp_sub (ecc, F, B, E);
+  ecc_modp_add (ecc, G, B, E);
+
+  /* x3 */
+  ecc_modp_add (ecc, B, x1, y1);
+  ecc_modp_add (ecc, E, x2, y2);
+  ecc_modp_mul (ecc, T, B, E);
+  ecc_modp_sub (ecc, T, T, C);
+  ecc_modp_sub (ecc, x3, T, D);
+  ecc_modp_mul (ecc, T, x3, z1);
+  ecc_modp_mul (ecc, x3, T, F);
+
+  /* y3 */
+  ecc_modp_sub (ecc, C, D, C);
+  ecc_modp_mul (ecc, T, z1, C);
+  ecc_modp_mul (ecc, y3, T, G);
+
+  /* z3 */
+  ecc_modp_mul (ecc, T, F, G);
+  mpn_copyi (z3, T, ecc->size);
+}
diff --git a/ecc-internal.h b/ecc-internal.h
index 1fefd138..f2b99278 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -242,6 +242,7 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
 #define ECC_DUP_EH_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) (8*(size))
 #define ECC_ADD_EHH_ITCH(size) (9*(size))
 #define ECC_MUL_G_ITCH(size) (9*(size))
 #if ECC_MUL_A_WBITS == 0
diff --git a/ecc.h b/ecc.h
index f8cadf5e..df9013aa 100644
--- a/ecc.h
+++ b/ecc.h
@@ -71,6 +71,8 @@ extern "C" {
 #define ecc_add_jjj nettle_ecc_add_jjj
 #define ecc_dup_eh_itch nettle_ecc_dup_eh_itch
 #define ecc_dup_eh nettle_ecc_dup_eh
+#define ecc_add_eh_itch nettle_ecc_add_eh_itch
+#define ecc_add_eh nettle_ecc_add_eh
 #define ecc_add_ehh_itch nettle_ecc_add_ehh_itch
 #define ecc_add_ehh nettle_ecc_add_ehh
 #define ecc_mul_g_itch nettle_ecc_mul_g_itch
@@ -246,6 +248,13 @@ ecc_dup_eh (const struct ecc_curve *ecc,
 	    mp_limb_t *scratch);
 
 mp_size_t
+ecc_add_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_add_eh (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	    mp_limb_t *scratch);
+
+mp_size_t
 ecc_add_ehh_itch (const struct ecc_curve *ecc);
 void
 ecc_add_ehh (const struct ecc_curve *ecc,
diff --git a/testsuite/curve25519-add-test.c b/testsuite/curve25519-add-test.c
index 6a0d3250..cee6b51d 100644
--- a/testsuite/curve25519-add-test.c
+++ b/testsuite/curve25519-add-test.c
@@ -85,28 +85,43 @@ test_main (void)
   if (!point_zero_p (ecc, pe))
     die ("dup of zero point failed.\n");
 
+  ecc_add_eh (ecc, pe, z, z, scratch);
+  if (!point_zero_p (ecc, pe))
+    die ("dup of zero point failed.\n");
+
   ecc_add_ehh (ecc, pe, g, pe, scratch);
+  ecc_eh_to_a (ecc, 0, pa, pe, scratch);
+  test_ecc_point (ecc, &rg, pa);
 
+  ecc_add_eh (ecc, pe, z, g, scratch);
   ecc_eh_to_a (ecc, 0, pa, pe, scratch);
   test_ecc_point (ecc, &rg, pa);
 
   ecc_add_ehh (ecc, g2, g, pe, scratch);
+  ecc_eh_to_a (ecc, 0, pa, g2, scratch);
+  test_ecc_point (ecc, &rg2, pa);
 
+  ecc_add_eh (ecc, g2, g, g, scratch);
   ecc_eh_to_a (ecc, 0, pa, g2, scratch);
   test_ecc_point (ecc, &rg2, pa);
 
   ecc_add_ehh (ecc, g3, g, g2, scratch);
+  ecc_eh_to_a (ecc, 0, pa, g3, scratch);
+  test_ecc_point (ecc, &rg3, pa);
 
+  ecc_add_eh (ecc, g3, g2, g, scratch);
   ecc_eh_to_a (ecc, 0, pa, g3, scratch);
   test_ecc_point (ecc, &rg3, pa);
 
   ecc_add_ehh (ecc, g4, g, g3, scratch);
+  ecc_eh_to_a (ecc, 0, pa, g4, scratch);
+  test_ecc_point (ecc, &rg4, pa);
 
+  ecc_add_eh (ecc, g4, g3, g, scratch);
   ecc_eh_to_a (ecc, 0, pa, g4, scratch);
   test_ecc_point (ecc, &rg4, pa);
 
   ecc_add_ehh (ecc, g4, g2, g2, scratch);
-
   ecc_eh_to_a (ecc, 0, pa, g4, scratch);
   test_ecc_point (ecc, &rg4, pa);