ecc: Prepare for future Ed25519 optimization.
authorWerner Koch <wk@gnupg.org>
Mon, 30 Sep 2013 18:32:20 +0000 (20:32 +0200)
committerWerner Koch <wk@gnupg.org>
Mon, 30 Sep 2013 18:45:58 +0000 (20:45 +0200)
* mpi/ec-ed25519.c: New but empty file.
* mpi/ec-internal.h: New.
* mpi/ec.c: Include ec-internal.h.
(ec_mod): New.
(ec_addm): Use ec_mod.
(ec_mulm): Remove commented code.  Use ec_mod.
(ec_subm): Call simple sub.
(ec_pow2): Use ec_mulm.
(ec_mul2): New.
(dup_point_weierstrass): Use ec_mul2.
(dup_point_twistededwards): Add special case for a == -1.  Use
ec_mul2.
(add_points_weierstrass): Use ec_mul2.
(add_points_twistededwards): Add special case for a == -1.
(_gcry_mpi_ec_curve_point): Ditto.
(ec_p_init): Add hack to test Barrett functions.
* src/ec-context.h (mpi_ec_ctx_s): Add P_BARRETT.

* mpi/mpi-mod.c (_gcry_mpi_mod_barrett): Fix sign problem.

Signed-off-by: Werner Koch <wk@gnupg.org>
mpi/Makefile.am
mpi/ec-ed25519.c [new file with mode: 0644]
mpi/ec-internal.h [new file with mode: 0644]
mpi/ec.c
mpi/mpi-mod.c
src/ec-context.h
src/misc.c

index e900539..c41b1ea 100644 (file)
@@ -174,4 +174,4 @@ libmpi_la_SOURCES = longlong.h         \
              mpih-div.c     \
              mpih-mul.c     \
              mpiutil.c      \
-              ec.c
+              ec.c ec-internal.h ec-ed25519.c
diff --git a/mpi/ec-ed25519.c b/mpi/ec-ed25519.c
new file mode 100644 (file)
index 0000000..acfe2a6
--- /dev/null
@@ -0,0 +1,37 @@
+/* ec-ed25519.c -  Ed25519 optimized elliptic curve functions
+ * Copyright (C) 2013 g10 Code GmbH
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Libgcrypt is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * Libgcrypt 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+
+#include "mpi-internal.h"
+#include "longlong.h"
+#include "g10lib.h"
+#include "context.h"
+#include "ec-context.h"
+
+
+void
+_gcry_mpi_ec_ed25519_mod (gcry_mpi_t a)
+{
+  (void)a;
+
+}
diff --git a/mpi/ec-internal.h b/mpi/ec-internal.h
new file mode 100644 (file)
index 0000000..759335a
--- /dev/null
@@ -0,0 +1,25 @@
+/* ec-internal.h - Internal declarations of ec*.c
+ * Copyright (C) 2013 g10 Code GmbH
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Libgcrypt is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * Libgcrypt 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef GCRY_EC_INTERNAL_H
+#define GCRY_EC_INTERNAL_H
+
+void _gcry_mpi_ec_ed25519_mod (gcry_mpi_t a);
+
+#endif /*GCRY_EC_INTERNAL_H*/
index de681a1..889df8e 100644 (file)
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -28,6 +28,7 @@
 #include "g10lib.h"
 #include "context.h"
 #include "ec-context.h"
+#include "ec-internal.h"
 
 
 #define point_init(a)  _gcry_mpi_point_init ((a))
@@ -224,131 +225,46 @@ gcry_mpi_point_snatch_set (mpi_point_t point,
 }
 
 
+/* W = W mod P.  */
+static void
+ec_mod (gcry_mpi_t w, mpi_ec_t ec)
+{
+  if (0 && ec->dialect == ECC_DIALECT_ED25519)
+    _gcry_mpi_ec_ed25519_mod (w);
+  else if (ec->t.p_barrett)
+    _gcry_mpi_mod_barrett (w, w, ec->t.p_barrett);
+  else
+    _gcry_mpi_mod (w, w, ec->p);
+}
+
 static void
 ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
 {
-  mpi_addm (w, u, v, ctx->p);
+  gcry_mpi_add (w, u, v);
+  ec_mod (w, ctx);
 }
 
 static void
-ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
+ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
 {
-  mpi_subm (w, u, v, ctx->p);
+  (void)ec;
+  gcry_mpi_sub (w, u, v);
+  /*ec_mod (w, ec);*/
 }
 
 static void
 ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
 {
-#if 0
-  /* NOTE: This code works only for limb sizes of 32 bit.  */
-  mpi_limb_t *wp, *sp;
+  mpi_mul (w, u, v);
+  ec_mod (w, ctx);
+}
 
-  if (ctx->nist_nbits == 192)
-    {
-      mpi_mul (w, u, v);
-      mpi_resize (w, 12);
-      wp = w->d;
-
-      sp = ctx->s[0]->d;
-      sp[0*2+0] = wp[0*2+0];
-      sp[0*2+1] = wp[0*2+1];
-      sp[1*2+0] = wp[1*2+0];
-      sp[1*2+1] = wp[1*2+1];
-      sp[2*2+0] = wp[2*2+0];
-      sp[2*2+1] = wp[2*2+1];
-
-      sp = ctx->s[1]->d;
-      sp[0*2+0] = wp[3*2+0];
-      sp[0*2+1] = wp[3*2+1];
-      sp[1*2+0] = wp[3*2+0];
-      sp[1*2+1] = wp[3*2+1];
-      sp[2*2+0] = 0;
-      sp[2*2+1] = 0;
-
-      sp = ctx->s[2]->d;
-      sp[0*2+0] = 0;
-      sp[0*2+1] = 0;
-      sp[1*2+0] = wp[4*2+0];
-      sp[1*2+1] = wp[4*2+1];
-      sp[2*2+0] = wp[4*2+0];
-      sp[2*2+1] = wp[4*2+1];
-
-      sp = ctx->s[3]->d;
-      sp[0*2+0] = wp[5*2+0];
-      sp[0*2+1] = wp[5*2+1];
-      sp[1*2+0] = wp[5*2+0];
-      sp[1*2+1] = wp[5*2+1];
-      sp[2*2+0] = wp[5*2+0];
-      sp[2*2+1] = wp[5*2+1];
-
-      ctx->s[0]->nlimbs = 6;
-      ctx->s[1]->nlimbs = 6;
-      ctx->s[2]->nlimbs = 6;
-      ctx->s[3]->nlimbs = 6;
-
-      mpi_add (ctx->c, ctx->s[0], ctx->s[1]);
-      mpi_add (ctx->c, ctx->c, ctx->s[2]);
-      mpi_add (ctx->c, ctx->c, ctx->s[3]);
-
-      while ( mpi_cmp (ctx->c, ctx->p ) >= 0 )
-        mpi_sub ( ctx->c, ctx->c, ctx->p );
-      mpi_set (w, ctx->c);
-    }
-  else if (ctx->nist_nbits == 384)
-    {
-      int i;
-      mpi_mul (w, u, v);
-      mpi_resize (w, 24);
-      wp = w->d;
-
-#define NEXT(a) do { ctx->s[(a)]->nlimbs = 12; \
-                     sp = ctx->s[(a)]->d; \
-                     i = 0; } while (0)
-#define X(a) do { sp[i++] = wp[(a)];} while (0)
-#define X0(a) do { sp[i++] = 0; } while (0)
-      NEXT(0);
-      X(0);X(1);X(2);X(3);X(4);X(5);X(6);X(7);X(8);X(9);X(10);X(11);
-      NEXT(1);
-      X0();X0();X0();X0();X(21);X(22);X(23);X0();X0();X0();X0();X0();
-      NEXT(2);
-      X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);X(21);X(22);X(23);
-      NEXT(3);
-      X(21);X(22);X(23);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);
-      NEXT(4);
-      X0();X(23);X0();X(20);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);
-      NEXT(5);
-      X0();X0();X0();X0();X(20);X(21);X(22);X(23);X0();X0();X0();X0();
-      NEXT(6);
-      X(20);X0();X0();X(21);X(22);X(23);X0();X0();X0();X0();X0();X0();
-      NEXT(7);
-      X(23);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);X(21);X(22);
-      NEXT(8);
-      X0();X(20);X(21);X(22);X(23);X0();X0();X0();X0();X0();X0();X0();
-      NEXT(9);
-      X0();X0();X0();X(23);X(23);X0();X0();X0();X0();X0();X0();X0();
-#undef X0
-#undef X
-#undef NEXT
-      mpi_add (ctx->c, ctx->s[0], ctx->s[1]);
-      mpi_add (ctx->c, ctx->c, ctx->s[1]);
-      mpi_add (ctx->c, ctx->c, ctx->s[2]);
-      mpi_add (ctx->c, ctx->c, ctx->s[3]);
-      mpi_add (ctx->c, ctx->c, ctx->s[4]);
-      mpi_add (ctx->c, ctx->c, ctx->s[5]);
-      mpi_add (ctx->c, ctx->c, ctx->s[6]);
-      mpi_sub (ctx->c, ctx->c, ctx->s[7]);
-      mpi_sub (ctx->c, ctx->c, ctx->s[8]);
-      mpi_sub (ctx->c, ctx->c, ctx->s[9]);
-
-      while ( mpi_cmp (ctx->c, ctx->p ) >= 0 )
-        mpi_sub ( ctx->c, ctx->c, ctx->p );
-      while ( ctx->c->sign )
-        mpi_add ( ctx->c, ctx->c, ctx->p );
-      mpi_set (w, ctx->c);
-    }
-  else
-#endif /*0*/
-    mpi_mulm (w, u, v, ctx->p);
+/* W = 2 * U mod P.  */
+static void
+ec_mul2 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
+{
+  mpi_lshift (w, u, 1);
+  ec_mod (w, ctx);
 }
 
 static void
