This ticket is for possible RSA improvement.
Description
Status | Assigned | Task | ||
---|---|---|---|---|
Invalid | • gniibe | T3264 Possible RSA improvement | ||
Resolved | • gniibe | T3269 (Constant-time) modular reduction |
Event Timeline
In search of algorithm, I found this slide:
http://www1.spms.ntu.edu.sg/~ccrg/documents/chienning-multiexponentiation.pdf
If not patented, it seems for me it's worth considering.
Paper: https://link.springer.com/article/10.1007/s13389-012-0032-4
And his thesis:
http://ir.lib.ncu.edu.tw:88/thesis/view_etd.asp?URN=89522019
(The page is mainly in Chinese, but his thesis is in English.)
The part of using Simultaneous Multiple Exponentiation (SME) for RSA is not patented, I think.
So, let me consider with SME.
Now, libgcrypt 1.7.7 does:
Given:
dP = d mod (p-1)
dQ = d mod (q-1)
q_inv = q^-1 mod p
and cipher text input of original_c, and random byte of rand,
we compute:
rand_inv = rand ^ -1 mod n
c = original_c * rand ^ e mod n
m1 := c ^ dP mod p
m2 := c ^ dQ mod q
h := q_inv * (m1 - m2) mod p
m := m2 + h * q # m := c ^ d mod n = original_c ^ d * rand ^ (e*d) mod n = original_c^d * rand mod n
m_output := m * rand_inv mod n # m_output := original_c^d mod n
That is, it uses base blinding to avoid the computation is somehow controlled by the input.
And now, 1.7.8 introduced exponent blinding, because the modular exponentiation computation leaks some signal.
Using SME technique, we can delete computation of rand_inv.
rand1 := length as same as p
rand2 := length as same as q
m1 := c^dP * rand1^(p - 1) mod p # by SME
m2 := c^dQ * rand2^(q - 1) mod q # by SME
h := q_inv * (m1 - m2) mod p
m := m2 + h * q
Here, rand1^(p -1) = 1 and rand2^(q - 1) = 1, as p and q are prime.
If SME computation with nonce can blind leaked signal, this is a bit simpler than base blinding + exponent blinding.
Bonus is that it can be also applied to general case (no CRT).