RFR: 8295011: EC point multiplication improvement for secp256r1 [v3]

Xue-Lei Andrew Fan xuelei at openjdk.org
Fri Oct 28 18:05:30 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 tailing whitespaces

-------------

Changes:
  - all: https://git.openjdk.org/jdk/pull/10893/files
  - new: https://git.openjdk.org/jdk/pull/10893/files/c644b6be..aa224efc

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=10893&range=02
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=10893&range=01-02

  Stats: 1 line in 1 file changed: 0 ins; 0 del; 1 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