# Fix for RSA Blinding

NIIBE Yutaka gniibe at fsij.org
Fri Jan 31 02:41:10 CET 2014

```I got an idea or two for improvements around our implementation of RSA
Blinding (in the function rsa_decrypt in cipher/rsa.c).

For RSA Blinding, we need a random value R (0 <= R <= N - 1, coprime
to N) and R^-1 mod N.  We use R^e to encode input, and use R^-1 to
decode output.

Currently, the procedure is like:

(a) Get R.

(b) Compute R^-1 mod N.  When fail (R is not coprime to N), go back
to (a).

(c) Compute R^e

My idea is:

(1) We can use Chinese Remainder Theorem (CRT) to construct R and
R^-1.  Procedure will be like:

(a1) Get R1.
Go back to (a1), if it's not 0 < R1 < p.

(a2) Get R2.
Go back to (a2), if it's not 0 < R2 < q.

(b') Compute m1 = R1^-1 mod p and m2 = R2^-1 mod q.
Then compute R^-1 with the expression:

h = u * (m1 - m2) mod q
m = m1 + h * p

R^-1 = m

(c') Compute R^e by R1 and R2, likewise.

(2) I read the RSA Bulletin #2 (January 1996) , and it was
suggested to use deterministic way for getting random value R.  I
think that the basic idea is as same as the one of RFC 6979.
It would be good to introduce this method.

 Timing Attacks on Cryptosystems: ftp://ftp.rsa.com/pub/pdfs/bull-2.pdf

Well, I will implement (1) above, when I will have time.  I think that
it will be somewhat faster, then.  The mathematical proof of (1) is
left as my homework.
--

```