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