Repository: go
Issue: crypto/rsa: RSA key generation is unreasonably slow on MIPS architecture
Labels: Performance,NeedsInvestigation

<!-- Please answer these questions before submitting your issue. Thanks! -->

### What version of Go are you using (`go version`)?

<pre>
$ go version
go version go1.12.7 linux/amd64
</pre>

### Does this issue reproduce with the latest release?
yes


### What operating system and processor architecture are you using (`go env`)?
```
GOARCH="mipsle"
GOOS="linux"
```

### What did you do?

<!--
If possible, provide a recipe for reproducing the error.
A complete runnable program is good.
A link on play.golang.org is best.
-->
Created a simple benchmark for generating RSA keys. Made some adjustments to make the algorithm deterministic, so the benchmark time is independent from the value of the input random seed

rsa_test.go
```go
package rsa_test

import (
	"crypto/aes"
	"crypto/cipher"
	"crypto/rsa"
	"io"
	"runtime/debug"
	"strings"
	"testing"
)

type devZero struct{}

func (dz devZero) Read(p []byte) (n int, err error) {
	for i, _ := range p {
		p[i] = 0
	}
	return len(p), nil
}

// reader which tries to negate the effect of crypto/internal/randutil/randutil.MaybeReadByte
// https://github.com/golang/go/blob/6269dcdc24d74379d8a609ce886149811020b2cc/src/crypto/internal/randutil/randutil.go#L25
// useful to regain deterministic output of some crypto routines with respect to a fixed pseudo-random stream
// such as https://github.com/golang/go/blob/6269dcdc24d74379d8a609ce886149811020b2cc/src/crypto/rsa/rsa.go#L222
type maybenotReader struct {
	io.Reader
}

func (r maybenotReader) Read(p []byte) (n int, err error) {
	if strings.Contains(string(debug.Stack()), "crypto/internal/randutil.MaybeReadByte") {
		// feed MaybeReadByte with dummy zeroes
		for i := range p {
			p[i] = 0
		}
		return len(p), nil
	}

	return r.Reader.Read(p)
}

var seed = []byte{0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f}

func newDRNG() io.Reader {
	block, _ := aes.NewCipher(seed)
	stream := cipher.NewCTR(block, make([]byte, 16))

	return cipher.StreamReader{S: stream, R: devZero{}}
}

func benchmarkRsaGenerateKey(bits int, b *testing.B) {
	for n := 0; n < b.N; n++ {
		_, e := rsa.GenerateKey(maybenotReader{newDRNG()}, bits)
		if e != nil {
			b.Fatal(e)
		}
	}
}

func BenchmarkRsaGenerateKey1024(b *testing.B) {
	benchmarkRsaGenerateKey(1024, b)
}

func BenchmarkRsaGenerateKey2048(b *testing.B) {
        benchmarkRsaGenerateKey(2048, b)
}

func BenchmarkRsaGenerateKey4096(b *testing.B) {
        benchmarkRsaGenerateKey(4096, b)
}
```

Compile the above and run on a target platform:
```
$ GOARCH=mipsle go test -c -o testmips rsa_test.go
# copy ./testmips to MIPS Linux - I used Debian Stretch in QEMU
$ $ uname -a
Linux debmips 4.9.0-9-4kc-malta #1 Debian 4.9.168-1 (2019-04-12) mips GNU/Linux
```


### What did you expect to see?
Seconds to generate RSA keys


