1 /* $OpenBSD: bn_mul_div.c,v 1.7 2023/06/21 07:18:10 jsing Exp $ */
2 /*
3 * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 #include <sys/resource.h>
19 #include <sys/time.h>
20
21 #include <err.h>
22 #include <signal.h>
23 #include <stdio.h>
24 #include <string.h>
25 #include <time.h>
26 #include <unistd.h>
27
28 #include <openssl/bn.h>
29
30 static int
benchmark_bn_div_setup(BIGNUM * a,size_t a_bits,BIGNUM * b,size_t b_bits,BIGNUM * r,BIGNUM * q)31 benchmark_bn_div_setup(BIGNUM *a, size_t a_bits, BIGNUM *b, size_t b_bits,
32 BIGNUM *r, BIGNUM *q)
33 {
34 if (!BN_rand(a, a_bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
35 return 0;
36 if (!BN_rand(b, b_bits - 1, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
37 return 0;
38 if (!BN_set_bit(r, a_bits))
39 return 0;
40 if (!BN_set_bit(q, b_bits))
41 return 0;
42
43 return 1;
44 }
45
46 static void
benchmark_bn_div_run_once(BIGNUM * r,BIGNUM * q,BIGNUM * a,BIGNUM * b,BN_CTX * bn_ctx)47 benchmark_bn_div_run_once(BIGNUM *r, BIGNUM *q, BIGNUM *a, BIGNUM *b, BN_CTX *bn_ctx)
48 {
49 if (!BN_div(r, q, a, b, bn_ctx))
50 errx(1, "BN_div");
51 }
52
53 static int
benchmark_bn_mul_setup(BIGNUM * a,size_t a_bits,BIGNUM * b,size_t b_bits,BIGNUM * r,BIGNUM * q)54 benchmark_bn_mul_setup(BIGNUM *a, size_t a_bits, BIGNUM *b, size_t b_bits,
55 BIGNUM *r, BIGNUM *q)
56 {
57 if (!BN_rand(a, a_bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
58 return 0;
59 if (!BN_rand(b, b_bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
60 return 0;
61 if (!BN_set_bit(r, (a_bits + b_bits) - 1))
62 return 0;
63
64 return 1;
65 }
66
67 static void
benchmark_bn_mul_run_once(BIGNUM * r,BIGNUM * q,BIGNUM * a,BIGNUM * b,BN_CTX * bn_ctx)68 benchmark_bn_mul_run_once(BIGNUM *r, BIGNUM *q, BIGNUM *a, BIGNUM *b, BN_CTX *bn_ctx)
69 {
70 if (!BN_mul(r, a, b, bn_ctx))
71 errx(1, "BN_mul");
72 }
73
74 static int
benchmark_bn_sqr_setup(BIGNUM * a,size_t a_bits,BIGNUM * b,size_t b_bits,BIGNUM * r,BIGNUM * q)75 benchmark_bn_sqr_setup(BIGNUM *a, size_t a_bits, BIGNUM *b, size_t b_bits,
76 BIGNUM *r, BIGNUM *q)
77 {
78 if (!BN_rand(a, a_bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
79 return 0;
80 if (!BN_set_bit(r, (a_bits + a_bits) - 1))
81 return 0;
82
83 return 1;
84 }
85
86 static void
benchmark_bn_sqr_run_once(BIGNUM * r,BIGNUM * q,BIGNUM * a,BIGNUM * b,BN_CTX * bn_ctx)87 benchmark_bn_sqr_run_once(BIGNUM *r, BIGNUM *q, BIGNUM *a, BIGNUM *b, BN_CTX *bn_ctx)
88 {
89 if (!BN_sqr(r, a, bn_ctx))
90 errx(1, "BN_sqr");
91 }
92
93 struct benchmark {
94 const char *desc;
95 int (*setup)(BIGNUM *, size_t, BIGNUM *, size_t, BIGNUM *, BIGNUM *);
96 void (*run_once)(BIGNUM *, BIGNUM *, BIGNUM *, BIGNUM *, BN_CTX *);
97 size_t a_bits;
98 size_t b_bits;
99 };
100
101 struct benchmark benchmarks[] = {
102 {
103 .desc = "BN_div (64 bit / 64 bit)",
104 .setup = benchmark_bn_div_setup,
105 .run_once = benchmark_bn_div_run_once,
106 .a_bits = 64,
107 .b_bits = 64,
108 },
109 {
110 .desc = "BN_div (128 bit / 128 bit)",
111 .setup = benchmark_bn_div_setup,
112 .run_once = benchmark_bn_div_run_once,
113 .a_bits = 128,
114 .b_bits = 128,
115 },
116 {
117 .desc = "BN_div (196 bit / 196 bit)",
118 .setup = benchmark_bn_div_setup,
119 .run_once = benchmark_bn_div_run_once,
120 .a_bits = 196,
121 .b_bits = 196,
122 },
123 {
124 .desc = "BN_div (256 bit / 256 bit)",
125 .setup = benchmark_bn_div_setup,
126 .run_once = benchmark_bn_div_run_once,
127 .a_bits = 256,
128 .b_bits = 256,
129 },
130 {
131 .desc = "BN_div (320 bit / 320 bit)",
132 .setup = benchmark_bn_div_setup,
133 .run_once = benchmark_bn_div_run_once,
134 .a_bits = 320,
135 .b_bits = 320,
136 },
137 {
138 .desc = "BN_div (384 bit / 384 bit)",
139 .setup = benchmark_bn_div_setup,
140 .run_once = benchmark_bn_div_run_once,
141 .a_bits = 384,
142 .b_bits = 384,
143 },
144 {
145 .desc = "BN_div (384 bit / 128 bit)",
146 .setup = benchmark_bn_div_setup,
147 .run_once = benchmark_bn_div_run_once,
148 .a_bits = 384,
149 .b_bits = 128,
150 },
151 {
152 .desc = "BN_div (448 bit / 256 bit)",
153 .setup = benchmark_bn_div_setup,
154 .run_once = benchmark_bn_div_run_once,
155 .a_bits = 448,
156 .b_bits = 256,
157 },
158 {
159 .desc = "BN_div (512 bit / 512 bit)",
160 .setup = benchmark_bn_div_setup,
161 .run_once = benchmark_bn_div_run_once,
162 .a_bits = 512,
163 .b_bits = 512,
164 },
165 {
166 .desc = "BN_div (768 bit / 256 bit)",
167 .setup = benchmark_bn_div_setup,
168 .run_once = benchmark_bn_div_run_once,
169 .a_bits = 768,
170 .b_bits = 256,
171 },
172 {
173 .desc = "BN_div (1024 bit / 128 bit)",
174 .setup = benchmark_bn_div_setup,
175 .run_once = benchmark_bn_div_run_once,
176 .a_bits = 1024,
177 .b_bits = 128,
178 },
179 {
180 .desc = "BN_div (2048 bit / 512 bit)",
181 .setup = benchmark_bn_div_setup,
182 .run_once = benchmark_bn_div_run_once,
183 .a_bits = 2048,
184 .b_bits = 128,
185 },
186 {
187 .desc = "BN_div (3072 bit / 1024 bit)",
188 .setup = benchmark_bn_div_setup,
189 .run_once = benchmark_bn_div_run_once,
190 .a_bits = 2048,
191 .b_bits = 1024,
192 },
193 {
194 .desc = "BN_div (4288 bit / 2176 bit)",
195 .setup = benchmark_bn_div_setup,
196 .run_once = benchmark_bn_div_run_once,
197 .a_bits = 2048,
198 .b_bits = 1024,
199 },
200 {
201 .desc = "BN_div (6144 bit / 2048 bit)",
202 .setup = benchmark_bn_div_setup,
203 .run_once = benchmark_bn_div_run_once,
204 .a_bits = 2048,
205 .b_bits = 1024,
206 },
207 {
208 .desc = "BN_div (16384 bit / 8192 bit)",
209 .setup = benchmark_bn_div_setup,
210 .run_once = benchmark_bn_div_run_once,
211 .a_bits = 16384,
212 .b_bits = 8192,
213 },
214 {
215 .desc = "BN_mul (128 bit x 128 bit)",
216 .setup = benchmark_bn_mul_setup,
217 .run_once = benchmark_bn_mul_run_once,
218 .a_bits = 128,
219 .b_bits = 128,
220 },
221 {
222 .desc = "BN_mul (128 bit x 256 bit)",
223 .setup = benchmark_bn_mul_setup,
224 .run_once = benchmark_bn_mul_run_once,
225 .a_bits = 128,
226 .b_bits = 256,
227 },
228 {
229 .desc = "BN_mul (256 bit x 256 bit)",
230 .setup = benchmark_bn_mul_setup,
231 .run_once = benchmark_bn_mul_run_once,
232 .a_bits = 256,
233 .b_bits = 256,
234 },
235 {
236 .desc = "BN_mul (512 bit x 512 bit)",
237 .setup = benchmark_bn_mul_setup,
238 .run_once = benchmark_bn_mul_run_once,
239 .a_bits = 512,
240 .b_bits = 512,
241 },
242 {
243 .desc = "BN_mul (1024 bit x 1024 bit)",
244 .setup = benchmark_bn_mul_setup,
245 .run_once = benchmark_bn_mul_run_once,
246 .a_bits = 1024,
247 .b_bits = 1024,
248 },
249 {
250 .desc = "BN_mul (1024 bit x 2048 bit)",
251 .setup = benchmark_bn_mul_setup,
252 .run_once = benchmark_bn_mul_run_once,
253 .a_bits = 1024,
254 .b_bits = 2048,
255 },
256 {
257 .desc = "BN_mul (2048 bit x 2048 bit)",
258 .setup = benchmark_bn_mul_setup,
259 .run_once = benchmark_bn_mul_run_once,
260 .a_bits = 2048,
261 .b_bits = 2048,
262 },
263 {
264 .desc = "BN_mul (4096 bit x 4096 bit)",
265 .setup = benchmark_bn_mul_setup,
266 .run_once = benchmark_bn_mul_run_once,
267 .a_bits = 4096,
268 .b_bits = 4096,
269 },
270 {
271 .desc = "BN_mul (4096 bit x 8192 bit)",
272 .setup = benchmark_bn_mul_setup,
273 .run_once = benchmark_bn_mul_run_once,
274 .a_bits = 4096,
275 .b_bits = 8192,
276 },
277 {
278 .desc = "BN_mul (8192 bit x 8192 bit)",
279 .setup = benchmark_bn_mul_setup,
280 .run_once = benchmark_bn_mul_run_once,
281 .a_bits = 8192,
282 .b_bits = 8192,
283 },
284 {
285 .desc = "BN_sqr (128 bit)",
286 .setup = benchmark_bn_sqr_setup,
287 .run_once = benchmark_bn_sqr_run_once,
288 .a_bits = 128,
289 },
290 {
291 .desc = "BN_sqr (256 bit)",
292 .setup = benchmark_bn_sqr_setup,
293 .run_once = benchmark_bn_sqr_run_once,
294 .a_bits = 256,
295 },
296 {
297 .desc = "BN_sqr (512 bit)",
298 .setup = benchmark_bn_sqr_setup,
299 .run_once = benchmark_bn_sqr_run_once,
300 .a_bits = 512,
301 },
302 {
303 .desc = "BN_sqr (1024 bit)",
304 .setup = benchmark_bn_sqr_setup,
305 .run_once = benchmark_bn_sqr_run_once,
306 .a_bits = 1024,
307 },
308 {
309 .desc = "BN_sqr (2048 bit)",
310 .setup = benchmark_bn_sqr_setup,
311 .run_once = benchmark_bn_sqr_run_once,
312 .a_bits = 2048,
313 },
314 {
315 .desc = "BN_sqr (4096 bit)",
316 .setup = benchmark_bn_sqr_setup,
317 .run_once = benchmark_bn_sqr_run_once,
318 .a_bits = 4096,
319 },
320 {
321 .desc = "BN_sqr (8192 bit)",
322 .setup = benchmark_bn_sqr_setup,
323 .run_once = benchmark_bn_sqr_run_once,
324 .a_bits = 8192,
325 },
326 };
327
328 #define N_BENCHMARKS (sizeof(benchmarks) / sizeof(benchmarks[0]))
329
330 static volatile sig_atomic_t benchmark_stop;
331
332 static void
benchmark_sig_alarm(int sig)333 benchmark_sig_alarm(int sig)
334 {
335 benchmark_stop = 1;
336 }
337
338 static void
benchmark_run(const struct benchmark * bm,int seconds)339 benchmark_run(const struct benchmark *bm, int seconds)
340 {
341 struct timespec start, end, duration;
342 struct rusage rusage;
343 BIGNUM *a, *b, *r, *q;
344 BN_CTX *bn_ctx;
345 int i;
346
347 signal(SIGALRM, benchmark_sig_alarm);
348
349 if ((bn_ctx = BN_CTX_new()) == NULL)
350 errx(1, "BN_CTX_new");
351
352 BN_CTX_start(bn_ctx);
353
354 if ((a = BN_CTX_get(bn_ctx)) == NULL)
355 errx(1, "BN_CTX_get");
356 if ((b = BN_CTX_get(bn_ctx)) == NULL)
357 errx(1, "BN_CTX_get");
358 if ((r = BN_CTX_get(bn_ctx)) == NULL)
359 errx(1, "BN_CTX_get");
360 if ((q = BN_CTX_get(bn_ctx)) == NULL)
361 errx(1, "BN_CTX_get");
362
363 BN_set_flags(a, BN_FLG_CONSTTIME);
364 BN_set_flags(b, BN_FLG_CONSTTIME);
365
366 if (!bm->setup(a, bm->a_bits, b, bm->b_bits, r, q))
367 errx(1, "benchmark setup failed");
368
369 benchmark_stop = 0;
370 i = 0;
371 alarm(seconds);
372
373 if (getrusage(RUSAGE_SELF, &rusage) == -1)
374 err(1, "getrusage failed");
375 TIMEVAL_TO_TIMESPEC(&rusage.ru_utime, &start);
376
377 fprintf(stderr, "Benchmarking %s for %ds: ", bm->desc, seconds);
378 while (!benchmark_stop) {
379 bm->run_once(r, q, a, b, bn_ctx);
380 i++;
381 }
382 if (getrusage(RUSAGE_SELF, &rusage) == -1)
383 err(1, "getrusage failed");
384 TIMEVAL_TO_TIMESPEC(&rusage.ru_utime, &end);
385
386 timespecsub(&end, &start, &duration);
387 fprintf(stderr, "%d iterations in %f seconds - %llu op/s\n", i,
388 duration.tv_sec + duration.tv_nsec / 1000000000.0,
389 (uint64_t)i * 1000000000 /
390 (duration.tv_sec * 1000000000 + duration.tv_nsec));
391
392 BN_CTX_end(bn_ctx);
393 BN_CTX_free(bn_ctx);
394 }
395
396 static void
benchmark_bn_mul_sqr(void)397 benchmark_bn_mul_sqr(void)
398 {
399 const struct benchmark *bm;
400 size_t i;
401
402 for (i = 0; i < N_BENCHMARKS; i++) {
403 bm = &benchmarks[i];
404 benchmark_run(bm, 5);
405 }
406 }
407
408 static int
test_bn_sqr(void)409 test_bn_sqr(void)
410 {
411 BN_CTX *bn_ctx = NULL;
412 BIGNUM *a, *r;
413 int failed = 1;
414
415 if ((bn_ctx = BN_CTX_new()) == NULL)
416 errx(1, "BN_CTX_new");
417
418 BN_CTX_start(bn_ctx);
419
420 if ((a = BN_CTX_get(bn_ctx)) == NULL)
421 errx(1, "BN_new");
422 if ((r = BN_CTX_get(bn_ctx)) == NULL)
423 errx(1, "BN_new");
424
425 /* Square of a new BN. */
426 if (!BN_sqr(r, a, bn_ctx)) {
427 fprintf(stderr, "FAIL: BN_sqr() on new BN failed\n");
428 goto failure;
429 }
430 if (!BN_is_zero(r)) {
431 fprintf(stderr, "FAIL: BN_sqr() on new BN is not zero\n");
432 goto failure;
433 }
434
435 /* Square of BN that is explicitly set to zero. */
436 if (!BN_set_word(a, 0)) {
437 fprintf(stderr, "FAIL: BN_set_word(0) failed\n");
438 goto failure;
439 }
440 if (!BN_sqr(r, a, bn_ctx)) {
441 fprintf(stderr, "FAIL: BN_sqr(0) failed\n");
442 goto failure;
443 }
444 if (!BN_is_zero(r)) {
445 fprintf(stderr, "FAIL: BN_sqr(0) != 0\n");
446 goto failure;
447 }
448
449 /* Square of BN with value one. */
450 if (!BN_set_word(a, 1)) {
451 fprintf(stderr, "FAIL: BN_set_word(1) failed\n");
452 goto failure;
453 }
454 if (!BN_sqr(r, a, bn_ctx)) {
455 fprintf(stderr, "FAIL: BN_sqr(1) failed\n");
456 goto failure;
457 }
458 if (BN_get_word(r) != 1) {
459 fprintf(stderr, "FAIL: BN_sqr(1) != 1\n");
460 goto failure;
461 }
462
463 /* Square of BN with value two. */
464 if (!BN_set_word(a, 2)) {
465 fprintf(stderr, "FAIL: BN_set_word(2) failed\n");
466 goto failure;
467 }
468 if (!BN_sqr(r, a, bn_ctx)) {
469 fprintf(stderr, "FAIL: BN_sqr(2) failed\n");
470 goto failure;
471 }
472 if (BN_get_word(r) != 4) {
473 fprintf(stderr, "FAIL: BN_sqr(2) != 4\n");
474 goto failure;
475 }
476
477 failed = 0;
478
479 failure:
480 BN_CTX_end(bn_ctx);
481 BN_CTX_free(bn_ctx);
482
483 return failed;
484 }
485
486 int
main(int argc,char ** argv)487 main(int argc, char **argv)
488 {
489 int benchmark = 0, failed = 0;
490
491 if (argc == 2 && strcmp(argv[1], "--benchmark") == 0)
492 benchmark = 1;
493
494 failed |= test_bn_sqr();
495
496 if (benchmark && !failed)
497 benchmark_bn_mul_sqr();
498
499 return failed;
500 }
501