Page MenuHome GnuPG

Possible RSA improvement
Closed, InvalidPublic

Description

This ticket is for possible RSA improvement.

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.)

Another area would be faster (constant time) Barrett reduction.

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).

RSA improvement is not that worth now.