ecc-benchmark.c 7.97 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
#include "../ecc.h"
#include "../ecc-internal.h"
#include "../gmp-glue.h"

#define BENCH_INTERVAL 0.1

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;

86
      time_start();
87
88
      for (i = 0; i < ncalls; i++)
	f(arg);
89
      elapsed = time_end();
90
91
92
93
94
95
96
97
98
99
      if (elapsed > BENCH_INTERVAL)
	break;
      else if (elapsed < BENCH_INTERVAL / 10)
	ncalls *= 10;
      else
	ncalls *= 2;
    }
  return elapsed / ncalls;
}

100
#if !NETTLE_USE_MINI_GMP
101
102
103
104
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
105
  mp_size_t size = ecc->p.size;
106
107
108
109
110
111
112
  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
113
  mpn_copyi (vp, ecc->p.m, size);
114
115
116
117
118
  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
119
    mpn_sub (sp, ecc->p.m, size, sp, -sn);
120
121
122
123
124
125
126
  else if (sn < size)
    /* Zero-pad. */
    mpn_zero (sp + sn, size - sn);

  mpn_copyi (rp, sp, size);
  return 1;
}
127
#endif
128
129
130
131
132
133
134
135
136
137
138
139
140

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
141
  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
142
  ctx->ecc->p.mod (&ctx->ecc->p, ctx->rp);
143
144
145
}

static void
Niels Möller's avatar
Niels Möller committed
146
bench_reduce (void *p)
147
148
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
149
  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
150
  ctx->ecc->p.reduce (&ctx->ecc->p, ctx->rp);
151
152
153
154
155
156
}

static void
bench_modq (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
157
  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
158
  ctx->ecc->q.mod(&ctx->ecc->q, ctx->rp);
159
160
161
162
163
164
}

static void
bench_modinv (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
165
  ctx->ecc->p.invert (&ctx->ecc->p, ctx->rp, ctx->ap, ctx->tp);
166
167
}

168
#if !NETTLE_USE_MINI_GMP
169
170
171
172
static void
bench_modinv_gcd (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
Niels Möller's avatar
Niels Möller committed
173
174
  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);  
175
}
176
#endif
177

178
179
180
181
182
183
#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
184
  mp_size_t size = ecc->p.size;
185
  
186
  mpn_sub_1 (ctx->rp + size, ecc->p.m, size, 2);
187
  mpn_sec_powm (ctx->rp, ctx->ap, size,
188
189
		ctx->rp + size, ecc->p.bit_size,
		ecc->p.m, size, ctx->tp);
190
191
192
}
#endif

193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
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
208
bench_add_hhh (void *p)
209
210
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
211
  ctx->ecc->add_hhh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
212
213
214
215
216
217
}

static void
bench_mul_g (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
218
  ctx->ecc->mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
219
220
221
222
223
224
}

static void
bench_mul_a (void *p)
{
  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
225
  ctx->ecc->mul (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
226
227
}

228
229
230
231
232
233
234
235
236
237
238
239
240
241
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);
}

242
243
244
245
246
247
248
249
250
251
#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

252
253
254
255
static void
bench_curve (const struct ecc_curve *ecc)
{
  struct ecc_ctx ctx;  
Niels Möller's avatar
Niels Möller committed
256
  double modp, reduce, modq, modinv, modinv_gcd, modinv_powm,
257
    dup_jj, add_jja, add_hhh,
258
259
260
    mul_g, mul_a;

  mp_limb_t mask;
261
  mp_size_t itch;
262
263

  ctx.ecc = ecc;
Niels Möller's avatar
Niels Möller committed
264
265
266
  ctx.rp = xalloc_limbs (3*ecc->p.size);
  ctx.ap = xalloc_limbs (3*ecc->p.size);
  ctx.bp = xalloc_limbs (3*ecc->p.size);
267
  itch = ecc->mul_itch;
268
269
270
#ifdef mpn_sec_powm
  {
    mp_size_t powm_itch
271
      = mpn_sec_powm_itch (ecc->p.size, ecc->p.bit_size, ecc->p.size);
272
273
274
275
276
    if (powm_itch > itch)
      itch = powm_itch;
  }
#endif
  ctx.tp = xalloc_limbs (itch);
277

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

Niels Möller's avatar
Niels Möller committed
281
282
283
284
285
286
287
  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;
288
289

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

292
  modq = time_function (bench_modq, &ctx);
293
294

  modinv = time_function (bench_modinv, &ctx);
295
#if !NETTLE_USE_MINI_GMP
296
  modinv_gcd = time_function (bench_modinv_gcd, &ctx);
297
298
299
#else
  modinv_gcd = 0;
#endif
300
301
302
303
304
#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
305
  if (ecc->p.bit_size == 255)
306
307
308
309
310
311
312
313
314
315
    {
      /* 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);
    }
316
  add_hhh = time_function (bench_add_hhh, &ctx);
317
318
  mul_g = time_function (bench_mul_g, &ctx);
  mul_a = time_function (bench_mul_a, &ctx);
319
320
321
322
323
324

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

325
  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
326
	  ecc->p.bit_size, 1e6 * modp, 1e6 * reduce, 1e6 * modq,
327
	  1e6 * modinv, 1e6 * modinv_gcd, 1e6 * modinv_powm,
328
	  1e6 * dup_jj, 1e6 * add_jja, 1e6 * add_hhh,
329
330
331
332
	  1e6 * mul_g, 1e6 * mul_a);
}

const struct ecc_curve * const curves[] = {
333
334
  &_nettle_secp_192r1,
  &_nettle_secp_224r1,
335
  &_nettle_curve25519,
336
337
338
  &_nettle_secp_256r1,
  &_nettle_secp_384r1,
  &_nettle_secp_521r1,
339
340
341
342
343
344
345
346
347
};

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

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

348
  time_init();
349
  printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
Niels Möller's avatar
Niels Möller committed
350
	  "size", "modp", "reduce", "modq", "modinv", "mi_gcd", "mi_pow",
351
	  "dup_jj", "ad_jja", "ad_hhh",
352
353
354
355
356
357
	  "mul_g", "mul_a");
  for (i = 0; i < numberof (curves); i++)
    bench_curve (curves[i]);

  return EXIT_SUCCESS;
}