密碼學的研究成果

Research Results in Cryptography

　

計畫主持人

張真誠教授

　

　

C. C. Chang

國立中正大學資訊工程系

E-mail：ccc@cs.ccu.edu.tw

　

　　生於民國四十三年十一月十二日，民國六十六年畢業於清華大學數學系，民國六十八年獲得清華大學計算機科學碩士，民國七十一年獲得交通大學計算機工程博士。曾任職於交通大學、中興大學及中正大學，並曾擔任中正大學資訊工程研究所所長，自動化研究中心主任，共同科主任，工學院院長，教務長及代理校長，目前是中正大學資訊工程系專任教授兼教育部顧問室主任。

　　張教授從事教職工作十九年，在資料庫設計，資訊安全及影像處理等研究領域，發表上百篇學術論文，指導八十餘位碩博士研究生，為國內學術界及產業界培育許多優秀的資訊工程人才。除此之外，張教授著有12冊學術專書，其中「電腦密碼學與資訊安全」及「近代密碼學及其應用」是目前國內僅有的兩本密碼學中文參考書籍，曾被多所大專校院選為資訊安全課程之教材。

　

　

一. 前言

　

　　近七年來，我所做的研究大多集中在密碼學(Cryptography)這個領域，「密碼」這兩個字乍聽起來還蠻嚇人的，究竟什麼是密碼？我在這裡簡單地解釋一下密碼系統的意義。

　　一個密碼系統通常有三個主角，他們是發信者，收信者和破密者，典型的密碼系統是由發信者首先將訊息m，利用一個加密器E及加密金匙k1，將訊息加密成一堆看起來亂七八糟的符號，我們稱之為密文C=Ek1(m)，俗稱密碼。接著，發信者利用公眾通道(Public Channel)將密文C送給了收信者，收信者在收到密文C之後，利用解碼器D及解密金匙k2，將C解密，還原成原來的訊息m= Dk2(C)。在密碼系統中我們必須設想有一個破密者在公眾網路上虎視眈眈地想盡各種方法要得知訊息m。通常一個密碼系統的好壞就在於他的加解密速度夠不夠快？密文本身夠不夠安全？亦即容不容易被破密者破解？從密碼學的演進，我們發現傳統的密碼系統往往只注重資訊的安全性及隱密性，然而近代的密碼學者認為資訊的鑑定性、完整性及不可否認性，在商業上的應用要遠比秘密性更加地重要。因此發信者向收信者證明訊息m確實是他個人所發送的，就如同發信者在合約書上簽字一樣，而收信者就是保有這份合約書的人，他當然要相信這份簽有字跡的合約書之法律效力。

　　在網路上，發信者通常利用自己的私密金匙將訊息透過運算簽署成簽署文，而任何人均可以透過該發信者的公開金匙將此簽署文解密還原成原來的訊息，由於只有發信者本人才有自己的私密金匙，亦即只有他本人才有能力將訊息簽署，而其他任何人均只能驗證而無法偽造。因此此簽署文就如同發信者親筆簽名一樣，具有法律效力，日後若有爭執（如簽署者事後矢口否認），第三者（如法院）可以很容易地做出正確的判斷。此種系統，稱之為數位簽署系統。

　

　

二. 研究方向

　

　　近七年來，我在密碼學的研究循著下列幾個大方向發展：

（一）設計安全的密碼系統

（二）設計有效的數位簽署

（三）破解密碼系統

（四）密碼系統的加速運算

　　由於近代許多研發的密碼系統及數位簽署系統均利用到多項指數運算連乘，這是一種相當耗時費事的算數運算。因此如何研究出好的方法用來加速多項指數運算連乘就等於直接幫忙了多數的密碼系統及數位簽署系統提昇其系統績效一樣。

　　近年來，我們設計了許多有效的演算法應用於指數運算及多項指數運算連乘，同時我們也已研究出透過平行計算的技巧來加快這一類複雜的計算。

　

　

