From 0b39bee81703b04e8a92bfb4183f0f4dd54e7445 Mon Sep 17 00:00:00 2001 From: jsing Date: Sat, 17 Dec 2022 17:18:46 +0000 Subject: [PATCH] Provide regress coverage for BN shift functions. Provide regress coverage for BN_lshift1(), BN_rshift1(), BN_lshift() and BN_rshift(), along with basic benchmarking functionality (run via 'make benchmark'). --- regress/lib/libcrypto/bn/Makefile | 6 +- regress/lib/libcrypto/bn/bn_shift.c | 538 ++++++++++++++++++++++++++++ 2 files changed, 543 insertions(+), 1 deletion(-) create mode 100644 regress/lib/libcrypto/bn/bn_shift.c diff --git a/regress/lib/libcrypto/bn/Makefile b/regress/lib/libcrypto/bn/Makefile index e95091aeb52..8a51a2ccad3 100644 --- a/regress/lib/libcrypto/bn/Makefile +++ b/regress/lib/libcrypto/bn/Makefile @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile,v 1.16 2022/12/09 09:56:41 tb Exp $ +# $OpenBSD: Makefile,v 1.17 2022/12/17 17:18:46 jsing Exp $ PROGS += bn_add_sub PROGS += bn_cmp @@ -10,6 +10,7 @@ PROGS += bn_mod_sqrt PROGS += bn_mont PROGS += bn_primes PROGS += bn_rand_interval +PROGS += bn_shift PROGS += bn_test PROGS += bn_to_string PROGS += bn_unit @@ -63,4 +64,7 @@ CLEANFILES += bn_test.out bc.out LDADD_$p += ${CRYPTO_INT} .endfor +benchmark: bn_shift + ./bn_shift --benchmark + .include diff --git a/regress/lib/libcrypto/bn/bn_shift.c b/regress/lib/libcrypto/bn/bn_shift.c new file mode 100644 index 00000000000..c8f9d3ad1cd --- /dev/null +++ b/regress/lib/libcrypto/bn/bn_shift.c @@ -0,0 +1,538 @@ +/* $OpenBSD: bn_shift.c,v 1.1 2022/12/17 17:18:46 jsing Exp $ */ +/* + * Copyright (c) 2022 Joel Sing + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include +#include +#include +#include +#include +#include + +#include + +static const char *bn_shift_want_hex = \ + "02AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \ + "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA8"; + +static int +check_shift_result(BIGNUM *bn1) +{ + BIGNUM *bn2 = NULL; + char *s = NULL; + int ret = 0; + + if (!BN_hex2bn(&bn2, bn_shift_want_hex)) { + fprintf(stderr, "FAIL: BN_hex2bn() failed\n"); + goto failure; + } + if (BN_cmp(bn1, bn2) != 0) { + fprintf(stderr, "FAIL: shifted result differs\n"); + if ((s = BN_bn2hex(bn1)) == NULL) { + fprintf(stderr, "FAIL: BN_bn2hex()\n"); + goto failure; + } + fprintf(stderr, "Got: %s\n", s); + free(s); + if ((s = BN_bn2hex(bn2)) == NULL) { + fprintf(stderr, "FAIL: BN_bn2hex()\n"); + goto failure; + } + fprintf(stderr, "Want: %s\n", s); + } + + ret = 1; + + failure: + BN_free(bn2); + free(s); + + return ret; +} + +static int +test_bn_shift1(void) +{ + BIGNUM *bn1 = NULL, *bn2 = NULL; + int i; + int failed = 1; + + if ((bn1 = BN_new()) == NULL) { + fprintf(stderr, "FAIL: failed to create BN\n"); + goto failure; + } + if ((bn2 = BN_new()) == NULL) { + fprintf(stderr, "FAIL: failed to create BN\n"); + goto failure; + } + + for (i = 1; i <= 256; i++) { + if (!BN_set_bit(bn1, 1)) { + fprintf(stderr, "FAIL: failed to set bit\n"); + goto failure; + } + if (!BN_lshift1(bn1, bn1)) { + fprintf(stderr, "FAIL: failed to BN_lshift1()\n"); + goto failure; + } + if (!BN_lshift1(bn1, bn1)) { + fprintf(stderr, "FAIL: failed to BN_lshift1()\n"); + goto failure; + } + if (!BN_rshift1(bn1, bn1)) { + fprintf(stderr, "FAIL: failed to BN_rshift1()\n"); + goto failure; + } + if (!BN_lshift1(bn1, bn1)) { + fprintf(stderr, "FAIL: failed to BN_lshift1()\n"); + goto failure; + } + } + + if (!check_shift_result(bn1)) + goto failure; + + /* + * Shift result into a different BN. + */ + if (!BN_lshift1(bn1, bn1)) { + fprintf(stderr, "FAIL: failed to BN_lshift1()\n"); + goto failure; + } + if (!BN_rshift1(bn2, bn1)) { + fprintf(stderr, "FAIL: failed to BN_rshift1()\n"); + goto failure; + } + + if (!check_shift_result(bn2)) + goto failure; + + if (!BN_rshift1(bn2, bn2)) { + fprintf(stderr, "FAIL: failed to BN_rshift1()\n"); + goto failure; + } + if (!BN_lshift1(bn1, bn2)) { + fprintf(stderr, "FAIL: failed to BN_lshift1()\n"); + goto failure; + } + + if (!check_shift_result(bn1)) + goto failure; + + failed = 0; + + failure: + BN_free(bn1); + BN_free(bn2); + + return failed; +} + +static int +test_bn_shift(void) +{ + BIGNUM *bn1 = NULL, *bn2 = NULL; + int i; + int failed = 1; + + if ((bn1 = BN_new()) == NULL) { + fprintf(stderr, "FAIL: failed to create BN 1\n"); + goto failure; + } + if ((bn2 = BN_new()) == NULL) { + fprintf(stderr, "FAIL: failed to create BN 2\n"); + goto failure; + } + + for (i = 1; i <= 256; i++) { + if (!BN_set_bit(bn1, 1)) { + fprintf(stderr, "FAIL: failed to set bit\n"); + goto failure; + } + if (!BN_lshift(bn1, bn1, i + 1)) { + fprintf(stderr, "FAIL: failed to BN_lshift()\n"); + goto failure; + } + if (!BN_rshift(bn1, bn1, i - 1)) { + fprintf(stderr, "FAIL: failed to BN_rshift()\n"); + goto failure; + } + } + + if (!check_shift_result(bn1)) + goto failure; + + for (i = 0; i <= 256; i++) { + if (!BN_lshift(bn1, bn1, i)) { + fprintf(stderr, "FAIL: failed to BN_lshift()\n"); + goto failure; + } + if (i > 1) { + if (!BN_set_bit(bn1, 1)) { + fprintf(stderr, "FAIL: failed to set bit\n"); + goto failure; + } + } + } + + if (BN_num_bytes(bn1) != 4177) { + fprintf(stderr, "FAIL: BN has %d bytes, want 4177\n", + BN_num_bytes(bn1)); + goto failure; + } + + for (i = 0; i <= 256; i++) { + if (!BN_rshift(bn1, bn1, i)) { + fprintf(stderr, "FAIL: failed to BN_rshift()\n"); + goto failure; + } + } + + if (!check_shift_result(bn1)) + goto failure; + + /* + * Shift result into a different BN. + */ + if (!BN_lshift(bn1, bn1, BN_BITS2 + 1)) { + fprintf(stderr, "FAIL: failed to BN_lshift()\n"); + goto failure; + } + if (!BN_rshift(bn2, bn1, BN_BITS2 + 1)) { + fprintf(stderr, "FAIL: failed to BN_rshift()\n"); + goto failure; + } + + if (!check_shift_result(bn2)) + goto failure; + + if (!BN_rshift(bn2, bn2, 3)) { + fprintf(stderr, "FAIL: failed to BN_rshift()\n"); + goto failure; + } + if (!BN_lshift(bn1, bn2, 3)) { + fprintf(stderr, "FAIL: failed to BN_lshift()\n"); + goto failure; + } + + if (!check_shift_result(bn1)) + goto failure; + + failed = 0; + + failure: + BN_free(bn1); + BN_free(bn2); + + return failed; +} + +static int +test_bn_rshift_to_zero(void) +{ + BIGNUM *bn1 = NULL, *bn2 = NULL; + int failed = 1; + + if (!BN_hex2bn(&bn1, "ffff")) { + fprintf(stderr, "FAIL: BN_hex2bn() failed\n"); + goto failure; + } + if (!BN_lshift(bn1, bn1, BN_BITS2)) { + fprintf(stderr, "FAIL: BN_lshift() failed\n"); + goto failure; + } + + if ((bn2 = BN_new()) == NULL) { + fprintf(stderr, "FAIL: BN_new() failed\n"); + goto failure; + } + + /* Shift all words. */ + if (!BN_rshift(bn2, bn1, BN_BITS2 * 2)) { + fprintf(stderr, "FAIL: BN_rshift() failed\n"); + goto failure; + } + if (BN_is_zero(bn1)) { + fprintf(stderr, "FAIL: BN is zero\n"); + goto failure; + } + if (!BN_is_zero(bn2)) { + fprintf(stderr, "FAIL: BN is not zero\n"); + goto failure; + } + + /* Shift to zero, with partial shift for top most word. */ + if (!BN_rshift(bn2, bn1, BN_BITS2 + 16)) { + fprintf(stderr, "FAIL: BN_rshift() failed\n"); + goto failure; + } + if (BN_is_zero(bn1)) { + fprintf(stderr, "FAIL: BN is zero\n"); + goto failure; + } + if (!BN_is_zero(bn2)) { + fprintf(stderr, "FAIL: BN is not zero\n"); + goto failure; + } + + /* Shift to zero of negative value. */ + if (!BN_one(bn1)) { + fprintf(stderr, "FAIL: BN_one() failed\n"); + goto failure; + } + BN_set_negative(bn1, 1); + if (!BN_rshift(bn1, bn1, 1)) { + fprintf(stderr, "FAIL: BN_rshift() failed\n"); + goto failure; + } + if (!BN_is_zero(bn1)) { + fprintf(stderr, "FAIL: BN is not zero\n"); + goto failure; + } + + failed = 0; + + failure: + BN_free(bn1); + BN_free(bn2); + + return failed; +} + +static void +benchmark_bn_lshift1(BIGNUM *bn) +{ + int i; + + if (!BN_one(bn)) + errx(1, "BN_one"); + + for (i = 0; i < 8192; i++) { + if (!BN_lshift1(bn, bn)) + errx(1, "BN_lshift1"); + } +} + +static void +benchmark_bn_lshift(BIGNUM *bn, int n) +{ + int i; + + if (!BN_one(bn)) + errx(1, "BN_one"); + + for (i = 0; i < 8192; i++) { + if (!BN_lshift(bn, bn, n)) + errx(1, "BN_lshift"); + } +} + +static void +benchmark_bn_lshift_1(BIGNUM *bn) +{ + benchmark_bn_lshift(bn, 1); +} + +static void +benchmark_bn_lshift_32(BIGNUM *bn) +{ + benchmark_bn_lshift(bn, 32); +} + +static void +benchmark_bn_lshift_64(BIGNUM *bn) +{ + benchmark_bn_lshift(bn, 64); +} + +static void +benchmark_bn_lshift_127(BIGNUM *bn) +{ + benchmark_bn_lshift(bn, 127); +} + +static void +benchmark_bn_rshift1(BIGNUM *bn) +{ + int i; + + if (!BN_set_bit(bn, 8192)) + errx(1, "BN_set_bit"); + + for (i = 0; i < 8192; i++) { + if (!BN_rshift1(bn, bn)) + errx(1, "BN_rshift1"); + } +} + +static void +benchmark_bn_rshift(BIGNUM *bn, int n) +{ + int i; + + if (!BN_set_bit(bn, 8192 * n)) + errx(1, "BN_set_bit"); + + for (i = 0; i < 8192; i++) { + if (!BN_rshift(bn, bn, n)) + errx(1, "BN_rshift"); + } +} + +static void +benchmark_bn_rshift_1(BIGNUM *bn) +{ + benchmark_bn_rshift(bn, 1); +} + +static void +benchmark_bn_rshift_32(BIGNUM *bn) +{ + benchmark_bn_rshift(bn, 32); +} + +static void +benchmark_bn_rshift_64(BIGNUM *bn) +{ + benchmark_bn_rshift(bn, 64); +} + +static void +benchmark_bn_rshift_127(BIGNUM *bn) +{ + benchmark_bn_rshift(bn, 127); +} + +struct benchmark { + const char *desc; + void (*func)(BIGNUM *); +}; + +struct benchmark benchmarks[] = { + { + .desc = "BN_lshift1()", + .func = benchmark_bn_lshift1, + }, + { + .desc = "BN_lshift(_, _, 1)", + .func = benchmark_bn_lshift_1, + }, + { + .desc = "BN_lshift(_, _, 32)", + .func = benchmark_bn_lshift_32, + }, + { + .desc = "BN_lshift(_, _, 64)", + .func = benchmark_bn_lshift_64, + }, + { + .desc = "BN_lshift(_, _, 127)", + .func = benchmark_bn_lshift_127, + }, + { + .desc = "BN_rshift1()", + .func = benchmark_bn_rshift1, + }, + { + .desc = "BN_rshift(_, _, 1)", + .func = benchmark_bn_rshift_1, + }, + { + .desc = "BN_rshift(_, _, 32)", + .func = benchmark_bn_rshift_32, + }, + { + .desc = "BN_rshift(_, _, 64)", + .func = benchmark_bn_rshift_64, + }, + { + .desc = "BN_rshift(_, _, 127)", + .func = benchmark_bn_rshift_127, + }, +}; + +#define N_BENCHMARKS (sizeof(benchmarks) / sizeof(benchmarks[0])) + +static int benchmark_stop; + +static void +benchmark_sig_alarm(int sig) +{ + benchmark_stop = 1; +} + +static void +benchmark_run(const struct benchmark *bm, int seconds) +{ + struct timespec start, end, duration; + BIGNUM *bn; + int i; + + signal(SIGALRM, benchmark_sig_alarm); + + if ((bn = BN_new()) == NULL) + errx(1, "BN_new"); + + benchmark_stop = 0; + i = 0; + alarm(seconds); + + clock_gettime(CLOCK_MONOTONIC, &start); + + fprintf(stderr, "Benchmarking %s for %ds: ", bm->desc, seconds); + while (!benchmark_stop) { + bm->func(bn); + i++; + } + clock_gettime(CLOCK_MONOTONIC, &end); + timespecsub(&end, &start, &duration); + fprintf(stderr, "%d iterations in %f seconds\n", i, + duration.tv_sec + duration.tv_nsec / 1000000000.0); + + BN_free(bn); +} + +static void +benchmark_bn_shift(void) +{ + const struct benchmark *bm; + size_t i; + + for (i = 0; i < N_BENCHMARKS; i++) { + bm = &benchmarks[i]; + benchmark_run(bm, 5); + } +} + +int +main(int argc, char **argv) +{ + int benchmark = 0, failed = 0; + + if (argc == 2 && strcmp(argv[1], "--benchmark") == 0) + benchmark = 1; + + failed |= test_bn_shift1(); + failed |= test_bn_shift(); + failed |= test_bn_rshift_to_zero(); + + if (benchmark && !failed) + benchmark_bn_shift(); + + return failed; +} -- 2.20.1