# Bitwise method of generating r for RSA-KEM

It seems that RSA-KEM has a very troublesome method of generating the secret $r$. It seems that the random value needs to be in the range $0 \le r \le {n - 1}$.

Now most cryptographic environments don't have a random number generator that generates those kind of numbers; usually they are just provided with a seeded DRBG that outputs full bytes. Performing all kinds of integer operations on the bytes may lead to leaks of the master key within these kind of environments. Especially the $\bmod$ operation seems to be tricky in this regards.

Is there a known good way of generating $r$ that disposes of the $\bmod$ operation and possible looping?

For instance I could think of constructing $r$ as

00 | R


The | operation is of course concatenation.

In this construction $R$ is then an octet string consisting of (pseudo) random bytes. $r$ consists of the value of 00 | R when used as a big endian unsigned integer. It can be used directly as input to raw "RSA encryption" as implemented by most libraries.

That would provide $\operatorname{len}(R) * 8$ bits of entropy for the KDF. I think that would be $\lfloor (log_2(n) - 1) / 8\rfloor \cdot 8$ bits of entropy when measured against the modulus value $n$.

The scheme would otherwise be unaltered of course; there would be no explicit checks on the value of $r$ during decryption.

Would this suffice as a secure scheme of constructing $r$ instead of performing integer calculations and checks to get to $0 \le r \le {n - 1}$?

• This is half a suggestion/half a question regarding "Is there a known good way of generating m that disposes of the mod operation and possible looping?": I have been using (data && mask) || floor, where mask is equal to (1 << required_bits) - 1 and floor is set to the minimum bound to retrieve a value x: floor <= x <= mask. This appears to provide me with a value in the appropriate range in constant time, but I am not certain of how "clean" it is in terms of bias or if it's helpful to you here (I see you need x < y <z whereas I need x <= y <= z). Mar 28 '16 at 16:19
• Why do you require $1<m$? I see no issues with $0$ and $1$. Mar 28 '16 at 16:56
• It should be straightforward to show that reducing the space of the message by 1 bit can't reduce security by more than 1 bit. Mar 28 '16 at 17:06
• Since a CSPRNG seeded from a low/no entropy seed still produces a random looking sequence, that doesn't seem like a worthwhile protection to me. Also mapping 0 to 2 won't help you in that case, since you can guess it just as easily. Mar 28 '16 at 17:13
• @CodesInChaos I've removed the > 1 requirement from the quesetion, I'll probably edit the Wikipedia article to be more scientific (or at least correct). Mar 29 '16 at 8:58

Here are a few options. I include modular reduction and rejection sampling because I suspect they are less costly than you worry.

1. What you suggested, roughly: Pick $$r$$ uniformly in $$\{0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor} - 1\}$$.

If there were an IND-CCA2 or NM-CCA2 adversary with success probability $$p$$ against RSA-KEM with $$r$$ uniform in $$\{0, 1, 2, \dots, n - 1\}$$, the success probability of the same adversary can't be more than $$2p$$ since we're removing less than half the possible space of $$r$$. If $$2p$$ was too high, then $$p$$ was almost certainly too high already. If you set the high byte to zero, as you suggested, then you remove more of the output space and it's $$256p$$ instead of just $$2p$$.

Theoretical concern: The standard security reduction to the RSA problem[1], which demonstrates how to turn an IND-CCA2 attacker into a procedure to compute $$e^{\mathit{th}}$$ roots modulo $$n$$, would no longer apply, because a little under half the space is guaranteed not to be covered. It's a little hard to imagine that the general RSA problem is hard, but becomes easy if you restrict it to this domain; however, the more space you eliminate, the more irrelevant the reduction becomes to justifying the security, so better to set the high bit to zero than to set the high byte to zero as you suggested.

2. Modular reduction: Pick $$r$$ uniformly in $$\{0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor + k} - 1\}$$ where $$k$$ is, say, 64, or 256 if you're paranoid or $$\lfloor\log_2 n\rfloor$$ if you're really paranoid, and reduce modulo $$n$$.

You don't need a general purpose division routine: You can easily reduce $$r$$ modulo $$n$$ in constant time with Barrett reduction using only two multiplications and a subtraction, if you precompute $$2^{\lceil\log_2 n\rceil}/n$$ (with bit-by-bit long division in constant time if $$n$$ is ever secret), as long as $$r < n^2$$.

This doesn't give a uniform distribution, but it's awfully close—much closer than option (1), if for no other reason than that it doesn't completely exclude any of $$\mathbb Z/n\mathbb Z$$ like (1) does. (Exercise for the reader: Quantify the modulo bias in, say, total variation distance—this puts a similar bound on the advantage of an IND-CCA2 or NM-CCA2 adversary vs. a true uniform distribution.)

3. Rejection sampling: Pick $$r$$ uniformly in $$\{0, 1, 2, \dots, 2^{\lceil\log_2 n\rceil} - 1\}$$, and start over if $$r \geq n$$.

Since $$2^{\lceil\log_2 n\rceil}/2 < n < 2^{\lceil\log_2 n\rceil}$$, the number of trials is geometrically distributed with probability $$p < 1/2$$; the expected number of trials is just over 1 and well below 2. You will obviously never see more than 128 trials—for a 4096-bit RSA modulus, you need to generate much less than 4096 KB of data.

This guarantees a uniform distribution for $$r$$ in $$\{0, 1, 2, \dots, n - 1\}$$.

• So 1. would be my idea, 2. would be modular reduction and 3. would be rejection sampling I assume? Well, I know, but it's not in the text. Feb 21 '19 at 9:16