ecc-benchmark.c 8.24 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/* ecc-benchmark.c

   Copyright (C) 2013 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/.
*/
31

32
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
33 34 35 36 37 38 39 40 41 42 43 44 45 46

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <errno.h>

#include <time.h>

47 48
#include "timing.h"

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
#include "../ecc.h"
#include "../ecc-internal.h"
#include "../gmp-glue.h"

#define BENCH_INTERVAL 0.1

static void NORETURN PRINTF_STYLE(1,2)
die(const char *format, ...)
{
  va_list args;
  va_start(args, format);
  vfprintf(stderr, format, args);
  va_end(args);

  exit(EXIT_FAILURE);
}

static void *
xalloc (size_t size)
{
  void *p = malloc (size);
  if (!p)
    {
      fprintf (stderr, "Virtual memory exhausted\n");
      abort ();
    }
  return p;
}

static mp_limb_t *
xalloc_limbs (mp_size_t size)
{
  return xalloc (size * sizeof(mp_limb_t));
}

/* Returns second per function call */
static double
time_function(void (*f)(void *arg), void *arg)
{
  unsigned ncalls;
  double elapsed;

  /* Warm up */
  f(arg);
  for (ncalls = 10 ;;)
    {
      unsigned i;

97
      time_start();
98 99
      for (i = 0; i < ncalls; i++)
	f(arg);
100
      elapsed = time_end();
101 102 103 104 105 106 107 108 109 110
      if (elapsed > BENCH_INTERVAL)
	break;
      else if (elapsed < BENCH_INTERVAL / 10)
	ncalls *= 10;
      else
	ncalls *= 2;
    }
  return elapsed / ncalls;
}

111
#if !NETTLE_USE_MINI_GMP
112 113 114 115
static int
modinv_gcd (const struct ecc_curve *ecc,
	    mp_limb_t *rp, mp_limb_t *ap, mp_limb_t *tp)
{
Niels Möller's avatar
Niels Möller committed
116
  mp_size_t size = ecc->p.size;
117 118 119 120 121 122 123
  mp_limb_t *up = tp;
  mp_limb_t *vp = tp + size+1;
  mp_limb_t *gp = tp + 2*(size+1);
  mp_limb_t *sp = tp + 3*(size+1);
  mp_size_t gn, sn;

  mpn_copyi (up, ap, size);
Niels Möller's avatar
Niels Möller committed
124
  mpn_copyi (vp, ecc->p.m, size);
125 126 127 128 129
  gn = mpn_gcdext (gp, sp, &sn, up, size, vp, size);
  if (gn != 1 || gp[0] != 1)
    return 0;
  
  if (sn < 0)
Niels Möller's avatar
Niels Möller committed
130
    mpn_sub (sp, ecc->p.m, size, sp, -sn);
131 132 133 134 135 136 137
  else if (sn < size)
    /* Zero-pad. */
    mpn_zero (sp + sn, size - sn);

  mpn_copyi (rp, sp, size);
  return 1;
}
138
#endif
139 140 141 142 143 144 145 146 147 148 149 150 151

struct ecc_ctx {
  const struct ecc_curve *ecc;
  mp_limb_t *rp;
  mp_limb_t *ap;
  mp_limb_t *bp;
  mp_limb_t *tp;
};

static void
bench_modp (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
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
Niels Möller's avatar
Niels Möller committed
157
bench_reduce (void *p)
158 159
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
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 165 166 167
}

static void
bench_modq (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
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 173 174 175
}

static void
bench_modinv (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
176
  mpn_copyi (ctx->rp + ctx->ecc->p.size, ctx->ap, ctx->ecc->p.size);
177
  ctx->ecc->p.invert (&ctx->ecc->p, ctx->rp, ctx->rp + ctx->ecc->p.size, ctx->tp);
178 179
}

180
#if !NETTLE_USE_MINI_GMP
181 182 183 184
static void
bench_modinv_gcd (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
185 186
  mpn_copyi (ctx->rp + ctx->ecc->p.size, ctx->ap, ctx->ecc->p.size);
  modinv_gcd (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->p.size, ctx->tp);  
187
}
188
#endif
189

190 191 192 193 194 195
#ifdef mpn_sec_powm
static void
bench_modinv_powm (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  const struct ecc_curve *ecc = ctx->ecc;
Niels Möller's avatar
Niels Möller committed
196
  mp_size_t size = ecc->p.size;
197
  
198
  mpn_sub_1 (ctx->rp + size, ecc->p.m, size, 2);
199
  mpn_sec_powm (ctx->rp, ctx->ap, size,
200 201
		ctx->rp + size, ecc->p.bit_size,
		ecc->p.m, size, ctx->tp);
202 203 204
}
#endif

