在科技日益發達的現今社會，資訊安全是一項非常重要的技術，而RSA密碼系統即是目前最為廣泛使用的公開金鑰密碼系統，其不僅被許多世界級的公司用在其所開發的作業系統裡，如視窗程式、麥金塔、Novell等…，更被設計使用在一般的硬體設備裡面，例如網路電話、網路卡、智慧卡等 等….。另外，在密碼學上的許多通訊協定，也時常隱含RSA密碼系統的機 制。RSA之所以受到廣泛大眾的喜愛，最主要是因為此系統是植基於分解大因數的困難度上，具有相當高的安全性。自古以來，因數分解一直是許多數學家與密碼學家研究的問題，然而，始終找不到一套有效率的演算法去完成這項艱難的工作，所謂有效率即是在多項式時間內可以完成。即使目前並沒有研究證明，破解RSA密碼系統的困難度等同於解決因數分解問題，但一般學者皆認為，在沒有找到有效率的因數分解方法之前，RSA 密碼系統可以說是相當的安全。然而，由於其加密與解密的過程，需要做大指數模乘法的運算，這使得在使用RSA密碼系統時，加解密花費過長的時間成為其最大的缺點。因此，如何改善RSA加密與解密的運算速度，一直是許多密碼學家研究的重要問題。一般的方法都是選擇較短位元數的公鑰或私鑰指數。可惜的是，在傳統的RSA演算法裡，並不能同時選擇短指數的公鑰與私鑰，兩者只能取其一。
許多實際應用RSA 密碼系統的場合中，在加密或解密方面，我們通常會希望私密金鑰(d,N)中，指數d可以選擇較短的位元數，以減少解密或簽署的時間，例如在IC 卡的使用上，由於IC 卡的計算能力遠低於一般傳統電腦，因此若使用長度較短的指數d，可使得IC 卡在解密或簽署時，大幅減少IC卡在計算上的負擔﹔而讓較複雜的加密或驗證運算，也就是公開金鑰(e,N)中，位元數較長的指數e ，經由計算能力強的主電腦端執行。然而，私密金鑰中，位元數過短的指數d 是會造成安全性上的威脅。在1999 年的亞洲密碼學會議，Sun，Yang，和Laih證實如果選擇不平衡的RSA模數N，則可以抵抗某些已經發表過的短密鑰指數攻擊，包含了Wiener 的連分數攻擊和Boneh等人所提出的某些格子點攻擊。然而，在2000 年的亞洲密碼學會議，Durfee和Nguyen卻證實了選擇不平衡RSA模數的結果，反而更降低了RSA 密碼系統的安全性。因此，一般學者還是建議在使用RSA 密碼系統時，最好選擇平衡狀態的RSA 模數，即所選的p 跟q皆為512 位元的強質數，在此情況下的RSA 密碼系統，就一般層面來說，是比較安全的。
在本文中，我們成功設計出三種具不同特性之新RSA密碼系統：第一種是一個具有平衡狀態RSA模數的新RSA密碼系統，不僅RSA模數p 跟q皆為512位元的強質數，公鑰及私鑰的位元長度亦相等；第二種是一個同時具有平衡狀態RSA模數與權衡指數的RSA密碼系統，它改善了Sun，Yang，和Laih在亞洲密碼會議所發表的第三個方法滿足log2e + log2d = log2N + lk，lk是一個安全參數；第三種是一個具有同時客製格式公鑰與平衡狀態RSA模數的RSA密碼系統，它延伸我們所設計的第二種RSA系統，公鑰為特殊低漢明權重格式指數（low Hamming weight exponents），來增快加密速度。這些新RSA密碼系統均可以抵禦目前已發表的各種短指數攻擊，而且我們均實際地建構一組（公鑰、私鑰、p、q、RSA模數）來證明我們的方法是可行的。
另外，基於在RSA密碼系統、我們將所設計的第一種RSA密碼系統應用在公開金鑰密碼系統的實體認證。它可以在雙方認證時，抵禦秘密偷竊攻擊。此外，在我們研究過程中，我們觀察到在重平衡RSA(rebalanced RSA)中的CRT-等式是完全獨立的，我們利用此特性，設計了一個類多人簽章系統，它可以多個簽章者同時簽章，由一個代理人製成完整簽章，此簽章只需一次計算式即可驗證完成，是一個高效率的多人簽章系統。

