簡易檢索 / 詳目顯示

回結果列表
研究生： 任上鳴
Jen, Shang-Ming
論文名稱： 公開金鑰基礎建設之長期安全性
Long-Term Security of Public Key Infrastructure
指導教授： 楊家輝
Yang, Jar-Ferr
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 70
中文關鍵詞： 公開金鑰基礎建設 、長期安全性 、隱私空窗期 、非對稱秘密性 、迷袋密碼
外文關鍵詞： Public Key Infrastructure, Long-term security, Privacy-Free Window, Asymmetric secrecy property, Knapsack
相關次數： 點閱：128  下載：10 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 公開金鑰基礎建設(Public Key Infrastructure, PKI)是現今密碼應用中最重要的一環，其牽涉之領域廣及生活中的諸多領域，如：自然人憑證，即為常見之應用之一。公開金鑰基礎建設在虛擬網路環境中提供不可或缺的信任來源。然而，隨密碼解析技術之演進，其安全性已受到威脅，其中最重要的議題即長期安全性(Long-term security)，可分為長期隱私性(Long-term confidentiality)與長期認證性(Long-term authenticity)討論。長期認證性在過去文獻中已有部份學者研究，產生些許對應之改善方式，本文亦將整合此部份之研究，然而長期隱私性至今仍未見著墨，使其成為現今公開金鑰基礎建設應用中，最急需解決的問題。本文首先將長期隱私性之問題以隱私空窗期(Privacy-Free Window, PFW)做為量化，再提出公開金鑰基礎建設之非對稱秘密性質(Asymmetric secrecy property)，以解決隱私空窗期之問題。此方法如經延伸，可改善具有非對稱秘密性之密碼工具。本文對提出之理論以邏輯之方式證明其可行性，並提供驗證協定是否存在隱私空窗期之方法，與對應的修正建議。此外，由於RSA公開金鑰系統植基之因數分解問題在未來可能實現之量子運算下已不安全，本文亦針對可維持量子運算安全之迷袋密碼系統進行研究，由實作觀點分析迷袋密碼系統現存之格狀攻擊，並開發安全迷袋密碼系統之原型，以提供未來量子運算系統下，可用之公開金鑰密碼系統。

    The ubiquitous cryptographic concept, Public Key Infrastructure (PKI), is facing a slew of severe risks. A particular issue is long-term security, which can be classified into long-term authenticity and long-term confidentiality. The issue of authenticity has been widely discussed in the last decade while the confidentiality issue has been neglected. As the factorization of RSA is advancing, there is increased urgency to refresh confidentiality of existing instances of PKI with longer validity terms. Unfortunately, among these discussions, there is no realistic, low cost and efficient solution to the problem. Long-term confidentiality is the most challenging unaddressed open problem from previous works. In this dissertation, we formalize this problem by defining Privacy-Free Window (PFW). By taking advantage of a PKI special property called asymmetric secrecy property, we give a specific solution addressing PFW. This method can be further developed to extend the originally defined security interval of some PKIs and other cryptographic tools. We also furnish an algorithm to verify existing protocols and provide suggested actions for reacting to a PFW occurrence. Furthermore, pending the possible realization of quantum computers, the RSA public key cryptosystems which PKI relies on is facing critical challenges because of weaknesses under quantum cryptanalysis. We research a possible replacement, knapsack cryptosystems, which do not yield any weaknesses to quantum computation in this dissertation. Building on experimental results, we develop an empirically secure knapsack cryptosystem which explores possible directions for improving a candidate for public key cryptosystem which can survives in the quantum era.

    1. Introduction 1 1.1. Background and Motivations 1 1.2. Long-Term Security 5 1.3. Synopsis of the Dissertation 6 2. Related Works 9 2.1. RSA Public Key Cryptosystem 9 2.2. Factorization of the RSA Algorithm 11 2.3. Merkle-Hellman (MH) Knapsack Cryptosystem 12 2.4. Attacks toward the Knapsack Cryptosystem 13 2.4.1. Attacks on Trapdoor Functions 13 2.4.2. Lattice Attack 14 2.5. The Logic of Authentication 17 3. Long-Term Security of the Public Key Infrastructure (PKI) 23 3.1. Long-Term Authenticity 23 3.2. Long-Term Confidentiality and Privacy-Free Window (PFW) 27 3.3. Long-Term Confidentiality in the Public Key Infrastructure (PKI) 30 3.3.1. Asymmetric Secrecy Property 30 3.3.2. An Example of Addressing Privacy-Free Window 33 3.3.3. Verification of Authenticity and Discussion 35 3.4. An Algorithm for Distinguishing the Existence of PFW 40 4. Knapsack – A Candidate for Future Public Key Cryptosystem 43 4.1. Revising an Algorithm Considered Secure – LLHS 43 4.2. Breaking LLHS by Implementing Lattice Attacks 45 4.2.1. Implementation of Lattice Attack 46 4.2.2. Tests on Revised LLHS Knapsack Cryptosystem 47 4.3. More Discoveries on Related Factors 48 4.4. An Empirically Secure Knapsack Cryptosystem 51 4.4.1. The Proposed Knapsack Cryptosystem 52 4.4.2. Parameter Selection 53 4.4.3. Improving the Proposed Knapsack Cryptosystem 54 5. Conclusions 59 5.1. Contributions on Long-Term Confidentiality 59 5.2. Contributions on the Next Generation Public Key Cryptosystems 60 5.3. Future Research Perspective 61 References 63 Vita 67

    [1] Adleman, L. M., “On Breaking Generalized Knapsack Public Key Cryptosystems,” in Proc. of the 15th ACM Symposium on Theory of Computing, pp. 402-412, 1983.
    [2] Barker, E., Barker, W., Burr, W., Polk, W. and Smid, M., “NIST SP800-57: Recommendation for Key Management,” which is available at http://csrc.nist.gov /publications/PubsSPs.html, May 2007.
    [3] Brickell, E. F., “Solving Low Density Knapsacks,” in Advances in Cryptology: Proc. of Crypto83, pp. 25-37, 1984.
    [4] Buchmann J., May, A. and Vollmer, U., “Perspective for Cryptographic Long-Term Security,” in Communications of ACM, Vol. 49, No. 9, pp. 50-55, Sep. 2006.
    [5] Burrows, M., Abadi, M. and Needham, R. “A Logic of Authentication,” in ACM Trans. on Computer Systems, Vol. 8, No. 1, pp. 18-36, Feb. 1990.
    [6] Cavallar, S., Dodson, B., Lenstra, A. K., Lioen, W., Montgomery, P. L., Murphy, B., Riele, H., Aardal, K., Gilchrist, J., Guillerm, J., Leyland, P., Marchand, J., Morain, F., Muffett, A., Putnam, C. & C., and Zimmermann, P., “Factorization of a 512-bit RSA Modulus” in Proc. of the 19th International Conference on Theory and Application of Cryptographic Techniques, pp. 1-18, May 2000.
    [7] Chor, B. and Rivest, R. L., “A Knapsack Type Public Key Cryptosystem Based on Arithmetic in Finite Fields,” in Advances in Cryptology: Proc. of Crypto84, LNCS., pp. 54-65, 1985.
    [8] Coster, M. J., LaMacchia, B. A., Odlyzko, A. M., and Schnorr, C. P., “An Improved Low-density Subset Sum Algorithm,” in Proc. of the 10th annual international conference on Theory and application of cryptographic techniques (Eurocrypt91), pp. 54-67, 1991.
    [9] Diffie, W. and Hellman, M. E., “New Directions in Cryptography,” in IEEE Trans. on Information Theory, Vol. IT-22, pp. 644-654, Nov. 1976.
    [10] Feistel, H., “Cryptography and Computer Privacy,” in Scientific American, Vol. 228, No. 5, pp. 15-23, May 1973.
    [11] Izu, T., Kogure, Koshiba, J., T. and Shimoyama, T., “Low-Density Attack Revisited,” in Designs, Codes and Cryptography, Vol. 43, No. 1, pp. 47-59, 2007.
    [12] Jen, S.-M., Lai T.-L., Lu, C.-Y. and Yang J.-F., “Knapsack Cryptosystems and Unreliable Reliance on Density,” in Proc. of 26th IEEE International Conference on Advanced Information Networking and Applications, pp. 748-754, Mar. 2012.
    [13] Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L., Osvik, D. A., Riele, H., Timofeev, A. and Zimmermann, P., “Factorization of a 768-bit RSA modulus” in Proc. of the 30th Annual Conference on Advances in Cryptology, pp. 333-350, Jan. 2010.
    [14] Kunihiro, N., “New Definition of Density on Knapsack Cryptosystems,” in Progress in Cryptology: Proc. of Africacrypt 2008, LNCS., Vol.5023, pp.156-173, 2008.
    [15] Lagarias, J. C. and Odlyzko, A. M., “Solving Low-Density Subset Sum Problems,” in Proc. of 24th Annual IEEE Symposium on Foundations of Computer Science, pp. 1–10, 1983.
    [16] Laih, C.-S., Jen, S.-M., Lu, C.-Y., Lin, T.-H., Chen, J.-M., Huang, Y.-J., Wang, P.-H. and Lin, C.-H., “A Study of Cryptanalysis and Attack Methods,” in Proc. of the 18th National Conference on Science and Technology of National Defense, Taoyuan, Taiwan, Nov. 2009.
    [17] Laih, C.-S., Lee, J.-Y., Harn, L. and Su, Y.-K., “Linearly Shift Knapsack Public-key Cryptosystem,” in IEEE Journal on Selected Areas in Communications, Vol. 7, No. 4, pp. 534-539, May 1989.
    [18] Lenstra, A.K. and Verheul, E.R., “Selecting Cryptographic Key Sizes” in Journal of Cryptology, pp. 255-293, Aug. 2001.
    [19] Merkle, R. and Hellman, M., “Hiding Information and Signatures in Trapdoor Knapsacks,” in IEEE Trans. on Information Theory, Vol. IT-24, pp. 525-530, Sep. 1978.
    [20] Miller, S. P., Neuman, C., Schiller, J. I., AND Saltzer, J. H., “Kerberos Authentication and Authorization System,” in Project Athena Technical Plan, Sect. E.2.1. MIT, Cambridge, Mass., Jul. 1987.
    [21] Myers, L. W. “Spycomm: Covert Communication Techniques of the Underground,” Boulder, CO: Paladin Press, Nov. 1991.
    [22] Nguyen, P. Q. and Stern, J., “Adapting Density Attacks to Low-Weight Knapsacks,” in Advances of Cryptology: Proc. of Asiacrypt05, LNCS., Vol. 3788, pp. 41-58, 2005.
    [23] Odlyzko, A. M., “Cryptanalytic Attacks on the Multiplicative Knapsack Cryptosystem and on Shamir’s Fast Signature System,” in IEEE Trans. on Information Theory, Vol. IT-30, pp. 594-601, 1984.
    [24] Okamoto, T., Tanaka, K. and Uchiyama, S., “Quantum Public-Key Cryptosystems,” in Proc. of the 20th Annual International Cryptology Conference on Advances in Cryptology, pp. 147-165, Aug. 2000.
    [25] Pinkas, D., Ross, J., and Pope, N., “Electronic Signature Formats for Long-Term Electronic Signatures,” IETF RFC 3126, which is available at http://www.rfc-editor.org /rfc/rfc3126.txt, Sep. 2001.
    [26] Rivest, R., Shamir, A. and Adleman, L., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” in Communications of the ACM, Vol. 21, No. 2, pp. 120-126, Feb. 1978.
    [27] Schnorr, C. P. and Euchner, M., “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems,” in Mathematical Programming, Vol.66, pp.181-199, 1994.
    [28] Shamir, A., “A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem,” in Proc. of 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 145-152, Nov. 1982.
    [29] Shor, P. W., “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” in SIAM Journal on Computing, Vol. 26, Issue 5, pp. 1484-1509, Oct. 1997.
    [30] Vaudenay, S., “Cryptanalysis of the Chor-Rivest Cryptosystem,” in Advances in Cryptology: Proc. of the 18th Annual International Cryptology Conference (Crypto98), LNCS, pp.243-256, 1998.
    [31] “Data Encryption Standard (DES),” Federal Information Processing Standards Publication No. 46-3, National Institute of Standards and Technology, which is available at http://csrc.nist.gov/publications/PubsFIPSArch.html, Oct. 1999.
    [32] “Advanced Encryption Standard (AES),” Federal Information Processing Standards Publication No. 197, National Institute of Standards and Technology, which is available at http://csrc.nist.gov/publications/PubsFIPS.html, Nov. 2001.
    [33] eSTREAM: the ECRYPT Stream Cipher Project, which is available at http://www. ecrypt.eu.org/stream.
    [34] Certificate Authority of the Ministry of the Interior of Taiwan, which is available at http://moica.nat.gov.tw.
    [35] “Directive 1999/93/EC of the European Parliament and of the Council of 13 December 1999 on a Community Framework for Electronic Signatures”, Official Journal L 013, pp. 12 - 20, which is available at http://eur-lex.europa.eu/JOHtml.do?uri=OJ:L:2000:013: SOM:EN:HTML, Jan. 2000.
    [36] NTL: A Library for doing Number Theory, which is available at http://www.shoup.net/ ntl.

    下載圖示 校內：2014-07-24公開
    校外：2014-07-24公開
    QR CODE