ecc: Use constant time point operation for Twisted Edwards.
[libgcrypt.git] / mpi / ec.c
index 46cc270..6fca95b 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))
@@ -42,6 +43,12 @@ _gcry_mpi_point_log (const char *name, mpi_point_t point, mpi_ec_t ctx)
   gcry_mpi_t x, y;
   char buf[100];
 
+  if (!point)
+    {
+      snprintf (buf, sizeof buf - 1, "%s.*", name);
+      log_mpidump (buf, NULL);
+      return;
+    }
   snprintf (buf, sizeof buf - 1, "%s.X", name);
 
   if (ctx)
@@ -132,23 +139,6 @@ point_set (mpi_point_t d, mpi_point_t s)
 }
 
 
-/* Return a copy of POINT.  */
-static gcry_mpi_point_t
-point_copy (gcry_mpi_point_t point)
-{
-  gcry_mpi_point_t newpoint;
-
-  if (point)
-    {
-      newpoint = gcry_mpi_point_new (0);
-      point_set (newpoint, point);
-    }
-  else
-    newpoint = NULL;
-  return newpoint;
-}
-
-
 /* Set the projective coordinates from POINT into X, Y, and Z.  If a
    coordinate is not required, X, Y, or Z may be passed as NULL.  */
 void
@@ -235,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
@@ -367,19 +272,47 @@ ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e,
          mpi_ec_t ctx)
 {
   mpi_powm (w, b, e, ctx->p);
-  _gcry_mpi_abs (w);
+  /* _gcry_mpi_abs (w); */
+}
+
+
+/* Shortcut for
+     ec_powm (B, B, mpi_const (MPI_C_TWO), ctx);
+   for easier optimization.  */
+static void
+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); */
+  ec_mulm (w, b, b, ctx);
 }
 
+
+/* Shortcut for
+     ec_powm (B, B, mpi_const (MPI_C_THREE), ctx);
+   for easier optimization.  */
+static void
+ec_pow3 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
+{
+  mpi_powm (w, b, mpi_const (MPI_C_THREE), ctx->p);
+}
+
+
 static void
 ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx)
 {
-  mpi_invm (x, a, ctx->p);
+  if (!mpi_invm (x, a, ctx->p))
+    {
+      log_error ("ec_invm: inverse does not exist:\n");
+      log_mpidump ("  a", a);
+      log_mpidump ("  p", ctx->p);
+    }
 }
 
 
 /* Force recomputation of all helper variables.  */
-static void
-ec_get_reset (mpi_ec_t ec)
+void
+_gcry_mpi_ec_get_reset (mpi_ec_t ec)
 {
   ec->t.valid.a_is_pminus3 = 0;
   ec->t.valid.two_inv_p = 0;
@@ -426,19 +359,37 @@ ec_get_two_inv_p (mpi_ec_t ec)
    coefficient.  CTX is expected to be zeroized.  */
 static void
 ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
+           enum ecc_dialects dialect,
+           int flags,
            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  */
 
   ctx->model = model;
+  ctx->dialect = dialect;
+  ctx->flags = flags;
+  if (dialect == ECC_DIALECT_ED25519)
+    ctx->nbits = 256;
+  else
+    ctx->nbits = mpi_get_nbits (p);
   ctx->p = mpi_copy (p);
   ctx->a = mpi_copy (a);
-  if (b && model == MPI_EC_TWISTEDEDWARDS)
-    ctx->b = mpi_copy (b);
+  ctx->b = mpi_copy (b);
+
+  ctx->t.p_barrett = use_barrett > 0? _gcry_mpi_barrett_init (ctx->p, 0):NULL;
 
-  ec_get_reset (ctx);
+  _gcry_mpi_ec_get_reset (ctx);
 
   /* Allocate scratch variables.  */
   for (i=0; i< DIM(ctx->t.scratch); i++)
@@ -470,6 +421,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);
@@ -511,19 +464,21 @@ ec_deinit (void *opaque)
    This context needs to be released using _gcry_mpi_ec_free.  */
 mpi_ec_t
 _gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model,
