0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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)$. $\endgroup$
    – Daniel S
    Dec 30, 2022 at 18:05
  • $\begingroup$ 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. $\endgroup$ Dec 30, 2022 at 19:04
  • $\begingroup$ 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... $\endgroup$
    – poncho
    Dec 30, 2022 at 19:31
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Dec 30, 2022 at 20:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – poncho
    Dec 30, 2022 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.