Key generation times vs CPU load

Does the key generation time affect the CPU load in a mobile phone, an embedded device? I am searching on Google for info, but I am not fully sure that I have concluded to something.

• Note that, a good question should include your searches and confusions, too. With that, you will get more upvotes to your post. – kelalaka Jul 12 at 11:45
• The most common key generations on a smart phone would most likely be (EC)DHE ephemeral keys for TLS handshakes, and yes those can introduce minor delays. That's why session resumption and Keepalives improve Web Browser experience. – eckes Jul 12 at 14:46

Any generation will consume CPU, but it is rather unlikely that you will find that it slows down a modern smart phone.

Of the known algorithms - barring post-quantum cryptography - common two-prime RSA has the most CPU intense generation technique as it needs to find two large primes. However, RSA key pairs are normally used as long term, static key pairs. So generally applications only create them once in a while. And barring client authentication, they aren't required for setting up e.g. TLS connections.

Symmetric key pair generation is limited to random number generation. As long as the secure RNG doesn't block it is extremely unlikely that you'd notice any slowdowns for normal use cases with just a few keys. And if it does block it won't affect the CPU; it will only affect the application that requires the keys. (EC)DH key pair generation is relatively fast as well.

Finally, it is always possible to botch an implementation. You could try and create a random number generator that uses a lot of CPU or memory access to retrieve enough entropy. This could e.g. be used by programmers that use an API that lacks access to the normal cryptographic operations, e.g. when using a cross compatible, high level runtime.

• Note that, this totally depends on the encryption scheme. For example, one of the FHE schemes of the N. Smart, was requiring around one-minute for the one-time key generation. That was on a desktop. Also, Removing the Linux /dev/random blocking pool – kelalaka Jul 12 at 11:47

If you mean symmetric keys, generation does not require much CPU resources. Usually, operating system provides some source of entropy. Generation of a key based on this is trivial.

Keys for asymmetric schemes are based on prime numbers. The essential part of key generation is generation of prime numbers.

Many devices (PCs, laptops, tablets, smartphones) use probabilistic approach for generation of prime numbers. Briefly, when Rabin-Miller test is used, it looks as follows . You generate some initial number. Then estimate if this number is composite with probability $$1/2^n$$. If you see that the number is composite, not prime, you generate a new candidate and start from the very begin. If the check shows that the candidate is composite with probability not higher than $$1/2^n$$, you check if it is composite with probability not higher than $$1/2^{n+1}$$, then with probability $$1/2^{n+2}$$, etc., until the probability that the candidate is composite (that it is not prime) is less than threshold that you accept.

See details here.

All these operations need CPU a lot. Means, if CPU is loaded with other tasks, the time needed to find a prime number may be longer compared to the case when CPU is not loaded with other tasks.

CPU load depends also on the hardware used. If the hardware supports the cryptographic operations you use, it loads CPU less. Execution of the same operations implemented in software loads CPU more.

• Are there a reference for the last paragraph? – kelalaka Jul 12 at 11:54
• @just_learning: 1) Key management is more about the process (even if it includes key generation). So you I would not connect it with CPU load. 2) CPU load depends on what cryptographic functionality is embedded in hardware. 3) ECC provides the same strength as RSA with shorter keys. Thus key generation for ECC can require less time and can load CPU less. 4) To protocol: Usually, time for network communication is much longer than the time used by CPU. Thus CPU is usually not a bottleneck. – mentallurg Jul 12 at 12:30
• @kelalaka: To fixed time: I am not aware of any formula that provides upper time limit for a give device. Do you find this statement confusing? To time distribution: I have just generated with openssl 10 RSA keys of 8192 bits. Times were: 58, 11, 6, 7, 52, 42, 28, 47, 13, 12 s. – mentallurg Jul 12 at 12:41
• One can go with some probability on the distribution of the primes, that is too much for this question. Also, you did not mention the Rabin-Miller while you are talking about the probability. – kelalaka Jul 12 at 14:25
• @kelalaka: To Rabin-Miller: The answer I linked describes it well. But since you find it helpful, I mentioned Rabin-Miller explicitly. To distribution: you are right, if one searches many prime N-bit numbers, on average one would need to test ~N*0,7 candidates for each prime (ln(2) ~= 0,7). But again you are right, it is out of scope of this question. I have deleted the last paragraph. – mentallurg Jul 12 at 21:33