+                             enum ecc_dialects dialect,
+                             int flags,
                              gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
 {
   mpi_ec_t ctx;
 
   ctx = gcry_xcalloc (1, sizeof *ctx);
-  ec_p_init (ctx, model, p, a, b);
+  ec_p_init (ctx, model, dialect, flags, p, a, b);
 
   return ctx;
 }
 
 
 /* This is a variant of _gcry_mpi_ec_p_internal_new which returns an
-   public contect and does some error checking on the supplied
+   public context and does some error checking on the supplied
    arguments.  On success the new context is stored at R_CTX and 0 is
    returned; on error NULL is stored at R_CTX and an error code is
    returned.
@@ -532,6 +487,8 @@ _gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model,
 gpg_err_code_t
 _gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx,
                     enum gcry_mpi_ec_models model,
+                    enum ecc_dialects dialect,
+                    int flags,
                     gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
 {
   gcry_ctx_t ctx;
@@ -545,7 +502,7 @@ _gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx,
   if (!ctx)
     return gpg_err_code_from_syserror ();
   ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
-  ec_p_init (ec, model, p, a, b);
+  ec_p_init (ec, model, dialect, flags, p, a, b);
 
   *r_ctx = ctx;
   return 0;
@@ -568,44 +525,7 @@ _gcry_mpi_ec_get_mpi (const char *name, gcry_ctx_t ctx, int copy)
 {
   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
 
-  if (!strcmp (name, "p") && ec->p)
-    return mpi_is_const (ec->p) && !copy? ec->p : mpi_copy (ec->p);
-  if (!strcmp (name, "a") && ec->a)
-    return mpi_is_const (ec->a) && !copy? ec->a : mpi_copy (ec->a);
-  if (!strcmp (name, "b") && ec->b)
-    return mpi_is_const (ec->b) && !copy? ec->b : mpi_copy (ec->b);
-  if (!strcmp (name, "n") && ec->n)
-    return mpi_is_const (ec->n) && !copy? ec->n : mpi_copy (ec->n);
-  if (!strcmp (name, "d") && ec->d)
-    return mpi_is_const (ec->d) && !copy? ec->d : mpi_copy (ec->d);
-
-  /* Return a requested point coordinate.  */
-  if (!strcmp (name, "g.x") && ec->G && ec->G->x)
-    return mpi_is_const (ec->G->x) && !copy? ec->G->x : mpi_copy (ec->G->x);
-  if (!strcmp (name, "g.y") && ec->G && ec->G->y)
-    return mpi_is_const (ec->G->y) && !copy? ec->G->y : mpi_copy (ec->G->y);
-  if (!strcmp (name, "q.x") && ec->Q && ec->Q->x)
-    return mpi_is_const (ec->Q->x) && !copy? ec->Q->x : mpi_copy (ec->Q->x);
-  if (!strcmp (name, "q.y") && ec->Q && ec->Q->y)
-    return mpi_is_const (ec->G->y) && !copy? ec->Q->y : mpi_copy (ec->Q->y);
-
-  /* If a point has been requested, return it in standard encoding.  */
-  if (!strcmp (name, "g") && ec->G)
-    return _gcry_mpi_ec_ec2os (ec->G, ec);
-  if (!strcmp (name, "q"))
-    {
-      /* If only the private key is given, compute the public key.  */
-      if (!ec->Q && ec->d && ec->G && ec->p && ec->a)
-        {
-          ec->Q = gcry_mpi_point_new (0);
-          _gcry_mpi_ec_mul_point (ec->Q, ec->d, ec->G, ec);
-        }
-
-      if (ec->Q)
-        return _gcry_mpi_ec_ec2os (ec->Q, ec);
-    }
-
-  return NULL;
+  return _gcry_ecc_get_mpi (name, ec, copy);
 }
 
 
@@ -616,22 +536,7 @@ _gcry_mpi_ec_get_point (const char *name, gcry_ctx_t ctx, int copy)
 
   (void)copy;  /* Not used.  */
 
