ecc-benchmark.c 8.22 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->modp (&ctx->ecc->p, ctx->rp);
154
155
156
157
158
159
}

static void
bench_redc (void *p)
{
  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->redc (&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->modq (&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
177
  mpn_copyi (ctx->rp + ctx->ecc->p.size, ctx->ap, ctx->ecc->p.size);
  ecc_modp_inv (ctx->ecc, 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
199
200
201
202
203
204
  
  mpn_sub_1 (ctx->rp + size, ecc->p, size, 2);
  mpn_sec_powm (ctx->rp, ctx->ap, size,
		ctx->rp + size, ecc->bit_size,
		ecc->p, size, ctx->tp);
}
#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;  
268
  double modp, redc, 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
Niels Möller's avatar
Niels Möller committed
283
      = mpn_sec_powm_itch (ecc->p.size, ecc->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
302
303

  modp = time_function (bench_modp, &ctx);
  redc = ecc->redc ? time_function (bench_redc, &ctx) : 0;

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 * redc, 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
362
  printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
	  "size", "modp", "redc", "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;
}