RSA, the first proposed public key cryptosystem in the world, is the most widely used public key cryptosystem. This cryptosystem is not only built into several operating systems, like Microsoft, Apple, Sun, and Novell, but also used for securing web traffic, E-mail, smart cards or IC cards. Based on the believed difficulty of computing eth roots modulo N, where N = pq is the product of two large unknown primes, it is widely believed to be secure for large enough N. Since RSA can also be broken by factoring N, the security of RSA is often based on the integer factorization problem (IFP), which is and continues to be a well studied problem.
In some applications, a short private exponent d is chosen to improve the decryption or signing process for RSA public key cryptosystem. However, in a typical RSA, if the private exponent d is selected first, the public exponent e should be of the same order of magnitude as (N). Sun et al. devised three RSA variants using unbalanced prime factors p and q to lower the computational cost. Unfortunately, Durfee & Nguyen broke the illustrated instances of the first and third variants by solving small roots to trivariate modular polynomial equations. They also indicated that the instances with unbalanced primes p and q are more insecure than the instances with balanced p and q. This investigation focuses on designing a new RSA variant with balanced p and q, and short exponents d and e, to improve the security of an RSA variant against the Durfee & Nguyen's attack, and the other existing attacks. Furthermore, the proposed variant (Scheme A) is also extended to another RSA variant (Scheme B) in which p and q are balanced, and a trade-off between the lengths of d and e is enable. In addition, we provide the security analysis and feasibility analysis of the proposed schemes.
On the other hand, Using Scheme B's method, it is successful in designing variants of RSA in which the public and private exponents can be chosen obviously smaller than those in typical RSA. However, their RSA variants don't provide the use of public key of special form 2X+1, which can further reduce the encryption cost. In this article, we design a customized public key RSA variant which not only remains the same property as the previous RSA variants, but also provides that the public exponent can be the special form of 2X + 1.
The widespread use of open networks and distributed systems brought many communication security risks including users and network components. The basic and .first step in an ensuring secure network is how two entities mutually authenticate each other. With entity authentication protocols in place, it is easy for one participant to establish secure communications with one another. A secret-key based authentication protocol allows two parties sharing a common secret key to authenticate each other. However, this mechanism is insecure against a new attack, named the stolen-secret attack, in which once the secret of an entity is divulged, the attacker may be able to impersonate his partner to fool this entity. In this paper, we are interesting in designing secure secret-key based protocols which can defend against the stolen-secret attack.
Furthermore, we propose a property from the CRT-equations in Rebalanced-RSA. We point out that, in fact, two CRT-equations can be totally independent. This means, we can choose different public exponents when using Rebalance RSA. Furthermore, we propose a multisignature-like scheme based on Rebalanced-RSA. In our proposed scheme, the signers can sign the same message simultaneously and then combine all individual signatures into a multisignature. In addition, there exists an exponential operation in the multisignature verification procedure.

[1] D. Alpern. (2003, Oct.). Available: http://www.alpertron.com.ar/ECM.HTM
[2] A. Aziz and W. Di¢ e, “A secure communications protocol to prevent unauthorized access - privacy and authentication for wireless local area networks”, IEEE Pers. Commun., First Quarter, 1994.
[3] M. Bellare and P. Rogaway, “Entity authentication and key distribution”, Proceedings of Crypto’93 , LNCS 773, pp. 232-249, 1994.
[4] M. Bellare and P. Rogaway, “The exact security of digital signatures –how to sign with RSA and Rabin,”Proceedings of Eurocrypt’96, LNCS 1070, pp. 399–416, 1996
[5] S. M. Bellovin and M. Merritt, “Encrypted key exchange: password-based protocols secure against dictionary attacks.”, Proc. IEEE Computer Society Conference on Research in Security and Privacy, pp. 72-84, 1992.
[6] S.M. Bellovin andM.Merritt, “Augmented encrypted key exchange: A password-based protocol secure against dictionary attacks and password …le compromise.”, Technical report, AT&T Bell Laboratories, 1994.
[7] S. Blake-Wilson and A. Menezes, “Security Proofs for Entity Authentication and Authenticated Key Transport Protocols Employing Asymmetric Techniques”, Proceedings of the 5th International Workshop on Security Protocols, LNCS 1361, pp. 137-158, 1998.
[8] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than N0:292”, Proceedings of Eurocrypt’99, LNCS 1592 , pp. 1–11, 1999.
[9] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than N0:292”, IEEE Trans. Inform. Theory, vol. 46, no. 4, pp. 1339-1349, July 2000.
[10] V. Boyko, P. MacKenzie and S. Patel, “Provably secure password authenticated key exchange using Di¢ e-Hellman”, Proceedings of Eurocrypt’00, pp. 156-171, 2000.
[11] S. Cavallar, B. Dodson, A. K. Lenstra, W. Lioen, P. L. Montgomery, B. Murphy, H. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand, F. Morain, A. Mu¤ett, C. Putnam, C. Putnam and P. Zimmermann, “Factorization of 512-bit RSA key using the number …eld sieve”, Proceedings of Eurocrypt’00, LNCS 1807, pp. 1-18, 2000.
[12] D. Coppersmith, “Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known”, Proceedings of Eurocrypt’96, LNCS 1070, pp. 178–189, 1996.
[13] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithm,second edition, McGraw-hill Book Company, 2001.
[14] G. Durfee and P. Nguyen, “Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt’99”, Proceedings of Asiacrypt’00, LNCS 1976, pp. 14– 29, 2000.
[15] Y. Frankel, “A Practical Protocol for Large Group Oriented Networks”, Proceedings of Eurocrypt’89, LNCS 0434, pp. 56–61, 1989.
[16] S. D. Galbraith, C. Heneghan AND J. F. McKee, “Tunable balancing of RSA.Information Security and Privacy”, 10th Australasian Conference - ACISP 2005, LNCS Vol. 3574, pp. 280-292, 2005.
[17] I. N. Herstein, Topics in Algebra, Xerox Corporation, 1975.
[18] H. S. Hong, H. K. Lee, H. S. Lee and H. J. Lee, “The better bound of private key in RSA with unbalanced primes”, Applied Mathematics and Computation, Vol. 139, pp. 351-362, 2003.
[19] D. Jablon, “Strong password-only authenticated key exchange”, Computer Communication Review, vol.26, no.5, pp. 5-26, 1996.
[20] M. Joye, J. J. Quisquater, S. M. Yen and M. Yung, “Security paradoxes: how improving a cryptosystem may weaken it”, Proceedings of the Ninth National Conference on Information Security, pp. 27-32, 1999.
[21] A. Lenstra, H. Lenstra and L. Lovasz, “Factoring polynomial with rational coef…cients”, Mathematiche Annalen, Vol. 261, pp. 515-534, 1982.
[22] Lenstra Jr and H.W., “Factoring integers with elliptic curves”, Annuals of Mathematics, vol. 126, pp. 649–673, 1987.
[23] R. Pinch, “Extending the Wiener attack to RSA-type cryptosystems”, Electronics Letters, Vol. 31, pp. 1736-1738, 1995.
[24] J. Pollard, “Theorems of factorization and primality testing”, Proc. Cambridge Philos. Soc., pp. 76:521–528, 1974.
[25] J. J. Quisquater and C. Couvreur, “Fast decipherment algorithm for RSA public key cryptosystem,”Electronic Letters, vol. 18, pp.905-907, 1982.
[26] R. L. Rivest, A. Shamir and L. M. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM, Vol. 21,pp. 120-126, 1987.
[27] R. Rivest and R. D. Silverman, “Are strong primes needed for RSA?”, The 1997 RSA Laboratories Seminar series, Seminar Proceedings, 1997.
[28] R. Sakai, M. Morii and M. Kasahara, “New key generation algorithm for RSA cryptosystem”, IEICE Transactions on Fundamentals, Vol. E77-A, pp. 89-97, 1994.
[29] V. Shoup, “OAEP reconsidered,” Proceedings of Crypto’01, J. Killian, Ed., LNCS 2139, pp. 239-259, 2001.
[30] H. M. Sun and C. T. Yang, “RSA with Balanced Short Exponents and Its Application to Entity Authentication”, Proceedings of PKC 2005, LNCS 3386, pp. 199–215, 2005.
[31] H. M. Sun, W. C. Yang and C. S. Laih, “On the design of RSA with short secret exponent”, Proceedings of Asiacrypt’99, LNCS 1716, pp. 150–164, 1999.
[32] H.M. Sun andM. E.Wu, “Design of Rebalanced RSA-CRT for Fast Encryption”, Information Security Conference 2005, pp. 16-27, 2005.
[33] H. M. Sun, M. J. Hinek and M. E. Wu, “On the Design of Rebalanced RSA-CRT”, Technical Report CACR 2005-35, 2005.
[34] E. Verheul and H. van Tilborg, “Cryptanalysis of less short RSA secret exponents”, Applicable Algebra in Engineering, Communication and Computing, Vol. 8, pp. 425-435, 1997.
[35] B. de Weger, “Cryptanalysis of RSA with small prime di¤erence”, Applicable Algebra in Engineering, Communication and Computing, Vol. 13, pp. 17-28, 2002.
[36] M.Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Trans. Inform. Theory, Vol. 36, no. 3, pp. 553–558, 1990.
[37] S.B. Wilson and A. Menezes, “Authenticated Di¢ e-hellman key agreement protocols”, 5th Annual International Workshop, SAC’98, pp. 339-361, 1998.