-  if (!strcmp (name, "g") && ec->G)
-    return point_copy (ec->G);
-  if (!strcmp (name, "q"))
-    {
-      /* If only the private key is given, compute the public key.  */
-      if (!ec->Q && ec->d && ec->G && ec->p && ec->a)
-        {
-          ec->Q = gcry_mpi_point_new (0);
-          _gcry_mpi_ec_mul_point (ec->Q, ec->d, ec->G, ec);
-        }
-
-      if (ec->Q)
-        return point_copy (ec->Q);
-    }
-
-  return NULL;
+  return _gcry_ecc_get_point (name, ec);
 }
 
 
@@ -641,37 +546,7 @@ _gcry_mpi_ec_set_mpi (const char *name, gcry_mpi_t newvalue,
 {
   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
 
-  if (!strcmp (name, "p"))
-    {
-      mpi_free (ec->p);
-      ec->p = mpi_copy (newvalue);
-      ec_get_reset (ec);
-    }
-  else if (!strcmp (name, "a"))
-    {
-      mpi_free (ec->a);
-      ec->a = mpi_copy (newvalue);
-      ec_get_reset (ec);
-    }
-  else if (!strcmp (name, "b"))
-    {
-      mpi_free (ec->b);
-      ec->b = mpi_copy (newvalue);
-    }
-  else if (!strcmp (name, "n"))
-    {
-      mpi_free (ec->n);
-      ec->n = mpi_copy (newvalue);
-    }
-  else if (!strcmp (name, "d"))
-    {
-      mpi_free (ec->d);
-      ec->d = mpi_copy (newvalue);
-    }
-  else
-    return GPG_ERR_UNKNOWN_NAME;
-
-  return 0;
+  return _gcry_ecc_set_mpi (name, newvalue, ec);
 }
 
 
@@ -681,20 +556,7 @@ _gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue,
 {
   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
 
-  if (!strcmp (name, "g"))
-    {
-      gcry_mpi_point_release (ec->G);
-      ec->G = point_copy (newvalue);
-    }
-  else if (!strcmp (name, "q"))
-    {
-      gcry_mpi_point_release (ec->Q);
-      ec->Q = point_copy (newvalue);
-    }
-  else
-    return GPG_ERR_UNKNOWN_NAME;
-
-  return 0;
+  return _gcry_ecc_set_point (name, newvalue, ec);
 }
 
 
@@ -706,30 +568,62 @@ int
 _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
                          mpi_ec_t ctx)
 {
-  gcry_mpi_t z1, z2, z3;
-
   if (!mpi_cmp_ui (point->z, 0))
     return -1;
 
-  z1 = mpi_new (0);
-  z2 = mpi_new (0);
-  ec_invm (z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
-  ec_mulm (z2, z1, z1, ctx);    /* z2 = z^(-2) mod p  */
+  switch (ctx->model)
+    {
+    case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates.  */
+      {
+        gcry_mpi_t z1, z2, z3;
+
+        z1 = mpi_new (0);
+        z2 = mpi_new (0);
+        ec_invm (z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
+        ec_mulm (z2, z1, z1, ctx);    /* z2 = z^(-2) mod p  */
+
+        if (x)
+          ec_mulm (x, point->x, z2, ctx);
+
+        if (y)
+          {
+            z3 = mpi_new (0);
+            ec_mulm (z3, z2, z1, ctx);      /* z3 = z^(-3) mod p  */
+            ec_mulm (y, point->y, z3, ctx);
+            mpi_free (z3);
+          }
+
+        mpi_free (z2);
+        mpi_free (z1);
+      }
+      return 0;
 
-  if (x)
-    ec_mulm (x, point->x, z2, ctx);
+    case MPI_EC_MONTGOMERY:
+      {
+        log_fatal ("%s: %s not yet supported\n",
+                   "_gcry_mpi_ec_get_affine", "Montgomery");
+      }
+      return -1;
 
-  if (y)
-    {
-      z3 = mpi_new (0);
-      ec_mulm (z3, z2, z1, ctx);      /* z3 = z^(-3) mod p  */
-      ec_mulm (y, point->y, z3, ctx);
-      mpi_free (z3);
-    }
+    case MPI_EC_TWISTEDEDWARDS:
+      {
+        gcry_mpi_t z;
 
-  mpi_free (z2);
-  mpi_free (z1);
-  return 0;
+        z = mpi_new (0);
+        ec_invm (z, point->z, ctx);
+
+        if (x)
+          ec_mulm (x, point->x, z, ctx);
+        if (y)
+          ec_mulm (y, point->y, z, ctx);
+
+        gcry_mpi_release (z);
+      }
+      return 0;
+
+    default:
+      return -1;
+    }
 }
 
 
@@ -762,7 +656,7 @@ dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
           /* L1 = 3(X - Z^2)(X + Z^2) */
           /*                          T1: used for Z^2. */
           /*                          T2: used for the right term.  */
-          ec_powm (t1, point->z, mpi_const (MPI_C_TWO), ctx);
+          ec_pow2 (t1, point->z, ctx);
           ec_subm (l1, point->x, t1, ctx);
           ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
           ec_addm (t2, point->x, t1, ctx);
@@ -772,7 +666,7 @@ dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
         {
           /* L1 = 3X^2 + aZ^4 */
           /*                          T1: used for aZ^4. */
-          ec_powm (l1, point->x, mpi_const (MPI_C_TWO), ctx);
+          ec_pow2 (l1, point->x, ctx);
           ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
           ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx);
           ec_mulm (t1, t1, ctx->a, ctx);
@@ -780,23 +674,23 @@ 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. */
-      ec_powm (t2, point->y, mpi_const (MPI_C_TWO), ctx);
+      ec_pow2 (t2, point->y, ctx);
       ec_mulm (l2, t2, point->x, ctx);
       ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx);
 
       /* X3 = L1^2 - 2L2 */
       /*                              T1: used for L2^2. */
-      ec_powm (x3, l1, mpi_const (MPI_C_TWO), ctx);
-      ec_mulm (t1, l2, mpi_const (MPI_C_TWO), ctx);
+      ec_pow2 (x3, l1, ctx);
+      ec_mul2 (t1, l2, ctx);
       ec_subm (x3, x3, t1, ctx);
 
       /* L3 = 8Y^4 */
       /*                              T2: taken from above. */
-      ec_powm (t2, t2, mpi_const (MPI_C_TWO), ctx);
+      ec_pow2 (t2, t2, ctx);
       ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx);
 
       /* Y3 = L1(L2 - X3) - L3 */
