diff options
author | Andy Polyakov <appro@openssl.org> | 2013-12-03 22:05:17 +0100 |
---|---|---|
committer | Andy Polyakov <appro@openssl.org> | 2013-12-03 22:17:55 +0100 |
commit | 87d9526d0c5016358344cb520cf9a2ebdad4eaf3 (patch) | |
tree | bfad3797dc560149bac04cec012d9137442e8907 /crypto/bn | |
parent | 36982f056a921c2a0186b1af7ad3fe9a062fa4b0 (diff) |
crypto/bn/rsaz*: fix licensing note.
rsaz_exp.c: harmonize line terminating;
asm/rsaz-*.pl: minor optimizations.
asm/rsaz-x86_64.pl: sync from master.
(cherry picked from commit 31ed9a21315c571db443c68e4f618ecb51c631f9)
Diffstat (limited to 'crypto/bn')
-rwxr-xr-x | crypto/bn/asm/rsaz-avx2.pl | 215 | ||||
-rwxr-xr-x | crypto/bn/asm/rsaz-x86_64.pl | 901 | ||||
-rw-r--r-- | crypto/bn/rsaz_exp.c | 624 |
3 files changed, 1100 insertions, 640 deletions
diff --git a/crypto/bn/asm/rsaz-avx2.pl b/crypto/bn/asm/rsaz-avx2.pl index 09c45b0ec2..3eb95569fb 100755 --- a/crypto/bn/asm/rsaz-avx2.pl +++ b/crypto/bn/asm/rsaz-avx2.pl @@ -1,54 +1,66 @@ #!/usr/bin/env perl -#****************************************************************************** -#* Copyright(c) 2012, Intel Corp. -#* Developers and authors: -#* Shay Gueron (1, 2), and Vlad Krasnov (1) -#* (1) Intel Corporation, Israel Development Center, Haifa, Israel -#* (2) University of Haifa, Israel -#****************************************************************************** -#* LICENSE: -#* This submission to OpenSSL is to be made available under the OpenSSL -#* license, and only to the OpenSSL project, in order to allow integration -#* into the publicly distributed code. -#* The use of this code, or portions of this code, or concepts embedded in -#* this code, or modification of this code and/or algorithm(s) in it, or the -#* use of this code for any other purpose than stated above, requires special -#* licensing. -#****************************************************************************** -#* DISCLAIMER: -#* THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS AND THE COPYRIGHT OWNERS -#* ``AS IS''. ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED -#* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR -#* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS OR THE COPYRIGHT -#* OWNERS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, -#* OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF -#* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS -#* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN -#* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) -#* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE -#* POSSIBILITY OF SUCH DAMAGE. -#****************************************************************************** -#* Reference: -#* [1] S. Gueron, V. Krasnov: "Software Implementation of Modular -#* Exponentiation, Using Advanced Vector Instructions Architectures", -#* F. Ozbudak and F. Rodriguez-Henriquez (Eds.): WAIFI 2012, LNCS 7369, -#* pp. 119?135, 2012. Springer-Verlag Berlin Heidelberg 2012 -#* [2] S. Gueron: "Efficient Software Implementations of Modular -#* Exponentiation", Journal of Cryptographic Engineering 2:31-43 (2012). -#* [3] S. Gueron, V. Krasnov: "Speeding up Big-numbers Squaring",IEEE -#* Proceedings of 9th International Conference on Information Technology: -#* New Generations (ITNG 2012), pp.821-823 (2012) -#* [4] S. Gueron, V. Krasnov: "[PATCH] Efficient and side channel analysis -#* resistant 1024-bit modular exponentiation, for optimizing RSA2048 -#* on AVX2 capable x86_64 platforms", -#* http://rt.openssl.org/Ticket/Display.html?id=2850&user=guest&pass=guest -#****************************************************************************** - -# +10% improvement by <appro@openssl.org> +############################################################################## +# # +# Copyright (c) 2012, Intel Corporation # +# # +# All rights reserved. # +# # +# Redistribution and use in source and binary forms, with or without # +# modification, are permitted provided that the following conditions are # +# met: # +# # +# * Redistributions of source code must retain the above copyright # +# notice, this list of conditions and the following disclaimer. # +# # +# * Redistributions in binary form must reproduce the above copyright # +# notice, this list of conditions and the following disclaimer in the # +# documentation and/or other materials provided with the # +# distribution. # +# # +# * Neither the name of the Intel Corporation nor the names of its # +# contributors may be used to endorse or promote products derived from # +# this software without specific prior written permission. # +# # +# # +# THIS SOFTWARE IS PROVIDED BY INTEL CORPORATION ""AS IS"" AND ANY # +# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE # +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR # +# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL INTEL CORPORATION OR # +# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, # +# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, # +# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR # +# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF # +# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING # +# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS # +# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. # +# # +############################################################################## +# Developers and authors: # +# Shay Gueron (1, 2), and Vlad Krasnov (1) # +# (1) Intel Corporation, Israel Development Center, Haifa, Israel # +# (2) University of Haifa, Israel # +############################################################################## +# Reference: # +# [1] S. Gueron, V. Krasnov: "Software Implementation of Modular # +# Exponentiation, Using Advanced Vector Instructions Architectures", # +# F. Ozbudak and F. Rodriguez-Henriquez (Eds.): WAIFI 2012, LNCS 7369, # +# pp. 119?135, 2012. Springer-Verlag Berlin Heidelberg 2012 # +# [2] S. Gueron: "Efficient Software Implementations of Modular # +# Exponentiation", Journal of Cryptographic Engineering 2:31-43 (2012). # +# [3] S. Gueron, V. Krasnov: "Speeding up Big-numbers Squaring",IEEE # +# Proceedings of 9th International Conference on Information Technology: # +# New Generations (ITNG 2012), pp.821-823 (2012) # +# [4] S. Gueron, V. Krasnov: "[PATCH] Efficient and side channel analysis # +# resistant 1024-bit modular exponentiation, for optimizing RSA2048 # +# on AVX2 capable x86_64 platforms", # +# http://rt.openssl.org/Ticket/Display.html?id=2850&user=guest&pass=guest# +############################################################################## +# +# +13% improvement over original submission by <appro@openssl.org> # # rsa2048 sign/sec OpenSSL 1.0.1 scalar(*) this -# 2.3GHz Haswell 621 732/+18% 1112/+79% +# 2.3GHz Haswell 621 765/+23% 1113/+79% # # (*) if system doesn't support AVX2, for reference purposes; @@ -143,24 +155,24 @@ rsaz_1024_sqr_avx2: # 702 cycles, 14% faster than rsaz_1024_mul_avx2 push %r13 push %r14 push %r15 + vzeroupper ___ $code.=<<___ if ($win64); lea -0xa8(%rsp),%rsp - movaps %xmm6,-0xd8(%rax) - movaps %xmm7,-0xc8(%rax) - movaps %xmm8,-0xb8(%rax) - movaps %xmm9,-0xa8(%rax) - movaps %xmm10,-0x98(%rax) - movaps %xmm11,-0x88(%rax) - movaps %xmm12,-0x78(%rax) - movaps %xmm13,-0x68(%rax) - movaps %xmm14,-0x58(%rax) - movaps %xmm15,-0x48(%rax) + vmovaps %xmm6,-0xd8(%rax) + vmovaps %xmm7,-0xc8(%rax) + vmovaps %xmm8,-0xb8(%rax) + vmovaps %xmm9,-0xa8(%rax) + vmovaps %xmm10,-0x98(%rax) + vmovaps %xmm11,-0x88(%rax) + vmovaps %xmm12,-0x78(%rax) + vmovaps %xmm13,-0x68(%rax) + vmovaps %xmm14,-0x58(%rax) + vmovaps %xmm15,-0x48(%rax) .Lsqr_1024_body: ___ $code.=<<___; mov %rax,%rbp - vzeroall mov %rdx, $np # reassigned argument sub \$$FrameSize, %rsp mov $np, $tmp @@ -171,6 +183,7 @@ $code.=<<___; and \$4095, $tmp # see if $np crosses page add \$32*10, $tmp shr \$12, $tmp + vpxor $ACC9,$ACC9,$ACC9 jz .Lsqr_1024_no_n_copy # unaligned 256-bit load that crosses page boundary can @@ -198,7 +211,7 @@ $code.=<<___; vmovdqu $ACC6, 32*6-128($np) vmovdqu $ACC7, 32*7-128($np) vmovdqu $ACC8, 32*8-128($np) - vmovdqu $ACC9, 32*9-128($np) # $ACC9 is zero after vzeroall + vmovdqu $ACC9, 32*9-128($np) # $ACC9 is zero .Lsqr_1024_no_n_copy: and \$-1024, %rsp @@ -876,17 +889,18 @@ rsaz_1024_mul_avx2: push %r15 ___ $code.=<<___ if ($win64); + vzeroupper lea -0xa8(%rsp),%rsp - movaps %xmm6,-0xd8(%rax) - movaps %xmm7,-0xc8(%rax) - movaps %xmm8,-0xb8(%rax) - movaps %xmm9,-0xa8(%rax) - movaps %xmm10,-0x98(%rax) - movaps %xmm11,-0x88(%rax) - movaps %xmm12,-0x78(%rax) - movaps %xmm13,-0x68(%rax) - movaps %xmm14,-0x58(%rax) - movaps %xmm15,-0x48(%rax) + vmovaps %xmm6,-0xd8(%rax) + vmovaps %xmm7,-0xc8(%rax) + vmovaps %xmm8,-0xb8(%rax) + vmovaps %xmm9,-0xa8(%rax) + vmovaps %xmm10,-0x98(%rax) + vmovaps %xmm11,-0x88(%rax) + vmovaps %xmm12,-0x78(%rax) + vmovaps %xmm13,-0x68(%rax) + vmovaps %xmm14,-0x58(%rax) + vmovaps %xmm15,-0x48(%rax) .Lmul_1024_body: ___ $code.=<<___; @@ -900,6 +914,7 @@ $code.=<<___; # cross page boundary, swap it with $bp [meaning that caller # is advised to lay down $ap and $bp next to each other, so # that only one can cross page boundary]. + .byte 0x67,0x67 mov $ap, $tmp and \$4095, $tmp add \$32*10, $tmp @@ -915,6 +930,7 @@ $code.=<<___; and \$4095, $tmp # see if $np crosses page add \$32*10, $tmp + .byte 0x67,0x67 shr \$12, $tmp jz .Lmul_1024_no_n_copy @@ -960,6 +976,7 @@ $code.=<<___; vpbroadcastq ($bp), $Bi vmovdqu $ACC0, (%rsp) # clear top of stack xor $r0, $r0 + .byte 0x67 xor $r1, $r1 xor $r2, $r2 xor $r3, $r3 @@ -1564,22 +1581,22 @@ rsaz_1024_gather5_avx2: ___ $code.=<<___ if ($win64); lea -0x88(%rsp),%rax + vzeroupper .LSEH_begin_rsaz_1024_gather5: # I can't trust assembler to use specific encoding:-( .byte 0x48,0x8d,0x60,0xe0 #lea -0x20(%rax),%rsp - .byte 0x0f,0x29,0x70,0xe0 #movaps %xmm6,-0x20(%rax) - .byte 0x0f,0x29,0x78,0xf0 #movaps %xmm7,-0x10(%rax) - .byte 0x44,0x0f,0x29,0x00 #movaps %xmm8,0(%rax) - .byte 0x44,0x0f,0x29,0x48,0x10 #movaps %xmm9,0x10(%rax) - .byte 0x44,0x0f,0x29,0x50,0x20 #movaps %xmm10,0x20(%rax) - .byte 0x44,0x0f,0x29,0x58,0x30 #movaps %xmm11,0x30(%rax) - .byte 0x44,0x0f,0x29,0x60,0x40 #movaps %xmm12,0x40(%rax) - .byte 0x44,0x0f,0x29,0x68,0x50 #movaps %xmm13,0x50(%rax) - .byte 0x44,0x0f,0x29,0x70,0x60 #movaps %xmm14,0x60(%rax) - .byte 0x44,0x0f,0x29,0x78,0x70 #movaps %xmm15,0x70(%rax) + .byte 0xc5,0xf8,0x29,0x70,0xe0 #vmovaps %xmm6,-0x20(%rax) + .byte 0xc5,0xf8,0x29,0x78,0xf0 #vmovaps %xmm7,-0x10(%rax) + .byte 0xc5,0x78,0x29,0x40,0x00 #vmovaps %xmm8,0(%rax) + .byte 0xc5,0x78,0x29,0x48,0x10 #vmovaps %xmm9,0x10(%rax) + .byte 0xc5,0x78,0x29,0x50,0x20 #vmovaps %xmm10,0x20(%rax) + .byte 0xc5,0x78,0x29,0x58,0x30 #vmovaps %xmm11,0x30(%rax) + .byte 0xc5,0x78,0x29,0x60,0x40 #vmovaps %xmm12,0x40(%rax) + .byte 0xc5,0x78,0x29,0x68,0x50 #vmovaps %xmm13,0x50(%rax) + .byte 0xc5,0x78,0x29,0x70,0x60 #vmovaps %xmm14,0x60(%rax) + .byte 0xc5,0x78,0x29,0x78,0x70 #vmovaps %xmm15,0x70(%rax) ___ $code.=<<___; - vzeroupper lea .Lgather_table(%rip),%r11 mov $power,%eax and \$3,$power @@ -1596,25 +1613,25 @@ $code.=<<___; vpbroadcastb 2(%r11,%rax), %xmm14 vpbroadcastb 1(%r11,%rax), %xmm15 - lea ($inp,$power),$inp + lea 64($inp,$power),$inp mov \$64,%r11 # size optimization mov \$9,%eax jmp .Loop_gather_1024 .align 32 .Loop_gather_1024: - vpand ($inp), %xmm8,%xmm0 - vpand ($inp,%r11), %xmm9,%xmm1 - vpand ($inp,%r11,2), %xmm10,%xmm2 - vpand 64($inp,%r11,2), %xmm11,%xmm3 + vpand -64($inp), %xmm8,%xmm0 + vpand ($inp), %xmm9,%xmm1 + vpand 64($inp), %xmm10,%xmm2 + vpand ($inp,%r11,2), %xmm11,%xmm3 vpor %xmm0,%xmm1,%xmm1 - vpand ($inp,%r11,4), %xmm12,%xmm4 + vpand 64($inp,%r11,2), %xmm12,%xmm4 vpor %xmm2,%xmm3,%xmm3 - vpand 64($inp,%r11,4), %xmm13,%xmm5 + vpand ($inp,%r11,4), %xmm13,%xmm5 vpor %xmm1,%xmm3,%xmm3 - vpand -128($inp,%r11,8), %xmm14,%xmm6 + vpand 64($inp,%r11,4), %xmm14,%xmm6 vpor %xmm4,%xmm5,%xmm5 - vpand -64($inp,%r11,8), %xmm15,%xmm2 + vpand -128($inp,%r11,8), %xmm15,%xmm2 lea ($inp,%r11,8),$inp vpor %xmm3,%xmm5,%xmm5 vpor %xmm2,%xmm6,%xmm6 @@ -1798,16 +1815,16 @@ rsaz_se_handler: .rva .Lmul_1024_body,.Lmul_1024_epilogue .LSEH_info_rsaz_1024_gather5: .byte 0x01,0x33,0x16,0x00 - .byte 0x33,0xf8,0x09,0x00 #movaps 0x90(rsp),xmm15 - .byte 0x2e,0xe8,0x08,0x00 #movaps 0x80(rsp),xmm14 - .byte 0x29,0xd8,0x07,0x00 #movaps 0x70(rsp),xmm13 - .byte 0x24,0xc8,0x06,0x00 #movaps 0x60(rsp),xmm12 - .byte 0x1f,0xb8,0x05,0x00 #movaps 0x50(rsp),xmm11 - .byte 0x1a,0xa8,0x04,0x00 #movaps 0x40(rsp),xmm10 - .byte 0x15,0x98,0x03,0x00 #movaps 0x30(rsp),xmm9 - .byte 0x10,0x88,0x02,0x00 #movaps 0x20(rsp),xmm8 - .byte 0x0c,0x78,0x01,0x00 #movaps 0x10(rsp),xmm7 - .byte 0x08,0x68,0x00,0x00 #movaps 0x00(rsp),xmm6 + .byte 0x36,0xf8,0x09,0x00 #vmovaps 0x90(rsp),xmm15 + .byte 0x31,0xe8,0x08,0x00 #vmovaps 0x80(rsp),xmm14 + .byte 0x2c,0xd8,0x07,0x00 #vmovaps 0x70(rsp),xmm13 + .byte 0x27,0xc8,0x06,0x00 #vmovaps 0x60(rsp),xmm12 + .byte 0x22,0xb8,0x05,0x00 #vmovaps 0x50(rsp),xmm11 + .byte 0x1d,0xa8,0x04,0x00 #vmovaps 0x40(rsp),xmm10 + .byte 0x18,0x98,0x03,0x00 #vmovaps 0x30(rsp),xmm9 + .byte 0x13,0x88,0x02,0x00 #vmovaps 0x20(rsp),xmm8 + .byte 0x0e,0x78,0x01,0x00 #vmovaps 0x10(rsp),xmm7 + .byte 0x09,0x68,0x00,0x00 #vmovaps 0x00(rsp),xmm6 .byte 0x04,0x01,0x15,0x00 #sub rsp,0xa8 ___ } diff --git a/crypto/bn/asm/rsaz-x86_64.pl b/crypto/bn/asm/rsaz-x86_64.pl index 592f769cb0..b55421b7db 100755 --- a/crypto/bn/asm/rsaz-x86_64.pl +++ b/crypto/bn/asm/rsaz-x86_64.pl @@ -1,48 +1,60 @@ #!/usr/bin/env perl -#******************************************************************************# -#* Copyright(c) 2012, Intel Corp. *# -#* Developers and authors: *# -#* Shay Gueron (1, 2), and Vlad Krasnov (1) *# -#* (1) Intel Architecture Group, Microprocessor and Chipset Development, *# -#* Israel Development Center, Haifa, Israel *# -#* (2) University of Haifa *# -#******************************************************************************# -#* This submission to OpenSSL is to be made available under the OpenSSL *# -#* license, and only to the OpenSSL project, in order to allow integration *# -#* into the publicly distributed code. ? *# -#* The use of this code, or portions of this code, or concepts embedded in *# -#* this code, or modification of this code and/or algorithm(s) in it, or the *# -#* use of this code for any other purpose than stated above, requires special *# -#* licensing. *# -#******************************************************************************# -#******************************************************************************# -#* DISCLAIMER: *# -#* THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS AND THE COPYRIGHT OWNERS *# -#* ``AS IS''. ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *# -#* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR *# -#* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS OR THE COPYRIGHT*# -#* OWNERS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, *# -#* OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF *# -#* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS *# -#* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN *# -#* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) *# -#* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE *# -#* POSSIBILITY OF SUCH DAMAGE. *# -#******************************************************************************# -#* Reference: *# -#* [1] S. Gueron, "Efficient Software Implementations of Modular *# -#* Exponentiation", http://eprint.iacr.org/2011/239 *# -#* [2] S. Gueron, V. Krasnov. "Speeding up Big-Numbers Squaring". *# -#* IEEE Proceedings of 9th International Conference on Information *# -#* Technology: New Generations (ITNG 2012), 821-823 (2012). *# -#* [3] S. Gueron, Efficient Software Implementations of Modular Exponentiation*# -#* Journal of Cryptographic Engineering 2:31-43 (2012). *# -#* [4] S. Gueron, V. Krasnov: "[PATCH] Efficient and side channel analysis *# -#* resistant 512-bit and 1024-bit modular exponentiation for optimizing *# -#* RSA1024 and RSA2048 on x86_64 platforms", *# -#* http://rt.openssl.org/Ticket/Display.html?id=2582&user=guest&pass=guest*# -################################################################################ +############################################################################## +# # +# Copyright (c) 2012, Intel Corporation # +# # +# All rights reserved. # +# # +# Redistribution and use in source and binary forms, with or without # +# modification, are permitted provided that the following conditions are # +# met: # +# # +# * Redistributions of source code must retain the above copyright # +# notice, this list of conditions and the following disclaimer. # +# # +# * Redistributions in binary form must reproduce the above copyright # +# notice, this list of conditions and the following disclaimer in the # +# documentation and/or other materials provided with the # +# distribution. # +# # +# * Neither the name of the Intel Corporation nor the names of its # +# contributors may be used to endorse or promote products derived from # +# this software without specific prior written permission. # +# # +# # +# THIS SOFTWARE IS PROVIDED BY INTEL CORPORATION ""AS IS"" AND ANY # +# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE # +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR # +# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL INTEL CORPORATION OR # +# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, # +# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, # +# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR # +# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF # +# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING # +# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS # +# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. # +# # +############################################################################## +# Developers and authors: # +# Shay Gueron (1, 2), and Vlad Krasnov (1) # +# (1) Intel Architecture Group, Microprocessor and Chipset Development, # +# Israel Development Center, Haifa, Israel # +# (2) University of Haifa # +############################################################################## +# Reference: # +# [1] S. Gueron, "Efficient Software Implementations of Modular # +# Exponentiation", http://eprint.iacr.org/2011/239 # +# [2] S. Gueron, V. Krasnov. "Speeding up Big-Numbers Squaring". # +# IEEE Proceedings of 9th International Conference on Information # +# Technology: New Generations (ITNG 2012), 821-823 (2012). # +# [3] S. Gueron, Efficient Software Implementations of Modular Exponentiation# +# Journal of Cryptographic Engineering 2:31-43 (2012). # +# [4] S. Gueron, V. Krasnov: "[PATCH] Efficient and side channel analysis # +# resistant 512-bit and 1024-bit modular exponentiation for optimizing # +# RSA1024 and RSA2048 on x86_64 platforms", # +# http://rt.openssl.org/Ticket/Display.html?id=2582&user=guest&pass=guest# +############################################################################## # While original submission covers 512- and 1024-bit exponentiation, # this module is limited to 512-bit version only (and as such @@ -70,8 +82,7 @@ # # (*) rsax engine and fips numbers are presented for reference # purposes; -# (**) you might notice MULX code below, strangely enough gain is -# marginal, which is why code remains disabled; +# (**) MULX was attempted, but found to give only marginal improvement; $flavour = shift; $output = shift; @@ -87,6 +98,21 @@ die "can't locate x86_64-xlate.pl"; open OUT,"| $^X $xlate $flavour $output"; *STDOUT=*OUT; +if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1` + =~ /GNU assembler version ([2-9]\.[0-9]+)/) { + $addx = ($1>=2.23); +} + +if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) && + `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) { + $addx = ($1>=2.10); +} + +if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) && + `ml64 2>&1` =~ /Version ([0-9]+)\./) { + $addx = ($1>=11); +} + ($out, $inp, $mod) = ("%rdi", "%rsi", "%rbp"); # common internal API { my ($out,$inp,$mod,$n0,$times) = ("%rdi","%rsi","%rdx","%rcx","%r8d"); @@ -94,6 +120,8 @@ my ($out,$inp,$mod,$n0,$times) = ("%rdi","%rsi","%rdx","%rcx","%r8d"); $code.=<<___; .text +.extern OPENSSL_ia32cap_P + .globl rsaz_512_sqr .type rsaz_512_sqr,\@function,5 .align 32 @@ -111,14 +139,19 @@ rsaz_512_sqr: # 25-29% faster than rsaz_512_mul movq ($inp), %rdx movq 8($inp), %rax movq $n0, 128(%rsp) +___ +$code.=<<___ if ($addx); + movl \$0x80100,%r11d + andl OPENSSL_ia32cap_P+8(%rip),%r11d + cmpl \$0x80100,%r11d # check for MULX and ADO/CX + je .Loop_sqrx +___ +$code.=<<___; jmp .Loop_sqr .align 32 .Loop_sqr: movl $times,128+8(%rsp) -___ -if (1) { -$code.=<<___; #first iteration movq %rdx, %rbx mulq %rdx @@ -446,242 +479,278 @@ $code.=<<___; movq %r13, 112(%rsp) movq %r14, 120(%rsp) + + movq (%rsp), %r8 + movq 8(%rsp), %r9 + movq 16(%rsp), %r10 + movq 24(%rsp), %r11 + movq 32(%rsp), %r12 + movq 40(%rsp), %r13 + movq 48(%rsp), %r14 + movq 56(%rsp), %r15 + + call __rsaz_512_reduce + + addq 64(%rsp), %r8 + adcq 72(%rsp), %r9 + adcq 80(%rsp), %r10 + adcq 88(%rsp), %r11 + adcq 96(%rsp), %r12 + adcq 104(%rsp), %r13 + adcq 112(%rsp), %r14 + adcq 120(%rsp), %r15 + sbbq %rcx, %rcx + + call __rsaz_512_subtract + + movq %r8, %rdx + movq %r9, %rax + movl 128+8(%rsp), $times + movq $out, $inp + + decl $times + jnz .Loop_sqr ___ -} else { +if ($addx) { $code.=<<___; + jmp .Lsqr_tail + +.align 32 +.Loop_sqrx: + movl $times,128+8(%rsp) movq $out, %xmm0 # off-load + movq %rbp, %xmm1 # off-load #first iteration mulx %rax, %r8, %r9 mulx 16($inp), %rcx, %r10 + xor %rbp, %rbp # cf=0, of=0 mulx 24($inp), %rax, %r11 - add %rcx, %r9 + adcx %rcx, %r9 mulx 32($inp), %rcx, %r12 - adc %rax, %r10 + adcx %rax, %r10 mulx 40($inp), %rax, %r13 - adc %rcx, %r11 + adcx %rcx, %r11 - mulx 48($inp), %rcx, %r14 - adc %rax, %r12 + .byte 0xc4,0x62,0xf3,0xf6,0xb6,0x30,0x00,0x00,0x00 # mulx 48($inp), %rcx, %r14 + adcx %rax, %r12 + adcx %rcx, %r13 - mulx 56($inp), %rax, %r15 - adc %rcx, %r13 - mov %r9, %rcx - adc %rax, %r14 - adc \$0, %r15 + .byte 0xc4,0x62,0xfb,0xf6,0xbe,0x38,0x00,0x00,0x00 # mulx 56($inp), %rax, %r15 + adcx %rax, %r14 + adcx %rbp, %r15 # %rbp is 0 + mov %r9, %rcx shld \$1, %r8, %r9 shl \$1, %r8 + xor %ebp, %ebp mulx %rdx, %rax, %rdx - add %rdx, %r8 - adc \$0, %r9 + adcx %rdx, %r8 + mov 8($inp), %rdx + adcx %rbp, %r9 mov %rax, (%rsp) mov %r8, 8(%rsp) #second iteration - mov 8($inp), %rdx mulx 16($inp), %rax, %rbx + adox %rax, %r10 + adcx %rbx, %r11 - mulx 24($inp), $out, %r8 - add %rax, %r10 - adc %rbx, %r11 - adc \$0, %r8 + .byte 0xc4,0x62,0xc3,0xf6,0x86,0x18,0x00,0x00,0x00 # mulx 24($inp), $out, %r8 + adox $out, %r11 + adcx %r8, %r12 mulx 32($inp), %rax, %rbx - add $out, %r11 - adc %r8, %r12 - adc \$0, %rbx + adox %rax, %r12 + adcx %rbx, %r13 mulx 40($inp), $out, %r8 - add %rax, %r12 - adc %rbx, %r13 - adc \$0, %r8 + adox $out, %r13 + adcx %r8, %r14 - mulx 48($inp), %rax, %rbx - add $out, %r13 - adc %r8, %r14 - adc \$0, %rbx + .byte 0xc4,0xe2,0xfb,0xf6,0x9e,0x30,0x00,0x00,0x00 # mulx 48($inp), %rax, %rbx + adox %rax, %r14 + adcx %rbx, %r15 - mulx 56($inp), $out, %r8 - add %rax, %r14 - adc %rbx, %r15 - mov %r11, %rbx - adc \$0, %r8 - add $out, %r15 - adc \$0, %r8 + .byte 0xc4,0x62,0xc3,0xf6,0x86,0x38,0x00,0x00,0x00 # mulx 56($inp), $out, %r8 + adox $out, %r15 + adcx %rbp, %r8 + adox %rbp, %r8 + mov %r11, %rbx shld \$1, %r10, %r11 shld \$1, %rcx, %r10 + xor %ebp,%ebp mulx %rdx, %rax, %rcx - add %rax, %r9 - adc %rcx, %r10 - adc \$0, %r11 + mov 16($inp), %rdx + adcx %rax, %r9 + adcx %rcx, %r10 + adcx %rbp, %r11 mov %r9, 16(%rsp) - mov %r10, 24(%rsp) + .byte 0x4c,0x89,0x94,0x24,0x18,0x00,0x00,0x00 # mov %r10, 24(%rsp) #third iteration - mov 16($inp), %rdx - mulx 24($inp), $out, %r9 + .byte 0xc4,0x62,0xc3,0xf6,0x8e,0x18,0x00,0x00,0x00 # mulx 24($inp), $out, %r9 + adox $out, %r12 + adcx %r9, %r13 mulx 32($inp), %rax, %rcx - add $out, %r12 - adc %r9, %r13 - adc \$0, %rcx + adox %rax, %r13 + adcx %rcx, %r14 mulx 40($inp), $out, %r9 - add %rax, %r13 - adc %rcx, %r14 - adc \$0, %r9 + adox $out, %r14 + adcx %r9, %r15 - mulx 48($inp), %rax, %rcx - add $out, %r14 - adc %r9, %r15 - adc \$0, %rcx + .byte 0xc4,0xe2,0xfb,0xf6,0x8e,0x30,0x00,0x00,0x00 # mulx 48($inp), %rax, %rcx + adox %rax, %r15 + adcx %rcx, %r8 - mulx 56($inp), $out, %r9 - add %rax, %r15 - adc %rcx, %r8 - mov %r13, %rcx - adc \$0, %r9 - add $out, %r8 - adc \$0, %r9 + .byte 0xc4,0x62,0xc3,0xf6,0x8e,0x38,0x00,0x00,0x00 # mulx 56($inp), $out, %r9 + adox $out, %r8 + adcx %rbp, %r9 + adox %rbp, %r9 + mov %r13, %rcx shld \$1, %r12, %r13 shld \$1, %rbx, %r12 + xor %ebp, %ebp mulx %rdx, %rax, %rdx - add %rax, %r11 - adc %rdx, %r12 - adc \$0, %r13 + adcx %rax, %r11 + adcx %rdx, %r12 + mov 24($inp), %rdx + adcx %rbp, %r13 mov %r11, 32(%rsp) - mov %r12, 40(%rsp) + .byte 0x4c,0x89,0xa4,0x24,0x28,0x00,0x00,0x00 # mov %r12, 40(%rsp) #fourth iteration - mov 24($inp), %rdx - mulx 32($inp), %rax, %rbx + .byte 0xc4,0xe2,0xfb,0xf6,0x9e,0x20,0x00,0x00,0x00 # mulx 32($inp), %rax, %rbx + adox %rax, %r14 + adcx %rbx, %r15 mulx 40($inp), $out, %r10 - add %rax, %r14 - adc %rbx, %r15 - adc \$0, %r10 + adox $out, %r15 + adcx %r10, %r8 mulx 48($inp), %rax, %rbx - add $out, %r15 - adc %r10, %r8 - adc \$0, %rbx + adox %rax, %r8 + adcx %rbx, %r9 mulx 56($inp), $out, %r10 - add %rax, %r8 - adc \$0, %rbx - add $out, %r9 - adc \$0, %r10 - add %rbx, %r9 - mov %r15, %rbx - adc \$0, %r10 + adox $out, %r9 + adcx %rbp, %r10 + adox %rbp, %r10 + .byte 0x66 + mov %r15, %rbx shld \$1, %r14, %r15 shld \$1, %rcx, %r14 + xor %ebp, %ebp mulx %rdx, %rax, %rdx - add %rax, %r13 - adc %rdx, %r14 - adc \$0, %r15 + adcx %rax, %r13 + adcx %rdx, %r14 + mov 32($inp), %rdx + adcx %rbp, %r15 mov %r13, 48(%rsp) mov %r14, 56(%rsp) #fifth iteration - mov 32($inp), %rdx - mulx 40($inp), $out, %r11 + .byte 0xc4,0x62,0xc3,0xf6,0x9e,0x28,0x00,0x00,0x00 # mulx 40($inp), $out, %r11 + adox $out, %r8 + adcx %r11, %r9 mulx 48($inp), %rax, %rcx - add $out, %r8 - adc %r11, %r9 - adc \$0, %rcx + adox %rax, %r9 + adcx %rcx, %r10 mulx 56($inp), $out, %r11 - add %rax, %r9 - adc %rcx, %r10 - adc \$0, %r11 - add $out, %r10 - adc \$0, %r11 + adox $out, %r10 + adcx %rbp, %r11 + adox %rbp, %r11 mov %r9, %rcx shld \$1, %r8, %r9 shld \$1, %rbx, %r8 + xor %ebp, %ebp mulx %rdx, %rax, %rdx - add %rax, %r15 - adc %rdx, %r8 - adc \$0, %r9 + adcx %rax, %r15 + adcx %rdx, %r8 + mov 40($inp), %rdx + adcx %rbp, %r9 mov %r15, 64(%rsp) mov %r8, 72(%rsp) #sixth iteration - mov 40($inp), %rdx - mulx 48($inp), %rax, %rbx + .byte 0xc4,0xe2,0xfb,0xf6,0x9e,0x30,0x00,0x00,0x00 # mulx 48($inp), %rax, %rbx + adox %rax, %r10 + adcx %rbx, %r11 - mulx 56($inp), $out, %r12 - add %rax, %r10 - adc %rbx, %r11 - adc \$0, %r12 - add $out, %r11 - adc \$0, %r12 + .byte 0xc4,0x62,0xc3,0xf6,0xa6,0x38,0x00,0x00,0x00 # mulx 56($inp), $out, %r12 + adox $out, %r11 + adcx %rbp, %r12 + adox %rbp, %r12 mov %r11, %rbx shld \$1, %r10, %r11 shld \$1, %rcx, %r10 + xor %ebp, %ebp mulx %rdx, %rax, %rdx - add %rax, %r9 - adc %rdx, %r10 - adc \$0, %r11 + adcx %rax, %r9 + adcx %rdx, %r10 + mov 48($inp), %rdx + adcx %rbp, %r11 mov %r9, 80(%rsp) mov %r10, 88(%rsp) #seventh iteration - mov 48($inp), %rdx - mulx 56($inp), %rax, %r13 - add %rax, %r12 - adc \$0, %r13 + .byte 0xc4,0x62,0xfb,0xf6,0xae,0x38,0x00,0x00,0x00 # mulx 56($inp), %rax, %r13 + adox %rax, %r12 + adox %rbp, %r13 xor %r14, %r14 shld \$1, %r13, %r14 shld \$1, %r12, %r13 shld \$1, %rbx, %r12 + xor %ebp, %ebp mulx %rdx, %rax, %rdx - add %rax, %r11 - adc %rdx, %r12 - adc \$0, %r13 + adcx %rax, %r11 + adcx %rdx, %r12 + mov 56($inp), %rdx + adcx %rbp, %r13 - mov %r11, 96(%rsp) - mov %r12, 104(%rsp) + .byte 0x4c,0x89,0x9c,0x24,0x60,0x00,0x00,0x00 # mov %r11, 96(%rsp) + .byte 0x4c,0x89,0xa4,0x24,0x68,0x00,0x00,0x00 # mov %r12, 104(%rsp) #eighth iteration - mov 56($inp), %rdx mulx %rdx, %rax, %rdx - add %rax, %r13 - adc \$0, %rdx - + adox %rax, %r13 + adox %rbp, %rdx + + .byte 0x66 add %rdx, %r14 movq %r13, 112(%rsp) movq %r14, 120(%rsp) movq %xmm0, $out -___ -} -$code.=<<___; + movq %xmm1, %rbp + + movq 128(%rsp), %rdx # pull $n0 movq (%rsp), %r8 movq 8(%rsp), %r9 movq 16(%rsp), %r10 @@ -691,7 +760,7 @@ $code.=<<___; movq 48(%rsp), %r14 movq 56(%rsp), %r15 - call _rsaz_512_reduce + call __rsaz_512_reducex addq 64(%rsp), %r8 adcq 72(%rsp), %r9 @@ -703,7 +772,7 @@ $code.=<<___; adcq 120(%rsp), %r15 sbbq %rcx, %rcx - call _rsaz_512_subtract + call __rsaz_512_subtract movq %r8, %rdx movq %r9, %rax @@ -711,7 +780,12 @@ $code.=<<___; movq $out, $inp decl $times - jnz .Loop_sqr + jnz .Loop_sqrx + +.Lsqr_tail: +___ +} +$code.=<<___; leaq 128+24+48(%rsp), %rax movq -48(%rax), %r15 @@ -745,7 +819,15 @@ rsaz_512_mul: movq $out, %xmm0 # off-load arguments movq $mod, %xmm1 movq $n0, 128(%rsp) - +___ +$code.=<<___ if ($addx); + movl \$0x80100,%r11d + andl OPENSSL_ia32cap_P+8(%rip),%r11d + cmpl \$0x80100,%r11d # check for MULX and ADO/CX + je .Lmulx +___ +$code.=<<___; + movq ($bp), %rbx # pass b[0] movq $bp, %rbp # pass argument call __rsaz_512_mul @@ -761,8 +843,34 @@ rsaz_512_mul: movq 48(%rsp), %r14 movq 56(%rsp), %r15 - call _rsaz_512_reduce + call __rsaz_512_reduce +___ +$code.=<<___ if ($addx); + jmp .Lmul_tail + +.align 32 +.Lmulx: + movq $bp, %rbp # pass argument + movq ($bp), %rdx # pass b[0] + call __rsaz_512_mulx + + movq %xmm0, $out + movq %xmm1, %rbp + movq 128(%rsp), %rdx # pull $n0 + movq (%rsp), %r8 + movq 8(%rsp), %r9 + movq 16(%rsp), %r10 + movq 24(%rsp), %r11 + movq 32(%rsp), %r12 + movq 40(%rsp), %r13 + movq 48(%rsp), %r14 + movq 56(%rsp), %r15 + + call __rsaz_512_reducex |