Fix for RSA Blinding
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
Currently, the procedure is like:
(a) Get R.
(b) Compute R^-1 mod N. When fail (R is not coprime to N), go back
(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.
More information about the Gcrypt-devel