@@ -833,8 +727,75 @@ dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
 static void
 dup_point_twistededwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
 {
-  log_fatal ("%s: %s not yet supported\n",
-             "_gcry_mpi_ec_dup_point", "Twisted Edwards");
+#define X1 (point->x)
+#define Y1 (point->y)
+#define Z1 (point->z)
+#define X3 (result->x)
+#define Y3 (result->y)
+#define Z3 (result->z)
+#define B (ctx->t.scratch[0])
+#define C (ctx->t.scratch[1])
+#define D (ctx->t.scratch[2])
+#define E (ctx->t.scratch[3])
+#define F (ctx->t.scratch[4])
+#define H (ctx->t.scratch[5])
+#define J (ctx->t.scratch[6])
+
+  /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
+
+  /* B = (X_1 + Y_1)^2  */
+  ec_addm (B, X1, Y1, ctx);
+  ec_pow2 (B, B, ctx);
+
+  /* C = X_1^2 */
+  /* D = Y_1^2 */
+  ec_pow2 (C, X1, ctx);
+  ec_pow2 (D, Y1, ctx);
+
+  /* E = aC */
+  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);
+
+  /* H = Z_1^2 */
+  ec_pow2 (H, Z1, ctx);
+
+  /* J = F - 2H */
+  ec_mul2 (J, H, ctx);
+  ec_subm (J, F, J, ctx);
+
+  /* X_3 = (B - C - D) · J */
+  ec_subm (X3, B, C, ctx);
+  ec_subm (X3, X3, D, ctx);
+  ec_mulm (X3, X3, J, ctx);
+
+  /* Y_3 = F · (E - D) */
+  ec_subm (Y3, E, D, ctx);
+  ec_mulm (Y3, Y3, F, ctx);
+
+  /* Z_3 = F · J */
+  ec_mulm (Z3, F, J, ctx);
+
+#undef X1
+#undef Y1
+#undef Z1
+#undef X3
+#undef Y3
+#undef Z3
+#undef B
+#undef C
+#undef D
+#undef E
+#undef F
+#undef H
+#undef J
 }
 
 
