RSA 是一被廣泛使用的公開金鑰密碼系統。然而，對於 RSA 金鑰產生器而言，其內部很可能被安裝後門使得所產生之公開金鑰隱藏著私密金鑰的資訊。從 1996 年開始，Young and Yung 陸續提出了一些在 RSA 金鑰產生器內建立後門的方法。他們所提出的方法大部分都滿足 Strong-SETUP 的特性，也就是說，即使金鑰產生器被拆開使得內部的後門設計方式被得知，一般人仍無法判斷任一給定的金鑰是否由此裝有後門的金鑰產生器所產生。然而，利用Young and Yung 的方法，所產生的模數 n 的前兩個 bits 的機率分佈並不符合一般正常 RSA 模數的機率分布情形，此外，其所產生金鑰的時間也不同於正常產生金鑰所花的時間，因此，藉由觀察這些不一致性，使用者便很可能地偵測到後門的存在。在2003年，Crepéau 和 Slakmon 提出了四種簡易的 RSA 後門，其中三種，執行所花的時間和正常的金鑰產生時間類似，但是它們都不是Strong-SETUP。此外，只有最後一個方法 RSA-HP□ 將後門植入 n，其他三種都是植入 e。當後門植入 e 時，e 的大小就會受限制，這對於經常使用小的 e (例如 e = 2^16 + 1) 用以加速加密的 RSA 系統來說，是不實用的。基於過去的研究，我們提出了三種在 RSA 系統中植入後門的新方法和一種在 rebalanced RSA-CRT 中植入後門的方法。四種方法的後門都是植入 n，因此 e 的大小並不受限。第一種方法ーRSA-SBLT 運用了格子點 (lattice) 攻擊的技巧，而第二種方法ーRSA-SBES 運用了窮舉搜尋攻擊的技巧，兩種方法產生金鑰的時間，和正常 RSA 金鑰的產生時間類似，故不易由時間的差異性察覺到後門的存在。至於第三種方法 RSA-BDH，是運用 p 和 q 的關係設計後門，此方法並無 Young 和 Yung 方法中模數的前兩個 bit 機率不正常分佈的問題，此外，我們證明了在迪菲-赫爾曼 (DH) 的假設正確的前提下，RSA-BDH 是一個 Strong-SETUP。除了在 RSA 系統植入後門外，我們的第四種方法，是針對 Sun et al.’s rebalanced RSA-CRT 系統上植入後門，到目前為止，尚無關於在rebalanced RSA-CRT上植入後門的研究，因此，這是第一個設計在 rebalanced RSA-CRT 的後門機制。

RSA is a widely used public key cryptosystem. However, it is possible for a RSA key generator to be embedded a backdoor such that the generated public key contains the information about the private key. Young and Yung have presented some methods to embed backdoors for RSA key generation since 1996. Most of their backdoors satisfy the properties of Strong-SETUP. That is, even though the device is reverse-engineered, anyone except the backdoor manufacturer can not distinguish whether a casually given key is generated by the backdoor device or not. However, the two MSBs of the modulus n generated by their methods have different distribution compared with those of the normal RSA modulus, and the running time of their schemes can not match the normal RSA key-generation time. Hence, anyone may detect the existence of the backdoor by observing these differences. In 2003, Crepéau and Slakmon suggested four simple RSA backdoors. Although three of their schemes have roughly the same running time as the normal RSA, they are all not Strong-SETUPs. Besides, only the last scheme, RSA-HP□, embeds the backdoor in n and the other three schemes embed the backdoor in e. When the backdoor is embedded in e, the size of e is restricted. This is impractical since e = 2^16 +1 is often used to speed RSA encryption. Based on the previous research, we propose three new backdoor mechanisms for RSA key generation, and one backdoor mechanism for rebalanced RSA-CRT. All of the methods embed the backdoor in n so the size of e is not limited. In the first method, RSA-SBLT, the technique of lattice attack is used and in the second method, RSA-SBES, the technique of exhaustive search attack is employed. Both of them roughly have the same running time as the normal RSA key generation so anyone can hardly detect the backdoor by observing the time imparity. As for our third method, RSA-BDH, we utilize the relationship between p and q to devise a backdoor mechanism which solves the problem that the two MSBs of n have abnormal distribution, as it occurs in Young and Yong's method. Moreover, we prove that RSA-BDH is a Strong-SETUP based on DH assumption. Besides the backdoor for RSA, we also devise a backdoor mechanism for Sun et al.’s rebalanced RSA-CRT. Up to now, there is no method proposed to embed the backdoor for rebalanced RSA-CRT. Hence, this is the first backdoor mechanism for rebalanced RSA-CRT.

1. INTRODUCTION 1
1.1. Background and Motivation 1
1.2. Organization of the thesis 3
2. PRELIMINARY 4
2.1. Notation 4
2.2. Public Key Cryptosystem 4
2.3. RSA Cryptosystem 5
2.3.1. Background Knowledge of RSA 5
2.3.2. RSA Algorithm 6
2.3.3. Security Consideration of RSA 7
2.4. Some Variants of RSA 8
2.4.1. RSA Decryption based on CRT 8
2.4.2. Wiener’s small CRT-exponent RSA 10
2.4.3. Sun et al’s Rebalanced RSA-CRT 11
2.5. Previous RSA Backdoors 12
2.5.1. The Definition of Strong-SETUP 12
2.5.2. Anderson’s RSA trapdoor 13
2.5.3. Young and Yung’s Four RSA Backdoors 14
2.5.4. Crépeau and Slakmon’s Simple Backdoors 21
3. ATTACK ON RSA 27
3.1. Continued fractions attack 27
3.1.1. Continued Fractions Background 27
3.1.2. Continued Fraction Attack on RSA 28
3.2. Lattice-based Attack 28
3.2.1. Introduction to LLL Algorithm 29
3.2.2. Lattice-based Attack on RSA 31
3.2.3. Lattice-based Attack on Small CRT-exponent RSA 34
3.3. Attack on the small k RSA 37
3.4. The Summary of Insecure RSA Keys 38
4. THE PROPOSED SIMPLE RSA BACKDOOR SYSTEMS 39
4.1. Simple Backdoor based on Lattice Technique (RSA-SBLT) 39
4.1.1. Preprocessing: Parameters Set by Manufacturers 40
4.1.2. Algorithm of RSA-SBLT: 40
4.1.3. Usage of RSA-SBLT Backdoor: 40
4.2. Simple Backdoor based on Exhaustive Search (RSA-SBES) 41
4.2.1. Preprocessing: Parameters Set by Manufacturers 41
4.2.2. Algorithm of RSA-SBES: 41
4.2.3. Usage of RSA-SBES Backdoor: 42
5. THE PROPOSED RSA STRONG-SETUP 43
5.1. RSA Backdoor based on Diffie-Hellman (RSA-BDH) 43
5.1.1. Preprocessing: Parameters Set by Manufacturers 43
5.1.2. Algorithm of RSA-BDH 43
5.1.3. Usage of RSA-BDH Backdoor: 44
5.2. Security Analysis of RSA-BDH 45
5.2.1. Distributions of p and q 45
5.2.2. Interrelationships among p, q, and n 46
6. THE PROPOSED BACKDOOR FOR REBALANCED RSA-CRT 51
6.1. The Functions About ECDH 51
6.2. Algorithm of Rebalanced RSA-CRT Backdoor 51
6.3. Usage of Rebalanced RSA-CRT Backdoor 54
7. EXPERIMENTS 55
8. CONCLUSIONS AND FUTURE WORK 59
BIBLIOGRAPHY 60
PUBLICATIONS LIST 64

