跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.87) 您好!臺灣時間:2025/02/17 13:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張黃道
研究生(外文):Hwang-Daw Chang
論文名稱:新的Skip-and-Go亂數序列產生器之實現與應用
論文名稱(外文):A New Skip-and-Go Sequence Generator with Implementation and Applications
指導教授:涂世雄涂世雄引用關係黃景東黃景東引用關係
指導教授(外文):Shih-Hiung TwuJung-Dong Huang
學位類別:碩士
校院名稱:中原大學
系所名稱:電機工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:156
中文關鍵詞:串流密碼器亂數序列產生器線性回授移位暫存器線性複雜度通信安全
外文關鍵詞:LFSRPseudorandom sequenceLinear complexityComSecStream cipher
相關次數:
  • 被引用被引用:0
  • 點閱點閱:284
  • 評分評分:
  • 下載下載:11
  • 收藏至我的研究室書目清單書目收藏:0
摘要
本論文推薦一種新機制的亂數序列產生器,稱為skip-and-go亂數序列產生器,它是以最大序列之線性回授移位暫存器(LFSR),搭配 k-層記憶體及skip控制電路及非線性函數電路組成。
傳統的LFSR式亂數產生器只有一個"go"處理程序,亦即在外部時序觸發時,移位暫存器執行移位及透過非線性函數產生亂數序列,整個亂數序列的週期係以載入的金鑰為起始值,到最大週期時,亂數序列開始循環。
skip-and-go亂數序列產生器利用k -層記憶體佇存著序列最大週期的狀態值,在每一"go"處理程序之後,接著執行"skip"處理程序,此程序在於檢查移位暫存器是否到達了序列最大值,若相等,則意味著週期已達循環點,進而強迫移位暫存器移位至下一個狀態,使其進入另外的一種亂數序列。如此的機制,使得亂數序列週期得以擴展。舉個例子,在n位元長度的LFSR, 其序列週期長度為(2^n)-1,隨著搭配不同的非線性函數,其線性複雜度為n至(2^n)-1 。skip-and-go亂數序列產生器因為k-層記憶體的比對及"skip"處理程序機制, 週期可擴展到4{(2^n)-1}^(k+1),搭配我們所設計的非線性函數, 其線性複雜度會提升到為4{(2^n)-1}^(k+1),換言之,我們以n位元級數的skip-and-go亂數序列產生器所產生的亂數序列,非授權者若要以暴力攻擊則需4{(2^n)-1}^(k+1)位元級數的線性回授移位暫存器,方能重新構建與我們相同的亂數序列。
本論文對於skip-and-go亂數序列產生器顯示下列五項重要研究結果:
一. 藉由簡單的k -層記憶體及"skip"處理程序,我們設計出線性複雜度可以以指數成長的skip-and-go演算法,並經由序列週期延展分析,推導其線性複雜度的計算公式。
二. 模擬及驗證skip-and-go亂數序列產生器所產生的亂數序列,確認此架構所產生的亂數序列符合我國及美國密碼模組亂數檢測標準。
三. 模擬及驗證skip-and-go亂數序列產生器及一些傳統典型的LFSR式亂數產生器所產生的亂數序列,確認skip-and-go亂數序列產生器所產生的亂數序列之安全特性優於其他亂數產生器。
四. 以可程式化場閘陣列元件(FPGA)實現skip-and-go亂數序列產生器,證明本演算法在硬體實作上不但簡易性實現,且符合我國及美國密碼模組實體保護檢測標準。
五. 最後我們提出單向赫序函數/訊息鑑別碼的應用實例,證明skip-and-go演算法除了應用在密碼學上的串流密碼器外,仍具有相當廣泛的應用領域。
“具有高線性複雜度的亂數序列並不表示此亂數序列是安全的,但是低線性複雜度的亂數序列是絕對不安全的”,所以如何設計一個具有極高線性雜雜度的亂數序列產生器是資訊或通信安全的基本設計要求。skip-and-go亂數序列產生器的線性複雜度隨著金鑰的長度及k-層記憶體的層數以指數倍成長,所以是一個極具安全特性及實用價值的亂數產生器。
Abstract
This thesis proposed a new pseudorandom sequence generator, called the skip-and-go sequence generator. It is composed of maximum sequence linear feedback shift register (LFSR), k-layer memory and skip control circuit for generating basic pseudorandom sequences. Then, the practical pseudorandom sequences are generated through a nonlinear function circuit.
In general, a typical LFSR pseudorandom sequence generator has only one "go" process. When clock triggered,it starts to shift the states from seeds (key), run to its maximum length. However, the skip-and-go sequence generator, proposed by the authors, executes "skip" process after every "go" process, according to current contents of k-layer memory. The contents of k-layer memory are determined by the states of LFSR.
In our design, if the LFSR has arrived at its maximum length, it was forced to execute the skip operation for initializing a new sequence. Such mechanism can expand the period of the sequence generated by LFSR. For instance, the period of n-bits typical LFSR is (2^n)-1, and its linear complexity (LC) may be n or up to (2^n)-1 depend on what kinds of nonlinear function circuits are used. On the other hand, the period and LC of the skip-and-go sequence generator can be expanded up to 4{(2^n)-1}^(k+1).
In other words, threats want to the pseudorandom sequence by our skip-and-go mechanism with n-bits LFSR, it needs a 4{(2^n)-1}^(k+1) bits traditional LFSR.
There are four distinguished research results of the skip-and-go sequence generator in this thesis as follows:
(1). To test and verify LC up to 4{(2^n)-1}^(k+1).
(2). Simulation skip-and-go sequence generator and some typical LFSR pseudorandom sequence generator, and list them test results of randomness and LC.
(3). Implement the skip-and-go sequence generator in hardware by field programmable gate array technology (FPGA) device.
(4). Besides the stream cipher, The skip-and-go sequence generator is still used in the wide application field shown that by the application example of one-way hash function or message authentication codes (MAC).
"Remember that a high linear complexity does not necessarily indicates a security generator, but
a low linear complexity indicates an insecure one." Hence, the high linear complexity is still a very essential
condition for pseudorandom sequence generator design. Consequently, the proposed skip-and-go mechanism is
a better scheme for pseudorandom sequence generator design since its LC grows with exponential rate.
第一章 簡介
第二章 傳統線性回授移位暫存器式亂數序列產生器
第三章 Skip-and-Go 亂數序列產生器
第四章 安全特性測試與評估
第五章 硬體實現
第六章 單向赫序函數與訊息鑑別碼之應用
第七章 結論與未來研究方向
英文附錄
1 Introduction
1.1 Backgrounds
1.2 Introduction of Cryptography
1.2.1 Contemporary Cryptography
1.2.2 Classical Cryptography
1.3 Contribution and Motive of Research
1.4 Organization of The Thesis
2 Previous Studies on Linear Feedback Shift Register Based Sequence Generator
2.1 Single Sequence Mode
2.1.1 Single LFSR Sequence Generator
2.1.2 Single Sequence with Combinational Sequence Generator
2.2 Multi-Sequence Mode
2.3 Multi-Clocking Mode
2.3.1 Beth-Piper Stop-and-Go Sequence Generator
2.3.2 Gollmann Cascade Stop-and-Go Sequence Generator
2.3.3 Rueppel''s Self-decimation of m-Sequence
2.3.4 Gollmann''s Self-decimation Sequence
2.4 Arbitrary Mode
2.4.1 Geffe Sequence Generator
2.4.2 Real Adder Sequence Generator
2.5 Summary
3 Skip-and-Go Sequence Generator
3.1 Design Concept
3.2 Approach
3.3 Summary of Algorithm
3.3.1 Initial State
3.3.2 Idle State
3.3.3 Go State
3.3.4 Skip State
3.4 Statistical Analysis
3.5 Skip-and-Go Sequence Generator in RAM Mode
3.6 Summary
4 Tests and Evaluations
4.1 Random Number Test Theory
4.2 Random Number Test Standards
4.3 Test Tools - CRYPT-X''98
4.4 Performance Evaluation of Skip-and-Go Sequence Generator
4.4.1 Evaluation under FIPS PUB 140-1 Standard
4.4.2 Evaluation with Different Value of k
4.4.3 Evaluation of Different Random Sequence Generator
4.4.4 Efficiency of Key Management
4.5 Summary
5 Skip-and-Go Sequence Generator Implementation by FPGA
5.1 Design Concept and Tools
5.2 Circuit Design and Operation Description
5.2.1 LFSR Module
5.2.2 RAM Module
5.2.3 SKIP_CTL Module
5.2.4 NOLINEAR Module
5.3 Results of Waveform Simulation
5.3.1 Waveform Simulation of Initial State
5.3.2 Waveform Simulation of Go State
5.3.3 Waveform Simulation Skip state
5.4 Skip-and-Go Sequence Compare with Standard LFSR sequence
5.5 Chip Resource Usages
5.6 Summary
6 An Application at One-Way Hash Function and Message Authentication Codes
6.1 Design Concept
6.2 Implementation Steps
6.3 Summary
7 Conclusions and Future Researches
Bibliography
Appendix
A Source Program
A.1 Skip-and-Go sequence generator
A.2 Gollmann Cascade Stop-and-Go sequence generator
A.3 Beth-Piper sequence generator
A.4 Single LFSR sequence generator
A.5 Real Adder sequence generator
A.6 Geffe sequence generator
B AHDL Code of Skip-and-Go FPGA Chip Design
B.1 5X8RAM_CORE.tdf
B.2 MUX5_2.tdf
B.3 MUX3_2.tdf
B.4 MUX2_1.tdf
B.5 5SFR.tdf
B.6 CNT2.tdf
B.7 REALADDER.tdf
B.8 MSTEP_ROM.tdf
B.9 MICROSTEP_CNT.tdf
B.10 nCMP0.tdf
B.11 nCMP1.tdf
B.12 nRD_CNT.tdf
B.13 nWR_CNT.tdf
C Source Code of Skip-and-Go FPGA Chip Design
C.1 Source code of ROM_TBL.HEX
[1] W. Stallings, Cryptography and Network Security Principles and Practice, Prentice Hall, 1999.[2] D. Weissman, D. W. Dudich and M. S. Grob, "End-to-End Security for Commercial PCS Network", IEEE MILCOM''95, vol. 3, pp. 1253-1257, Nov. 1995. [3] F. Warwick, S. B. Michael, Secure Electronic Commerce, Prentice Hall, 1997.[4] R. M. Yang, "Development at Today and trend of Eectronic Commerce", Information Security Newsletter, CCISA, vol. 5, no.2, pp. 34-35, Mar. 1999.[5] J. Z. Huang, "A Preface of Special Compilation", Information Security Newsletter, CCISA, vol. 5, no.2, pp. 33, Mar. 1999.[6] R. L. Rivest, M. E. Hellman, J. C. Anderson, and J. W. Lyons, "Responses to NIST''s Proposal", Communications of the ACM, vol. 35, no.7, pp.41-54, jul. 1992. [7] H. C. A. van Tillborg, An Introduction to Cryptology, Kluwer Academic Publishers, 1989.[8] W. G. Barker, Cryptanalysis of Shift-Register Generated Stream Cipher Systems, 1984.[9] R. A. Rueppel, Analysis and Design of Stream Ciphers, Springer-Verlag, 1986.[10] J. H. Chiu, "Stream Cihper", Manuscript Lecture, 1997. [11] C. S. Laih, L. Harn and C. C. Chang, Contemporary Cryptography and Its Applications, UNALIS, 1995.[12] B. Schneier, Applied Cryptography - Protocols, Algorithms, and Source Code in C, John Wiley & Sons, Inc., 1996.[13] D. G. W. Birch and I. J. Shaw, "Mobile Communication Security-Private or Public", Security and Cryptography Application to Radio Systems, IEE Colloquium on, pp. 5/1-5/6, Jun. 1994. [14] M. Soriano, "Stream Ciphers Based on NLFSR", Telecommunications Symposium, vol. 2, pp. 528-533, Aug. 1998.[15] C. C. Lo, Y. J. Chen, "A Secure Communication Architecture for GSM Network", Communications, Computers and Signal Processing, 1999 IEEE Pacific Rim Conference on, pp. 221-224, Aug. 1999.[16] C. C. Lo, Y. J. Chen, "Stream Cipher for GSM Networks", Communications, 2000. ICC 2000 IEEE International Conference on, vol. 1, pp. 80-84, Jun. 2000.[17] S. Sengodan, D. Smith and M. Abou-Rizk, "On End-to-End Security for Bluetooth/WAP and TCP/IP Networks", Personal Wireless Communications, 20000 IEEE International Conference on, pp. 399-403, Dec. 2000.[18] K. Zeng, C. H. Yang, D. Y. Wei and T.R.N. Rao, "Pseudorandom Bit Generators in Stream-Cipher Cryptography", Computer, vol. 24, issue 2, pp. 8-17, Feb. 1991.[19] G. L. Mayhew, "A Low Cost, High Speed Encryption System and Method", Research in Security and Privacy, 1994. Proc., 1994 IEEE Computer Society Symposium on, pp. 147-154, May. 1994.[20] M. H. Shao and J. Z. Huang, "Cryptography technique of SET : evaluation of an advantage and a fault", Information Security Newsletter, CCISA, vol. 6, no.1, pp. 50-61, Dec. 1999.[21] C. H. Lin, "Security Eectronic Commerce of Network", Information Security Newsletter, CCISA, vol. 5, no.2, pp. 67-71, Mar. 1999.[22] F. L. Mayer, W. C. Barker, T. K. Haley, J. N. McAuliffe, D. F. Sterne and L. S. Vidmar, "Evaluation Issue for an Integrated "INFOSEC" Product", Computer Security Applications Conference, pp. 271-275, Dec. 1989.[23] R. Benjamin, "Security Considerations in Communications Systems and Network", Communications, Speech and Vision, IEE Proc. I, vol. 137, issue 2, pp. 61-72, Apr. 1990.[24] D. R. Stinson, Cryptography Theory and Practice, Boca Raton, Fla. CRC Press, 1995.[25] R. A. Rueppel, "Good Stream Cipher are Hard to Design", Security Technology, 1989. Proc. 1989 International Carnahan Conference on, pp. 163-174, Oct. 1989.[26] N.I.S.T., Announcing the Advanced Encryption Standard (AES), http://csrc.nist.gov/encryption/aes/, 2001.[27] A. J. Elbirt, W. Yip, B. Chetwynd, and C. Paar, "An FPGA-Based Performance Evaluation of the AES Block Cipher Candidate Algorithm Finalists", Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 9, issue 4, pp. 545-557, Aug. 2001.[28] C. S. Laih, "Information Security Actions and Development of R.O.C.", Information Security Newsletter, CCISA, vol. 5, no.2, pp. 20-32, Mar. 1999.[29] W. T. Penzhorn, "Complexity Measures for Cryptographic Sequences", COMSIG 1991 Proc., pp. 178-185, Aug. 1991.[30] A. H. Chan, M. Goresky, and A. Klapper, "On the Linear Complexity of Feedback Registers", IEEE Trans. Information Theory, vol. 36, no.3, pp. 640-644, May. 1990.[31] X. M. Wang and G. Xiao, Error Correcting Code - Principle and method, Ru-Lin Books Co., 1991.[32] W. G. Chambers, "Clock-Controlled Shift Registers in Binary Sequence", IEE Proc., vol. 135, no.1, pp. 17-24, Jan. 1988.[33] D. GOLLMANN and W. G. CHAMBERS, "Clock-Controlled Shift Register: A Review", IEEE Journal on Selected Areas in Communications, vol. 7, no.4, pp. 525-533, May. 1989.[34] J. D. Golic, "Cryptanalysis of There Mutually Clock-Controlled Stop-and-Go Shift Register", IEEE Trans. on Information Theory, vol. 46, no.3, pp. 1081-1089, May. 2000.[35] R. Menicocci, J. D. Golic, "Correlation Attacks on Up/Down and Stop-and-Go Cascades", IEEE Trans. on Information Theory, vol. 45, no.2, pp. 486-498, Mar. 1999.[36] W. G. Chambers, D. Gollmann, "Generators for Sequences with Near-Maximal Linear Equivalence", Computers and Digital Techniques, IEE Proc. E, vol. 135, issue 1, pp. 67-69, Jan. 1988.[37] C. K. Chan, L. M. Cheng, "Design of Keystream Generator", Electronics Letters, vol. 34, no.12, pp. 1206-1207, Jun. 1998.[38] K. Chakrabarty, J. P. Hayes, "Balanced Boolean Functions", Computers and Digital Techniques, IEE Proc. on, vol. 145, issue 1, pp. 52-62, Jan. 1998.[39] M. M. Alabbadi, R. M. Alrumiah, and M. Adi, "On the Comparison of Pseudo-random Number Generator for VLSI Applications", Microelectronics, 1998. ICM ''98. Proc. of the Tenth International Conference on, pp. 262-264, Dec. 1998.[40] W. N. Havener, R. J. Medlock, L. D. Mitchell, R. J. Walcott, Derived Test Requirements for FIPS PUB 140-1, Security Requirements for Cryptographic Modules, N.I.S.T., Mar. 1995.[41] CCISA, "Technology Standard of Communications Cryptographic Modules and Project of Development Related verify Technology", CCISA, vol. 6, no.2, pp. 37-66, Mar. 2000.[42] E. Dawson, A. Clark, H. Gustafson, L. Nielsen and M. Rutherford,CRYPT-X''98, Queensland University of Technology, 1998.[43] M. McLoone and J. V. McCanny, "A High Performance FPGA Implementation of DES", Signal Proc. Systems. 2000. SiPS 2000. 2000 IEEE Workshop on, pp. 374-383, Oct. 2000.[44] W. Millan, K. Wong, M. Wark and E. Dawson, "A Single-Chip FPGA Implementation of A Self-Synchronous Cipher", TENCON''97. IEEE, vol. 1, pp. 223-226, Dec. 1997.[45] K. Wong, M. Wark and E. dawson, "A Single-Chip FPGA Implementation of The Data Encryption Standard (DES) Algorithm", GLOBECOM 1998, vol. 2, pp. 827-832, Nov. 1998.[46] ALTERA 1998 DATA BOOK, Altera Co., 1998. [47] G. Tsudik, "Message Authentication with One-Way Hash Functions", INFOCOM ''92, vol. 3, pp. 2055-2059, May. 1992.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top