@@ -368,7 +284,7 @@ ec_pow2 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
 {
   /* Using mpi_mul is slightly faster (at least on amd64).  */
   /* mpi_powm (w, b, mpi_const (MPI_C_TWO), ctx->p); */
-  mpi_mulm (w, b, b, ctx->p);
+  ec_mulm (w, b, b, ctx);
 }
 
 
@@ -437,6 +353,15 @@ ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
            gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
 {
   int i;
+  static int use_barrett;
+
+  if (!use_barrett)
+    {
+      if (getenv ("GCRYPT_BARRETT"))
+        use_barrett = 1;
+      else
+        use_barrett = -1;
+    }
 
   /* Fixme: Do we want to check some constraints? e.g.  a < p  */
 
@@ -451,6 +376,8 @@ ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
   if (b && model == MPI_EC_TWISTEDEDWARDS)
     ctx->b = mpi_copy (b);
 
+  ctx->t.p_barrett = use_barrett > 0? _gcry_mpi_barrett_init (ctx->p, 0):NULL;
+
   _gcry_mpi_ec_get_reset (ctx);
 
   /* Allocate scratch variables.  */
@@ -483,6 +410,8 @@ ec_deinit (void *opaque)
   mpi_ec_t ctx = opaque;
   int i;
 
+  _gcry_mpi_barrett_free (ctx->t.p_barrett);
+
   /* Domain parameter.  */
   mpi_free (ctx->p);
   mpi_free (ctx->a);
@@ -732,7 +661,7 @@ dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
         }
       /* Z3 = 2YZ */
       ec_mulm (z3, point->y, point->z, ctx);
-      ec_mulm (z3, z3, mpi_const (MPI_C_TWO), ctx);
+      ec_mul2 (z3, z3, ctx);
 
       /* L2 = 4XY^2 */
       /*                              T2: used for Y2; required later. */
@@ -743,7 +672,7 @@ dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
       /* X3 = L1^2 - 2L2 */
       /*                              T1: used for L2^2. */
       ec_pow2 (x3, l1, ctx);
-      ec_mulm (t1, l2, mpi_const (MPI_C_TWO), ctx);
+      ec_mul2 (t1, l2, ctx);
       ec_subm (x3, x3, t1, ctx);
 
       /* L3 = 8Y^4 */
@@ -811,7 +740,13 @@ dup_point_twistededwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
   ec_pow2 (D, Y1, ctx);
 
   /* E = aC */
-  ec_mulm (E, ctx->a, C, ctx);
+  if (ctx->dialect == ECC_DIALECT_ED25519)
+    {
+      mpi_set (E, C);
+      _gcry_mpi_neg (E, E);
+    }
+  else
+    ec_mulm (E, ctx->a, C, ctx);
 
   /* F = E + D */
   ec_addm (F, E, D, ctx);
@@ -820,7 +755,7 @@ dup_point_twistededwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
   ec_pow2 (H, Z1, ctx);
 
   /* J = F - 2H */
-  ec_mulm (J, H, mpi_const (MPI_C_TWO), ctx);
+  ec_mul2 (J, H, ctx);
   ec_subm (J, F, J, ctx);
 
   /* X_3 = (B - C - D) · J */