@@ -914,14 +875,14 @@ add_points_weierstrass (mpi_point_t result,
         mpi_set (l1, x1);
       else
         {
-          ec_powm (l1, z2, mpi_const (MPI_C_TWO), ctx);
+          ec_pow2 (l1, z2, ctx);
           ec_mulm (l1, l1, x1, ctx);
         }
       if (z1_is_one)
         mpi_set (l2, x2);
       else
         {
-          ec_powm (l2, z1, mpi_const (MPI_C_TWO), ctx);
+          ec_pow2 (l2, z1, ctx);
           ec_mulm (l2, l2, x2, ctx);
         }
       /* l3 = l1 - l2 */
@@ -960,12 +921,12 @@ add_points_weierstrass (mpi_point_t result,
           ec_mulm (z3, z1, z2, ctx);
           ec_mulm (z3, z3, l3, ctx);
           /* x3 = l6^2 - l7 l3^2  */
-          ec_powm (t1, l6, mpi_const (MPI_C_TWO), ctx);
-          ec_powm (t2, l3, mpi_const (MPI_C_TWO), ctx);
+          ec_pow2 (t1, l6, ctx);
+          ec_pow2 (t2, l3, ctx);
           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);
@@ -1020,8 +981,95 @@ add_points_twistededwards (mpi_point_t result,
                            mpi_point_t p1, mpi_point_t p2,
                            mpi_ec_t ctx)
 {
-  log_fatal ("%s: %s not yet supported\n",
-             "_gcry_mpi_ec_add_points", "Twisted Edwards");
+#define X1 (p1->x)
+#define Y1 (p1->y)
+#define Z1 (p1->z)
+#define X2 (p2->x)
+#define Y2 (p2->y)
+#define Z2 (p2->z)
+#define X3 (result->x)
+#define Y3 (result->y)
+#define Z3 (result->z)
+#define A (ctx->t.scratch[0])
+#define B (ctx->t.scratch[1])
+#define C (ctx->t.scratch[2])
+#define D (ctx->t.scratch[3])
+#define E (ctx->t.scratch[4])
+#define F (ctx->t.scratch[5])
+#define G (ctx->t.scratch[6])
+#define tmp (ctx->t.scratch[7])
+
+  /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3)  */
+
+  /* A = Z1 · Z2 */
+  ec_mulm (A, Z1, Z2, ctx);
+
+  /* B = A^2 */
+  ec_pow2 (B, A, ctx);
+
+  /* C = X1 · X2 */
+  ec_mulm (C, X1, X2, ctx);
+
+  /* D = Y1 · Y2 */
+  ec_mulm (D, Y1, Y2, ctx);
+
+  /* E = d · C · D */
+  ec_mulm (E, ctx->b, C, ctx);
+  ec_mulm (E, E, D, ctx);
+
+  /* F = B - E */
+  ec_subm (F, B, E, ctx);
+
+  /* G = B + E */
+  ec_addm (G, B, E, ctx);
+
+  /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
+  ec_addm (tmp, X1, Y1, ctx);
+  ec_addm (X3, X2, Y2, ctx);
+  ec_mulm (X3, X3, tmp, ctx);
+  ec_subm (X3, X3, C, ctx);
+  ec_subm (X3, X3, D, ctx);
+  ec_mulm (X3, X3, F, ctx);
+  ec_mulm (X3, X3, A, ctx);
+
+  /* Y_3 = A · G · (D - aC) */
+  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);
+
+  /* Z_3 = F · G */
+  ec_mulm (Z3, F, G, ctx);
+
+
+#undef X1
+#undef Y1
+#undef Z1
+#undef X2
+#undef Y2
+#undef Z2
+#undef X3
+#undef Y3
+#undef Z3
+#undef A
+#undef B
+#undef C
+#undef D
+#undef E
+#undef F
+#undef G
+#undef tmp
 }
 
 
@@ -1054,28 +1102,49 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
                         gcry_mpi_t scalar, mpi_point_t point,
                         mpi_ec_t ctx)
 {
-#if 0
-  /* Simple left to right binary method.  GECC Algorithm 3.27 */
-  unsigned int nbits;
-  int i;
-
-  nbits = mpi_get_nbits (scalar);
-  mpi_set_ui (result->x, 1);
-  mpi_set_ui (result->y, 1);
-  mpi_set_ui (result->z, 0);
-
-  for (i=nbits-1; i >= 0; i--)
-    {
-      _gcry_mpi_ec_dup_point (result, result, ctx);
-      if (mpi_test_bit (scalar, i) == 1)
-        _gcry_mpi_ec_add_points (result, result, point, ctx);
-    }
-
-#else
   gcry_mpi_t x1, y1, z1, k, h, yy;
   unsigned int i, loops;
   mpi_point_struct p1, p2, p1inv;
 
+  if (ctx->model == MPI_EC_TWISTEDEDWARDS)
+    {
+      /* Simple left to right binary method.  GECC Algorithm 3.27 */
+      unsigned int nbits;
+      int j;
+
+      nbits = mpi_get_nbits (scalar);
+      mpi_set_ui (result->x, 0);
+      mpi_set_ui (result->y, 1);
+      mpi_set_ui (result->z, 1);
+
+      if (mpi_is_secure (scalar))
+        {
+          /* If SCALAR is in secure memory we assume that it is the
+             secret key we use constant time operation.  */
+          mpi_point_struct tmppnt;
+
+          point_init (&tmppnt);
+          for (j=nbits-1; j >= 0; j--)
+            {
+              _gcry_mpi_ec_dup_point (result, result, ctx);
+              _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
+              if (mpi_test_bit (scalar, j))
+                point_set (result, &tmppnt);
+            }
+          point_free (&tmppnt);
+        }
+      else
+        {
+          for (j=nbits-1; j >= 0; j--)
+            {
+              _gcry_mpi_ec_dup_point (result, result, ctx);
+              if (mpi_test_bit (scalar, j))
+                _gcry_mpi_ec_add_points (result, result, point, ctx);
+            }
+        }
+      return;
+    }
+
   x1 = mpi_alloc_like (ctx->p);
   y1 = mpi_alloc_like (ctx->p);
   h  = mpi_alloc_like (ctx->p);
@@ -1159,7 +1228,6 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
   point_free (&p1inv);
   mpi_free (h);
   mpi_free (k);
-#endif
 }
 
 
@@ -1180,8 +1248,22 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
   switch (ctx->model)
     {
     case MPI_EC_WEIERSTRASS:
-      log_fatal ("%s: %s not yet supported\n",
-                 "_gcry_mpi_ec_curve_point", "Weierstrass");
+      {
+        gcry_mpi_t xxx = mpi_new (0);
+
+        /* y^2 == x^3 + a·x + b */
+        ec_pow2 (y, y, ctx);
+
+        ec_pow3 (xxx, x, ctx);
+        ec_mulm (w, ctx->a, x, ctx);
+        ec_addm (w, w, ctx->b, ctx);
+        ec_addm (w, w, xxx, ctx);
+
+        if (!mpi_cmp (y, w))
+          res = 1;
+
+        gcry_mpi_release (xxx);
+      }
       break;
     case MPI_EC_MONTGOMERY:
       log_fatal ("%s: %s not yet supported\n",
@@ -1190,9 +1272,15 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
     case MPI_EC_TWISTEDEDWARDS:
       {
         /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
-        ec_powm (x, x, mpi_const (MPI_C_TWO), ctx);
-        ec_powm (y, y, mpi_const (MPI_C_TWO), ctx);
-        ec_mulm (w, ctx->a, x, ctx);
+        ec_pow2 (x, x, ctx);
+        ec_pow2 (y, y, 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);