Add support for primality checking

Project Wycheproof's primality_tests.json contain a set of 280 numbers
that trigger edge cases in Miller-Rabin and related checks. libcrypto's
Miller-Rabin test is known to be rather poor, hopefully we will soon see
a diff on tech that improves on this.

This extends the Go test in the usual way and also adds a perl script
that allows testing on non-Go architectures.

Deliberately not yet linked to regress since the tests are flaky with
the current BN_is_prime_ex() implementatation.

4 files changed, 218 insertions, 10 deletions

diff --git a/src/regress/lib/libcrypto/wycheproof/Makefile b/src/regress/lib/libcrypto/wycheproof/Makefile
index 0fcde086f7..2e1d16b165 100644
--- a/src/regress/lib/libcrypto/wycheproof/Makefile
+++ b/src/regress/lib/libcrypto/wycheproof/Makefile
@@ -1,17 +1,21 @@
-# $OpenBSD: Makefile,v 1.3 2019/04/24 20:25:19 bluhm Exp $
+# $OpenBSD: Makefile,v 1.4 2022/07/07 20:01:20 tb Exp $
 
-.if ! (make(clean) || make(cleandir) || make(obj))
-GO_VERSION != sh -c "(go version) 2>/dev/null || true"
-.endif
+WYCHEPROOF_TESTVECTORS = /usr/local/share/wycheproof/testvectors/
 
-.if empty(GO_VERSION)
+.if !exists(${WYCHEPROOF_TESTVECTORS})
 regress:
-        @echo package go is required for this regress
+        @echo package wycheproof-testvectors is required for this regress
+        @echo package go should be installed if available
         @echo SKIPPED
-.endif
+.else
+
+# REGRESS_TARGETS += regress-wycheproof-primes
+
+. if exists(/usr/local/bin/go)
 
-CLEANFILES+=wycheproof
-REGRESS_TARGETS=regress-wycheproof
+REGRESS_TARGETS += regress-wycheproof
+
+CLEANFILES +=   wycheproof
 
 audit: wycheproof
         ./wycheproof -v
@@ -24,4 +28,25 @@ regress-wycheproof: wycheproof
 
 .PHONY: audit
 
+. endif
+
+PROGS += wycheproof-primes
+
+LDADD =         -lcrypto
+DPADD =         ${LIBCRYPTO}
+CFLAGS =        -I${.CURDIR} -I${.OBJDIR}
+
+primality_testcases.h: wycheproof-json.pl ${WYCHEPROOF_TESTVECTORS}/primality_test.json
+        perl ${.CURDIR}/wycheproof-json.pl > $@.tmp
+        mv -f $@.tmp $@
+
+wycheproof-primes: wycheproof-primes.c primality_testcases.h
+
+regress-wycheproof-primes: primality_testcases.h wycheproof-primes
+        ./wycheproof-primes
+
+CLEANFILES +=   primality_testcases.h
+
+.endif
+
 .include <bsd.regress.mk>
