ecc-benchmark.c 8.15 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;
176
  ctx->ecc->p.invert (&ctx->ecc->p, ctx->rp, ctx->ap, ctx->tp);
177
178
}

179
#if !NETTLE_USE_MINI_GMP
180
181
182
183
static void
bench_modinv_gcd (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
184
185
  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);  
186
}
187
#endif
188

189
190
191
192
193
194
#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
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
200
		ctx->rp + size, ecc->p.bit_size,
		ecc->p.m, size, ctx->tp);
201
202
203
}
#endif

204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
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
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
226
227
228
}

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

static void
bench_mul_a (void *p)
{
  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
240
241
242
243
244
245
246
247
248
249
250
251
252
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);
}

253
254
255
256
257
258
259
260
261
262
#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

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

  mp_limb_t mask;
272
  mp_size_t itch;
273
274

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

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

Niels Möller's avatar
Niels Möller committed
292
293
294
295
296
297
298
  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;
299
300

  modp = time_function (bench_modp, &ctx);
Niels Möller's avatar
Niels Möller committed
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
309
310
#else
  modinv_gcd = 0;
#endif
311
312
313
314
315
#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
316
  if (ecc->p.bit_size == 255)
317
318
319
320
321
322
323
324
325
326
    {
      /* 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);
    }
327
  add_hhh = time_function (bench_add_hhh, &ctx);
328
329
  mul_g = time_function (bench_mul_g, &ctx);
  mul_a = time_function (bench_mul_a, &ctx);
330
331
332
333
334
335

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

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",
Niels Möller's avatar
Niels Möller committed
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
341
342
343
344
345
	  1e6 * mul_g, 1e6 * mul_a);
}

const struct ecc_curve * const curves[] = {
  &nettle_secp_192r1,
  &nettle_secp_224r1,
346
  &_nettle_curve25519,
347
348
349
350
351
352
353
354
355
356
357
358
  &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;

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

  return EXIT_SUCCESS;
}