Implemented point doubling for Edwards curves.

6 files changed, 232 insertions, 11 deletions

diff --git a/ChangeLog b/ChangeLog
index c7177074..5c02b911 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,13 @@
 2014-07-11  Niels Möller  <nisse@lysator.liu.se>
 
+	* ecc-dup-eh.c (ecc_dup_eh, ecc_dup_eh_itch): New file, new functions.
+	* ecc-eh-to-a.c (ecc_eh_to_a, ecc_eh_to_a_itch): New file, new
+	functions.
+	* ecc.h: Declare new functions.
+	* ecc-internal.h (ECC_EH_TO_A_ITCH, ECC_DUP_EH_ITCH): New macros.
+	* Makefile.in (hogweed_SOURCES): Added ecc-dup-eh.c and
+	ecc-eh-to-a.c.
+
 	* ecc-internal.h (struct ecc_curve): New constant edwards_root.
 	* ecc-192.c (nettle_secp_192r1): Updated accordingly, additional
 	NULL pointer.
diff --git a/Makefile.in b/Makefile.in
index 5888b004..0c74f878 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -167,6 +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-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-dup-eh.c b/ecc-dup-eh.c
new file mode 100644
index 00000000..70650631
--- /dev/null
+++ b/ecc-dup-eh.c
@@ -0,0 +1,98 @@
+/* ecc-dup-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_dup_eh_itch (const struct ecc_curve *ecc)
+{
+  return ECC_DUP_EH_ITCH (ecc->size);
+}
+
+/* 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-edwards-projective.html#doubling-dbl-2007-bl):
+
+     Computation	Operation	Live variables
+     
+     b = (x+y)^2	sqr		b
+     c = x^2		sqr		b, c
+     d = y^2		sqr		b, c, d
+     e = c+d				b, c, d, e
+     h = z^2		sqr		b, c, d, e, h
+     j = e-2*h				b, c, d, e, j
+     x' = (b-e)*j	mul		c, d, e, j
+     y' = e*(c-d)	mul		e, j
+     z' = e*j		mul
+  */
+#define b scratch 
+#define c (scratch  + ecc->size)
+#define d (scratch  + 2*ecc->size)
+#define e (scratch  + 3*ecc->size)
+#define j (scratch  + 4*ecc->size)
+
+  /* b */
+  ecc_modp_add (ecc, e, p, p + ecc->size);
+  ecc_modp_sqr (ecc, b, e);
+
+  /* c */
+  ecc_modp_sqr (ecc, c, p);
+  /* d */
+  ecc_modp_sqr (ecc, d, p + ecc->size);
+  /* h, can use r as scratch, even for in-place operation. */
+  ecc_modp_sqr (ecc, r, p + 2*ecc->size);
+  /* e, */
+  ecc_modp_add (ecc, e, c, d);
+  /* b - e */
+  ecc_modp_sub (ecc, b, b, e);
+  /* j */
+  ecc_modp_add (ecc, r, r, r);
+  ecc_modp_sub (ecc, j, e, r);
+
+  /* x' */
+  ecc_modp_mul (ecc, r, b, j);
+  /* y' */
+  ecc_modp_sub (ecc, c, c, d);
+  ecc_modp_mul (ecc, r + ecc->size, e, c);
+  /* z' */
+  ecc_modp_mul (ecc, b, e, j);
+  mpn_copyi (r + 2*ecc->size, b, ecc->size);
+}
diff --git a/ecc-eh-to-a.c b/ecc-eh-to-a.c
new file mode 100644
index 00000000..bd0625d4
--- /dev/null
+++ b/ecc-eh-to-a.c
@@ -0,0 +1,101 @@
+/* ecc-eh-to-a.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_eh_to_a_itch (const struct ecc_curve *ecc)
+{
+  /* Needs 2*ecc->size + scratch for ecc_modq_inv */
+  return ECC_EH_TO_A_ITCH (ecc->size);
+}
+
+/* Convert from homogeneous coordinates on the Edwards curve to affine
+   coordinates on the corresponding Montgomery curve. */
+void
+ecc_eh_to_a (const struct ecc_curve *ecc,
+	     int flags,
+	     mp_limb_t *r, const mp_limb_t *p,
+	     mp_limb_t *scratch)
+{
+#define izp scratch
+#define sp (scratch + ecc->size)
+#define tp (scratch + 2*ecc->size)
+
+#define xp r
+#define yp (r + ecc->size)
+#define up p
+#define vp (p + ecc->size)
+#define wp (p + 2*ecc->size)
+  /* x = (v+1)/(v-1), y = t x / u (with t = sqrt(b+2))
+
+     In homogeneous coordinates,
+
+     X = (W + V) U
+     Y = t (W + V) W
+     Z = (W - V) U
+  */
+  /* FIXME: Simplify for common case that only x-coordinate is wanted. */
+
+  mp_limb_t cy;
+
+  ecc_modp_sub (ecc, izp, wp, vp);
+  /* FIXME: For the infinity point, this subtraction gives zero (mod
+     p), and the inversion below fails and returns something else. */
+  ecc_modp_mul (ecc, izp + ecc->size, izp, up);
+  /* Needs 3*size scratch */
+  ecc_modp_inv (ecc, izp, izp + ecc->size, izp + 2*ecc->size);
+
+  ecc_modp_add (ecc, sp, wp, vp);
+  ecc_modp_mul (ecc, tp, sp, up);
+  mpn_copyi (sp, tp, ecc->size); /* FIXME: Eliminate copy */
+  ecc_modp_mul (ecc, tp, sp, izp);
+  cy = mpn_sub_n (xp, tp, ecc->p, ecc->size);
+  cnd_copy (cy, xp, tp, ecc->size);
+
+  if (flags & 2)
+    /* Skip y coordinate */
+    return;
+  
+  ecc_modp_add (ecc, sp, wp, vp); /* FIXME: Redundant */
+  ecc_modp_mul (ecc, tp, sp, wp);
+  mpn_copyi (sp, tp, ecc->size); /* FIXME: Eliminate copy */
+  ecc_modp_mul (ecc, tp, sp, ecc->edwards_root);
+  mpn_copyi (sp, tp, ecc->size); /* FIXME: Eliminate copy */
+  ecc_modp_mul (ecc, tp, sp, izp);
+  cy = mpn_sub_n (yp, tp, ecc->p, ecc->size);
+  cnd_copy (cy, yp, tp, ecc->size);
+}
diff --git a/ecc-internal.h b/ecc-internal.h
index 8c3b6f78..b91e343e 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -237,8 +237,9 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
 /* Current scratch needs: */
 #define ECC_MODINV_ITCH(size) (3*(size))
 #define ECC_J_TO_A_ITCH(size) (5*(size))
-#define ECC_DUP_JA_ITCH(size) (5*(size))
+#define ECC_EH_TO_A_ITCH(size) (5*(size))
 #define ECC_DUP_JJ_ITCH(size) (5*(size))
+#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_MUL_G_ITCH(size) (9*(size))
diff --git a/ecc.h b/ecc.h
index ca8c8c37..03129348 100644
--- a/ecc.h
+++ b/ecc.h
@@ -61,14 +61,16 @@ extern "C" {
 #define ecc_a_to_j nettle_ecc_a_to_j
 #define ecc_j_to_a_itch nettle_ecc_j_to_a_itch
 #define ecc_j_to_a nettle_ecc_j_to_a
-#define ecc_dup_ja_itch nettle_ecc_dup_ja_itch
-#define ecc_dup_ja nettle_ecc_dup_ja
+#define ecc_eh_to_a_itch nettle_ecc_eh_to_a_itch
+#define ecc_eh_to_a nettle_ecc_eh_to_a
 #define ecc_dup_jj_itch nettle_ecc_dup_jj_itch
 #define ecc_dup_jj nettle_ecc_dup_jj
 #define ecc_add_jja_itch nettle_ecc_add_jja_itch
 #define ecc_add_jja nettle_ecc_add_jja
 #define ecc_add_jjj_itch nettle_ecc_add_jjj_itch
 #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_mul_g_itch nettle_ecc_mul_g_itch
 #define ecc_mul_g nettle_ecc_mul_g
 #define ecc_mul_a_itch nettle_ecc_mul_a_itch
@@ -186,17 +188,18 @@ ecc_j_to_a (const struct ecc_curve *ecc,
 	    mp_limb_t *r, const mp_limb_t *p,
 	    mp_limb_t *scratch);
 
-/* Group operations */
-
+/* Converts a point P on an Edwards curve to affine coordinates on
+   the corresponding Montgomery curve. */
 
-/* Point doubling, with jacobian output and affine input. Corner
-   cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
 mp_size_t
-ecc_dup_ja_itch (const struct ecc_curve *ecc);
+ecc_eh_to_a_itch (const struct ecc_curve *ecc);
 void
-ecc_dup_ja (const struct ecc_curve *ecc,
-	    mp_limb_t *r, const mp_limb_t *p,
-	    mp_limb_t *scratch);
+ecc_eh_to_a (const struct ecc_curve *ecc,
+	     int flags,
+	     mp_limb_t *r, const mp_limb_t *p,
+	     mp_limb_t *scratch);
+
+/* Group operations */
 
 /* Point doubling, with jacobian input and output. Corner cases:
    Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
@@ -230,6 +233,15 @@ ecc_add_jjj (const struct ecc_curve *ecc,
 	     mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 	     mp_limb_t *scratch);
 
+/* FIXME: Use a generic ecc_dup, ecc_add, for any type of curve. */
+/* Point doubling on an Edwards curve, with homogeneous
+   cooordinates. */
+mp_size_t
+ecc_dup_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_dup_eh (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    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,