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

2022-06-17 08:43:30

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

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 <[email protected]>
Reported-by: kernel test robot <[email protected]>
---
crypto/rsa.c | 78 ++++++++++++++++++++++++++++++++++++++++++++---
lib/mpi/mpi-add.c | 2 +-
lib/mpi/mpi-mul.c | 1 +
3 files changed, 75 insertions(+), 6 deletions(-)

diff --git a/crypto/rsa.c b/crypto/rsa.c
index 39e04176b04b..0e555ee4addb 100644
--- a/crypto/rsa.c
+++ b/crypto/rsa.c
@@ -17,6 +17,11 @@ struct rsa_mpi_key {
MPI n;
MPI e;
MPI d;
+ MPI p;
+ MPI q;
+ MPI dp;
+ MPI dq;
+ MPI qinv;
};

/*
@@ -35,16 +40,49 @@ static int _rsa_enc(const struct rsa_mpi_key *key, MPI c, MPI m)

/*
* RSADP function [RFC3447 sec 5.1.2]
- * m = c^d mod n;
+ * m_1 = c^dP mod p;
+ * m_2 = c^dQ mod q;
+ * h = (m_1 - m_2) * qInv mod p;
+ * m = m_2 + q * h;
*/
-static int _rsa_dec(const struct rsa_mpi_key *key, MPI m, MPI c)
+static int _rsa_dec_crt(const struct rsa_mpi_key *key, MPI m_or_m1_or_h, MPI c)
{
+ MPI m2, m12_or_qh;
+ int ret = -ENOMEM;
+
/* (1) Validate 0 <= c < n */
if (mpi_cmp_ui(c, 0) < 0 || mpi_cmp(c, key->n) >= 0)
return -EINVAL;

- /* (2) m = c^d mod n */
- return mpi_powm(m, c, key->d, key->n);
+ m2 = mpi_alloc(0);
+ m12_or_qh = mpi_alloc(0);
+ if (!m2 || !m12_or_qh)
+ goto err_free_mpi;
+
+ /* (2i) m_1 = c^dP mod p */
+ ret = mpi_powm(m_or_m1_or_h, c, key->dp, key->p);
+ if (ret)
+ goto err_free_mpi;
+
+ /* (2i) m_2 = c^dQ mod q */
+ ret = mpi_powm(m2, c, key->dq, key->q);
+ if (ret)
+ goto err_free_mpi;
+
+ /* (2iii) h = (m_1 - m_2) * qInv mod p */
+ mpi_sub(m12_or_qh, m_or_m1_or_h, m2);
+ mpi_mulm(m_or_m1_or_h, m12_or_qh, key->qinv, key->p);
+
+ /* (2iv) m = m_2 + q * h */
+ mpi_mul(m12_or_qh, key->q, m_or_m1_or_h);
+ mpi_addm(m_or_m1_or_h, m2, m12_or_qh, key->n);
+
+ ret = 0;
+
+err_free_mpi:
+ mpi_free(m12_or_qh);
+ mpi_free(m2);
+ return ret;
}

static inline struct rsa_mpi_key *rsa_get_key(struct crypto_akcipher *tfm)
@@ -112,7 +150,7 @@ static int rsa_dec(struct akcipher_request *req)
if (!c)
goto err_free_m;

- ret = _rsa_dec(pkey, m, c);
+ ret = _rsa_dec_crt(pkey, m, c);
if (ret)
goto err_free_c;

@@ -134,9 +172,19 @@ static void rsa_free_mpi_key(struct rsa_mpi_key *key)
mpi_free(key->d);
mpi_free(key->e);
mpi_free(key->n);
+ mpi_free(key->p);
+ mpi_free(key->q);
+ mpi_free(key->dp);
+ mpi_free(key->dq);
+ mpi_free(key->qinv);
key->d = NULL;
key->e = NULL;
key->n = NULL;
+ key->p = NULL;
+ key->q = NULL;
+ key->dp = NULL;
+ key->dq = NULL;
+ key->qinv = NULL;
}

static int rsa_check_key_length(unsigned int len)
@@ -217,6 +265,26 @@ static int rsa_set_priv_key(struct crypto_akcipher *tfm, const void *key,
if (!mpi_key->n)
goto err;

+ mpi_key->p = mpi_read_raw_data(raw_key.p, raw_key.p_sz);
+ if (!mpi_key->p)
+ goto err;
+
+ mpi_key->q = mpi_read_raw_data(raw_key.q, raw_key.q_sz);
+ if (!mpi_key->q)
+ goto err;
+
+ mpi_key->dp = mpi_read_raw_data(raw_key.dp, raw_key.dp_sz);
+ if (!mpi_key->dp)
+ goto err;
+
+ mpi_key->dq = mpi_read_raw_data(raw_key.dq, raw_key.dq_sz);
+ if (!mpi_key->dq)
+ goto err;
+
+ mpi_key->qinv = mpi_read_raw_data(raw_key.qinv, raw_key.qinv_sz);
+ if (!mpi_key->qinv)
+ goto err;
+
if (rsa_check_key_length(mpi_get_size(mpi_key->n) << 3)) {
rsa_free_mpi_key(mpi_key);
return -EINVAL;
diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c
index 2cdae54c1bd0..9056fc5167fc 100644
--- a/lib/mpi/mpi-add.c
+++ b/lib/mpi/mpi-add.c
@@ -138,7 +138,7 @@ void mpi_sub(MPI w, MPI u, MPI v)
mpi_add(w, u, vv);
mpi_free(vv);
}
-
+EXPORT_SYMBOL_GPL(mpi_sub);

void mpi_addm(MPI w, MPI u, MPI v, MPI m)
{
diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c
index 8f5fa200f297..7f4eda8560dc 100644
--- a/lib/mpi/mpi-mul.c
+++ b/lib/mpi/mpi-mul.c
@@ -82,6 +82,7 @@ void mpi_mul(MPI w, MPI u, MPI v)
if (tmp_limb)
mpi_free_limb_space(tmp_limb);
}
+EXPORT_SYMBOL_GPL(mpi_mul);

void mpi_mulm(MPI w, MPI u, MPI v, MPI m)
{
--
2.36.1

2022-06-24 09:15:50

by Herbert Xu

[permalink] [raw]

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

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 <[email protected]>
> Reported-by: kernel test robot <[email protected]>
> ---
> 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 <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

2022-07-07 17:30:06

by Harald Freudenberger

[permalink] [raw]

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

On 2022-06-17 10:42, 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 <[email protected]>
> Reported-by: kernel test robot <[email protected]>
> ---
> crypto/rsa.c | 78 ++++++++++++++++++++++++++++++++++++++++++++---
> lib/mpi/mpi-add.c | 2 +-
> lib/mpi/mpi-mul.c | 1 +
> 3 files changed, 75 insertions(+), 6 deletions(-)
>
> diff --git a/crypto/rsa.c b/crypto/rsa.c
> index 39e04176b04b..0e555ee4addb 100644
> --- a/crypto/rsa.c
> +++ b/crypto/rsa.c
> @@ -17,6 +17,11 @@ struct rsa_mpi_key {
> MPI n;
> MPI e;
> MPI d;
> + MPI p;
> + MPI q;
> + MPI dp;
> + MPI dq;
> + MPI qinv;
> };
>
> /*
> @@ -35,16 +40,49 @@ static int _rsa_enc(const struct rsa_mpi_key *key,
> MPI c, MPI m)
>
> /*
> * RSADP function [RFC3447 sec 5.1.2]
> - * m = c^d mod n;
> + * m_1 = c^dP mod p;
> + * m_2 = c^dQ mod q;
> + * h = (m_1 - m_2) * qInv mod p;
> + * m = m_2 + q * h;
> */
> -static int _rsa_dec(const struct rsa_mpi_key *key, MPI m, MPI c)
> +static int _rsa_dec_crt(const struct rsa_mpi_key *key, MPI
> m_or_m1_or_h, MPI c)
> {
> + MPI m2, m12_or_qh;
> + int ret = -ENOMEM;
> +
> /* (1) Validate 0 <= c < n */
> if (mpi_cmp_ui(c, 0) < 0 || mpi_cmp(c, key->n) >= 0)
> return -EINVAL;
>
> - /* (2) m = c^d mod n */
> - return mpi_powm(m, c, key->d, key->n);
> + m2 = mpi_alloc(0);
> + m12_or_qh = mpi_alloc(0);
> + if (!m2 || !m12_or_qh)
> + goto err_free_mpi;
> +
> + /* (2i) m_1 = c^dP mod p */
> + ret = mpi_powm(m_or_m1_or_h, c, key->dp, key->p);
> + if (ret)
> + goto err_free_mpi;
> +
> + /* (2i) m_2 = c^dQ mod q */
> + ret = mpi_powm(m2, c, key->dq, key->q);
> + if (ret)
> + goto err_free_mpi;
> +
> + /* (2iii) h = (m_1 - m_2) * qInv mod p */
> + mpi_sub(m12_or_qh, m_or_m1_or_h, m2);
> + mpi_mulm(m_or_m1_or_h, m12_or_qh, key->qinv, key->p);
> +
> + /* (2iv) m = m_2 + q * h */
> + mpi_mul(m12_or_qh, key->q, m_or_m1_or_h);
> + mpi_addm(m_or_m1_or_h, m2, m12_or_qh, key->n);
> +
> + ret = 0;
> +
> +err_free_mpi:
> + mpi_free(m12_or_qh);
> + mpi_free(m2);
> + return ret;
> }
>
> static inline struct rsa_mpi_key *rsa_get_key(struct crypto_akcipher
> *tfm)
> @@ -112,7 +150,7 @@ static int rsa_dec(struct akcipher_request *req)
> if (!c)
> goto err_free_m;
>
> - ret = _rsa_dec(pkey, m, c);
> + ret = _rsa_dec_crt(pkey, m, c);
> if (ret)
> goto err_free_c;
>
> @@ -134,9 +172,19 @@ static void rsa_free_mpi_key(struct rsa_mpi_key
> *key)
> mpi_free(key->d);
> mpi_free(key->e);
> mpi_free(key->n);
> + mpi_free(key->p);
> + mpi_free(key->q);
> + mpi_free(key->dp);
> + mpi_free(key->dq);
> + mpi_free(key->qinv);
> key->d = NULL;
> key->e = NULL;
> key->n = NULL;
> + key->p = NULL;
> + key->q = NULL;
> + key->dp = NULL;
> + key->dq = NULL;
> + key->qinv = NULL;
> }
>
> static int rsa_check_key_length(unsigned int len)
> @@ -217,6 +265,26 @@ static int rsa_set_priv_key(struct
> crypto_akcipher *tfm, const void *key,
> if (!mpi_key->n)
> goto err;
>
> + mpi_key->p = mpi_read_raw_data(raw_key.p, raw_key.p_sz);
> + if (!mpi_key->p)
> + goto err;
> +
> + mpi_key->q = mpi_read_raw_data(raw_key.q, raw_key.q_sz);
> + if (!mpi_key->q)
> + goto err;
> +
> + mpi_key->dp = mpi_read_raw_data(raw_key.dp, raw_key.dp_sz);
> + if (!mpi_key->dp)
> + goto err;
> +
> + mpi_key->dq = mpi_read_raw_data(raw_key.dq, raw_key.dq_sz);
> + if (!mpi_key->dq)
> + goto err;
> +
> + mpi_key->qinv = mpi_read_raw_data(raw_key.qinv, raw_key.qinv_sz);
> + if (!mpi_key->qinv)
> + goto err;
> +
> if (rsa_check_key_length(mpi_get_size(mpi_key->n) << 3)) {
> rsa_free_mpi_key(mpi_key);
> return -EINVAL;
> diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c
> index 2cdae54c1bd0..9056fc5167fc 100644
> --- a/lib/mpi/mpi-add.c
> +++ b/lib/mpi/mpi-add.c
> @@ -138,7 +138,7 @@ void mpi_sub(MPI w, MPI u, MPI v)
> mpi_add(w, u, vv);
> mpi_free(vv);
> }
> -
> +EXPORT_SYMBOL_GPL(mpi_sub);
>
> void mpi_addm(MPI w, MPI u, MPI v, MPI m)
> {
> diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c
> index 8f5fa200f297..7f4eda8560dc 100644
> --- a/lib/mpi/mpi-mul.c
> +++ b/lib/mpi/mpi-mul.c
> @@ -82,6 +82,7 @@ void mpi_mul(MPI w, MPI u, MPI v)
> if (tmp_limb)
> mpi_free_limb_space(tmp_limb);
> }
> +EXPORT_SYMBOL_GPL(mpi_mul);
>
> void mpi_mulm(MPI w, MPI u, MPI v, MPI m)
> {
> --
> 2.36.1

Hello Ignat
on s390 the linux-next kernel gives me this during startup:

Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: akcipher: decrypt test
failed. err -22
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: akcipher: test 1 failed
for rsa-generic, err=-22
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ------------[ cut here
]------------
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: self-tests for
rsa-generic (rsa) failed (rc=-22)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: WARNING: CPU: 6 PID: 111 at
crypto/testmgr.c:5773 alg_test+0x348/0x4d0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Modules linked in:
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: CPU: 6 PID: 111 Comm:
cryptomgr_test Not tainted 5.19.0-rc5-next-20220706 #1
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Hardware name: IBM 8561 T01
703 (LPAR)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl PSW : 0704d00180000000
00000000f8b15ab4 (alg_test+0x34c/0x4d0)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: R:0 T:1 IO:1 EX:1
Key:0 M:1 W:0 P:0 AS:3 CC:1 PM:0 RI:0 EA:3
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl GPRS: c0000000fffeffff
0000000080000000 0000000000000035 0000000000000000
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: 0000000000000001
0000000000000001 000000008da15c80 000000000000000d
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: 000000008da15c00
00000000ffffffff 00000380000000b6 ffffffffffffffea
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: 000000008cd53200
00000000fb19dfd0 00000000f8b15ab0 0000038004847cf8
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl Code: 00000000f8b15aa4:
c02000523738 larl %r2,00000000f955c914
00000000f8b15aaa:
c0e5002d52a7 brasl %r14,00000000f90bfff8
#00000000f8b15ab0:
af000000 mc 0,0
>00000000f8b15ab4:
b904002b lgr %r2,%r11
00000000f8b15ab8:
eb6ff1300004 lmg %r6,%r15,304(%r15)
00000000f8b15abe:
07fe bcr 15,%r14
00000000f8b15ac0:
47000700 bc 0,1792
00000000f8b15ac4:
1829 lr %r2,%r9
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Call Trace:
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f8b15ab4>]
alg_test+0x34c/0x4d0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ([<00000000f8b15ab0>]
alg_test+0x348/0x4d0)
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f8b13b98>]
cryptomgr_test+0x68/0x70
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f83b4be8>]
kthread+0x138/0x150
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f832f91c>]
__ret_from_fork+0x3c/0x58
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f90ecf6a>]
ret_from_fork+0xa/0x40
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: no locks held by
cryptomgr_test/111.
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Last Breaking-Event-Address:
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f90c005e>]
__warn_printk+0x66/0x70
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: irq event stamp: 729
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: hardirqs last enabled at
(737): [<00000000f841f3b4>] __up_console_sem+0x8c/0xc0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: hardirqs last disabled at
(744): [<00000000f841f396>] __up_console_sem+0x6e/0xc0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: softirqs last enabled at (0):
[<00000000f837d6da>] copy_process+0x7fa/0x17d0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: softirqs last disabled at (0):
[<0000000000000000>] 0x0
Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ---[ end trace
0000000000000000 ]---

I tracked this down with git bisect to exactly your patch.
Looks like the testmanager needs an update also ... maybe use CRT
formated keys instead of ME keys ?!?

regards
Harald Freudenberger

2022-07-07 19:08:58

by Ignat Korchagin

[permalink] [raw]

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

On Thu, Jul 7, 2022 at 6:29 PM Harald Freudenberger
<[email protected]> wrote:
>
> On 2022-06-17 10:42, 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 <[email protected]>
> > Reported-by: kernel test robot <[email protected]>
> > ---
> > crypto/rsa.c | 78 ++++++++++++++++++++++++++++++++++++++++++++---
> > lib/mpi/mpi-add.c | 2 +-
> > lib/mpi/mpi-mul.c | 1 +
> > 3 files changed, 75 insertions(+), 6 deletions(-)
> >
> > diff --git a/crypto/rsa.c b/crypto/rsa.c
> > index 39e04176b04b..0e555ee4addb 100644
> > --- a/crypto/rsa.c
> > +++ b/crypto/rsa.c
> > @@ -17,6 +17,11 @@ struct rsa_mpi_key {
> > MPI n;
> > MPI e;
> > MPI d;
> > + MPI p;
> > + MPI q;
> > + MPI dp;
> > + MPI dq;
> > + MPI qinv;
> > };
> >
> > /*
> > @@ -35,16 +40,49 @@ static int _rsa_enc(const struct rsa_mpi_key *key,
> > MPI c, MPI m)
> >
> > /*
> > * RSADP function [RFC3447 sec 5.1.2]
> > - * m = c^d mod n;
> > + * m_1 = c^dP mod p;
> > + * m_2 = c^dQ mod q;
> > + * h = (m_1 - m_2) * qInv mod p;
> > + * m = m_2 + q * h;
> > */
> > -static int _rsa_dec(const struct rsa_mpi_key *key, MPI m, MPI c)
> > +static int _rsa_dec_crt(const struct rsa_mpi_key *key, MPI
> > m_or_m1_or_h, MPI c)
> > {
> > + MPI m2, m12_or_qh;
> > + int ret = -ENOMEM;
> > +
> > /* (1) Validate 0 <= c < n */
> > if (mpi_cmp_ui(c, 0) < 0 || mpi_cmp(c, key->n) >= 0)
> > return -EINVAL;
> >
> > - /* (2) m = c^d mod n */
> > - return mpi_powm(m, c, key->d, key->n);
> > + m2 = mpi_alloc(0);
> > + m12_or_qh = mpi_alloc(0);
> > + if (!m2 || !m12_or_qh)
> > + goto err_free_mpi;
> > +
> > + /* (2i) m_1 = c^dP mod p */
> > + ret = mpi_powm(m_or_m1_or_h, c, key->dp, key->p);
> > + if (ret)
> > + goto err_free_mpi;
> > +
> > + /* (2i) m_2 = c^dQ mod q */
> > + ret = mpi_powm(m2, c, key->dq, key->q);
> > + if (ret)
> > + goto err_free_mpi;
> > +
> > + /* (2iii) h = (m_1 - m_2) * qInv mod p */
> > + mpi_sub(m12_or_qh, m_or_m1_or_h, m2);
> > + mpi_mulm(m_or_m1_or_h, m12_or_qh, key->qinv, key->p);
> > +
> > + /* (2iv) m = m_2 + q * h */
> > + mpi_mul(m12_or_qh, key->q, m_or_m1_or_h);
> > + mpi_addm(m_or_m1_or_h, m2, m12_or_qh, key->n);
> > +
> > + ret = 0;
> > +
> > +err_free_mpi:
> > + mpi_free(m12_or_qh);
> > + mpi_free(m2);
> > + return ret;
> > }
> >
> > static inline struct rsa_mpi_key *rsa_get_key(struct crypto_akcipher
> > *tfm)
> > @@ -112,7 +150,7 @@ static int rsa_dec(struct akcipher_request *req)
> > if (!c)
> > goto err_free_m;
> >
> > - ret = _rsa_dec(pkey, m, c);
> > + ret = _rsa_dec_crt(pkey, m, c);
> > if (ret)
> > goto err_free_c;
> >
> > @@ -134,9 +172,19 @@ static void rsa_free_mpi_key(struct rsa_mpi_key
> > *key)
> > mpi_free(key->d);
> > mpi_free(key->e);
> > mpi_free(key->n);
> > + mpi_free(key->p);
> > + mpi_free(key->q);
> > + mpi_free(key->dp);
> > + mpi_free(key->dq);
> > + mpi_free(key->qinv);
> > key->d = NULL;
> > key->e = NULL;
> > key->n = NULL;
> > + key->p = NULL;
> > + key->q = NULL;
> > + key->dp = NULL;
> > + key->dq = NULL;
> > + key->qinv = NULL;
> > }
> >
> > static int rsa_check_key_length(unsigned int len)
> > @@ -217,6 +265,26 @@ static int rsa_set_priv_key(struct
> > crypto_akcipher *tfm, const void *key,
> > if (!mpi_key->n)
> > goto err;
> >
> > + mpi_key->p = mpi_read_raw_data(raw_key.p, raw_key.p_sz);
> > + if (!mpi_key->p)
> > + goto err;
> > +
> > + mpi_key->q = mpi_read_raw_data(raw_key.q, raw_key.q_sz);
> > + if (!mpi_key->q)
> > + goto err;
> > +
> > + mpi_key->dp = mpi_read_raw_data(raw_key.dp, raw_key.dp_sz);
> > + if (!mpi_key->dp)
> > + goto err;
> > +
> > + mpi_key->dq = mpi_read_raw_data(raw_key.dq, raw_key.dq_sz);
> > + if (!mpi_key->dq)
> > + goto err;
> > +
> > + mpi_key->qinv = mpi_read_raw_data(raw_key.qinv, raw_key.qinv_sz);
> > + if (!mpi_key->qinv)
> > + goto err;
> > +
> > if (rsa_check_key_length(mpi_get_size(mpi_key->n) << 3)) {
> > rsa_free_mpi_key(mpi_key);
> > return -EINVAL;
> > diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c
> > index 2cdae54c1bd0..9056fc5167fc 100644
> > --- a/lib/mpi/mpi-add.c
> > +++ b/lib/mpi/mpi-add.c
> > @@ -138,7 +138,7 @@ void mpi_sub(MPI w, MPI u, MPI v)
> > mpi_add(w, u, vv);
> > mpi_free(vv);
> > }
> > -
> > +EXPORT_SYMBOL_GPL(mpi_sub);
> >
> > void mpi_addm(MPI w, MPI u, MPI v, MPI m)
> > {
> > diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c
> > index 8f5fa200f297..7f4eda8560dc 100644
> > --- a/lib/mpi/mpi-mul.c
> > +++ b/lib/mpi/mpi-mul.c
> > @@ -82,6 +82,7 @@ void mpi_mul(MPI w, MPI u, MPI v)
> > if (tmp_limb)
> > mpi_free_limb_space(tmp_limb);
> > }
> > +EXPORT_SYMBOL_GPL(mpi_mul);
> >
> > void mpi_mulm(MPI w, MPI u, MPI v, MPI m)
> > {
> > --
> > 2.36.1
>
> Hello Ignat
> on s390 the linux-next kernel gives me this during startup:
Hi Harald,

The issue has been reported previously and I've submitted a follow up patch: [1]

[1]: https://patchwork.kernel.org/project/linux-crypto/patch/[email protected]/

> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: akcipher: decrypt test
> failed. err -22
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: akcipher: test 1 failed
> for rsa-generic, err=-22
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ------------[ cut here
> ]------------
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: alg: self-tests for
> rsa-generic (rsa) failed (rc=-22)
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: WARNING: CPU: 6 PID: 111 at
> crypto/testmgr.c:5773 alg_test+0x348/0x4d0
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Modules linked in:
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: CPU: 6 PID: 111 Comm:
> cryptomgr_test Not tainted 5.19.0-rc5-next-20220706 #1
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Hardware name: IBM 8561 T01
> 703 (LPAR)
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl PSW : 0704d00180000000
> 00000000f8b15ab4 (alg_test+0x34c/0x4d0)
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: R:0 T:1 IO:1 EX:1
> Key:0 M:1 W:0 P:0 AS:3 CC:1 PM:0 RI:0 EA:3
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl GPRS: c0000000fffeffff
> 0000000080000000 0000000000000035 0000000000000000
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: 0000000000000001
> 0000000000000001 000000008da15c80 000000000000000d
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: 000000008da15c00
> 00000000ffffffff 00000380000000b6 ffffffffffffffea
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: 000000008cd53200
> 00000000fb19dfd0 00000000f8b15ab0 0000038004847cf8
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Krnl Code: 00000000f8b15aa4:
> c02000523738 larl %r2,00000000f955c914
> 00000000f8b15aaa:
> c0e5002d52a7 brasl %r14,00000000f90bfff8
> #00000000f8b15ab0:
> af000000 mc 0,0
> >00000000f8b15ab4:
> b904002b lgr %r2,%r11
> 00000000f8b15ab8:
> eb6ff1300004 lmg %r6,%r15,304(%r15)
> 00000000f8b15abe:
> 07fe bcr 15,%r14
> 00000000f8b15ac0:
> 47000700 bc 0,1792
> 00000000f8b15ac4:
> 1829 lr %r2,%r9
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Call Trace:
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f8b15ab4>]
> alg_test+0x34c/0x4d0
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ([<00000000f8b15ab0>]
> alg_test+0x348/0x4d0)
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f8b13b98>]
> cryptomgr_test+0x68/0x70
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f83b4be8>]
> kthread+0x138/0x150
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f832f91c>]
> __ret_from_fork+0x3c/0x58
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f90ecf6a>]
> ret_from_fork+0xa/0x40
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: no locks held by
> cryptomgr_test/111.
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: Last Breaking-Event-Address:
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: [<00000000f90c005e>]
> __warn_printk+0x66/0x70
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: irq event stamp: 729
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: hardirqs last enabled at
> (737): [<00000000f841f3b4>] __up_console_sem+0x8c/0xc0
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: hardirqs last disabled at
> (744): [<00000000f841f396>] __up_console_sem+0x6e/0xc0
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: softirqs last enabled at (0):
> [<00000000f837d6da>] copy_process+0x7fa/0x17d0
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: softirqs last disabled at (0):
> [<0000000000000000>] 0x0
> Jul 07 11:50:28 t35lp54.lnxne.boe kernel: ---[ end trace
> 0000000000000000 ]---
>
> I tracked this down with git bisect to exactly your patch.
> Looks like the testmanager needs an update also ... maybe use CRT
> formated keys instead of ME keys ?!?
>
> regards
> Harald Freudenberger
>
>
>

Regards,
Ignat