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

ubiquibacon

12/30/23, 4:05 AM

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?

1 + 0

blinding

Score:1

Crypto

poncho

12/30/23, 5:14 AM

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.

+ 6

Daniel S

12/30/23, 6:05 PM

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)$.

ubiquibacon

12/30/23, 7:04 PM

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.

poncho

12/30/23, 7:31 PM

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...

poncho

12/30/23, 8:16 PM

@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...

ubiquibacon

12/30/23, 9:29 PM

@poncho, haha, my keen senses are picking up some sarcasm. My project is on a low power microcontroller, so I was worried that the GDC calculation would be too expensive, but it actually doesn't take too long (less than a second). And while I am afraid of random meteors, I'm more afraid of someone saying my code is sub-par and doesn't cover corner cases. Speaking of corner cases, the Wikipedia page I linked to doesn't specify inclusivity. I.e. which of the following should be my random number criteria? `1 < r < n` or `1 <= r <=n`

poncho

12/30/23, 9:33 PM

@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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.