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 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 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 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 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 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 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 393 benchmark_bn_lshift_1(BIGNUM *bn) 394 { 395 benchmark_bn_lshift(bn, 1); 396 } 397 398 static void 399 benchmark_bn_lshift_16(BIGNUM *bn) 400 { 401 benchmark_bn_lshift(bn, 16); 402 } 403 404 static void 405 benchmark_bn_lshift_32(BIGNUM *bn) 406 { 407 benchmark_bn_lshift(bn, 32); 408 } 409 410 static void 411 benchmark_bn_lshift_64(BIGNUM *bn) 412 { 413 benchmark_bn_lshift(bn, 64); 414 } 415 416 static void 417 benchmark_bn_lshift_65(BIGNUM *bn) 418 { 419 benchmark_bn_lshift(bn, 65); 420 } 421 422 static void 423 benchmark_bn_lshift_80(BIGNUM *bn) 424 { 425 benchmark_bn_lshift(bn, 80); 426 } 427 428 static void 429 benchmark_bn_lshift_127(BIGNUM *bn) 430 { 431 benchmark_bn_lshift(bn, 127); 432 } 433 434 static void 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 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 469 benchmark_bn_rshift_1(BIGNUM *bn) 470 { 471 benchmark_bn_rshift(bn, 1); 472 } 473 474 static void 475 benchmark_bn_rshift_16(BIGNUM *bn) 476 { 477 benchmark_bn_rshift(bn, 16); 478 } 479 480 static void 481 benchmark_bn_rshift_32(BIGNUM *bn) 482 { 483 benchmark_bn_rshift(bn, 32); 484 } 485 486 static void 487 benchmark_bn_rshift_64(BIGNUM *bn) 488 { 489 benchmark_bn_rshift(bn, 64); 490 } 491 492 static void 493 benchmark_bn_rshift_65(BIGNUM *bn) 494 { 495 benchmark_bn_rshift(bn, 65); 496 } 497 498 static void 499 benchmark_bn_rshift_80(BIGNUM *bn) 500 { 501 benchmark_bn_rshift(bn, 80); 502 } 503 504 static void 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 587 benchmark_sig_alarm(int sig) 588 { 589 benchmark_stop = 1; 590 } 591 592 static void 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 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 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