RFR: 8294731: Improve multiplicative inverse for secp256r1 implementation [v6]
Xue-Lei Andrew Fan
xuelei at openjdk.org
Sat Nov 12 18:52:59 UTC 2022
> Hi,
>
> May I have this patch reviewed?
>
> This is one of a few steps to improve the EC performance. The multiplicative inverse implementation could be improved for better performance.
>
> For secp256r1 prime p, the current multiplicative inverse impl needs 256 square and 128 multiplication. With the path, the operation needs 256 square and 13 multiplication.
>
> For secp256r1 order n, the current multiplicative inverse impl needs 256 square and 169 multiplication. With the patch, the operation needs 256 square and 43 multiplication.
>
> In EC operations, square operation is much faster than multiplication. Decreasing multiplication numbers could speed up the multiplicative inverse significantly.
>
> The benchmark for ECDSA Signature is checked in order to see if the performance improvement is visible. Here are the benchmark numbers before the patch applied:
>
> Benchmark (messageLength) Mode Cnt Score Error Units
> Signatures.sign 64 thrpt 15 1412.644 ± 5.529 ops/s
> Signatures.sign 512 thrpt 15 1407.711 ± 14.118 ops/s
> Signatures.sign 2048 thrpt 15 1415.674 ± 6.965 ops/s
> Signatures.sign 16384 thrpt 15 1395.582 ± 12.689 ops/s
>
>
> And the following are the benchmarking after the patch applied.
>
> Signatures.sign 64 thrpt 15 1484.404 ± 10.705 ops/s
> Signatures.sign 512 thrpt 15 1486.563 ± 7.514 ops/s
> Signatures.sign 2048 thrpt 15 1479.866 ± 15.028 ops/s
> Signatures.sign 16384 thrpt 15 1469.789 ± 3.844 ops/s
>
>
> The performance improvement of the patch is about 5% for ECDSA signature. It looks like the improvement is no significant enough for now. But it may be 2+ times more in numbers when the scalar multiplication implementation is improved in a follow-up enhancement in another pull request.
>
> For comparing, here is the benchmarking numbers by using BigInteger.modInverse();
>
> Benchmark (messageLength) Mode Cnt Score Error Units
> Signatures.sign 64 thrpt 15 1395.628 ± 180.649 ops/s
> Signatures.sign 512 thrpt 15 1510.590 ± 9.826 ops/s
> Signatures.sign 2048 thrpt 15 1514.282 ± 3.382 ops/s
> Signatures.sign 16384 thrpt 15 1497.325 ± 6.854 ops/s
>
> and numbers for using BigInteger.modPow():
>
> Benchmark (messageLength) Mode Cnt Score Error Units
> Signatures.sign 64 thrpt 15 1486.764 ± 17.908 ops/s
> Signatures.sign 512 thrpt 15 1494.801 ± 14.072 ops/s
> Signatures.sign 2048 thrpt 15 1500.170 ± 6.998 ops/s
> Signatures.sign 16384 thrpt 15 1434.192 ± 49.269 ops/s
>
>
> Enhancement for other curves will be considered in separate pull requests.
>
> Thanks,
> Xuelei
Xue-Lei Andrew Fan has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains eight commits:
- Merge
- remove duplicated benchmark case
- remove unnecessary comment
- more improvement
- more performance improvement
- replace tab with whitrespaces
- add field order impl
- 8294731: Improve multiplicative inverse for EC implementation
-------------
Changes: https://git.openjdk.org/jdk/pull/10544/files
Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=10544&range=05
Stats: 201 lines in 1 file changed: 199 ins; 0 del; 2 mod
Patch: https://git.openjdk.org/jdk/pull/10544.diff
Fetch: git fetch https://git.openjdk.org/jdk pull/10544/head:pull/10544
PR: https://git.openjdk.org/jdk/pull/10544
More information about the security-dev
mailing list