Fix for RSA Blinding

NIIBE Yutaka gniibe at
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) [0], 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.

[0] Timing Attacks on Cryptosystems:

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.

More information about the Gcrypt-devel mailing list