RFR: 8294248: Use less limbs for P256 in EC implementation

[Daniel Jeliński]

On Thu, 22 Sep 2022 20:40:08 GMT, Xue-Lei Andrew Fan <xuelei at openjdk.org> wrote:

> Hi,
> 
> Please review this performance improvement for Secp256R1 implementation in OpenJDK.  With this update, there is an about 20% performance improvement for Secp256R1 key generation and signature.
> 
> Basically, 256 bits EC curves could use 9 integer limbs for the computation.  The current implementation use 10 limbs instead.  By reducing the number of limbs, the implementation could benefit from less integer computation (add/sub/multiply/square/inverse/mod/pow, etc), and thus improve the performance.
> 
> Here are the benchmark numbers without the patch:
> 
> Benchmark         (messageLength)   Mode  Cnt  Score   Error   Units
> Signatures.sign               64  thrpt   15  1.414 ± 0.022  ops/ms
> Signatures.sign              512  thrpt   15  1.418 ± 0.004  ops/ms
> Signatures.sign             2048  thrpt   15  1.419 ± 0.005  ops/ms
> Signatures.sign            16384  thrpt   15  1.395 ± 0.003  ops/ms
> 
> KeyGenerators.keyPairGen          thrpt   15  1.475 ± 0.043  ops/ms
> 
> 
> And here are the numbers with the patch applied:
> 
> Benchmark         (messageLength)   Mode  Cnt  Score   Error   Units
> ECSignature.sign               64  thrpt   15  1.719 ± 0.010  ops/ms
> ECSignature.sign              512  thrpt   15  1.704 ± 0.012  ops/ms
> ECSignature.sign             2048  thrpt   15  1.699 ± 0.018  ops/ms
> ECSignature.sign            16384  thrpt   15  1.681 ± 0.006  ops/ms
> 
> KeyGenerators.keyPairGen           thrpt   15  1.881 ± 0.008  ops/ms
> 
> 
> Thanks,
> Xuelei

Can you prove that this is correct?
My back-of-the-envelope calculations suggest that this may overflow:
- starting with 29 bit limbs
- after 2 additions (maxAdds) we have up to 31 bits
- then we multiply limbs (62 bits) and add up to numLimbs (9) results together = 65 bits, which overflows long
- and we didn't start reducing yet.

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

PR: https://git.openjdk.org/jdk/pull/10398