Hi Nazar,

On 24/04/2020 10:22, Nazar Chornenkyy via mbed-tls wrote:

On the PSoC6 device we are using mbedtls_rsa_gen_key function with a good hardware TRNG passed FIPS 140-2 verification.

This function verifies generated random pair and requests new pair if they don’t follow FIPS 186-4 criteria.

The number of verification loops is between 1 and 6 in worst case.

Is it expected behavior?

The arithmetic of one loop takes a lots of time.

How can we improve the random number to have always pass FIPS 186-4 in a one loop?

I'm not sure what you're doing. Are you calling mbedtls_rsa_gen_key() multiple times and rejecting the key if it doesn't pass additional checks? Or are you just calling it once?

As far as I know, mbedtls_rsa_gen_key() follows the procedure described in FIPS 186-4 (which is compatible with previous versions of FIPS 186), and no additional checks should be needed.

If you're calling it once and observing that it tries multiple values of p and q before finding a suitable one, this is expected behavior. There's no way to "improve" the random numbers to make it faster: the probability that a pair of (probabilistic) primes can work together as an RSA key is less than 1. I don't know the math off the top of my head, but 1–6 tries seems reasonable.

Key generation is the slowest of the RSA operations. If that's a problem in your application, consider using elliptic curve cryptography instead. ECC has very fast key generation, faster private key operations (signature, decryption) than RSA, and smaller keys. The main benefit of RSA is that public key operations (verification, encryption) are faster.

-- Gilles Peskine Mbed TLS developer

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.