Re: [PATCH v2] crypto: rsa - implement Chinese Remainder Theorem for faster private key operations

[Herbert Xu]

On Fri, Jun 17, 2022 at 09:42:10AM +0100, Ignat Korchagin wrote:
> Changes from v1:
>   * exported mpi_sub and mpi_mul, otherwise the build fails when RSA is a module
> 
> The kernel RSA ASN.1 private key parser already supports only private keys with
> additional values to be used with the Chinese Remainder Theorem [1], but these
> values are currently not used.
> 
> This rudimentary CRT implementation speeds up RSA private key operations for the
> following Go benchmark up to ~3x.
> 
> This implementation also tries to minimise the allocation of additional MPIs,
> so existing MPIs are reused as much as possible (hence the variable names are a
> bit weird).
> 
> The benchmark used:
> 
> ```
> package keyring_test
> 
> import (
> 	"crypto"
> 	"crypto/rand"
> 	"crypto/rsa"
> 	"crypto/x509"
> 	"io"
> 	"syscall"
> 	"testing"
> 	"unsafe"
> )
> 
> type KeySerial int32
> type Keyring int32
> 
> const (
> 	KEY_SPEC_PROCESS_KEYRING Keyring = -2
> 	KEYCTL_PKEY_SIGN                 = 27
> )
> 
> var (
> 	keyTypeAsym = []byte("asymmetric\x00")
> 	sha256pkcs1 = []byte("enc=pkcs1 hash=sha256\x00")
> )
> 
> func (keyring Keyring) LoadAsym(desc string, payload []byte) (KeySerial, error) {
> 	cdesc := []byte(desc + "\x00")
> 	serial, _, errno := syscall.Syscall6(syscall.SYS_ADD_KEY, uintptr(unsafe.Pointer(&keyTypeAsym[0])), uintptr(unsafe.Pointer(&cdesc[0])), uintptr(unsafe.Pointer(&payload[0])), uintptr(len(payload)), uintptr(keyring), uintptr(0))
> 	if errno == 0 {
> 		return KeySerial(serial), nil
> 	}
> 
> 	return KeySerial(serial), errno
> }
> 
> type pkeyParams struct {
> 	key_id         KeySerial
> 	in_len         uint32
> 	out_or_in2_len uint32
> 	__spare        [7]uint32
> }
> 
> // the output signature buffer is an input parameter here, because we want to
> // avoid Go buffer allocation leaking into our benchmarks
> func (key KeySerial) Sign(info, digest, out []byte) error {
> 	var params pkeyParams
> 	params.key_id = key
> 	params.in_len = uint32(len(digest))
> 	params.out_or_in2_len = uint32(len(out))
> 
> 	_, _, errno := syscall.Syscall6(syscall.SYS_KEYCTL, KEYCTL_PKEY_SIGN, uintptr(unsafe.Pointer(&params)), uintptr(unsafe.Pointer(&info[0])), uintptr(unsafe.Pointer(&digest[0])), uintptr(unsafe.Pointer(&out[0])), uintptr(0))
> 	if errno == 0 {
> 		return nil
> 	}
> 
> 	return errno
> }
> 
> func BenchmarkSign(b *testing.B) {
> 	priv, err := rsa.GenerateKey(rand.Reader, 2048)
> 	if err != nil {
> 		b.Fatalf("failed to generate private key: %v", err)
> 	}
> 
> 	pkcs8, err := x509.MarshalPKCS8PrivateKey(priv)
> 	if err != nil {
> 		b.Fatalf("failed to serialize the private key to PKCS8 blob: %v", err)
> 	}
> 
> 	serial, err := KEY_SPEC_PROCESS_KEYRING.LoadAsym("test rsa key", pkcs8)
> 	if err != nil {
> 		b.Fatalf("failed to load the private key into the keyring: %v", err)
> 	}
> 
> 	b.Logf("loaded test rsa key: %v", serial)
> 
> 	digest := make([]byte, 32)
> 	_, err = io.ReadFull(rand.Reader, digest)
> 	if err != nil {
> 		b.Fatalf("failed to generate a random digest: %v", err)
> 	}
> 
> 	sig := make([]byte, 256)
> 	for n := 0; n < b.N; n++ {
> 		err = serial.Sign(sha256pkcs1, digest, sig)
> 		if err != nil {
> 			b.Fatalf("failed to sign the digest: %v", err)
> 		}
> 	}
> 
> 	err = rsa.VerifyPKCS1v15(&priv.PublicKey, crypto.SHA256, digest, sig)
> 	if err != nil {
> 		b.Fatalf("failed to verify the signature: %v", err)
> 	}
> }
> ```
> 
> [1]: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
> 
> Signed-off-by: Ignat Korchagin <ignat@xxxxxxxxxxxxxx>
> Reported-by: kernel test robot <lkp@xxxxxxxxx>
> ---
>  crypto/rsa.c      | 78 ++++++++++++++++++++++++++++++++++++++++++++---
>  lib/mpi/mpi-add.c |  2 +-
>  lib/mpi/mpi-mul.c |  1 +
>  3 files changed, 75 insertions(+), 6 deletions(-)

Patch applied.  Thanks.
-- 
Email: Herbert Xu <herbert@xxxxxxxxxxxxxxxxxxx>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt