On the Design and Cryptanalysis of Efficient RSA Variants

基於高效能的RSA 變形設計與分析

吳牧恩(Mu-En Wu)

指導教授 ： 孫宏民

國立清華大學/電機資訊學院/資訊工程學系/博士(2009年)

https://doi.org/10.6843/NTHU.2009.00048

摘要

RSA is the most widely used public-key cryptosystem in the world. However, there are still two main shortcomings when using this system. One is the inefficiency in encryption/decryption, and the other one is high cost for key storage requirement. In this thesis, we focus on designing efficient RSA variants to improve the efficiency of operation or storage requirement. We design three RSA variants, including Generalized Rebalanced-RSA, Dual RSA, and LSBS-RSA. We briefly describe them in the following:

Generalized Rebalanced-RSA is an RSA variant based on the CRT-decryption. The term "Rebalanced" denotes speeding up RSA decryption by shifting decryption costs to encryption costs. In our design, we let the public exponent e being much smaller than the modulus N, while still maintaining the CRT-exponents small. Thus,the goal of efficient encryption and decryption are achieved simultaneously. Dual RSA is an RSA variant whose key generation algorithm outputs two distinct RSA key pairs having the same public and private exponents. This variant can be used in scenarios that require two instances of RSA with the advantage of reducing the storage requirements for the keys. We also propose two applications for Dual RSA,
blind signatures and authentication/secrecy.

LSBS-RSA is the traditional RSA system but with modulus prime sharing least significant bits (LSBs). This property can be used in server-aided signature generation (SASG) to improve the computational efficiency. We give the detailed security analysis for LSBS-RSA and specify the tightly security boundary by using the lattice reduction technique.

All the cryptanalysis of the proposed variants show that the systems require higher security boundary while comparing with the traditional RSA. This is a trade-off
phenomenon between the security level and efficiency. Thus, we finally point out that one should be more careful when using other kinds of RSA variants.

關鍵字

密碼學 ； 密碼分析 ； RSA ； 加密 ； RSA Small-e ； RSA Small-d ； Rebalanced ； CRT-公式 ； 格子點基底化 ； LLL 演算法 ； Twin RSA ； LSBS-RSA

並列摘要

RSA 為世界上最為廣泛使用的公開金鑰密碼系統。然而，在使用RSA 時仍然有兩項主要的缺點。一個是在加密與解密上的耗時；另一個是在金鑰儲存上需要較大的儲存空間。在本論文裡，我們提出三種RSA 變形設計去改善RSA 運算的效率， 或降低金鑰儲存的空間， 三種RSA 變形分別為Generalized Rebalanced-RSA、Dual RSA、LSBS-RSA。我們分別介紹如下： Generalized Rebalanced RSA 是一種基於CRT 解密的RSA 變形設計。"Rebalanced"表示將部分解密的工作代價轉移到加密上面。在我們的設計裡，我們讓公開金鑰e 遠比模數N 短，卻仍然保持短的CRT 指數。因此，我們可達到同時有效加密與解密的目標。 Dual RSA 是一種將兩組RSA 公開金鑰與私密金鑰合併在一起的RSA 變形設計 (具有相同的公開金鑰指數與私密金鑰指數)。這樣的變形設計可以使用在需要兩組RSA 密碼系統的環境，以節省金鑰儲存的空間。我們也提出了兩種DualRSA 的應用：盲簽章與 認證且私密通訊。 LSBS-RSA 為傳統的RSA 密碼系統，但是RSA 模質數具有大量相同的最低位元(LSBs)。這樣的特型可以增加Server-Aided Signature Generation (SASG)的計算效率。我們藉由格子點化簡的技巧給出完整的安全分析，並指出緊緻的安全邊界條件。 我們的分析指出所有的RSA 變形設計皆需要更高的安全邊界條件。這是一種在安全程度與效率上的Trade-Off 現象。所以，在本論文最後，我們結論使用者要更小心當使用其他的RSA 變形演算法。

並列關鍵字

Cryptography ； Cryptanalysis ； RSA ； encryption ； RSA-Small-e ； RSA-Small-d ； Rebalanced RSA, ； CRT-equation ； lattice basis reduction ； LLL algorithm ； Twin RSA ； LSBS-RSA

參考文獻

[1] S. Berkovits. Factoring via superencryption. Cryptologia, 6(3): 229-237, 1982.

[2] M. Bellare and P. Rogaway, “Optimal asymmetric encryption –how to encrypt

with RSA”, Advances in Cryptology - EUROCRYPT’94, Lecture Notes in Com-

[3] M. Bellare and P. Rogaway, “The exact security of digital signatures: How to sign

[4] D. Boneh, G. Durfee, and Y. Frankel, “An attack on RSA given a small fraction of