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 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 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 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 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 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 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 333 benchmark_sig_alarm(int sig) 334 { 335 benchmark_stop = 1; 336 } 337 338 static void 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 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 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 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