三.研究成果

　

　　過去七年內，我的研究成果，利用上列的四個研究方向來分類：

（一）有關密碼系統的研究

  1. Chang, C. C. and Hwang, R. J., (1993): "Master Keys for an M3 Cryptoscheme," Cryptologia, Vol. XVII, No. 2, Apr. 1993, pp. 175-186.
  2. Chang, C. C. and Lee, H. C., (1993): "A New Generalized Group Oriented Cryptoscheme without Trusted Centers," IEEE Journal on Selected Areas in Communications, Vol. 11, No. 5, June 1993, pp. 725-729.
  3. Lin, C. H. and Chang, C. C., (1994): "Method for Constructing a Group-Oriented Cipher System," Computer Communications, Vol. 17, No. 11, Nov. 1994, pp. 805-808.
  4. Laih, C. S., Chiou, W. H., and Chang, C. C., (1994): "Authentication and Protection of Public Keys," Computers and Security, Vol. 13, No. 7, 1994, pp. 581-585.
  5. Lee, W. B. and Chang, C. C., (1995): "Authenticated Encryption Scheme without Using a One Way Function," Electronics Letters, Vol. 31, No. 19, Sep. 1995, pp. 1656-1657.
  6. Lin, C. H., Chang, C. C., and Lee, R. C. T. (1995): "A New Public-key Cipher System Based upon the Diophantine Equations," IEEE Transactions on Computers, Vol. 44, No. 1, Jan. 1995, pp. 13-19.
  7. Lee, W. B. and Chang, C. C., (1996): "Integrating Authentication in Public Key Distribution System," Information Processing Letters, Vol. 57, 1996, pp. 49-52.
  8. Lee, W. B. and Chang, C. C., (1996): "On Key Changeable ID-Based Digital Signature Scheme," Journal of Information Science and Engineering, Vol. 12, No. 3, Sep. 1996, pp. 381-386.
  9. Hwang, S. J., Chang, C. C., and Yang, W. P. (1996): "Authenticated Encryption Schemes with Message Linkages," Information Processing Letters, Vol. 58, 1996, pp. 189-194.
  10. Laih, C. S., Kuo, W. C., Gau, M. J., and Chang, C. C., (1997): "On the Number of Messages Cannot be Concealed in LUC," to appear in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences.
  11. Chen, T. S., Chang, C. C., and Hwang, M. S., (1997): "A Virtual Image Cryptosystem Based on Vector Quantization," IEEE Transactions on Image Processing, Vol. 7, No. 10, 1997, pp. 1485-1488.
  12. Lee, W. B. and Chang, C. C., (1998): "Authenticity of Public Keys in Asymmetric Cryptosystems," Computer Communications, Vol. 21, No. 2, pp. 195-198, 1998.

　

