| 1 | #! /usr/bin/env perl
|
|---|
| 2 | # Copyright 2006-2020 The OpenSSL Project Authors. All Rights Reserved.
|
|---|
| 3 | #
|
|---|
| 4 | # Licensed under the OpenSSL license (the "License"). You may not use
|
|---|
| 5 | # this file except in compliance with the License. You can obtain a copy
|
|---|
| 6 | # in the file LICENSE in the source distribution or at
|
|---|
| 7 | # https://www.openssl.org/source/license.html
|
|---|
| 8 |
|
|---|
| 9 | #
|
|---|
| 10 | # ====================================================================
|
|---|
| 11 | # Written by Andy Polyakov <[email protected]> for the OpenSSL
|
|---|
| 12 | # project. The module is, however, dual licensed under OpenSSL and
|
|---|
| 13 | # CRYPTOGAMS licenses depending on where you obtain it. For further
|
|---|
| 14 | # details see http://www.openssl.org/~appro/cryptogams/.
|
|---|
| 15 | # ====================================================================
|
|---|
| 16 | #
|
|---|
| 17 | # Wrapper around 'rep montmul', VIA-specific instruction accessing
|
|---|
| 18 | # PadLock Montgomery Multiplier. The wrapper is designed as drop-in
|
|---|
| 19 | # replacement for OpenSSL bn_mul_mont [first implemented in 0.9.9].
|
|---|
| 20 | #
|
|---|
| 21 | # Below are interleaved outputs from 'openssl speed rsa dsa' for 4
|
|---|
| 22 | # different software configurations on 1.5GHz VIA Esther processor.
|
|---|
| 23 | # Lines marked with "software integer" denote performance of hand-
|
|---|
| 24 | # coded integer-only assembler found in OpenSSL 0.9.7. "Software SSE2"
|
|---|
| 25 | # refers to hand-coded SSE2 Montgomery multiplication procedure found
|
|---|
| 26 | # OpenSSL 0.9.9. "Hardware VIA SDK" refers to padlock_pmm routine from
|
|---|
| 27 | # Padlock SDK 2.0.1 available for download from VIA, which naturally
|
|---|
| 28 | # utilizes the magic 'repz montmul' instruction. And finally "hardware
|
|---|
| 29 | # this" refers to *this* implementation which also uses 'repz montmul'
|
|---|
| 30 | #
|
|---|
| 31 | # sign verify sign/s verify/s
|
|---|
| 32 | # rsa 512 bits 0.001720s 0.000140s 581.4 7149.7 software integer
|
|---|
| 33 | # rsa 512 bits 0.000690s 0.000086s 1450.3 11606.0 software SSE2
|
|---|
| 34 | # rsa 512 bits 0.006136s 0.000201s 163.0 4974.5 hardware VIA SDK
|
|---|
| 35 | # rsa 512 bits 0.000712s 0.000050s 1404.9 19858.5 hardware this
|
|---|
| 36 | #
|
|---|
| 37 | # rsa 1024 bits 0.008518s 0.000413s 117.4 2420.8 software integer
|
|---|
| 38 | # rsa 1024 bits 0.004275s 0.000277s 233.9 3609.7 software SSE2
|
|---|
| 39 | # rsa 1024 bits 0.012136s 0.000260s 82.4 3844.5 hardware VIA SDK
|
|---|
| 40 | # rsa 1024 bits 0.002522s 0.000116s 396.5 8650.9 hardware this
|
|---|
| 41 | #
|
|---|
| 42 | # rsa 2048 bits 0.050101s 0.001371s 20.0 729.6 software integer
|
|---|
| 43 | # rsa 2048 bits 0.030273s 0.001008s 33.0 991.9 software SSE2
|
|---|
| 44 | # rsa 2048 bits 0.030833s 0.000976s 32.4 1025.1 hardware VIA SDK
|
|---|
| 45 | # rsa 2048 bits 0.011879s 0.000342s 84.2 2921.7 hardware this
|
|---|
| 46 | #
|
|---|
| 47 | # rsa 4096 bits 0.327097s 0.004859s 3.1 205.8 software integer
|
|---|
| 48 | # rsa 4096 bits 0.229318s 0.003859s 4.4 259.2 software SSE2
|
|---|
| 49 | # rsa 4096 bits 0.233953s 0.003274s 4.3 305.4 hardware VIA SDK
|
|---|
| 50 | # rsa 4096 bits 0.070493s 0.001166s 14.2 857.6 hardware this
|
|---|
| 51 | #
|
|---|
| 52 | # dsa 512 bits 0.001342s 0.001651s 745.2 605.7 software integer
|
|---|
| 53 | # dsa 512 bits 0.000844s 0.000987s 1185.3 1013.1 software SSE2
|
|---|
| 54 | # dsa 512 bits 0.001902s 0.002247s 525.6 444.9 hardware VIA SDK
|
|---|
| 55 | # dsa 512 bits 0.000458s 0.000524s 2182.2 1909.1 hardware this
|
|---|
| 56 | #
|
|---|
| 57 | # dsa 1024 bits 0.003964s 0.004926s 252.3 203.0 software integer
|
|---|
| 58 | # dsa 1024 bits 0.002686s 0.003166s 372.3 315.8 software SSE2
|
|---|
| 59 | # dsa 1024 bits 0.002397s 0.002823s 417.1 354.3 hardware VIA SDK
|
|---|
| 60 | # dsa 1024 bits 0.000978s 0.001170s 1022.2 855.0 hardware this
|
|---|
| 61 | #
|
|---|
| 62 | # dsa 2048 bits 0.013280s 0.016518s 75.3 60.5 software integer
|
|---|
| 63 | # dsa 2048 bits 0.009911s 0.011522s 100.9 86.8 software SSE2
|
|---|
| 64 | # dsa 2048 bits 0.009542s 0.011763s 104.8 85.0 hardware VIA SDK
|
|---|
| 65 | # dsa 2048 bits 0.002884s 0.003352s 346.8 298.3 hardware this
|
|---|
| 66 | #
|
|---|
| 67 | # To give you some other reference point here is output for 2.4GHz P4
|
|---|
| 68 | # running hand-coded SSE2 bn_mul_mont found in 0.9.9, i.e. "software
|
|---|
| 69 | # SSE2" in above terms.
|
|---|
| 70 | #
|
|---|
| 71 | # rsa 512 bits 0.000407s 0.000047s 2454.2 21137.0
|
|---|
| 72 | # rsa 1024 bits 0.002426s 0.000141s 412.1 7100.0
|
|---|
| 73 | # rsa 2048 bits 0.015046s 0.000491s 66.5 2034.9
|
|---|
| 74 | # rsa 4096 bits 0.109770s 0.002379s 9.1 420.3
|
|---|
| 75 | # dsa 512 bits 0.000438s 0.000525s 2281.1 1904.1
|
|---|
| 76 | # dsa 1024 bits 0.001346s 0.001595s 742.7 627.0
|
|---|
| 77 | # dsa 2048 bits 0.004745s 0.005582s 210.7 179.1
|
|---|
| 78 | #
|
|---|
| 79 | # Conclusions:
|
|---|
| 80 | # - VIA SDK leaves a *lot* of room for improvement (which this
|
|---|
| 81 | # implementation successfully fills:-);
|
|---|
| 82 | # - 'rep montmul' gives up to >3x performance improvement depending on
|
|---|
| 83 | # key length;
|
|---|
| 84 | # - in terms of absolute performance it delivers approximately as much
|
|---|
| 85 | # as modern out-of-order 32-bit cores [again, for longer keys].
|
|---|
| 86 |
|
|---|
| 87 | $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
|
|---|
| 88 | push(@INC,"${dir}","${dir}../../perlasm");
|
|---|
| 89 | require "x86asm.pl";
|
|---|
| 90 |
|
|---|
| 91 | $output = pop;
|
|---|
| 92 | open STDOUT,">$output";
|
|---|
| 93 |
|
|---|
| 94 | &asm_init($ARGV[0]);
|
|---|
| 95 |
|
|---|
| 96 | # int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, const BN_ULONG *np,const BN_ULONG *n0, int num);
|
|---|
| 97 | $func="bn_mul_mont_padlock";
|
|---|
| 98 |
|
|---|
| 99 | $pad=16*1; # amount of reserved bytes on top of every vector
|
|---|
| 100 |
|
|---|
| 101 | # stack layout
|
|---|
| 102 | $mZeroPrime=&DWP(0,"esp"); # these are specified by VIA
|
|---|
| 103 | $A=&DWP(4,"esp");
|
|---|
| 104 | $B=&DWP(8,"esp");
|
|---|
| 105 | $T=&DWP(12,"esp");
|
|---|
| 106 | $M=&DWP(16,"esp");
|
|---|
| 107 | $scratch=&DWP(20,"esp");
|
|---|
| 108 | $rp=&DWP(24,"esp"); # these are mine
|
|---|
| 109 | $sp=&DWP(28,"esp");
|
|---|
| 110 | # &DWP(32,"esp") # 32 byte scratch area
|
|---|
| 111 | # &DWP(64+(4*$num+$pad)*0,"esp") # padded tp[num]
|
|---|
| 112 | # &DWP(64+(4*$num+$pad)*1,"esp") # padded copy of ap[num]
|
|---|
| 113 | # &DWP(64+(4*$num+$pad)*2,"esp") # padded copy of bp[num]
|
|---|
| 114 | # &DWP(64+(4*$num+$pad)*3,"esp") # padded copy of np[num]
|
|---|
| 115 | # Note that SDK suggests to unconditionally allocate 2K per vector. This
|
|---|
| 116 | # has quite an impact on performance. It naturally depends on key length,
|
|---|
| 117 | # but to give an example 1024 bit private RSA key operations suffer >30%
|
|---|
| 118 | # penalty. I allocate only as much as actually required...
|
|---|
| 119 |
|
|---|
| 120 | &function_begin($func);
|
|---|
| 121 | &xor ("eax","eax");
|
|---|
| 122 | &mov ("ecx",&wparam(5)); # num
|
|---|
| 123 | # meet VIA's limitations for num [note that the specification
|
|---|
| 124 | # expresses them in bits, while we work with amount of 32-bit words]
|
|---|
| 125 | &test ("ecx",3);
|
|---|
| 126 | &jnz (&label("leave")); # num % 4 != 0
|
|---|
| 127 | &cmp ("ecx",8);
|
|---|
| 128 | &jb (&label("leave")); # num < 8
|
|---|
| 129 | &cmp ("ecx",1024);
|
|---|
| 130 | &ja (&label("leave")); # num > 1024
|
|---|
| 131 |
|
|---|
| 132 | &pushf ();
|
|---|
| 133 | &cld ();
|
|---|
| 134 |
|
|---|
| 135 | &mov ("edi",&wparam(0)); # rp
|
|---|
| 136 | &mov ("eax",&wparam(1)); # ap
|
|---|
| 137 | &mov ("ebx",&wparam(2)); # bp
|
|---|
| 138 | &mov ("edx",&wparam(3)); # np
|
|---|
| 139 | &mov ("esi",&wparam(4)); # n0
|
|---|
| 140 | &mov ("esi",&DWP(0,"esi")); # *n0
|
|---|
| 141 |
|
|---|
| 142 | &lea ("ecx",&DWP($pad,"","ecx",4)); # ecx becomes vector size in bytes
|
|---|
| 143 | &lea ("ebp",&DWP(64,"","ecx",4)); # allocate 4 vectors + 64 bytes
|
|---|
| 144 | &neg ("ebp");
|
|---|
| 145 | &add ("ebp","esp");
|
|---|
| 146 | &and ("ebp",-64); # align to cache-line
|
|---|
| 147 | &xchg ("ebp","esp"); # alloca
|
|---|
| 148 |
|
|---|
| 149 | &mov ($rp,"edi"); # save rp
|
|---|
| 150 | &mov ($sp,"ebp"); # save esp
|
|---|
| 151 |
|
|---|
| 152 | &mov ($mZeroPrime,"esi");
|
|---|
| 153 | &lea ("esi",&DWP(64,"esp")); # tp
|
|---|
| 154 | &mov ($T,"esi");
|
|---|
| 155 | &lea ("edi",&DWP(32,"esp")); # scratch area
|
|---|
| 156 | &mov ($scratch,"edi");
|
|---|
| 157 | &mov ("esi","eax");
|
|---|
| 158 |
|
|---|
| 159 | &lea ("ebp",&DWP(-$pad,"ecx"));
|
|---|
| 160 | &shr ("ebp",2); # restore original num value in ebp
|
|---|
| 161 |
|
|---|
| 162 | &xor ("eax","eax");
|
|---|
| 163 |
|
|---|
| 164 | &mov ("ecx","ebp");
|
|---|
| 165 | &lea ("ecx",&DWP((32+$pad)/4,"ecx"));# padded tp + scratch
|
|---|
| 166 | &data_byte(0xf3,0xab); # rep stosl, bzero
|
|---|
| 167 |
|
|---|
| 168 | &mov ("ecx","ebp");
|
|---|
| 169 | &lea ("edi",&DWP(64+$pad,"esp","ecx",4));# pointer to ap copy
|
|---|
| 170 | &mov ($A,"edi");
|
|---|
| 171 | &data_byte(0xf3,0xa5); # rep movsl, memcpy
|
|---|
| 172 | &mov ("ecx",$pad/4);
|
|---|
| 173 | &data_byte(0xf3,0xab); # rep stosl, bzero pad
|
|---|
| 174 | # edi points at the end of padded ap copy...
|
|---|
| 175 |
|
|---|
| 176 | &mov ("ecx","ebp");
|
|---|
| 177 | &mov ("esi","ebx");
|
|---|
| 178 | &mov ($B,"edi");
|
|---|
| 179 | &data_byte(0xf3,0xa5); # rep movsl, memcpy
|
|---|
| 180 | &mov ("ecx",$pad/4);
|
|---|
| 181 | &data_byte(0xf3,0xab); # rep stosl, bzero pad
|
|---|
| 182 | # edi points at the end of padded bp copy...
|
|---|
| 183 |
|
|---|
| 184 | &mov ("ecx","ebp");
|
|---|
| 185 | &mov ("esi","edx");
|
|---|
| 186 | &mov ($M,"edi");
|
|---|
| 187 | &data_byte(0xf3,0xa5); # rep movsl, memcpy
|
|---|
| 188 | &mov ("ecx",$pad/4);
|
|---|
| 189 | &data_byte(0xf3,0xab); # rep stosl, bzero pad
|
|---|
| 190 | # edi points at the end of padded np copy...
|
|---|
| 191 |
|
|---|
| 192 | # let magic happen...
|
|---|
| 193 | &mov ("ecx","ebp");
|
|---|
| 194 | &mov ("esi","esp");
|
|---|
| 195 | &shl ("ecx",5); # convert word counter to bit counter
|
|---|
| 196 | &align (4);
|
|---|
| 197 | &data_byte(0xf3,0x0f,0xa6,0xc0);# rep montmul
|
|---|
| 198 |
|
|---|
| 199 | &mov ("ecx","ebp");
|
|---|
| 200 | &lea ("esi",&DWP(64,"esp")); # tp
|
|---|
| 201 | # edi still points at the end of padded np copy...
|
|---|
| 202 | &neg ("ebp");
|
|---|
| 203 | &lea ("ebp",&DWP(-$pad,"edi","ebp",4)); # so just "rewind"
|
|---|
| 204 | &mov ("edi",$rp); # restore rp
|
|---|
| 205 | &xor ("edx","edx"); # i=0 and clear CF
|
|---|
| 206 |
|
|---|
| 207 | &set_label("sub",8);
|
|---|
| 208 | &mov ("eax",&DWP(0,"esi","edx",4));
|
|---|
| 209 | &sbb ("eax",&DWP(0,"ebp","edx",4));
|
|---|
| 210 | &mov (&DWP(0,"edi","edx",4),"eax"); # rp[i]=tp[i]-np[i]
|
|---|
| 211 | &lea ("edx",&DWP(1,"edx")); # i++
|
|---|
| 212 | &loop (&label("sub")); # doesn't affect CF!
|
|---|
| 213 |
|
|---|
| 214 | &mov ("eax",&DWP(0,"esi","edx",4)); # upmost overflow bit
|
|---|
| 215 | &sbb ("eax",0);
|
|---|
| 216 |
|
|---|
| 217 | &mov ("ecx","edx"); # num
|
|---|
| 218 | &mov ("edx",0); # i=0
|
|---|
| 219 |
|
|---|
| 220 | &set_label("copy",8);
|
|---|
| 221 | &mov ("ebx",&DWP(0,"esi","edx",4));
|
|---|
| 222 | &mov ("eax",&DWP(0,"edi","edx",4));
|
|---|
| 223 | &mov (&DWP(0,"esi","edx",4),"ecx"); # zap tp
|
|---|
| 224 | &cmovc ("eax","ebx");
|
|---|
| 225 | &mov (&DWP(0,"edi","edx",4),"eax");
|
|---|
| 226 | &lea ("edx",&DWP(1,"edx")); # i++
|
|---|
| 227 | &loop (&label("copy"));
|
|---|
| 228 |
|
|---|
| 229 | &mov ("ebp",$sp);
|
|---|
| 230 | &xor ("eax","eax");
|
|---|
| 231 |
|
|---|
| 232 | &mov ("ecx",64/4);
|
|---|
| 233 | &mov ("edi","esp"); # zap frame including scratch area
|
|---|
| 234 | &data_byte(0xf3,0xab); # rep stosl, bzero
|
|---|
| 235 |
|
|---|
| 236 | # zap copies of ap, bp and np
|
|---|
| 237 | &lea ("edi",&DWP(64+$pad,"esp","edx",4));# pointer to ap
|
|---|
| 238 | &lea ("ecx",&DWP(3*$pad/4,"edx","edx",2));
|
|---|
| 239 | &data_byte(0xf3,0xab); # rep stosl, bzero
|
|---|
| 240 |
|
|---|
| 241 | &mov ("esp","ebp");
|
|---|
| 242 | &inc ("eax"); # signal "done"
|
|---|
| 243 | &popf ();
|
|---|
| 244 | &set_label("leave");
|
|---|
| 245 | &function_end($func);
|
|---|
| 246 |
|
|---|
| 247 | &asciz("Padlock Montgomery Multiplication, CRYPTOGAMS by <appro\@openssl.org>");
|
|---|
| 248 |
|
|---|
| 249 | &asm_finish();
|
|---|
| 250 |
|
|---|
| 251 | close STDOUT or die "error closing STDOUT: $!";
|
|---|
