Dual 1024-bit exponentiation optimization for Intel IceLake CPU

with AVX512_IFMA + AVX512_VL instructions, primarily for RSA CRT private key
operations. It uses 256-bit registers to avoid CPU frequency scaling issues.
The performance speedup for RSA2k signature on ICL is ~2x.

Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/13750)

2 files changed, 71 insertions, 0 deletions

diff --git a/doc/build.info b/doc/build.info
index 0a13f26927..95627bed4d 100644
--- a/doc/build.info
+++ b/doc/build.info
@@ -698,6 +698,10 @@ DEPEND[html/man3/BN_generate_prime.html]=man3/BN_generate_prime.pod
 GENERATE[html/man3/BN_generate_prime.html]=man3/BN_generate_prime.pod
 DEPEND[man/man3/BN_generate_prime.3]=man3/BN_generate_prime.pod
 GENERATE[man/man3/BN_generate_prime.3]=man3/BN_generate_prime.pod
+DEPEND[html/man3/BN_mod_exp_mont.html]=man3/BN_mod_exp_mont.pod
+GENERATE[html/man3/BN_mod_exp_mont.html]=man3/BN_mod_exp_mont.pod
+DEPEND[man/man3/BN_mod_exp_mont.3]=man3/BN_mod_exp_mont.pod
+GENERATE[man/man3/BN_mod_exp_mont.3]=man3/BN_mod_exp_mont.pod
 DEPEND[html/man3/BN_mod_inverse.html]=man3/BN_mod_inverse.pod
 GENERATE[html/man3/BN_mod_inverse.html]=man3/BN_mod_inverse.pod
 DEPEND[man/man3/BN_mod_inverse.3]=man3/BN_mod_inverse.pod
@@ -2808,6 +2812,7 @@ html/man3/BN_bn2bin.html \
 html/man3/BN_cmp.html \
 html/man3/BN_copy.html \
 html/man3/BN_generate_prime.html \
+html/man3/BN_mod_exp_mont.html \
 html/man3/BN_mod_inverse.html \
 html/man3/BN_mod_mul_montgomery.html \
 html/man3/BN_mod_mul_reciprocal.html \
@@ -3379,6 +3384,7 @@ man/man3/BN_bn2bin.3 \
 man/man3/BN_cmp.3 \
 man/man3/BN_copy.3 \
 man/man3/BN_generate_prime.3 \
+man/man3/BN_mod_exp_mont.3 \
 man/man3/BN_mod_inverse.3 \
 man/man3/BN_mod_mul_montgomery.3 \
 man/man3/BN_mod_mul_reciprocal.3 \
diff --git a/doc/man3/BN_mod_exp_mont.pod b/doc/man3/BN_mod_exp_mont.pod
new file mode 100644
index 0000000000..3c76e5bcbc
--- /dev/null
+++ b/doc/man3/BN_mod_exp_mont.pod
@@ -0,0 +1,65 @@
+=pod
+
+=head1 NAME
+
+BN_mod_exp_mont, BN_mod_exp_mont_consttime, BN_mod_exp_mont_consttime_x2 -
+Montgomery exponentiation
+
+=head1 SYNOPSIS
+
+ #include <openssl/bn.h>
+
+ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont);
+
+ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+                               const BIGNUM *m, BN_CTX *ctx,
+                               BN_MONT_CTX *in_mont);
+
+ int BN_mod_exp_mont_consttime_x2(BIGNUM *rr1, const BIGNUM *a1,
+                                  const BIGNUM *p1, const BIGNUM *m1,
+                                  BN_MONT_CTX *in_mont1, BIGNUM *rr2,
+                                  const BIGNUM *a2, const BIGNUM *p2,
+                                  const BIGNUM *m2, BN_MONT_CTX *in_mont2,
+                                  BN_CTX *ctx);
+
+=head1 DESCRIPTION
+
+BN_mod_exp_mont() computes I<a> to the I<p>-th power modulo I<m> (C<rr=a^p % m>)
+using Montgomery multiplication. I<in_mont> is a Montgomery context and can be
+NULL. In the case I<in_mont> is NULL, it will be initialized within the
+function, so you can save time on initialization if you provide it in advance.
+
+BN_mod_exp_mont_consttime() computes I<a> to the I<p>-th power modulo I<m>
+(C<rr=a^p % m>) using Montgomery multiplication. It is a variant of
+L<BN_mod_exp_mont(3)> that uses fixed windows and the special precomputation
+memory layout to limit data-dependency to a minimum to protect secret exponents.
+It is called automatically when L<BN_mod_exp_mont(3)> is called with parameters
+I<a>, I<p>, I<m>, any of which have B<BN_FLG_CONSTTIME> flag.
+
+BN_mod_exp_mont_consttime_x2() computes two independent exponentiations I<a1> to
+the I<p1>-th power modulo I<m1> (C<rr1=a1^p1 % m1>) and I<a2> to the I<p2>-th
+power modulo I<m2> (C<rr2=a2^p2 % m2>) using Montgomery multiplication. For some
+fixed and equal modulus sizes I<m1> and I<m2> it uses optimizations that allow
+to speedup two exponentiations. In all other cases the function reduces to two
+calls of L<BN_mod_exp_mont_consttime(3)>.
+
+=head1 RETURN VALUES
+
+For all functions 1 is returned for success, 0 on error.
+The error codes can be obtained by L<ERR_get_error(3)>.
+
+=head1 SEE ALSO
+
+L<ERR_get_error(3)>, L<BN_mod_exp_mont(3)>
+
+=head1 COPYRIGHT
+
+Copyright 2000-2020 The OpenSSL Project Authors. All Rights Reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use
+this file except in compliance with the License.  You can obtain a copy
+in the file LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut