白話導讀
Journal of Systems and Software
SCI · Q1
2009/09
Rebalanced-RSA 把解密變快了，卻讓加密慢到不能用
Trading Decryption for Speeding Encryption in Rebalanced-RSA
Hung-Min Sun, Mu-En Wu, M. Jason Hinek, Cheng-Ta Yang
一句話： Rebalanced-RSA 把解密成本轉嫁給加密，結果加密慢到極致（因為公開指數 e 的量級與模數相當）。作者提出兩個變形，讓 e 遠小於模數 ：1024-bit 下 Scheme A 加密至少快 2.6 倍 、Scheme B 至少快 3 倍 ——代價是解密與金鑰生成稍慢。
先問：這在解什麼問題？the problem
RSA 的加速史，是一連串的「拆東牆補西牆」：
1982
RSA-CRT
Quisquater 與 Couvreur 提出以中國剩餘定理（CRT）為基礎的 RSA 變形，用來加速 RSA 的解密 。
1990
Rebalanced-RSA
Wiener 提出另一個變形，把解密的成本轉嫁到加密上 ，讓解密再更快。
代價
加密變成最慢
但這個做法本質上把加密時間推到最大 ——因為公開指數 e 的量級通常與 RSA 模數相當。
換句話說：Rebalanced-RSA 把解密變快了，卻讓加密慢到幾乎不能用。這篇論文要做的，就是把那筆「借」過頭的成本還一點回去 。
怎麼做？讓公開指數 e 遠小於模數the method
作者提出兩個 Rebalanced-RSA 的變形，讓公開指數 e 遠小於模數 ，藉此降低加密成本，同時仍維持低解密成本 。
RSA-CRT
加速解密
Rebalanced-RSA
解密再更快
但 e ≈ 模數
加密變成最慢
本文：e 遠小於模數
Scheme A／B
研究脈絡：從 RSA-CRT 到 Rebalanced-RSA，解密越來越快但加密被推到最慢；本文的兩個變形讓公開指數 e 遠小於模數，把加密成本拉回來。
結果如何？results
在 1024-bit RSA 模數 下：
A Scheme A加密速度至少比原始的 Rebalanced-RSA 快 2.6 倍 。
作者自己標註的代價： 這兩個變形加密成本的下降，是用略為增加的解密成本 與增加的金鑰生成成本 換來的。因此作者明白指出：這裡提出的變形，最適合那些「加密與解密都需要低成本」的應用 ——而不是宣稱它在所有情境下都更好。
閱讀原始論文（ScienceDirect） →