• Ignat Korchagin's avatar
    crypto: rsa - implement Chinese Remainder Theorem for faster private key operations · f145d411
    Ignat Korchagin authored
    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_algorithmSigned-off-by: default avatarIgnat Korchagin <ignat@cloudflare.com>
    Reported-by: default avatarkernel test robot <lkp@intel.com>
    Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
    f145d411
mpi-add.c 3.43 KB