# How much risk is there for RSA blinding random number not being relatively prime to N

I'm working on the blinding portion of some RSA code. Some implementations I've looked at don't verify that the random number used for blinding is relative prime to N as described on the Wikipedia page for blinding:

RSA blinding involves computing the blinding operation E(x) = (xr)e mod N, where r is a random integer between 1 and N and relatively prime to N (i.e. gcd(r, N) = 1)

I assume this is because finding the blinding factor is expensive (is GDC the fastest/only way?). That being said, how much of a security risk does the random number used for blinding not being relatively prime to N pose?

That being said, how much of a security risk does the random number used for blinding not being relatively prime to N pose?

None, for two reasons:

• The probability of it happening is absurdly tiny; of the $$n=pq$$ numbers in the range $$[0, n)$$, there are $$p+q-1$$ values that are not relatively prime to $$n$$. Hence, if you select a value from the range randomly, the probability of it being between relatively prime is $$(p+q-1)/pq < 2/q$$ (where $$q$$ is the smaller factor). If $$q$$ is a 1024 bit number (which is should be if you're doing RSA-2048), well, anything that happens with probability $$2^{-1023}$$ can be safely assumed not to happen - you'd have better odds at winning the lottery 30 times in a row.

• If, by some miracle, that does happen, it's not a security issue - you just won't be able to unblind. The unblind step involves the computation of $$r^{-1} \bmod n$$; if $$r$$ is not relatively prime to $$n$$, that'll fail. If we look at things more closely, we find that it's not an issue with the unblind algorithm, but with the problem itself - what happens is that, in this case, the $$xr$$ computation will lose information about $$x$$ - for example, if $$\gcd(r, n) = p$$, then $$xr$$ will contain no information about $$x \bmod p$$ - because of that, you won't be able to restore that information in the unblind step.

• I agree with the first point, but if it did occur and the anomaly was clear to everyone, then adversaries would be able to factor $n$ by taking a GCD of $N$ with the $E(x)$. Dec 30, 2022 at 18:05
• Even not being able to unblind is a big problem in my mind, even if it turned out not to be a security problem. Seems like confirming r is relative prime to n is the safest way to go, even if it is expensive. Dec 30, 2022 at 19:04
• If that is your concern, aren't you also concerned with far more likely events that may also prevent you from unblinding; say, a meteor just happens to strike your computer at the right time... Dec 30, 2022 at 19:31
• @DanielS: if an adversary wants to factor $n$, there are easier ways than collecting $E(x)$ and computing $\gcd( n, E(x))$ - he can pick random values $r$ and compute $\gcd(n, r)$ - exactly the same success probability, and he doesn't have to wait for $E(x)$. Or, better yet, he can use a real factorization method... Dec 30, 2022 at 20:16
• @ubiquibacon: it doesn't really matter, but if you want to be precise, I'd use $1 \le r < n$; that skips the value 0, however you don't want to use that value anyways (and 1 is not a security risk). Also, you don't really need the GCD - if you try to compute $r^{-1} \bmod n$, and it fails, then you know $r$ and $n$ are not relatively prime - and you need to compute that anyways. All you need to do is compute that before you publish the blinded value. Dec 30, 2022 at 21:33