（二）有關數位簽署的研究

  1. Chang, C. C. and Liou, F. Y., (1994): "A Digital Multisignature Scheme Based upon the Digital Signature Scheme of a Modified ElGamal's Public Key Cryptosystem," Journal of Information Science and Engineering, Vol. 10, No. 3, Sep. 1994, pp. 423-432.
  2. Chen, C. Y., Chang, C. C., and Yang, W. P., (1995): "A New Subliminal Channel in RSA-Like Variant of the Fiat-Shamir Signature Scheme," Journal of Chinese Institute of Engineers, Vol. 18, No. 6, Sep. 1995, pp. 867-872.
  3. Hwang, S. J., Chang, C. C., and Yang, W. P., (1995): "An Encryption/Signature Scheme with Low Message Expansion," Journal of Chinese Institute of Engineers, Vol. 18, No. 4, Sep. 1995, pp. 591-595.
  4. Chang, C. C., Jan, J. K., and Kowng, H. C., (1997): "A Digital Signature Scheme Based upon Theory of Quadratic Residues," Cryptologia, Vol. XXI, No. 1, Jan. 1997, pp. 55-70.
  5. Chang, C. C. and Jiang, J. H. (1997): "General Multilevel Signature Method for Data Filtering in Mobile Environments," Information Syatems and Technologies for Network Society, (Y.Kambayashi, Y. Masunaga, M. Takizawa, and Y. Anzai Eds.), World Scientific publishing Company, Singapore, 1997, pp. 385-391.
  6. Lee, W. B. and Chang, C. C., (1997): "Efficient Group Signature Scheme Based on Discrete Logarithm," IEE Proceedings － Computers and Digital Techniques, Vol. 145, No. 1, Jan. 1997.
  7. Lee, W. B. and Chang, C. C., (1997): "(t, n) Threshold Digital Signature with Traceability Property," to appear in Journal of Information Science and Engineering, 1997.
  8. Chang, C. C., Leu, J. J., Hwang, P. C., and Lee, W. B., (1998): "A Scheme for Obtaining a Message from the Digital Multisignature," Lecture Notes in Computer Science：Public Key Cryptography, (H. Imai and Y. Zheng Eds.), Springer-Verlag Publishing Company, Germany, 1998, pp.154-163.
  9. Wang, C. T., Lin, C. H. and Chang, C. C., (1998): "Threshold Signature Schemes with Traceable Signers in Group Communications," Computer Communications, Vol. 21, 1998, pp. 771-776.

　

（三）有關破解密碼系統方面之研究

  1. Chang, C. C., Wu, T. C., and Laih, C. S., (1995): "Cryptanalysis of a Password Authentication Scheme Using Quadratic Residues," Computer Communications, Vol. 18, No. 1, Jan. 1995, pp. 45-47.
  2. Lee, W. B. and Chang, C. C., (1995): "Comment on Digital Signature with (t, n) Shared Verification Based on Discrete Logarithms," Electronics Letters, Vol. 31, No. 3, 1995, pp. 176-177.
  3. Chang, C. C., Wu, W. B., and Wu, T. C., (1995): "Cryptoanalysis and Improvement on a Conference Key Distribution System," Journal of the Chinese Institute of Engineers, Vol. 18, No. 3, May 1995, pp. 391-396.
  4. Hwang, S. J., Chang, C. C., and Yang, W. P., (1996): "Some Active Attacks on Fast Server-Aided Secret Computation Protocols for Modular Exponentiation," Lecture Notes in Computer Science - Cryptography Policy and Algorithms ( Dawson and Golic Jovan Eds. ), Springer-Verlag Publishing Company, 1996, pp. 215-227.
  5. Chen, C. Y., Chang, C. C., and Yang, W. P., (1996): "Cryptanalysis of the Secret Exponent of RSA," Journal of Information Science and Engineering, Vol. 12, 1996, pp. 277-290.

　