[1] R. J. Anderson, “A practical RSA trapdoor,” Electronic Letters, vol. 29, no. 11, p. 995, 1993.
[2] A. Shamir, “Partial Key Escrow: A new approach to software key escrow,” Proc. of the Key Escrow Conf., Washington, 1995
[3] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than n0.292,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1339-1349, 2000.
[4] D. Boneh, G. Durfee, and Y. Frankel, “An attack on RSA given a small fraction of the private key bits,” Advances in Cryptology–ASIACRYPT ’98 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1514, pp. 25-34, 1998.
[5] D. Boneh and R. Venkatesan, “Breaking RSA may not be equivalent to factoring,” Advances in Cryptology–EUROCRYPT '98 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1233, pp. 59-71, 1998.
[6] D. Coppersmith, “Finding a small root of a bivariate integer equation: factoring with high bits known,” Advances in Cryptology–EUROCRYPT ’96 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1070, pp. 178-189, 1996.
[7] D. Coppersmith, “Small solutions to polynomial equations, and low exponent RSA vulnerabilities,” J. Cryptology, vol. 10, pp.233-260, 1997.
[8] Z. Chai, Z. Cao, and R. Lu, “ID-based threshold decryption without random oracles and its application in key escrow,” Proc. of the 3rd Int. Conf. on Inf. Security, November 14-16, 2004.
[9] C. Coupé, P. Nguyen, and J. Stern, “The Effectiveness of Lattice Attacks Against Low-Exponent RSA,” Public Key Cryptography–PKC’ 99 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1560, pp. 204-218, 1999.
[10] C. Crépeau and A. Slakmon, “Simple backdoors for RSA key generation,” Topics in Cryptology—CT-RSA ’03 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 2612, pp. 403-416, 2003.
[11] D.E. Denning, “The US key escrow encryption technology,” Computer Communications, vol. 17, no.7, pp.453-457, 1994.
[12] W. Diffie and M. Hellman, “New Directions in Cryptography,” IEEE Trans. Inf. Theory, vol. 22, no. 6, pp. 644-654, 1976.
[13] G. Durfee and P. Q. Nguyen, “Cryptanalysis of the RSA Schemes with Short Secret Exponent form Asiacrypt '99,” Advances in Cryptology-ASIACRYPT ’00 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1976, pp. 1-11, 2000.
[14] N. Howgrave-Graham, “Finding small roots of univariate modular equations revisited,” Proc. of Cryptography and Coding (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1355, pp. 131-142, 1997.
[15] S. D. Galbraith, C. Heneghan, and J. F. Mckee, “Tunable balancing of RSA,” Inf. Security and Privacy: 10th Australasian Conf.–ACISP ’05 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 3574, pp. 280-292, 2005.
[16] J. Hasted, “On Using RSA with Low Exponent in a Public Key Network,” Advances in Cryptology–CRYPTO ’85 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, pp. 403-408, 1986.
[17] M. J. Hinek, “Lattice Attacks in Cryptography: A Partial Overview,” Technical Report CACR 2004-08, University of Waterloo, 2004.
[18] M Jason Hinek, Mo King Low, and Edlyn Teske, “On some attacks on multi-prime RSA,” Selected Areas in Cryptography–SAC ’02 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 2595, pp. 385-404, 2002.
[19] Jihoon Cho, “Ten Years of RSA Cheating Cryptosystems,” MMath Essay, Dept. of Combinatorics & Optimization, University of Waterloo, 2004.
[20] B. S. Kaliski, “Anderson’s RSA trapdoor can be broken,” Electronics Letters, vol. 29, no.15, p. 1387, 1993.
[21] A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen 261, pp. 515-534, 1982.
[22] A. May, “Cryptanalysis of unbalanced RSA with small CRT-exponent,” Advances in Cryptology–CRYPTO ’02 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 2442, pp. 242-256, 2002.
[23] J. Nechvatal, "A public-key-based key escrow system," J. of Systems and Software, vol. 35, no. 1, pp. 73-83, 1996.
[24] I. Niven and H. S. Zuckerman, An introduction to the theory of number, John Wiley and Sons Inc., 1991.
[25] J. J. Quisquater and C. Couvreur, “Fast decipherment algorithm for RSA public key cryptosystem,” Electronic Letters, vol. 18, pp. 905-907, 1982.
[26] M. Rabin, “Digitalized signatures and public-key functions as intractable as factorization,” Technical Report, MIT/LCS/TR212, MIT Lab., Computer Science, Cambridge, January 1979.
[27] R. L. Rivest and A. Shamir, “Efficient factoring based on partial information,” Advances in Cryptology–EUROCRYPT ’85 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 219, pp. 31-34, 1985.
[28] R. Rivest and R. D. Silverman, “Are ‘strong’ primes needed for RSA,” the 1997 RSA Laboratories Seminar Series, Seminars Proceedings, 1997.
[29] R. Rivest, A. Shamir, and L. Aldeman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, vol. 21, no.2, pp.120-126, 1978.
[30] H. M. Sun, M. J. Hinek and M. E. Wu, “On the Design of Rebalanced RSA-CRT,” Technical Report CACR 2005-35. The paper is available from http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-35.pdf.
[31] H. M. Sun and C. T. Yang, “RSA with Balanced Short Exponents and Its Application of Entity Authentication,” Public Key Cryptography–PKC ’05 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, pp. 199-215, 2005.
[32] Wade Trappe and Lawrence C. Washington, Introduction to Cryptography with coding theory, Practice-Hall, Inc., 2002.
[33] E. Verheul and H. van Tilborg, “Cryptanalysis of less short RSA secret exponents,” Applicable Algebra in Engineering, Communication and Computing. Berlin Germany: Springer-Verlag, vol. 8, pp. 425-435, 1997.
[34] M. Wiener, “Cryptanalysis of short RSA secret exponents,” IEEE Trans. Inf. Theory, vol. 36, no. 3, pp. 553-558, 1990.
[35] A. Young and M. Yung, “The Dark Side of Black-Box Cryptography or: Should We Trust Capstone?” Advances in Cryptology–CRYPTO ’96 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1109, pp 89-103, 1996.
[36] A. Young and M. Yung, “Kleptography : Using cryptography against cryptography” Advances in Cryptology–EUROCRYPT ’97 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 1233, pp. 62-74, 1997.
[37] A. Young and M. Yung, “A space efficient backdoor in RSA and its applications,” Selected Areas in Cryptography–SAC ’05 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 3897, pp. 128-143, 2005.
[38] A. Young and M. Yung, “Malicious cryptography: kleptographic aspects,” Topics in Cryptology—CT-RSA ’05 (Lecture Notes in Computer Science). Berlin Germany: Springer-Verlag, vol. 3376, pp. 7-18, 2005.
[39] NTL website: http://www.shoup.net/ntl/.
[40] GMP website: http://www.swox.com/gmp/.