]> Cypherpunks repositories - gostls13.git/commit
crypto/internal/bigmod: optimize addMulVVW on Wasm
authorCherry Mui <cherryyz@google.com>
Mon, 11 Nov 2024 15:04:17 +0000 (10:04 -0500)
committerCherry Mui <cherryyz@google.com>
Wed, 13 Nov 2024 20:44:08 +0000 (20:44 +0000)
commit3730814f2f2bf24550920c39a16841583de2dac1
tree6c8671c4ad4a0bfb8a44040f0dde43900fdf29f9
parent4ffa2aecc119bd70f4765cbb9b911f47dbadd117
crypto/internal/bigmod: optimize addMulVVW on Wasm

The current implementation of addMulVVW makes heavy use of
64x64->128 bit multiplications and 64-bit add-with-carry, which
are compiler intrinsics and are very efficient on many
architectures. However, those are not supported on Wasm. Here we
implement it with 32x32->64 bit operations, which is more
efficient on Wasm.

crypto/rsa benchmarks with Node:

                     │   old.txt   │              new.txt                │
                     │   sec/op    │   sec/op     vs base                │
DecryptPKCS1v15/2048   7.726m ± 1%   4.895m ± 2%  -36.65% (p=0.000 n=35)
DecryptPKCS1v15/3072   23.52m ± 1%   15.33m ± 1%  -34.83% (p=0.000 n=35)
DecryptPKCS1v15/4096   52.64m ± 2%   35.40m ± 1%  -32.75% (p=0.000 n=35)
EncryptPKCS1v15/2048   264.2µ ± 1%   176.9µ ± 1%  -33.02% (p=0.000 n=35)
DecryptOAEP/2048       7.608m ± 1%   4.911m ± 1%  -35.45% (p=0.000 n=35)
EncryptOAEP/2048       266.2µ ± 0%   183.3µ ± 2%  -31.15% (p=0.000 n=35)
SignPKCS1v15/2048      7.836m ± 1%   5.009m ± 2%  -36.08% (p=0.000 n=35)
VerifyPKCS1v15/2048    262.9µ ± 1%   176.3µ ± 1%  -32.94% (p=0.000 n=35)
SignPSS/2048           7.814m ± 0%   5.020m ± 1%  -35.76% (p=0.000 n=35)
VerifyPSS/2048         267.0µ ± 1%   183.8µ ± 1%  -31.17% (p=0.000 n=35)
geomean                2.718m        1.794m       -34.01%

With wazero:

                     │    old.txt   │              new.txt                │
                     │    sec/op    │   sec/op     vs base                │
DecryptPKCS1v15/2048   13.445m ± 0%   6.528m ± 0%  -51.45% (p=0.000 n=25)
DecryptPKCS1v15/3072    41.07m ± 0%   18.85m ± 0%  -54.10% (p=0.000 n=25)
DecryptPKCS1v15/4096    91.84m ± 1%   39.66m ± 0%  -56.81% (p=0.000 n=25)
EncryptPKCS1v15/2048    461.3µ ± 0%   197.2µ ± 0%  -57.25% (p=0.000 n=25)
DecryptOAEP/2048       13.438m ± 0%   6.577m ± 0%  -51.06% (p=0.000 n=25)
EncryptOAEP/2048        471.5µ ± 0%   207.7µ ± 0%  -55.95% (p=0.000 n=25)
SignPKCS1v15/2048      13.739m ± 0%   6.687m ± 0%  -51.33% (p=0.000 n=25)
VerifyPKCS1v15/2048     461.3µ ± 1%   196.8µ ± 0%  -57.35% (p=0.000 n=25)
SignPSS/2048           13.765m ± 0%   6.686m ± 0%  -51.43% (p=0.000 n=25)
VerifyPSS/2048          470.8µ ± 0%   208.9µ ± 1%  -55.64% (p=0.000 n=25)
geomean                 4.769m        2.179m       -54.31%

Change-Id: I97f37d8cf1e3e9756a4e03ab4e681bf04152925f
Reviewed-on: https://go-review.googlesource.com/c/go/+/626957
Reviewed-by: David Chase <drchase@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
src/crypto/internal/bigmod/nat.go
src/crypto/internal/bigmod/nat_generic.go [new file with mode: 0644]
src/crypto/internal/bigmod/nat_wasm.go [new file with mode: 0644]