examples/ecc-benchmark.c

   1 /* ecc-benchmark.c
   2
   3    Copyright (C) 2013 Niels Möller
   4
   5    This file is part of GNU Nettle.
   6
   7    GNU Nettle is free software: you can redistribute it and/or
   8    modify it under the terms of either:
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at your
  12        option) any later version.
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at your
  18        option) any later version.
  19
  20    or both in parallel, as here.
  21
  22    GNU Nettle is distributed in the hope that it will be useful,
  23    but WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see http://www.gnu.org/licenses/.
  30 */
  31
  32 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include <stdarg.h>
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42
  43 #include <errno.h>
  44
  45 #include <time.h>
  46
  47 #include "timing.h"
  48
  49 #include "../ecc.h"
  50 #include "../ecc-internal.h"
  51 #include "../gmp-glue.h"
  52
  53 #define BENCH_INTERVAL 0.1
  54
  55 static void NORETURN PRINTF_STYLE(1,2)
  56 die(const char *format, ...)
  57 {
  58   va_list args;
  59   va_start(args, format);
  60   vfprintf(stderr, format, args);
  61   va_end(args);
  62
  63   exit(EXIT_FAILURE);
  64 }
  65
  66 static void *
  67 xalloc (size_t size)
  68 {
  69   void *p = malloc (size);
  70   if (!p)
  71     {
  72       fprintf (stderr, "Virtual memory exhausted\n");
  73       abort ();
  74     }
  75   return p;
  76 }
  77
  78 static mp_limb_t *
  79 xalloc_limbs (mp_size_t size)
  80 {
  81   return xalloc (size * sizeof(mp_limb_t));
  82 }
  83
  84 /* Returns second per function call */
  85 static double
  86 time_function(void (*f)(void *arg), void *arg)
  87 {
  88   unsigned ncalls;
  89   double elapsed;
  90
  91   /* Warm up */
  92   f(arg);
  93   for (ncalls = 10 ;;)
  94     {
  95       unsigned i;
  96
  97       time_start();
  98       for (i = 0; i < ncalls; i++)
  99         f(arg);
 100       elapsed = time_end();
 101       if (elapsed > BENCH_INTERVAL)
 102         break;
 103       else if (elapsed < BENCH_INTERVAL / 10)
 104         ncalls *= 10;
 105       else
 106         ncalls *= 2;
 107     }
 108   return elapsed / ncalls;
 109 }
 110
 111 #if !NETTLE_USE_MINI_GMP
 112 static int
 113 modinv_gcd (const struct ecc_curve *ecc,
 114             mp_limb_t *rp, mp_limb_t *ap, mp_limb_t *tp)
 115 {
 116   mp_size_t size = ecc->p.size;
 117   mp_limb_t *up = tp;
 118   mp_limb_t *vp = tp + size+1;
 119   mp_limb_t *gp = tp + 2*(size+1);
 120   mp_limb_t *sp = tp + 3*(size+1);
 121   mp_size_t gn, sn;
 122
 123   mpn_copyi (up, ap, size);
 124   mpn_copyi (vp, ecc->p.m, size);
 125   gn = mpn_gcdext (gp, sp, &sn, up, size, vp, size);
 126   if (gn != 1 || gp[0] != 1)
 127     return 0;
 128
 129   if (sn < 0)
 130     mpn_sub (sp, ecc->p.m, size, sp, -sn);
 131   else if (sn < size)
 132     /* Zero-pad. */
 133     mpn_zero (sp + sn, size - sn);
 134
 135   mpn_copyi (rp, sp, size);
 136   return 1;
 137 }
 138 #endif
 139
 140 struct ecc_ctx {
 141   const struct ecc_curve *ecc;
 142   mp_limb_t *rp;
 143   mp_limb_t *ap;
 144   mp_limb_t *bp;
 145   mp_limb_t *tp;
 146 };
 147
 148 static void
 149 bench_modp (void *p)
 150 {
 151   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 152   mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
 153   ctx->ecc->p.mod (&ctx->ecc->p, ctx->rp);
 154 }
 155
 156 static void
 157 bench_reduce (void *p)
 158 {
 159   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 160   mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
 161   ctx->ecc->p.reduce (&ctx->ecc->p, ctx->rp);
 162 }
 163
 164 static void
 165 bench_modq (void *p)
 166 {
 167   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 168   mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
 169   ctx->ecc->q.mod(&ctx->ecc->q, ctx->rp);
 170 }
 171
 172 static void
 173 bench_modinv (void *p)
 174 {
 175   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 176   ctx->ecc->p.invert (&ctx->ecc->p, ctx->rp, ctx->ap, ctx->tp);
 177 }
 178
 179 #if !NETTLE_USE_MINI_GMP
 180 static void
 181 bench_modinv_gcd (void *p)
 182 {
 183   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 184   mpn_copyi (ctx->rp + ctx->ecc->p.size, ctx->ap, ctx->ecc->p.size);
 185   modinv_gcd (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->p.size, ctx->tp);
 186 }
 187 #endif
 188
 189 #ifdef mpn_sec_powm
 190 static void
 191 bench_modinv_powm (void *p)
 192 {
 193   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 194   const struct ecc_curve *ecc = ctx->ecc;
 195   mp_size_t size = ecc->p.size;
 196
 197   mpn_sub_1 (ctx->rp + size, ecc->p.m, size, 2);
 198   mpn_sec_powm (ctx->rp, ctx->ap, size,
 199                 ctx->rp + size, ecc->p.bit_size,
 200                 ecc->p.m, size, ctx->tp);
 201 }
 202 #endif
 203
 204 static void
 205 bench_dup_jj (void *p)
 206 {
 207   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 208   ecc_dup_jj (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
 209 }
 210
 211 static void
 212 bench_add_jja (void *p)
 213 {
 214   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 215   ecc_add_jja (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 216 }
 217
 218 static void
 219 bench_add_hhh (void *p)
 220 {
 221   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 222   ctx->ecc->add_hhh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 223 }
 224
 225 static void
 226 bench_mul_g (void *p)
 227 {
 228   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 229   ctx->ecc->mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
 230 }
 231
 232 static void
 233 bench_mul_a (void *p)
 234 {
 235   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 236   ctx->ecc->mul (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 237 }
 238
 239 static void
 240 bench_dup_eh (void *p)
 241 {
 242   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 243   ecc_dup_eh (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
 244 }
 245
 246 static void
 247 bench_add_eh (void *p)
 248 {
 249   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 250   ecc_add_eh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 251 }
 252
 253 #if NETTLE_USE_MINI_GMP
 254 static void
 255 mpn_random (mp_limb_t *xp, mp_size_t n)
 256 {
 257   mp_size_t i;
 258   for (i = 0; i < n; i++)
 259     xp[i] = rand();
 260 }
 261 #endif
 262
 263 static void
 264 bench_curve (const struct ecc_curve *ecc)
 265 {
 266   struct ecc_ctx ctx;
 267   double modp, reduce, modq, modinv, modinv_gcd, modinv_powm,
 268     dup_jj, add_jja, add_hhh,
 269     mul_g, mul_a;
 270
 271   mp_limb_t mask;
 272   mp_size_t itch;
 273
 274   ctx.ecc = ecc;
 275   ctx.rp = xalloc_limbs (3*ecc->p.size);
 276   ctx.ap = xalloc_limbs (3*ecc->p.size);
 277   ctx.bp = xalloc_limbs (3*ecc->p.size);
 278   itch = ecc->mul_itch;
 279 #ifdef mpn_sec_powm
 280   {
 281     mp_size_t powm_itch
 282       = mpn_sec_powm_itch (ecc->p.size, ecc->p.bit_size, ecc->p.size);
 283     if (powm_itch > itch)
 284       itch = powm_itch;
 285   }
 286 #endif
 287   ctx.tp = xalloc_limbs (itch);
 288
 289   mpn_random (ctx.ap, 3*ecc->p.size);
 290   mpn_random (ctx.bp, 3*ecc->p.size);
 291
 292   mask = (~(mp_limb_t) 0) >> (ecc->p.size * GMP_NUMB_BITS - ecc->p.bit_size);
 293   ctx.ap[ecc->p.size - 1] &= mask;
 294   ctx.ap[2*ecc->p.size - 1] &= mask;
 295   ctx.ap[3*ecc->p.size - 1] &= mask;
 296   ctx.bp[ecc->p.size - 1] &= mask;
 297   ctx.bp[2*ecc->p.size - 1] &= mask;
 298   ctx.bp[3*ecc->p.size - 1] &= mask;
 299
 300   modp = time_function (bench_modp, &ctx);
 301   reduce = time_function (bench_reduce, &ctx);
 302
 303   modq = time_function (bench_modq, &ctx);
 304
 305   modinv = time_function (bench_modinv, &ctx);
 306 #if !NETTLE_USE_MINI_GMP
 307   modinv_gcd = time_function (bench_modinv_gcd, &ctx);
 308 #else
 309   modinv_gcd = 0;
 310 #endif
 311 #ifdef mpn_sec_powm
 312   modinv_powm = time_function (bench_modinv_powm, &ctx);
 313 #else
 314   modinv_powm = 0;
 315 #endif
 316   if (ecc->p.bit_size == 255)
 317     {
 318       /* For now, curve25519 is a special case */
 319       dup_jj = time_function (bench_dup_eh, &ctx);
 320       add_jja = time_function (bench_add_eh, &ctx);
 321     }
 322   else
 323     {
 324       dup_jj = time_function (bench_dup_jj, &ctx);
 325       add_jja = time_function (bench_add_jja, &ctx);
 326     }
 327   add_hhh = time_function (bench_add_hhh, &ctx);
 328   mul_g = time_function (bench_mul_g, &ctx);
 329   mul_a = time_function (bench_mul_a, &ctx);
 330
 331   free (ctx.rp);
 332   free (ctx.ap);
 333   free (ctx.bp);
 334   free (ctx.tp);
 335
 336   printf ("%4d %6.4f %6.4f %6.4f %6.2f %6.3f %6.2f %6.3f %6.3f %6.3f %6.1f %6.1f\n",
 337           ecc->p.bit_size, 1e6 * modp, 1e6 * reduce, 1e6 * modq,
 338           1e6 * modinv, 1e6 * modinv_gcd, 1e6 * modinv_powm,
 339           1e6 * dup_jj, 1e6 * add_jja, 1e6 * add_hhh,
 340           1e6 * mul_g, 1e6 * mul_a);
 341 }
 342
 343 const struct ecc_curve * const curves[] = {
 344   &nettle_secp_192r1,
 345   &nettle_secp_224r1,
 346   &_nettle_curve25519,
 347   &nettle_secp_256r1,
 348   &nettle_secp_384r1,
 349   &nettle_secp_521r1,
 350 };
 351
 352 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
 353
 354 int
 355 main (int argc UNUSED, char **argv UNUSED)
 356 {
 357   unsigned i;
 358
 359   time_init();
 360   printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
 361           "size", "modp", "reduce", "modq", "modinv", "mi_gcd", "mi_pow",
 362           "dup_jj", "ad_jja", "ad_hhh",
 363           "mul_g", "mul_a");
 364   for (i = 0; i < numberof (curves); i++)
 365     bench_curve (curves[i]);
 366
 367   return EXIT_SUCCESS;
 368 }