diff --git a/src/regress/lib/libcrypto/wycheproof/wycheproof-json.pl b/src/regress/lib/libcrypto/wycheproof/wycheproof-json.pl
new file mode 100644
index 0000000000..01fa66f7f7
--- /dev/null
+++ b/src/regress/lib/libcrypto/wycheproof/wycheproof-json.pl
@@ -0,0 +1,71 @@
+# $OpenBSD: wycheproof-json.pl,v 1.1 2022/07/07 20:01:20 tb Exp $
+
+# Copyright (c) 2022 Joel Sing <jsing@openbsd.org>
+# Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
+# 
+# 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.
+
+use JSON::PP;
+
+$test_vector_path = "/usr/local/share/wycheproof/testvectors";
+
+open JSON, "$test_vector_path/primality_test.json" or die;
+@json = <JSON>;
+close JSON;
+
+$tv = JSON::PP::decode_json(join "\n", @json);
+$test_groups = %$tv{"testGroups"};
+
+my $wycheproof_struct = <<"EOL";
+struct wycheproof_testcase {
+        int id;
+        const char *value;
+        int acceptable;
+        int result;
+};
+
+struct wycheproof_testcase testcases[] = {
+EOL
+
+print $wycheproof_struct;
+
+foreach $test_group (@$test_groups) {
+        $test_group_type = %$test_group{"type"};
+        $test_group_tests = %$test_group{"tests"};
+
+        foreach $test_case (@$test_group_tests) {
+                %tc = %$test_case;
+
+                $tc_id = $tc{"tcId"};
+                $tc_value = $tc{"value"};
+                $tc_result = $tc{"result"};
+                $tc_flags = @{$tc{"flags"}};
+
+                my $result = $tc_result eq "valid" ? 1 : 0;
+
+                print "\t{\n";
+                print "\t\t.id = $tc_id,\n";
+                print "\t\t.value = \"$tc_value\",\n";
+                print "\t\t.result = $result,\n";
+
+                if ($tc_result eq "acceptable") {
+                        print "\t\t.acceptable = 1,\n";
+                }
+
+                print "\t},\n";
+        }
+}
+
+print "};\n\n";
+
+print "#define N_TESTS (sizeof(testcases) / sizeof(testcases[0]))\n"
diff --git a/src/regress/lib/libcrypto/wycheproof/wycheproof-primes.c b/src/regress/lib/libcrypto/wycheproof/wycheproof-primes.c
new file mode 100644
index 0000000000..669531d135
--- /dev/null
+++ b/src/regress/lib/libcrypto/wycheproof/wycheproof-primes.c
@@ -0,0 +1,63 @@
+/*      $OpenBSD: wycheproof-primes.c,v 1.1 2022/07/07 20:01:20 tb Exp $ */
+/*
+ * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
+ *
+ * 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 <err.h>
+#include <stdio.h>
+
+#include <openssl/bn.h>
+
+#include "primality_testcases.h"
+
+int
+primality_test(struct wycheproof_testcase *test)
+{
+        BIGNUM *value = NULL;
+        int ret;
+        int failed = 1;
+
+        if (!BN_hex2bn(&value, test->value))
+                errx(1, "%d: failed to set value \"%s\"", test->id, test->value);
+
+        if ((ret = BN_is_prime_ex(value, BN_prime_checks, NULL, NULL)) < 0)
+                errx(1, "%d: BN_is_prime_ex errored", test->id);
+
+        if (ret != test->result && !test->acceptable) {
+                fprintf(stderr, "%d failed, want %d, got %d\n", test->id,
+                    test->result, ret);
+                goto err;
+        }
+
+        failed = 0;
+ err:
+        BN_free(value);
+
+        return failed;
+}
+
+int
+main(void)
+{
+        size_t i;
+        int failed = 0;
+
+        for (i = 0; i < N_TESTS; i++)
+                failed |= primality_test(&testcases[i]);
+
+        printf("%s\n", failed ? "FAILED" : "SUCCESS");
+
+        return failed;
+}
diff --git a/src/regress/lib/libcrypto/wycheproof/wycheproof.go b/src/regress/lib/libcrypto/wycheproof/wycheproof.go
index bd45a733b4..a638d0fdd9 100644
--- a/src/regress/lib/libcrypto/wycheproof/wycheproof.go
+++ b/src/regress/lib/libcrypto/wycheproof/wycheproof.go
@@ -1,4 +1,4 @@
-/* $OpenBSD: wycheproof.go,v 1.126 2022/05/05 18:34:27 tb Exp $ */
+/* $OpenBSD: wycheproof.go,v 1.127 2022/07/07 20:01:20 tb Exp $ */
 /*
  * Copyright (c) 2018 Joel Sing <jsing@openbsd.org>
  * Copyright (c) 2018,2019,2022 Theo Buehler <tb@openbsd.org>
@@ -349,6 +349,19 @@ type wycheproofTestGroupKW struct {
         Tests   []*wycheproofTestKW `json:"tests"`
 }
 
+type wycheproofTestPrimality struct {
+        TCID    int      `json:"tcId"`
+        Comment string   `json:"comment"`
+        Value   string   `json:"value"`
+        Result  string   `json:"result"`
+        Flags   []string `json:"flags"`
+}
+
+type wycheproofTestGroupPrimality struct {
+        Type  string                     `json:"type"`
+        Tests []*wycheproofTestPrimality `json:"tests"`
+}
+
 type wycheproofTestRSA struct {
         TCID    int      `json:"tcId"`
         Comment string   `json:"comment"`
@@ -2223,6 +2236,35 @@ func runKWTestGroup(algorithm string, wtg *wycheproofTestGroupKW) bool {
         return success
 }
 
+func runPrimalityTest(wt *wycheproofTestPrimality) bool {
+        var bnValue *C.BIGNUM
+        value := C.CString(wt.Value)
+        if C.BN_hex2bn(&bnValue, value) == 0 {
+                log.Fatal("Failed to set bnValue")
+        }
+        C.free(unsafe.Pointer(value))
+        defer C.BN_free(bnValue)
+
+        ret := C.BN_is_prime_ex(bnValue, C.BN_prime_checks, (*C.BN_CTX)(unsafe.Pointer(nil)), (*C.BN_GENCB)(unsafe.Pointer(nil)))
+        success := wt.Result == "acceptable" || (ret == 0 && wt.Result == "invalid") || (ret == 1 && wt.Result == "valid")
+        if !success {
+                fmt.Printf("FAIL: Test case %d (%q) %v failed - got %d, want %v\n", wt.TCID, wt.Comment, wt.Flags, ret, wt.Result)
+        }
+        return success
+}
+
+func runPrimalityTestGroup(algorithm string, wtg *wycheproofTestGroupPrimality) bool {
+        fmt.Printf("Running %v test group...\n", algorithm)
+
+        success := true
+        for _, wt := range wtg.Tests {
+                if !runPrimalityTest(wt) {
+                        success = false
+                }
+        }
+        return success
+}
+
 func runRsaesOaepTest(rsa *C.RSA, sha *C.EVP_MD, mgfSha *C.EVP_MD, wt *wycheproofTestRsaes) bool {
         ct, err := hex.DecodeString(wt.CT)
         if err != nil {
@@ -2733,6 +2775,8 @@ func runTestVectors(path string, variant testVariant) bool {
                 wtg = &wycheproofTestGroupHmac{}
         case "KW":
                 wtg = &wycheproofTestGroupKW{}
+        case "PrimalityTest":
+                wtg = &wycheproofTestGroupPrimality{}
         case "RSAES-OAEP":
                 wtg = &wycheproofTestGroupRsaesOaep{}
         case "RSAES-PKCS1-v1_5":
@@ -2812,6 +2856,10 @@ func runTestVectors(path string, variant testVariant) bool {
                         if !runKWTestGroup(wtv.Algorithm, wtg.(*wycheproofTestGroupKW)) {
                                 success = false
                         }
+                case "PrimalityTest":
+                        if !runPrimalityTestGroup(wtv.Algorithm, wtg.(*wycheproofTestGroupPrimality)) {
+                                success = false
+                        }
                 case "RSAES-OAEP":
                         if !runRsaesOaepTestGroup(wtv.Algorithm, wtg.(*wycheproofTestGroupRsaesOaep)) {
                                 success = false
@@ -2875,6 +2923,7 @@ func main() {
                 {"HKDF", "hkdf_sha*_test.json", Normal},
                 {"HMAC", "hmac_sha*_test.json", Normal},
                 {"KW", "kw_test.json", Normal},
+                {"Primality test", "primality_test.json", Skip}, // XXX
                 {"RSA", "rsa_*test.json", Normal},
                 {"X25519", "x25519_test.json", Normal},
                 {"X25519 ASN", "x25519_asn_test.json", Skip},