ecc: Use constant time point operation for Twisted Edwards.
[libgcrypt.git] / mpi / ec.c
index 883d8f6..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)
@@ -218,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
@@ -362,7 +284,17 @@ 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);
+}
+
+
+/* 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);
 }
 
 
@@ -428,18 +360,34 @@ ec_get_two_inv_p (mpi_ec_t ec)
 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;
 
   _gcry_mpi_ec_get_reset (ctx);
 
@@ -473,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);
@@ -515,19 +465,20 @@ ec_deinit (void *opaque)
 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, dialect, 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.
@@ -537,6 +488,7 @@ 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;
@@ -550,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, dialect, p, a, b);
+  ec_p_init (ec, model, dialect, flags, p, a, b);
 
   *r_ctx = ctx;
   return 0;
@@ -722,7 +674,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. */
@@ -733,7 +685,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 */
@@ -801,7 +753,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);
@@ -810,7 +768,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 */
@@ -968,7 +926,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);
@@ -1075,8 +1033,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);
 
@@ -1148,11 +1117,30 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
       mpi_set_ui (result->y, 1);
       mpi_set_ui (result->z, 1);
 
-      for (j=nbits-1; j >= 0; j--)
+      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
         {
-          _gcry_mpi_ec_dup_point (result, result, ctx);
-          if (mpi_test_bit (scalar, j) == 1)
-            _gcry_mpi_ec_add_points (result, result, point, ctx);
+          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;
     }
@@ -1260,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",
@@ -1272,7 +1274,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);