2
$\begingroup$

To prevent some side-channel attacks in RSA, I've seen people use multiplicative blinding $$ a^d\bmod N=(r^{-1})^d(ra)^d\bmod N $$ or additive exponent blinding $$ a^d=a^{d+r\phi(N)}\bmod N. $$ However, I've recently come across something that might be called "modulus blinding" where the modulus $N$ is multiplicatively randomized and some other operations are performed (hard to follow the code I'm looking at).

I thought maybe this was protection against fault injection in CRT implementations, but the library I was looking at did this in both their "plain" and CRT implementation. Sorry I don't have more details; I'm specifically looking at NXP code mcuxClRsa_PrivatePlain.c and mcuxClRsa_PrivateCrt.c from an SDK for the FRDM-MCXN947 board (although I assume the code would be similar for other processors). Anyone can grab it after creating an NXP account.

If anyone can tell me what they're doing or might be doing (given my vague description), I'd appreciate it.

[Other weird things in that library: only 32 bits for the blinding in RSA and ECC (mcuxClEcc_Internal_GenerateMultiplicativeBlinding.c), so not uniformly random, and they do exponent blinding for RSA but by taking an exponent and dividing by a random 64-bit number $b$, $d=bq+r$, again not uniformly random, but maybe it's fine practically speaking.]

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think the technique discussed computes $c=m^e\bmod N$ by picking an arbitrary $r>0$, computing $N'=N\;\!r$, then $c'=m^e\bmod N'$, then $c=c'\bmod N$. Justification: if $N\in\mathbb N^*$ divides $N'\in\mathbb N^*$, then for all $x\in\mathbb Z$ it hold $x\bmod N\,=\,(x\bmod N')\bmod N$, applied for $x=m^e$.

If $r$ is random the objective is likely blinding to improve resistance to side-channel attacks. That makes some degree of sense even when raising to a public exponent modulo a public modulus: for encryption (what's encrypted is secret), or when verifying a secret signature. And of course that makes sense when the exponentiation is modulus a secret $p$ or $q$, rather than $N$.

Or (less likely), with $r$ fixed for a given $N$, the objective might be to use a more convenient modulus, e.g. we can pick $r$ so that the bit size of $N'$ fits some hardware, or/and a number of high bits of $N'$ are $1$ to facilitate (non-Montgomery) modular reduction.

This can be combined with additive blinding: pick arbitrary $r>0$ and $r'\in[0,r)$, compute $N'=r\;\!N\,$, $\dot m=m+r'\;\!N\,$, $c'=\dot m^e\bmod N'\,$, $c=c'\bmod N$. Even 32-bit $r$ and $r'$ add sizable noise in power analysis measurements, making whole classes of attacks more difficult, with only modest extra work.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Maybe not clear for all, however, $N\mid N'$ implies the $c=c'\bmod N$. The proof needs a little arithmetic. This is done to decorrelate the modulus and the exponent. Also, it is common to use Montgomery Reduction and Modulus binding one after. I've no idea that one can use both simultaneously, it may be the opposite of blinding due to fixed size for the Montgomery. $\endgroup$ Commented Sep 28 at 20:44
  • $\begingroup$ This is what it looks like, but I wondered if there was anything more to it since it doesn't randomize the exponentiation operations (just the reduction and register states). $\endgroup$ Commented Sep 29 at 15:06

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.