ecc-benchmark.c 8.35 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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
static int
modinv_gcd (const struct ecc_curve *ecc,
	    mp_limb_t *rp, mp_limb_t *ap, mp_limb_t *tp)
{
  mp_size_t size = ecc->size;
  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);
  mpn_copyi (vp, ecc->p, size);
  gn = mpn_gcdext (gp, sp, &sn, up, size, vp, size);
  if (gn != 1 || gp[0] != 1)
    return 0;
  
  if (sn < 0)
    mpn_sub (sp, ecc->p, size, sp, -sn);
  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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

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;
  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
  ctx->ecc->modp (ctx->ecc, ctx->rp);
}

static void
bench_redc (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
  ctx->ecc->redc (ctx->ecc, ctx->rp);
}

static void
bench_modq (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
  ctx->ecc->modq (ctx->ecc, ctx->rp);
}

static void
bench_modinv (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
  mpn_copyi (ctx->rp + ctx->ecc->size, ctx->ap, ctx->ecc->size);
  ecc_modp_inv (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->size, ctx->tp);
}

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

190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#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;
  mp_size_t size = ecc->size;
  
  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
220
221
222
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
bench_add_jjj (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
223
  ecc_add_jjj (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
254
255
256
257
258
259
260
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);
}

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

261
262
263
264
265
266
267
268
269
270
#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

271
272
273
274
static void
bench_curve (const struct ecc_curve *ecc)
{
  struct ecc_ctx ctx;  
275
  double modp, redc, modq, modinv, modinv_gcd, modinv_powm,
276
277
278
279
    dup_jj, add_jja, add_jjj,
    mul_g, mul_a;

  mp_limb_t mask;
280
  mp_size_t itch;
281
282
283
284
285

  ctx.ecc = ecc;
  ctx.rp = xalloc_limbs (3*ecc->size);
  ctx.ap = xalloc_limbs (3*ecc->size);
  ctx.bp = xalloc_limbs (3*ecc->size);
286
287
288
289
290
291
292
293
294
295
  itch = ECC_MUL_A_ITCH (ecc->size);
#ifdef mpn_sec_powm
  {
    mp_size_t powm_itch
      = mpn_sec_powm_itch (ecc->size, ecc->bit_size, ecc->size);
    if (powm_itch > itch)
      itch = powm_itch;
  }
#endif
  ctx.tp = xalloc_limbs (itch);
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310

  mpn_random (ctx.ap, 3*ecc->size);
  mpn_random (ctx.bp, 3*ecc->size);

  mask = (~(mp_limb_t) 0) >> (ecc->size * GMP_NUMB_BITS - ecc->bit_size);
  ctx.ap[ecc->size - 1] &= mask;
  ctx.ap[2*ecc->size - 1] &= mask;
  ctx.ap[3*ecc->size - 1] &= mask;
  ctx.bp[ecc->size - 1] &= mask;
  ctx.bp[2*ecc->size - 1] &= mask;
  ctx.bp[3*ecc->size - 1] &= mask;

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

311
  modq = time_function (bench_modq, &ctx);
312
313

  modinv = time_function (bench_modinv, &ctx);
314
#if !NETTLE_USE_MINI_GMP
315
  modinv_gcd = time_function (bench_modinv_gcd, &ctx);
316
317
318
#else
  modinv_gcd = 0;
#endif
319
320
321
322
323
#ifdef mpn_sec_powm
  modinv_powm = time_function (bench_modinv_powm, &ctx);
#else
  modinv_powm = 0;
#endif
324
325
326
327
328
329
330
331
332
333
334
335
336
  if (ecc->bit_size == 255)
    {
      /* For now, curve25519 is a special case */
      dup_jj = time_function (bench_dup_eh, &ctx);
      add_jja = time_function (bench_add_eh, &ctx);
      add_jjj = time_function (bench_add_ehh, &ctx);
    }
  else
    {
      dup_jj = time_function (bench_dup_jj, &ctx);
      add_jja = time_function (bench_add_jja, &ctx);
      add_jjj = time_function (bench_add_jjj, &ctx);
    }
337
338
  mul_g = time_function (bench_mul_g, &ctx);
  mul_a = time_function (bench_mul_a, &ctx);
339
340
341
342
343
344

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

345
  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",
346
	  ecc->bit_size, 1e6 * modp, 1e6 * redc, 1e6 * modq,
347
	  1e6 * modinv, 1e6 * modinv_gcd, 1e6 * modinv_powm,
348
349
350
351
352
353
354
	  1e6 * dup_jj, 1e6 * add_jja, 1e6 * add_jjj,
	  1e6 * mul_g, 1e6 * mul_a);
}

const struct ecc_curve * const curves[] = {
  &nettle_secp_192r1,
  &nettle_secp_224r1,
355
  &nettle_curve25519,
356
357
358
359
360
361
362
363
364
365
366
367
  &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;

368
  time_init();
369
370
  printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
	  "size", "modp", "redc", "modq", "modinv", "mi_gcd", "mi_pow",
371
372
373
374
375
376
377
	  "dup_jj", "ad_jja", "ad_jjj",
	  "mul_g", "mul_a");
  for (i = 0; i < numberof (curves); i++)
    bench_curve (curves[i]);

  return EXIT_SUCCESS;
}