RFR: 8295011: EC point multiplication improvement for secp256r1 [v6]
Xue-Lei Andrew Fan
xuelei at openjdk.org
Fri Nov 18 17:56:27 UTC 2022
> Hi,
>
> May I have this update reviewed?
>
> The EC point multiplication for secp256r1 could be improved for better performance, by using more efficient algorithm and pre-computation. Improvement for other curves are similar, but will be addressed in separated PRs.
>
> The basic idea is using pre-computed tables and safe table select in order to speed up the point multiplication and keep is safe. Before this patch applied, a secp256r1 point multiplication operation needs 256 double operations and 78 addition operations. With this patch, it is reduced to 16 double operations and 64 addition operations. **If assuming the performance for double and addition operations is about the same (double operation is a little bit faster actually), the new point multiplication implementation performance is about 4 times ((256+78)/(16+64)) of the current implementation.**
>
> ## SSLHandshake.java benchmark
> ### Use secp256r1 as the named group
> The following are TLS benchmarking (test/micro/org/openjdk/bench/java/security/SSLHandshake.java) results by using secp256r1 (Set the System property, "jdk.tls.namedGroups" to "secp256r1") as the key exchange algorithm in TLS connections:
>
> Benchmark with this patch:
>
> Benchmark (resume) (tlsVersion) Mode Cnt Score Error Units
> SSLHandshake.doHandshake true TLSv1.2 thrpt 15 7976.334 ± 96.877 ops/s
> SSLHandshake.doHandshake true TLS thrpt 15 315.783 ± 1.208 ops/s
> SSLHandshake.doHandshake false TLSv1.2 thrpt 15 235.646 ± 1.356 ops/s
> SSLHandshake.doHandshake false TLS thrpt 15 230.759 ± 1.789 ops/s
>
>
> Benchmark before this patch applied:
>
> Benchmark (resume) (tlsVersion) Mode Cnt Score Error Units
> SSLHandshake.doHandshake true TLSv1.2 thrpt 15 7830.289 ± 58.584 ops/s
> SSLHandshake.doHandshake true TLS thrpt 15 253.827 ± 0.690 ops/s
> SSLHandshake.doHandshake false TLSv1.2 thrpt 15 171.944 ± 0.667 ops/s
> SSLHandshake.doHandshake false TLS thrpt 15 169.383 ± 0.593 ops/s
>
>
> Per the result, the session resumption performance for TLS 1.2 is about the same. It is the expected result as there is no EC point multiplication involved for TLS 1.2 session resumption. TLS 1.3 is different as EC key generation is involved in either initial handshake and session resumption.
>
> **When EC key generation get involved (TLS 1.3 connections and TLS 1.2 initial handshake), the performance improvement is about 35% for named group secp256r1 based TLS connections..**
>
> ### Use default TLS named groups
> The following are TLS benchmarking (test/micro/org/openjdk/bench/java/security/SSLHandshake.java) results by using key exchange algorithms in TLS connections. In the current JDK implementation, the EC keys are generated for both secp256r1 and x25519 curves, and x25519 is the preferred curves.
>
> Benchmark with this patch:
>
> Benchmark (resume) (tlsVersion) Mode Cnt Score Error Units
> SSLHandshake.doHandshake true TLSv1.2 thrpt 15 7620.615 ± 62.459 ops/s
> SSLHandshake.doHandshake true TLS thrpt 15 746.924 ± 6.549 ops/s
> SSLHandshake.doHandshake false TLSv1.2 thrpt 15 456.066 ± 1.440 ops/s
> SSLHandshake.doHandshake false TLS thrpt 15 396.189 ± 2.275 ops/s
>
>
> Benchmark before this patch applied:
>
> Benchmark (resume) (tlsVersion) Mode Cnt Score Error Units
> SSLHandshake.doHandshake true TLSv1.2 thrpt 15 7605.177 ± 55.961 ops/s
> SSLHandshake.doHandshake true TLS thrpt 15 544.333 ± 23.431 ops/s
> SSLHandshake.doHandshake false TLSv1.2 thrpt 15 335.259 ± 1.926 ops/s
> SSLHandshake.doHandshake false TLS thrpt 15 269.422 ± 1.531 ops/s
>
>
> Per the result, the session resumption performance for TLS 1.2 is about the same. It is the expected result as there is no EC point multiplication involved for TLS 1.2 session resumption. TLS 1.3 is different as EC key generation is involved in either initial handshake and session resumption.
>
> **When EC key generation get involved (TLS 1.3 connections and TLS 1.2 initial handshake), the performance improvement is about 36%~47% for default configuration based TLS connections.**
>
> ## KeyPairGenerators.java benchmark
> The following are EC key pair generation benchmark (test/micro/org/openjdk/bench/java/security/KeyPairGenerators.java) results.
>
> Benchmark with this patch:
>
> Benchmark (curveName) Mode Cnt Score Error Units
> KeyPairGenerators.keyPairGen secp256r1 thrpt 15 4638.623 ± 93.320 ops/s
> KeyPairGenerators.keyPairGen secp384r1 thrpt 15 710.643 ± 6.404 ops/s
> KeyPairGenerators.keyPairGen secp521r1 thrpt 15 371.417 ± 1.302 ops/s
> KeyPairGenerators.keyPairGen Ed25519 thrpt 15 2355.491 ± 69.584 ops/s
> KeyPairGenerators.keyPairGen Ed448 thrpt 15 682.144 ± 6.671 ops/s
>
>
> Benchmark before this patch applied:
>
> Benchmark (curveName) Mode Cnt Score Error Units
> KeyPairGenerators.keyPairGen secp256r1 thrpt 15 1642.312 ± 52.155 ops/s
> KeyPairGenerators.keyPairGen secp384r1 thrpt 15 687.669 ± 30.576 ops/s
> KeyPairGenerators.keyPairGen secp521r1 thrpt 15 371.854 ± 1.736 ops/s
> KeyPairGenerators.keyPairGen Ed25519 thrpt 15 2448.139 ± 7.788 ops/s
> KeyPairGenerators.keyPairGen Ed448 thrpt 15 685.195 ± 4.994 ops/s
>
>
> **Per the result, the performance improvement is about 180% for key pair generation performance for secp256r1.** Other curves should not be impacted as the point multiplication implementation for them is not updated yet.
>
> ## Signatures.java benchmark
> The following are EC key pair generation benchmark (test/micro/org/openjdk/bench/java/security/Signatures.java) results.
>
> Benchmark with this patch:
>
> Benchmark (curveName) (messageLength) Mode Cnt Score Error Units
> Signatures.sign secp256r1 64 thrpt 15 3646.764 ± 28.633 ops/s
> Signatures.sign secp256r1 512 thrpt 15 3595.674 ± 69.761 ops/s
> Signatures.sign secp256r1 2048 thrpt 15 3633.184 ± 22.236 ops/s
> Signatures.sign secp256r1 16384 thrpt 15 3481.104 ± 21.043 ops/s
> Signatures.sign secp384r1 64 thrpt 15 631.036 ± 6.154 ops/s
> Signatures.sign secp384r1 512 thrpt 15 633.485 ± 18.700 ops/s
> Signatures.sign secp384r1 2048 thrpt 15 615.955 ± 4.598 ops/s
> Signatures.sign secp384r1 16384 thrpt 15 627.193 ± 6.551 ops/s
> Signatures.sign secp521r1 64 thrpt 15 303.849 ± 19.569 ops/s
> Signatures.sign secp521r1 512 thrpt 15 308.676 ± 7.002 ops/s
> Signatures.sign secp521r1 2048 thrpt 15 317.306 ± 0.327 ops/s
> Signatures.sign secp521r1 16384 thrpt 15 312.579 ± 1.753 ops/s
> Signatures.sign Ed25519 64 thrpt 15 1192.428 ± 10.424 ops/s
> Signatures.sign Ed25519 512 thrpt 15 1185.397 ± 1.993 ops/s
> Signatures.sign Ed25519 2048 thrpt 15 1181.980 ± 2.963 ops/s
> Signatures.sign Ed25519 16384 thrpt 15 1105.737 ± 4.339 ops/s
> Signatures.sign Ed448 64 thrpt 15 332.501 ± 1.471 ops/s
> Signatures.sign Ed448 512 thrpt 15 324.770 ± 9.631 ops/s
> Signatures.sign Ed448 2048 thrpt 15 325.833 ± 1.602 ops/s
> Signatures.sign Ed448 16384 thrpt 15 313.231 ± 1.440 ops/s
>
>
>
> Benchmark before this patch applied:
>
> Benchmark (curveName) (messageLength) Mode Cnt Score Error Units
> Signatures.sign secp256r1 64 thrpt 15 1515.924 ± 8.489 ops/s
> Signatures.sign secp256r1 512 thrpt 15 1521.586 ± 7.726 ops/s
> Signatures.sign secp256r1 2048 thrpt 15 1499.704 ± 9.704 ops/s
> Signatures.sign secp256r1 16384 thrpt 15 1499.392 ± 8.832 ops/s
> Signatures.sign secp384r1 64 thrpt 15 634.406 ± 8.328 ops/s
> Signatures.sign secp384r1 512 thrpt 15 633.766 ± 11.965 ops/s
> Signatures.sign secp384r1 2048 thrpt 15 634.608 ± 5.526 ops/s
> Signatures.sign secp384r1 16384 thrpt 15 628.815 ± 3.756 ops/s
> Signatures.sign secp521r1 64 thrpt 15 313.390 ± 9.728 ops/s
> Signatures.sign secp521r1 512 thrpt 15 316.420 ± 2.817 ops/s
> Signatures.sign secp521r1 2048 thrpt 15 307.386 ± 3.966 ops/s
> Signatures.sign secp521r1 16384 thrpt 15 315.384 ± 2.243 ops/s
> Signatures.sign Ed25519 64 thrpt 15 1187.227 ± 5.758 ops/s
> Signatures.sign Ed25519 512 thrpt 15 1189.044 ± 5.370 ops/s
> Signatures.sign Ed25519 2048 thrpt 15 1182.833 ± 13.186 ops/s
> Signatures.sign Ed25519 16384 thrpt 15 1099.599 ± 3.932 ops/s
> Signatures.sign Ed448 64 thrpt 15 331.810 ± 3.786 ops/s
> Signatures.sign Ed448 512 thrpt 15 332.885 ± 4.926 ops/s
> Signatures.sign Ed448 2048 thrpt 15 332.941 ± 4.292 ops/s
> Signatures.sign Ed448 16384 thrpt 15 318.226 ± 4.141 ops/s
>
>
> **Per the result, the performance improvement is about 140% for signature performance for secp256r1.** Other curves should not be impacted as the point multiplication implementation for them is not updated yet.
Xue-Lei Andrew Fan has updated the pull request incrementally with one additional commit since the last revision:
remove duplicated bench cases
-------------
Changes:
- all: https://git.openjdk.org/jdk/pull/10893/files
- new: https://git.openjdk.org/jdk/pull/10893/files/2999562e..618aeda3
Webrevs:
- full: https://webrevs.openjdk.org/?repo=jdk&pr=10893&range=05
- incr: https://webrevs.openjdk.org/?repo=jdk&pr=10893&range=04-05
Stats: 167 lines in 2 files changed: 0 ins; 167 del; 0 mod
Patch: https://git.openjdk.org/jdk/pull/10893.diff
Fetch: git fetch https://git.openjdk.org/jdk pull/10893/head:pull/10893
PR: https://git.openjdk.org/jdk/pull/10893
More information about the security-dev
mailing list