### What did you see instead?
Minutes (closer to hours) to generate 2048 and 4096 RSA keys
```
$ time ./testmips -test.bench=. -test.count 3
goos: linux
goarch: mipsle
BenchmarkRsaGenerateKey1024            1        35798014775 ns/op
BenchmarkRsaGenerateKey1024            1        31147393335 ns/op
BenchmarkRsaGenerateKey1024            1        6627440839 ns/op
BenchmarkRsaGenerateKey2048            1        168812137075 ns/op
BenchmarkRsaGenerateKey2048            1        134741347265 ns/op
BenchmarkRsaGenerateKey2048            1        147304597939 ns/op
BenchmarkRsaGenerateKey4096            1        1039797721543 ns/op
BenchmarkRsaGenerateKey4096            1        823377806776 ns/op
BenchmarkRsaGenerateKey4096            1        623262088403 ns/op
PASS

real    50m11.506s
user    33m49.000s
sys     15m33.744s
```
For comparison, generating 4096-bit key with `openssl` 3 times on the same QEMU instance:
```
$ time for i in 1 2 3; do openssl genpkey -algorithm rsa -pkeyopt rsa_keygen_bits:4096 1>/dev/null; done
........................++++
........................................................................................................++++
.................................++++
....++++
.........................................................................................................................................................................................................................................................................................................................................................................................................................................++++
.....................................++++

real	2m10.133s
user	2m8.800s
sys	0m0.308s
```

### Additional info

It seems the key generation time on MIPS grows disproportionally with the requested key size. Fun fact: for 4096-bit keys it is ~1.75 faster to emulate ARM on MIPS than to run MIPS code directly.

NOTE: for below simulations I used Go `1.10`, because later versions of Go are not `qemu-user` emulator friendly (probably, because of #24656). The test OS in question: Debian Stretch x86_64.

Compile the above test and run under `qemu-mipsel-static` emulator
```
$ GOARCH=mipsle go test -c -o testmips rsa_test.go
$ time qemu-mipsel-static ./testmips -test.bench=. -test.count 3
goos: linux
goarch: mipsle
BenchmarkRsaGenerateKey1024-32                 1        5689779179 ns/op
BenchmarkRsaGenerateKey1024-32                 1        5625519786 ns/op
BenchmarkRsaGenerateKey1024-32                 1        5634661337 ns/op
BenchmarkRsaGenerateKey2048-32                 1        89522431701 ns/op
BenchmarkRsaGenerateKey2048-32                 1        92388147744 ns/op
BenchmarkRsaGenerateKey2048-32                 1        91639958105 ns/op
BenchmarkRsaGenerateKey4096-32                 1        589441375945 ns/op
BenchmarkRsaGenerateKey4096-32                 1        583990222852 ns/op
BenchmarkRsaGenerateKey4096-32                 1        589008197818 ns/op
PASS

real    34m14.872s
user    34m8.239s
sys     0m22.022s
```

Compile the same code, but for arm and run it on `qemu-arm-static` emulator compiled for `mipsle` (which I just downloaded from official Debian MIPS stretch repositories) and running on `qemu-mipsel-static` emulator (double emulation):
```
$ GOARCH=arm go test -c -o testarm rsa_test.go
$ time qemu-mipsel-static ../emuemu/usr/bin/qemu-arm-static ./testarm -test.bench=. -test.count 3
goos: linux
goarch: arm
BenchmarkRsaGenerateKey1024-32                 1        8405353927 ns/op
BenchmarkRsaGenerateKey1024-32                 1        7890613791 ns/op
BenchmarkRsaGenerateKey1024-32                 1        7742888355 ns/op
BenchmarkRsaGenerateKey2048-32                 1        84443846429 ns/op
BenchmarkRsaGenerateKey2048-32                 1        85332574758 ns/op
BenchmarkRsaGenerateKey2048-32                 1        86418695881 ns/op
BenchmarkRsaGenerateKey4096-32                 1        332455626256 ns/op
BenchmarkRsaGenerateKey4096-32                 1        348751908420 ns/op
BenchmarkRsaGenerateKey4096-32                 1        350252575613 ns/op
PASS

real    25m46.399s
user    23m43.629s
sys     8m41.457s
```

As we can see it makes almost no difference for 2048-bit keys with double emulation through arm and 4096-bit keys are even faster when emulated with arm.