1 /* ecc-benchmark.c
2
3 Copyright (C) 2013 Niels Möller
4
5 This file is part of GNU Nettle.
6
7 GNU Nettle is free software: you can redistribute it and/or
8 modify it under the terms of either:
9
10 * the GNU Lesser General Public License as published by the Free
11 Software Foundation; either version 3 of the License, or (at your
12 option) any later version.
13
14 or
15
16 * the GNU General Public License as published by the Free
17 Software Foundation; either version 2 of the License, or (at your
18 option) any later version.
19
20 or both in parallel, as here.
21
22 GNU Nettle is distributed in the hope that it will be useful,
23 but WITHOUT ANY WARRANTY; without even the implied warranty of
24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 General Public License for more details.
26
27 You should have received copies of the GNU General Public License and
28 the GNU Lesser General Public License along with this program. If
29 not, see http://www.gnu.org/licenses/.
30 */
31
32 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
33
34 #if HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37
38 #include <stdarg.h>
39 #include <stdio.h>
40 #include <stdlib.h>
41 #include <string.h>
42
43 #include <errno.h>
44
45 #include <time.h>
46
47 #include "timing.h"
48
49 #include "../ecc.h"
50 #include "../ecc-internal.h"
51 #include "../gmp-glue.h"
52
53 #define BENCH_INTERVAL 0.1
54
55 static void *
xalloc(size_t size)56 xalloc (size_t size)
57 {
58 void *p = malloc (size);
59 if (!p)
60 {
61 fprintf (stderr, "Virtual memory exhausted\n");
62 abort ();
63 }
64 return p;
65 }
66
67 static mp_limb_t *
xalloc_limbs(mp_size_t size)68 xalloc_limbs (mp_size_t size)
69 {
70 return xalloc (size * sizeof(mp_limb_t));
71 }
72
73 /* Returns second per function call */
74 static double
time_function(void (* f)(void * arg),void * arg)75 time_function(void (*f)(void *arg), void *arg)
76 {
77 unsigned ncalls;
78 double elapsed;
79
80 /* Warm up */
81 f(arg);
82 for (ncalls = 10 ;;)
83 {
84 unsigned i;
85
86 time_start();
87 for (i = 0; i < ncalls; i++)
88 f(arg);
89 elapsed = time_end();
90 if (elapsed > BENCH_INTERVAL)
91 break;
92 else if (elapsed < BENCH_INTERVAL / 10)
93 ncalls *= 10;
94 else
95 ncalls *= 2;
96 }
97 return elapsed / ncalls;
98 }
99
100 #if !NETTLE_USE_MINI_GMP
101 static int
modinv_gcd(const struct ecc_curve * ecc,mp_limb_t * rp,mp_limb_t * ap,mp_limb_t * tp)102 modinv_gcd (const struct ecc_curve *ecc,
103 mp_limb_t *rp, mp_limb_t *ap, mp_limb_t *tp)
104 {
105 mp_size_t size = ecc->p.size;
106 mp_limb_t *up = tp;
107 mp_limb_t *vp = tp + size+1;
108 mp_limb_t *gp = tp + 2*(size+1);
109 mp_limb_t *sp = tp + 3*(size+1);
110 mp_size_t gn, sn;
111
112 mpn_copyi (up, ap, size);
113 mpn_copyi (vp, ecc->p.m, size);
114 gn = mpn_gcdext (gp, sp, &sn, up, size, vp, size);
115 if (gn != 1 || gp[0] != 1)
116 return 0;
117
118 if (sn < 0)
119 mpn_sub (sp, ecc->p.m, size, sp, -sn);
120 else if (sn < size)
121 /* Zero-pad. */
122 mpn_zero (sp + sn, size - sn);
123
124 mpn_copyi (rp, sp, size);
125 return 1;
126 }
127 #endif
128
129 struct ecc_ctx {
130 const struct ecc_curve *ecc;
131 mp_limb_t *rp;
132 mp_limb_t *ap;
133 mp_limb_t *bp;
134 mp_limb_t *tp;
135 };
136
137 static void
bench_modp(void * p)138 bench_modp (void *p)
139 {
140 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
141 mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
142 ctx->ecc->p.mod (&ctx->ecc->p, ctx->rp, ctx->rp);
143 }
144
145 static void
bench_reduce(void * p)146 bench_reduce (void *p)
147 {
148 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
149 mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
150 ctx->ecc->p.reduce (&ctx->ecc->p, ctx->rp, ctx->rp);
151 }
152
153 static void
bench_modq(void * p)154 bench_modq (void *p)
155 {
156 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
157 mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->p.size);
158 ctx->ecc->q.mod(&ctx->ecc->q, ctx->rp, ctx->rp);
159 }
160
161 static void
bench_modinv(void * p)162 bench_modinv (void *p)
163 {
164 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 static void
bench_modinv_gcd(void * p)170 bench_modinv_gcd (void *p)
171 {
172 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
173 mpn_copyi (ctx->rp + ctx->ecc->p.size, ctx->ap, ctx->ecc->p.size);
174 modinv_gcd (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->p.size, ctx->tp);
175 }
176 #endif
177
178 #ifdef mpn_sec_powm
179 static void
bench_modinv_powm(void * p)180 bench_modinv_powm (void *p)
181 {
182 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
183 const struct ecc_curve *ecc = ctx->ecc;
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 ctx->rp + size, ecc->p.bit_size,
189 ecc->p.m, size, ctx->tp);
190 }
191 #endif
192
193 static void
bench_dup_hh(void * p)194 bench_dup_hh (void *p)
195 {
196 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
197 ctx->ecc->dup (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
198 }
199
200 static void
bench_add_hh(void * p)201 bench_add_hh (void *p)
202 {
203 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
204 ctx->ecc->add_hh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
205 }
206
207 static void
bench_add_hhh(void * p)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 static void
bench_mul_g(void * p)215 bench_mul_g (void *p)
216 {
217 struct ecc_ctx *ctx = (struct ecc_ctx *) p;
218 ctx->ecc->mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
219 }
220
221 static void
bench_mul_a(void * p)222 bench_mul_a (void *p)
223 {
224 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 #if NETTLE_USE_MINI_GMP
229 static void
mpn_random(mp_limb_t * xp,mp_size_t n)230 mpn_random (mp_limb_t *xp, mp_size_t n)
231 {
232 mp_size_t i;
233 for (i = 0; i < n; i++)
234 xp[i] = rand();
235 }
236 #endif
237
238 static void
bench_curve(const struct ecc_curve * ecc)239 bench_curve (const struct ecc_curve *ecc)
240 {
241 struct ecc_ctx ctx;
242 double modp, reduce, modq, modinv, modinv_gcd, modinv_powm,
243 dup_hh, add_hh, add_hhh,
244 mul_g, mul_a;
245
246 mp_limb_t mask;
247 mp_size_t itch;
248
249 ctx.ecc = ecc;
250 ctx.rp = xalloc_limbs (3*ecc->p.size);
251 ctx.ap = xalloc_limbs (3*ecc->p.size);
252 ctx.bp = xalloc_limbs (3*ecc->p.size);
253 itch = ecc->mul_itch;
254 #ifdef mpn_sec_powm
255 {
256 mp_size_t powm_itch
257 = mpn_sec_powm_itch (ecc->p.size, ecc->p.bit_size, ecc->p.size);
258 if (powm_itch > itch)
259 itch = powm_itch;
260 }
261 #endif
262 ctx.tp = xalloc_limbs (itch);
263
264 mpn_random (ctx.ap, 3*ecc->p.size);
265 mpn_random (ctx.bp, 3*ecc->p.size);
266
267 mask = (~(mp_limb_t) 0) >> (ecc->p.size * GMP_NUMB_BITS - ecc->p.bit_size);
268 ctx.ap[ecc->p.size - 1] &= mask;
269 ctx.ap[2*ecc->p.size - 1] &= mask;
270 ctx.ap[3*ecc->p.size - 1] &= mask;
271 ctx.bp[ecc->p.size - 1] &= mask;
272 ctx.bp[2*ecc->p.size - 1] &= mask;
273 ctx.bp[3*ecc->p.size - 1] &= mask;
274
275 modp = time_function (bench_modp, &ctx);
276 reduce = time_function (bench_reduce, &ctx);
277
278 modq = time_function (bench_modq, &ctx);
279
280 modinv = time_function (bench_modinv, &ctx);
281 #if !NETTLE_USE_MINI_GMP
282 modinv_gcd = time_function (bench_modinv_gcd, &ctx);
283 #else
284 modinv_gcd = 0;
285 #endif
286 #ifdef mpn_sec_powm
287 modinv_powm = time_function (bench_modinv_powm, &ctx);
288 #else
289 modinv_powm = 0;
290 #endif
291 dup_hh = time_function (bench_dup_hh, &ctx);
292 add_hh = time_function (bench_add_hh, &ctx);
293 add_hhh = time_function (bench_add_hhh, &ctx);
294 mul_g = time_function (bench_mul_g, &ctx);
295 mul_a = time_function (bench_mul_a, &ctx);
296
297 free (ctx.rp);
298 free (ctx.ap);
299 free (ctx.bp);
300 free (ctx.tp);
301
302 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",
303 ecc->p.bit_size, 1e6 * modp, 1e6 * reduce, 1e6 * modq,
304 1e6 * modinv, 1e6 * modinv_gcd, 1e6 * modinv_powm,
305 1e6 * dup_hh, 1e6 * add_hh, 1e6 * add_hhh,
306 1e6 * mul_g, 1e6 * mul_a);
307 }
308
309 const struct ecc_curve * const curves[] = {
310 &_nettle_secp_192r1,
311 &_nettle_secp_224r1,
312 &_nettle_curve25519,
313 &_nettle_secp_256r1,
314 &_nettle_secp_384r1,
315 &_nettle_curve448,
316 &_nettle_secp_521r1,
317 &_nettle_gost_gc256b,
318 &_nettle_gost_gc512a,
319 };
320
321 #define numberof(x) (sizeof (x) / sizeof ((x)[0]))
322
323 int
main(int argc UNUSED,char ** argv UNUSED)324 main (int argc UNUSED, char **argv UNUSED)
325 {
326 unsigned i;
327
328 time_init();
329 printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
330 "size", "modp", "reduce", "modq", "modinv", "mi_gcd", "mi_pow",
331 "dup_hh", "add_hh", "ad_hhh",
332 "mul_g", "mul_a");
333 for (i = 0; i < numberof (curves); i++)
334 bench_curve (curves[i]);
335
336 return EXIT_SUCCESS;
337 }
338