205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
static void
bench_dup_jj (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  ecc_dup_jj (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
}

static void
bench_add_jja (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  ecc_add_jja (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
}

static void
220
bench_add_hhh (void *p)
221 222
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
223
  ctx->ecc->add_hhh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
224 225 226 227 228 229
}

static void
bench_mul_g (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
230
  ctx->ecc->mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
231 232 233 234 235 236
}

static void
bench_mul_a (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
237
  ctx->ecc->mul (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
238 239
}

240 241 242 243 244 245 246 247 248 249 250 251 252 253
static void
bench_dup_eh (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  ecc_dup_eh (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
}

static void
bench_add_eh (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  ecc_add_eh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
}

254 255 256 257 258 259 260 261 262 263
#if NETTLE_USE_MINI_GMP
static void
mpn_random (mp_limb_t *xp, mp_size_t n)
{
  mp_size_t i;
  for (i = 0; i < n; i++)
    xp[i] = rand();
}
#endif

264 265 266 267
static void
bench_curve (const struct ecc_curve *ecc)
{
  struct ecc_ctx ctx;  
Niels Möller's avatar
Niels Möller committed
268
  double modp, reduce, modq, modinv, modinv_gcd, modinv_powm,
269
    dup_jj, add_jja, add_hhh,
270 271 272
    mul_g, mul_a;

  mp_limb_t mask;
273
  mp_size_t itch;
274 275

  ctx.ecc = ecc;
Niels Möller's avatar
Niels Möller committed
276 277 278
  ctx.rp = xalloc_limbs (3*ecc->p.size);
  ctx.ap = xalloc_limbs (3*ecc->p.size);
  ctx.bp = xalloc_limbs (3*ecc->p.size);
279
  itch = ecc->mul_itch;
280 281 282
#ifdef mpn_sec_powm
  {
    mp_size_t powm_itch
283
      = mpn_sec_powm_itch (ecc->p.size, ecc->p.bit_size, ecc->p.size);
284 285 286 287 288
    if (powm_itch > itch)
      itch = powm_itch;
  }
#endif
  ctx.tp = xalloc_limbs (itch);
289

Niels Möller's avatar
Niels Möller committed
290 291
  mpn_random (ctx.ap, 3*ecc->p.size);
  mpn_random (ctx.bp, 3*ecc->p.size);
292

Niels Möller's avatar
Niels Möller committed
293 294 295 296 297 298 299
  mask = (~(mp_limb_t) 0) >> (ecc->p.size * GMP_NUMB_BITS - ecc->p.bit_size);
  ctx.ap[ecc->p.size - 1] &= mask;
  ctx.ap[2*ecc->p.size - 1] &= mask;
  ctx.ap[3*ecc->p.size - 1] &= mask;
  ctx.bp[ecc->p.size - 1] &= mask;
  ctx.bp[2*ecc->p.size - 1] &= mask;
  ctx.bp[3*ecc->p.size - 1] &= mask;
300 301

  modp = time_function (bench_modp, &ctx);
Niels Möller's avatar
Niels Möller committed
302
  reduce = time_function (bench_reduce, &ctx);
303

304
  modq = time_function (bench_modq, &ctx);
305 306

  modinv = time_function (bench_modinv, &ctx);
307
#if !NETTLE_USE_MINI_GMP
308
  modinv_gcd = time_function (bench_modinv_gcd, &ctx);
309 310 311
#else
  modinv_gcd = 0;
#endif
312 313 314 315 316
#ifdef mpn_sec_powm
  modinv_powm = time_function (bench_modinv_powm, &ctx);
#else
  modinv_powm = 0;
#endif
Niels Möller's avatar
Niels Möller committed
317
  if (ecc->p.bit_size == 255)
318 319 320 321 322 323 324 325 326 327
    {
      /* For now, curve25519 is a special case */
      dup_jj = time_function (bench_dup_eh, &ctx);
      add_jja = time_function (bench_add_eh, &ctx);
    }
  else
    {
      dup_jj = time_function (bench_dup_jj, &ctx);
      add_jja = time_function (bench_add_jja, &ctx);
    }
328
  add_hhh = time_function (bench_add_hhh, &ctx);
329 330
  mul_g = time_function (bench_mul_g, &ctx);
  mul_a = time_function (bench_mul_a, &ctx);
331 332 333 334 335 336

  free (ctx.rp);
  free (ctx.ap);
  free (ctx.bp);
  free (ctx.tp);

337
  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",
Niels Möller's avatar
Niels Möller committed
338
	  ecc->p.bit_size, 1e6 * modp, 1e6 * reduce, 1e6 * modq,
339
	  1e6 * modinv, 1e6 * modinv_gcd, 1e6 * modinv_powm,
340
	  1e6 * dup_jj, 1e6 * add_jja, 1e6 * add_hhh,
341 342 343 344 345 346
	  1e6 * mul_g, 1e6 * mul_a);
}

const struct ecc_curve * const curves[] = {
  &nettle_secp_192r1,
  &nettle_secp_224r1,
347
  &nettle_curve25519,
348 349 350 351 352 353 354 355 356 357 358 359
  &nettle_secp_256r1,
  &nettle_secp_384r1,
  &nettle_secp_521r1,
};

#define numberof(x)  (sizeof (x) / sizeof ((x)[0]))

int
main (int argc UNUSED, char **argv UNUSED)
{
  unsigned i;

360
  time_init();
361
  printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
Niels Möller's avatar
Niels Möller committed
362
	  "size", "modp", "reduce", "modq", "modinv", "mi_gcd", "mi_pow",
363
	  "dup_jj", "ad_jja", "ad_hhh",
364 365 366 367 368 369
	  "mul_g", "mul_a");
  for (i = 0; i < numberof (curves); i++)
    bench_curve (curves[i]);

  return EXIT_SUCCESS;
}