crypto/tls: tls.X509KeyPair is slow

[rogpeppe]

I was investigating why some code was taking a noticeable (260ms)
time to run, and found that it was because it was calling tls.X509KeyPair
a few times.

The time taken by tls.X509KeyPair is dominated by the time
taken by rsa.PrivateKey.Validate, which is itself dominated
by the probabilistic prime test, which takes ~30ms. Since the
test is not that great (cf. the comment in the function), perhaps
we could lose it.

The time taken by the code in my test case dropped
to 50ms with that test removed, with X509KeyPair no longer
being the dominant factor.

go version go1.2rc2 linux/amd64

[rsc]

Comment 1:

Not going to touch anything for Go 1.2.
That said, what if you change rsa.PrivateKey.Validate's ProbablyPrime(20) to
ProbablyPrime(1)?
There was a mistake transcribing Knuth's pseudocode in creating Plan 9's probably_prime
function, so that even when asked to do 20 rounds it did just 1 round, so I looked into
the importance of the extra rounds a while back. My summary is at
http://9fans.net/archive/2010/03/250. For real RSA keys, I believe one round suffices.
A followup message suggested that it might be worth varying the number of rounds based
on the length of the prime. http://9fans.net/archive/2010/03/252

Labels changed: added priority-later, go1.3maybe, removed priority-triage.

Status changed to Accepted.

[rsc]

Comment 2:

Labels changed: added release-none, removed go1.3maybe.

[rsc]

Comment 3:

Labels changed: added repo-main.

[benburkert]

I would like to see this issue added to the 1.5 milestone. RSA private key validation is prohibitively slow, to the point where it is dominating the startup time for a server that loads just a few keypairs.

I have submitted a CL for benchmarks that cover tls.X509KeyPair. Here is a sample run on my machine:

PASS
BenchmarkX509KeyPairECDSAP224     1000     1727143 ns/op     13410 B/op      349 allocs/op
BenchmarkX509KeyPairECDSAP256     2000      740906 ns/op     14625 B/op      365 allocs/op
BenchmarkX509KeyPairECDSAP384      100    11173441 ns/op   2851176 B/op    29839 allocs/op
BenchmarkX509KeyPairECDSAP521      100    20017927 ns/op   5203322 B/op    45132 allocs/op
BenchmarkX509KeyPairRSA512       200     8075167 ns/op    736272 B/op    14575 allocs/op
BenchmarkX509KeyPairRSA1024       50    28510635 ns/op   2252128 B/op    27745 allocs/op
BenchmarkX509KeyPairRSA2048       10   125728535 ns/op   7751872 B/op    54337 allocs/op
BenchmarkX509KeyPairRSA4096        2   619041582 ns/op  30324544 B/op   107405 allocs/op
ok    crypto/tls  13.740s

Switching the prime.ProbablyPrime(20) call to prime.ProbablyPrime(3) shows a substantial improvement for large RSA private keys:

PASS
BenchmarkX509KeyPairECDSAP224     1000     1573445 ns/op     14165 B/op      342 allocs/op
BenchmarkX509KeyPairECDSAP256     2000      650514 ns/op     15333 B/op      358 allocs/op
BenchmarkX509KeyPairECDSAP384      200     7402859 ns/op   2851451 B/op    29827 allocs/op
BenchmarkX509KeyPairECDSAP521      100    13063005 ns/op   5203804 B/op    45122 allocs/op
BenchmarkX509KeyPairRSA512        1000     1263790 ns/op    153504 B/op     2958 allocs/op
BenchmarkX509KeyPairRSA1024        300     3965701 ns/op    410464 B/op     5337 allocs/op
BenchmarkX509KeyPairRSA2048        100    17037333 ns/op   1349856 B/op    10513 allocs/op
BenchmarkX509KeyPairRSA4096         20    87310326 ns/op   5080576 B/op    20352 allocs/op
ok    crypto/tls  13.250s

[bradfitz]

Adam, thoughts?