# RSA-KEM: minimal number of random bits

I've already asked a few - as yet officially unanswered - questions about RSA-KEM with regards to the input secret encrypted using the public key here and (less on topic for this question) here.

CodesInChaos already commented in the first question linked to. It seems logical that having the most significant bit set to zero during generation of the random value $z$ to not impact security all that much.

Still, the use of random number generators for large amounts of data can be a draw back of the mode of operation, especially when they are required to generate 4096 bits of randomness for a single RSA operation. This could be an issue if said random number generator is slow or if insufficient entropy is available to the random number generator.

My related questions are:

1. Can we reduce the amount of input keying material to the KDF further without reducing the security of the RSA operation? If yes, by how much?

2. If yes, is there a good distribution of random bits required (half to the left, half to the right?)

3. If no, could we use a one-way primitive such as a XOF or indeed MGF-1 after retrieving the required number of bits for secure key derivation, and feed that to RSA-KEM?

Or should I just run away and use RSA OAEP instead if I run into situations where a fast DRBG is not available?

• If the PRNG provides sufficient entropy for 32-bytes, you could use a stream-cipher like ChaCha20 to expand the random bytes by using them as key... AFAIK libsodium does something like this internally. – K. Biermann Nov 17 '17 at 16:22
• Your 3rd paragraph is seems nonsensical. If a RNG is cumbersome, what do you call RSA and it's tentacles? Are you actually hinting at something else? – Paul Uszak Nov 17 '17 at 16:28
• Ok, what I meant was that requesting large amounts of data from a DRBG can be cumbersome; I'll adjust the question. – Maarten - reinstate Monica Nov 17 '17 at 16:35
• If requesting large amounts of data from a DRBG is cumbersome…get a better DRBG? You want a uniform random element of $\mathbb Z/n\mathbb Z$; the modulo bias at worst, for a modulus $n$ halfway between the generating power of two and the next one below, puts same mass in $[0,n/3)$ it puts in the double-length $[n/3,n)$. Usual heuristic is to pick $2\lceil\log_2n\rceil$ as the number of bits from which to reduce $n$ (e.g., why Ed25519 uses SHA-512 to get 256-bit scalar); I leave it as exercise for reader to quantify how nonuniform this is, and whether $256+\lceil\log_2 n\rceil$ is enough. – Squeamish Ossifrage Nov 17 '17 at 16:50
• @daniel No, that's for key pair generation, I was talking encryption. Encryption needs a random component as well, and with RSA-KEM the random component is a random number between $0$ and $n$, the modulus, which is used to derive the symmetric key, which is used to encrypt the message. – Maarten - reinstate Monica Nov 18 '17 at 1:34

Practical concern. If you don't generate all of the bits of the element $x \in \mathbb Z/n\mathbb Z$ from which you derive a key $k = H(x)$, even if you spread them out so that the standard real number cube root attack doesn't work on exponent $e = 3$, you may nevertheless be walking headfirst into the Franklin–Reiter related-message attack, which applies even to exponent $e = 65537$ that everyone quietly accepts without the PTSD over $e = 3$ left from the dark ages of cryptography engineering in the '90s.
Performance concern. It costs at best about 20k cycles on a modern AMD CPU to compute $x^3 \bmod n$ for 2048-bit $n$—the faster half of RSA with the fastest exponent; any other exponent is slower (except perhaps in Rabin territory), and decryption is much slower. It costs at worst about 1k cycles to generate 2048 bits with Salsa20 using naive C code, and that's about the easiest option, not the cheapest option.
OAEP also needs to generate about $\lg n$ bits of data, but usually with a much more expensive PRNG (‘MGF’), such as SHA-256. Under what circumstances could the generation of $x$ be a bottleneck, but not the MGF computation of OAEP?