（四）有關密碼系統的加速運算之研究

  1. Chen, Y. J., Chang, C. C., and Yang, W. P., (1994): "Some Properties of Vectorial Addition Chains," International Journal of Computer Mathematics, Vol. 54, 1994, pp. 185-196.
  2. Chang, C. C., Horng, W. J., and Buehrer, D. J., (1995): "A Cascade Exponentiation Evaluation Scheme Based on the Lempel-Ziv-Welch Compression Algorithm," Journal of Information Science and Engineering, Vol. 11, No. 3, Sep. 1995, pp. 417-431.
  3. Chen, Y. J., Chang, C. C., and Yang, W. P., (1995): "The Shortest Weighted Length Addition Chains," Journal of Information Science and Engineering, Vol. 11, No. 2, June 1995, pp. 295-305.
  4. Chen, Y. J., Chang, C. C., and Yang, W. P., (1995): "Parallel Computation of the Modular Cascade Exponentiation," Journal of Parallel Algorithms and Applications, Vol. 7, 1995, pp. 29-42.
  5. Chen, C. Y., Chang, C. C., and Yang, W. P., (1996): "Hybrid Method for Modular Exponentiation with Precomputation," Electronics Letters, Vol. 32, No. 6, Mar. 1996, pp. 540-541.
  6. Lou, D. C. and Chang, C. C., (1996): "Fast Exponentiation Method Obtained by Folding the Exponent in Half," Electronics Letters, Vol. 32, No. 11, May 1996, pp. 984-985.
  7. Chang, C. C. and Hwang, M. S., (1996): "Parallel Computation of the Generating Keys for RSA Cryptosystems," Electronics Letters, Vol. 32, No. 15, July 1996, pp. 1365-1366.
  8. Lou, D. C. and Chang, C. C., (1996): "A Parallel Two-list Algorithm for the Knapsack Problem," Parallel Computing, Vol. 22, 1996, pp. 1985-1996.
  9. Chang, C. C. and Lou, D. C., (1997): "Parallel Implementation of Multi-Exponentiation for the Public Key Cryptosystem," to appear in International Journal of Computer Mathematics, 1997.
  10. Chang, C. C. and Lou, D. C., (1997): "Parallel Computation of the Multi-Exponentiation for Cryptosystems," International Journal of Computer Mathematics, Vol. 63, No. 1-2, Jan. 1997, pp. 9-26.
  11. Lou, D. C. and Chang, C. C., (1997): "An Adaptive Exponentiation Method," Journal of Systems and Software, Vol. 42, 1997, pp. 59-69.
  12. Chang, C. C. and Lou, D. C., (1997): "An Efficient Divide-and-Conquer Technique for Parallel Computation of Modular Multi-Exponentiation," to appear in Computer Systems Science and Engineering, 1997.

　

　

四. 結論

　

　　歷史上第一篇討論密碼系統理論的文章是1949年由Shamir所提出的，至1960年代後期IBM公司才開始有了電腦密碼學的研究計畫，迄1977年美國國家標準局(NBS)正式建議採用DES (Data Encryption Standard) 為數據加密的標準，事隔一年之後，美國麻省理工學院的三位學者提出了RSA公開金匙密碼系統，此後電腦密碼系統之研究便如雨後春筍般地蓬勃發展起來。日本也在1984年正式成立了資訊安全協會，帶動日本學界及產業界密碼學的快速發展。回顧我國電腦密碼學的發展，在這個領域的研究我們大約比日本慢了六年。

　　目前看起來，密碼學研究最先進的國家仍然是美國，而在亞洲方面當是日本首屈一指。這個領域隨著網路的興起及個人電腦的普及及電子商務時代的來臨將會愈來愈重要。

　　為了加速密碼系統研究成果的交流，目前世界上有三個最有名的密碼學國際會議，它們是Crypto，Eurocrypto及Asiacrypto。這三個密碼學國際會議平均每年或每兩年舉辦一次，每一次的會議均會有許多重要的密碼學新觀念被提出來。除此之外，近年來，多數的資訊與通訊相關的國際學術期刊亦常刊載密碼學的最新研究成果。我覺得做我們這一行研究的人，一定要非常投入，對於最新的研究方向，一定要能隨時掌握。因此我們密碼學研究群每週固定一個下午舉行密碼學論文研討，請同學們輪流上台報告國際學術期刊及重要國際會議所發表的最新研究成果，以抓住密碼學學術研究的脈動。

　　多年來，我感覺到國內在密碼學方面的研究有兩點須要特別留意的。一是研究的開創性不足，我們在研究上一直是繞著別人指出來的問題及所提出來的方法在想改進之道，卻較少去high light新的研究導向。其次是想出了太多「花拳繡腿」式的花招。我們國家一直想盡辦法培植學術界大師級的人物，但學術生態卻無形中引導學者們往「速成」的方向去做研究。如何才能讓國內的學者也能想出一個「RSA密碼系統」？這是一個值得大家深思的問題。

　

 連絡地址：(106)台北市和平東路二段１０６號２０樓

連絡電話：(02)27377312　傳真電話：(02)27377673