1 /* $OpenBSD: bn_shift.c,v 1.9 2023/03/11 14:02:26 jsing Exp $ */
2 /*
3 * Copyright (c) 2022 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/time.h>
19
20 #include <err.h>
21 #include <signal.h>
22 #include <stdio.h>
23 #include <string.h>
24 #include <time.h>
25 #include <unistd.h>
26
27 #include <openssl/bn.h>
28
29 static const char *bn_shift_want_hex = \
30 "02AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \
31 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA8";
32
33 static int
check_shift_result(BIGNUM * bn1)34 check_shift_result(BIGNUM *bn1)
35 {
36 BIGNUM *bn2 = NULL;
37 char *s = NULL;
38 int ret = 0;
39
40 if (!BN_hex2bn(&bn2, bn_shift_want_hex)) {
41 fprintf(stderr, "FAIL: BN_hex2bn() failed\n");
42 goto failure;
43 }
44 if (BN_cmp(bn1, bn2) != 0) {
45 fprintf(stderr, "FAIL: shifted result differs\n");
46 if ((s = BN_bn2hex(bn1)) == NULL) {
47 fprintf(stderr, "FAIL: BN_bn2hex()\n");
48 goto failure;
49 }
50 fprintf(stderr, "Got: %s\n", s);
51 free(s);
52 if ((s = BN_bn2hex(bn2)) == NULL) {
53 fprintf(stderr, "FAIL: BN_bn2hex()\n");
54 goto failure;
55 }
56 fprintf(stderr, "Want: %s\n", s);
57 }
58
59 ret = 1;
60
61 failure:
62 BN_free(bn2);
63 free(s);
64
65 return ret;
66 }
67
68 static int
test_bn_shift1(void)69 test_bn_shift1(void)
70 {
71 BIGNUM *bn1 = NULL, *bn2 = NULL;
72 int i;
73 int failed = 1;
74
75 if ((bn1 = BN_new()) == NULL) {
76 fprintf(stderr, "FAIL: failed to create BN\n");
77 goto failure;
78 }
79 if ((bn2 = BN_new()) == NULL) {
80 fprintf(stderr, "FAIL: failed to create BN\n");
81 goto failure;
82 }
83
84 for (i = 1; i <= 256; i++) {
85 if (!BN_set_bit(bn1, 1)) {
86 fprintf(stderr, "FAIL: failed to set bit\n");
87 goto failure;
88 }
89 if (!BN_lshift1(bn1, bn1)) {
90 fprintf(stderr, "FAIL: failed to BN_lshift1()\n");
91 goto failure;
92 }
93 if (!BN_lshift1(bn1, bn1)) {
94 fprintf(stderr, "FAIL: failed to BN_lshift1()\n");
95 goto failure;
96 }
97 if (!BN_rshift1(bn1, bn1)) {
98 fprintf(stderr, "FAIL: failed to BN_rshift1()\n");
99 goto failure;
100 }
101 if (!BN_lshift1(bn1, bn1)) {
102 fprintf(stderr, "FAIL: failed to BN_lshift1()\n");
103 goto failure;
104 }
105 }
106
107 if (!check_shift_result(bn1))
108 goto failure;
109
110 /*
111 * Shift result into a different BN.
112 */
113 if (!BN_lshift1(bn1, bn1)) {
114 fprintf(stderr, "FAIL: failed to BN_lshift1()\n");
115 goto failure;
116 }
117 if (!BN_rshift1(bn2, bn1)) {
118 fprintf(stderr, "FAIL: failed to BN_rshift1()\n");
119 goto failure;
120 }
121
122 if (!check_shift_result(bn2))
123 goto failure;
124
125 if (!BN_rshift1(bn2, bn2)) {
126 fprintf(stderr, "FAIL: failed to BN_rshift1()\n");
127 goto failure;
128 }
129 if (!BN_lshift1(bn1, bn2)) {
130 fprintf(stderr, "FAIL: failed to BN_lshift1()\n");
131 goto failure;
132 }
133
134 if (!check_shift_result(bn1))
135 goto failure;
136
137 failed = 0;
138
139 failure:
140 BN_free(bn1);
141 BN_free(bn2);
142
143 return failed;
144 }
145
146 static int
test_bn_shift(void)147 test_bn_shift(void)
148 {
149 BIGNUM *bn1 = NULL, *bn2 = NULL;
150 int i;
151 int failed = 1;
152
153 if ((bn1 = BN_new()) == NULL) {
154 fprintf(stderr, "FAIL: failed to create BN 1\n");
155 goto failure;
156 }
157 if ((bn2 = BN_new()) == NULL) {
158 fprintf(stderr, "FAIL: failed to create BN 2\n");
159 goto failure;
160 }
161
162 for (i = 1; i <= 256; i++) {
163 if (!BN_set_bit(bn1, 1)) {
164 fprintf(stderr, "FAIL: failed to set bit\n");
165 goto failure;
166 }
167 if (!BN_lshift(bn1, bn1, i + 1)) {
168 fprintf(stderr, "FAIL: failed to BN_lshift()\n");
169 goto failure;
170 }
171 if (!BN_rshift(bn1, bn1, i - 1)) {
172 fprintf(stderr, "FAIL: failed to BN_rshift()\n");
173 goto failure;
174 }
175 }
176
177 if (!check_shift_result(bn1))
178 goto failure;
179
180 for (i = 0; i <= 256; i++) {
181 if (!BN_lshift(bn1, bn1, i)) {
182 fprintf(stderr, "FAIL: failed to BN_lshift()\n");
183 goto failure;
184 }
185 if (i > 1) {
186 if (!BN_set_bit(bn1, 1)) {
187 fprintf(stderr, "FAIL: failed to set bit\n");
188 goto failure;
189 }
190 }
191 }
192
193 if (BN_num_bytes(bn1) != 4177) {
194 fprintf(stderr, "FAIL: BN has %d bytes, want 4177\n",
195 BN_num_bytes(bn1));
196 goto failure;
197 }
198
199 for (i = 0; i <= 256; i++) {
200 if (!BN_rshift(bn1, bn1, i)) {
201 fprintf(stderr, "FAIL: failed to BN_rshift()\n");
202 goto failure;
203 }
204 }
205
206 if (!check_shift_result(bn1))
207 goto failure;
208
209 /*
210 * Shift result into a different BN.
211 */
212 if (!BN_lshift(bn1, bn1, BN_BITS2 + 1)) {
213 fprintf(stderr, "FAIL: failed to BN_lshift()\n");
214 goto failure;
215 }
216 if (!BN_rshift(bn2, bn1, BN_BITS2 + 1)) {
217 fprintf(stderr, "FAIL: failed to BN_rshift()\n");
218 goto failure;
219 }
220
221 if (!check_shift_result(bn2))
222 goto failure;
223
224 if (!BN_rshift(bn2, bn2, 3)) {
225 fprintf(stderr, "FAIL: failed to BN_rshift()\n");
226 goto failure;
227 }
228 if (!BN_lshift(bn1, bn2, 3)) {
229 fprintf(stderr, "FAIL: failed to BN_lshift()\n");
230 goto failure;
231 }
232
233 if (!check_shift_result(bn1))
234 goto failure;
235
236 /*
237 * Shift of zero (equivalent to a copy).
238 */
239 BN_zero(bn2);
240 if (!BN_lshift(bn2, bn1, 0)) {
241 fprintf(stderr, "FAIL: failed to BN_lshift()\n");
242 goto failure;
243 }
244
245 if (!check_shift_result(bn2))
246 goto failure;
247
248 if (!BN_lshift(bn2, bn2, 0)) {
249 fprintf(stderr, "FAIL: failed to BN_lshift()\n");
250 goto failure;
251 }
252
253 if (!check_shift_result(bn2))
254 goto failure;
255
256 BN_zero(bn2);
257 if (!BN_rshift(bn2, bn1, 0)) {
258 fprintf(stderr, "FAIL: failed to BN_rshift()\n");
259 goto failure;
260 }
261
262 if (!check_shift_result(bn2))
263 goto failure;
264
265 if (!BN_rshift(bn2, bn2, 0)) {
266 fprintf(stderr, "FAIL: failed to BN_rshift()\n");
267 goto failure;
268 }
269
270 if (!check_shift_result(bn2))
271 goto failure;
272
273 failed = 0;
274
275 failure:
276 BN_free(bn1);
277 BN_free(bn2);
278
279 return failed;
280 }
281
282 static int
test_bn_rshift_to_zero(void)283 test_bn_rshift_to_zero(void)
284 {
285 BIGNUM *bn1 = NULL, *bn2 = NULL;
286 int failed = 1;
287
288 if (!BN_hex2bn(&bn1, "ffff")) {
289 fprintf(stderr, "FAIL: BN_hex2bn() failed\n");
290 goto failure;
291 }
292 if (!BN_lshift(bn1, bn1, BN_BITS2)) {
293 fprintf(stderr, "FAIL: BN_lshift() failed\n");
294 goto failure;
295 }
296
297 if ((bn2 = BN_new()) == NULL) {
298 fprintf(stderr, "FAIL: BN_new() failed\n");
299 goto failure;
300 }
301
302 /* Shift all words. */
303 if (!BN_rshift(bn2, bn1, BN_BITS2 * 2)) {
304 fprintf(stderr, "FAIL: BN_rshift() failed\n");
305 goto failure;
306 }
307 if (BN_is_zero(bn1)) {
308 fprintf(stderr, "FAIL: BN is zero\n");
309 goto failure;
310 }
311 if (!BN_is_zero(bn2)) {
312 fprintf(stderr, "FAIL: BN is not zero\n");
313 goto failure;
314 }
315
316 /* Shift to zero, with partial shift for top most word. */
317 if (!BN_rshift(bn2, bn1, BN_BITS2 + 16)) {
318 fprintf(stderr, "FAIL: BN_rshift() failed\n");
319 goto failure;
320 }
321 if (BN_is_zero(bn1)) {
322 fprintf(stderr, "FAIL: BN is zero\n");
323 goto failure;
324 }
325 if (!BN_is_zero(bn2)) {
326 fprintf(stderr, "FAIL: BN is not zero\n");
327 goto failure;
328 }
329
330 /* Shift to zero of negative value. */
331 if (!BN_one(bn1)) {
332 fprintf(stderr, "FAIL: BN_one() failed\n");
333 goto failure;
334 }
335 BN_set_negative(bn1, 1);
336 if (!BN_rshift(bn1, bn1, 1)) {
337 fprintf(stderr, "FAIL: BN_rshift() failed\n");
338 goto failure;
339 }
340 if (!BN_is_zero(bn1)) {
341 fprintf(stderr, "FAIL: BN is not zero\n");
342 goto failure;
343 }
344 if (BN_is_negative(bn1)) {
345 fprintf(stderr, "FAIL: BN is negative zero\n");
346 goto failure;
347 }
348
349 failed = 0;
350
351 failure:
352 BN_free(bn1);
353 BN_free(bn2);
354
355 return failed;
356 }
357
358 static void
benchmark_bn_lshift1(BIGNUM * bn)359 benchmark_bn_lshift1(BIGNUM *bn)
360 {
361 int i;
362
363 if (!BN_set_bit(bn, 8192))
364 errx(1, "BN_set_bit");
365
366 if (!BN_one(bn))
367 errx(1, "BN_one");
368
369 for (i = 0; i < 8192; i++) {
370 if (!BN_lshift1(bn, bn))
371 errx(1, "BN_lshift1");
372 }
373 }
374
375 static void
benchmark_bn_lshift(BIGNUM * bn,int n)376 benchmark_bn_lshift(BIGNUM *bn, int n)
377 {
378 int i;
379
380 if (!BN_set_bit(bn, 8192 * n))
381 errx(1, "BN_set_bit");
382
383 if (!BN_one(bn))
384 errx(1, "BN_one");
385
386 for (i = 0; i < 8192; i++) {
387 if (!BN_lshift(bn, bn, n))
388 errx(1, "BN_lshift");
389 }
390 }
391
392 static void
benchmark_bn_lshift_1(BIGNUM * bn)393 benchmark_bn_lshift_1(BIGNUM *bn)
394 {
395 benchmark_bn_lshift(bn, 1);
396 }
397
398 static void
benchmark_bn_lshift_16(BIGNUM * bn)399 benchmark_bn_lshift_16(BIGNUM *bn)
400 {
401 benchmark_bn_lshift(bn, 16);
402 }
403
404 static void
benchmark_bn_lshift_32(BIGNUM * bn)405 benchmark_bn_lshift_32(BIGNUM *bn)
406 {
407 benchmark_bn_lshift(bn, 32);
408 }
409
410 static void
benchmark_bn_lshift_64(BIGNUM * bn)411 benchmark_bn_lshift_64(BIGNUM *bn)
412 {
413 benchmark_bn_lshift(bn, 64);
414 }
415
416 static void
benchmark_bn_lshift_65(BIGNUM * bn)417 benchmark_bn_lshift_65(BIGNUM *bn)
418 {
419 benchmark_bn_lshift(bn, 65);
420 }
421
422 static void
benchmark_bn_lshift_80(BIGNUM * bn)423 benchmark_bn_lshift_80(BIGNUM *bn)
424 {
425 benchmark_bn_lshift(bn, 80);
426 }
427
428 static void
benchmark_bn_lshift_127(BIGNUM * bn)429 benchmark_bn_lshift_127(BIGNUM *bn)
430 {
431 benchmark_bn_lshift(bn, 127);
432 }
433
434 static void
benchmark_bn_rshift1(BIGNUM * bn)435 benchmark_bn_rshift1(BIGNUM *bn)
436 {
437 int i;
438
439 if (!BN_one(bn))
440 errx(1, "BN_one");
441
442 if (!BN_set_bit(bn, 8192))
443 errx(1, "BN_set_bit");
444
445 for (i = 0; i < 8192; i++) {
446 if (!BN_rshift1(bn, bn))
447 errx(1, "BN_rshift1");
448 }
449 }
450
451 static void
benchmark_bn_rshift(BIGNUM * bn,int n)452 benchmark_bn_rshift(BIGNUM *bn, int n)
453 {
454 int i;
455
456 if (!BN_one(bn))
457 errx(1, "BN_one");
458
459 if (!BN_set_bit(bn, 8192 * n))
460 errx(1, "BN_set_bit");
461
462 for (i = 0; i < 8192; i++) {
463 if (!BN_rshift(bn, bn, n))
464 errx(1, "BN_rshift");
465 }
466 }
467
468 static void
benchmark_bn_rshift_1(BIGNUM * bn)469 benchmark_bn_rshift_1(BIGNUM *bn)
470 {
471 benchmark_bn_rshift(bn, 1);
472 }
473
474 static void
benchmark_bn_rshift_16(BIGNUM * bn)475 benchmark_bn_rshift_16(BIGNUM *bn)
476 {
477 benchmark_bn_rshift(bn, 16);
478 }
479
480 static void
benchmark_bn_rshift_32(BIGNUM * bn)481 benchmark_bn_rshift_32(BIGNUM *bn)
482 {
483 benchmark_bn_rshift(bn, 32);
484 }
485
486 static void
benchmark_bn_rshift_64(BIGNUM * bn)487 benchmark_bn_rshift_64(BIGNUM *bn)
488 {
489 benchmark_bn_rshift(bn, 64);
490 }
491
492 static void
benchmark_bn_rshift_65(BIGNUM * bn)493 benchmark_bn_rshift_65(BIGNUM *bn)
494 {
495 benchmark_bn_rshift(bn, 65);
496 }
497
498 static void
benchmark_bn_rshift_80(BIGNUM * bn)499 benchmark_bn_rshift_80(BIGNUM *bn)
500 {
501 benchmark_bn_rshift(bn, 80);
502 }
503
504 static void
benchmark_bn_rshift_127(BIGNUM * bn)505 benchmark_bn_rshift_127(BIGNUM *bn)
506 {
507 benchmark_bn_rshift(bn, 127);
508 }
509
510 struct benchmark {
511 const char *desc;
512 void (*func)(BIGNUM *);
513 };
514
515 static const struct benchmark benchmarks[] = {
516 {
517 .desc = "BN_lshift1()",
518 .func = benchmark_bn_lshift1,
519 },
520 {
521 .desc = "BN_lshift(_, _, 1)",
522 .func = benchmark_bn_lshift_1,
523 },
524 {
525 .desc = "BN_lshift(_, _, 16)",
526 .func = benchmark_bn_lshift_16,
527 },
528 {
529 .desc = "BN_lshift(_, _, 32)",
530 .func = benchmark_bn_lshift_32,
531 },
532 {
533 .desc = "BN_lshift(_, _, 64)",
534 .func = benchmark_bn_lshift_64,
535 },
536 {
537 .desc = "BN_lshift(_, _, 65)",
538 .func = benchmark_bn_lshift_65,
539 },
540 {
541 .desc = "BN_lshift(_, _, 80)",
542 .func = benchmark_bn_lshift_80,
543 },
544 {
545 .desc = "BN_lshift(_, _, 127)",
546 .func = benchmark_bn_lshift_127,
547 },
548 {
549 .desc = "BN_rshift1()",
550 .func = benchmark_bn_rshift1,
551 },
552 {
553 .desc = "BN_rshift(_, _, 1)",
554 .func = benchmark_bn_rshift_1,
555 },
556 {
557 .desc = "BN_rshift(_, _, 16)",
558 .func = benchmark_bn_rshift_16,
559 },
560 {
561 .desc = "BN_rshift(_, _, 32)",
562 .func = benchmark_bn_rshift_32,
563 },
564 {
565 .desc = "BN_rshift(_, _, 64)",
566 .func = benchmark_bn_rshift_64,
567 },
568 {
569 .desc = "BN_rshift(_, _, 65)",
570 .func = benchmark_bn_rshift_65,
571 },
572 {
573 .desc = "BN_rshift(_, _, 80)",
574 .func = benchmark_bn_rshift_80,
575 },
576 {
577 .desc = "BN_rshift(_, _, 127)",
578 .func = benchmark_bn_rshift_127,
579 },
580 };
581
582 #define N_BENCHMARKS (sizeof(benchmarks) / sizeof(benchmarks[0]))
583
584 static volatile sig_atomic_t benchmark_stop;
585
586 static void
benchmark_sig_alarm(int sig)587 benchmark_sig_alarm(int sig)
588 {
589 benchmark_stop = 1;
590 }
591
592 static void
benchmark_run(const struct benchmark * bm,int seconds)593 benchmark_run(const struct benchmark *bm, int seconds)
594 {
595 struct timespec start, end, duration;
596 BIGNUM *bn;
597 int i;
598
599 signal(SIGALRM, benchmark_sig_alarm);
600
601 if ((bn = BN_new()) == NULL)
602 errx(1, "BN_new");
603
604 benchmark_stop = 0;
605 i = 0;
606 alarm(seconds);
607
608 clock_gettime(CLOCK_MONOTONIC, &start);
609
610 fprintf(stderr, "Benchmarking %s for %ds: ", bm->desc, seconds);
611 while (!benchmark_stop) {
612 bm->func(bn);
613 i++;
614 }
615 clock_gettime(CLOCK_MONOTONIC, &end);
616 timespecsub(&end, &start, &duration);
617 fprintf(stderr, "%d iterations in %f seconds\n", i,
618 duration.tv_sec + duration.tv_nsec / 1000000000.0);
619
620 BN_free(bn);
621 }
622
623 static void
benchmark_bn_shift(void)624 benchmark_bn_shift(void)
625 {
626 const struct benchmark *bm;
627 size_t i;
628
629 for (i = 0; i < N_BENCHMARKS; i++) {
630 bm = &benchmarks[i];
631 benchmark_run(bm, 5);
632 }
633 }
634
635 int
main(int argc,char ** argv)636 main(int argc, char **argv)
637 {
638 int benchmark = 0, failed = 0;
639
640 if (argc == 2 && strcmp(argv[1], "--benchmark") == 0)
641 benchmark = 1;
642
643 failed |= test_bn_shift1();
644 failed |= test_bn_shift();
645 failed |= test_bn_rshift_to_zero();
646
647 if (benchmark && !failed)
648 benchmark_bn_shift();
649
650 return failed;
651 }
652