@@ -978,7 +913,7 @@ add_points_weierstrass (mpi_point_t result,
           ec_mulm (t2, t2, l7, ctx);
           ec_subm (x3, t1, t2, ctx);
           /* l9 = l7 l3^2 - 2 x3  */
-          ec_mulm (t1, x3, mpi_const (MPI_C_TWO), ctx);
+          ec_mul2 (t1, x3, ctx);
           ec_subm (l9, t2, t1, ctx);
           /* y3 = (l9 l6 - l8 l3^3)/2  */
           ec_mulm (l9, l9, l6, ctx);
@@ -1085,8 +1020,19 @@ add_points_twistededwards (mpi_point_t result,
   ec_mulm (X3, X3, A, ctx);
 
   /* Y_3 = A · G · (D - aC) */
-  ec_mulm (Y3, ctx->a, C, ctx);
-  ec_subm (Y3, D, Y3, ctx);
+  if (ctx->dialect == ECC_DIALECT_ED25519)
+    {
+      /* Using ec_addm (Y3, D, C, ctx) is possible but a litte bit
+         slower because a subm does currently skip the mod step.  */
+      mpi_set (Y3, C);
+      _gcry_mpi_neg (Y3, Y3);
+      ec_subm (Y3, D, Y3, ctx);
+    }
+  else
+    {
+      ec_mulm (Y3, ctx->a, C, ctx);
+      ec_subm (Y3, D, Y3, ctx);
+    }
   ec_mulm (Y3, Y3, G, ctx);
   ec_mulm (Y3, Y3, A, ctx);
 
@@ -1282,7 +1228,13 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
         /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
         ec_pow2 (x, x, ctx);
         ec_pow2 (y, y, ctx);
-        ec_mulm (w, ctx->a, x, ctx);
+        if (ctx->dialect == ECC_DIALECT_ED25519)
+          {
+            mpi_set (w, x);
+            _gcry_mpi_neg (w, w);
+          }
+        else
+          ec_mulm (w, ctx->a, x, ctx);
         ec_addm (w, w, y, ctx);
         ec_subm (w, w, mpi_const (MPI_C_ONE), ctx);
         ec_mulm (x, x, y, ctx);
index 795826e..3d6248b 100644 (file)
@@ -111,7 +111,7 @@ _gcry_mpi_barrett_free (mpi_barrett_t ctx)
    _gcry_mpi_barrett_init must have been called to do the
    precalculations.  CTX is the context created by this precalculation
    and also conveys M.  If the Barret reduction could no be done a
-   starightforward reduction method is used.
+   straightforward reduction method is used.
 
    We assume that these conditions are met:
    Input:  x =(x_2k-1 ...x_0)_b
@@ -126,6 +126,7 @@ _gcry_mpi_mod_barrett (gcry_mpi_t r, gcry_mpi_t x, mpi_barrett_t ctx)
   gcry_mpi_t y = ctx->y;
   gcry_mpi_t r1 = ctx->r1;
   gcry_mpi_t r2 = ctx->r2;
+  int sign;
 
   mpi_normalize (x);
   if (mpi_get_nlimbs (x) > 2*k )
@@ -134,6 +135,9 @@ _gcry_mpi_mod_barrett (gcry_mpi_t r, gcry_mpi_t x, mpi_barrett_t ctx)
       return;
     }
 
+  sign = x->sign;
+  x->sign = 0;
+
   /* 1. q1 = floor( x / b^k-1)
    *    q2 = q1 * y
    *    q3 = floor( q2 / b^k+1 )
@@ -172,6 +176,7 @@ _gcry_mpi_mod_barrett (gcry_mpi_t r, gcry_mpi_t x, mpi_barrett_t ctx)
   while ( mpi_cmp( r, m ) >= 0 )
     mpi_sub ( r, r, m );
 
+  x->sign = sign;
 }
 
 
index 8dce7a7..ba6bdfc 100644 (file)
@@ -53,6 +53,8 @@ struct mpi_ec_ctx_s
 
     gcry_mpi_t two_inv_p;
 
+    mpi_barrett_t p_barrett;
+
     /* Scratch variables.  */
     gcry_mpi_t scratch[11];
 
index d577b24..912039a 100644 (file)
@@ -396,7 +396,8 @@ _gcry_log_printsxp (const char *text, gcry_sexp_t sexp)
     {
       int any = 0;
       int n_closing;
-      char *buf, *p, *pend;
+      char *buf, *pend;
+      const char *p;
       size_t size;
 
       size = gcry_sexp_sprint (sexp, GCRYSEXP_FMT_ADVANCED, NULL, 0);