臺灣博碩士論文加值系統

本文將針對Gollmann Cascades亂數產生器來進行安全性分析，並提出一套演算法來改善其產生金鑰的效能。在安全性分析方面，我們採用Golomb的三種亂度基本條件、序列的線性複雜度及其輪廓等五種亂度分析法來分析Gollmann Cascades產生的擬亂序列(金鑰)及觸發序列，並探討改變Stage串接個數、LFSR的length個數及反饋函數對擬亂序列及觸發序列之亂度的影響。
除此之外，我們還發展出一套只需知道少數資訊(例如: length、Stage個數)就能取得反饋函數的攻擊法，由於此攻擊法必須先將擬亂序列分割成等長的區塊才能進行攻擊，所以我們稱之為區塊攻擊法。在擬亂序列長度足夠的情況下，此攻擊法對於多Stage與多length的Gollmann Cascades亦適用。
Gollmann Cascades一般都是以硬體實現，所以在一clock cycle內每個stage都可運作，但是若以軟體模擬，在一clock cycle內只有一個stage能運作。因此我們提出一套快速生成金鑰演算法，來提高Gollmann Cascades產生擬亂序列的軟體執行效率。

The security of Gollmann Cascades pseudorandom number generator is analyzed in this paper. Additional, an algorithm is proposed to improve the software efficiency for generating keystreams. In the security analysis, Golomb’s three randomness postulates, linear complexity, and profile of linear complexity were utilized to analyze Gollmann Cascades. The degree of randomness by changing the amount of Stage, length of LFSR, and feedback functions is discussed.
To attack a pseudorandom number generator is a part of security analysis. Some methods are developed to obtain the feedback functions with fewer information. The keystream of Gollmann Cascades is first divided into several blocks in these methods. Hence, these methods are called block attacks. Under the condition that the keystream is sufficiently long, block attacks can also be used on longer length of LFSR or longer cascades as well.
Gollmann Cascades is generally implemented in hardware, every stage can operate at one clock cycle. If it is implemented in software, there is only one stage can operate at one clock cycle. In order to improve the software efficiency for generating keystreams, we propose an algorithm to generate a huge keystream faster.

中文摘要………………………………………………… i
英文摘要………………………………………………… ii
誌謝 ………………………………………………… iii
目錄 ………………………………………………… iv
表目錄 ………………………………………………… vi
圖目錄 ………………………………………………… vii

ㄧ、緒論
1.1 研究動機與目的…………………………………… 1
1.2 論文架構…………………………………………… 2
二、Gollmann Cascades亂數產生器之安全性分析
2.1 亂數產生器原理簡介……………………………… 3
2.2 相關研究與知識…………………………………… 4
2.3 亂度分析法………………………………………… 7
2.4 序列週期搜尋演算法……………………………… 9
2.5 分析結果…………………………………………… 10
三、區塊攻擊法(Block Attacks on Gollmann Cascades)
3.1 先前對於Gollmann Cascades之攻擊法...……… 18
3.2 擬亂序列的特性…………………………………… 18
3.3 區塊攻擊法之設計原理…………………………… 18
3.4 三種區塊攻擊法之使用時機與攻擊步驟………… 19
四、Gollmann Cascades之快速生成金鑰演算法
4.1 發展快速生成金鑰演算法之重要性……………… 24
4.2 預測各Stage的輸出序列緩衝期………………… 24
4.3 快速生成金鑰演算法……………………………… 28
4.4 效能分析…………………………………………… 28
五、結論與未來發展
5.1 Gollmann Cascades安全性分析之結論…………… 31
5.2 區塊攻擊法之結論………………………………… 32
5.3 快速生成金鑰演算法之結論……………………… 33
5.4 未來發展方向……………………………………… 33
參考文獻………………………………………………… 35
附錄……………………………………………………… 37
自傳……………………………………………………… 56

[1]W. T. Penzhorn, C. S. Bruwer, 2002, “New correlation attacks on stream ciphers”, In Proceedings of the IEEE Africon 2002 Conference, IEEE, pp. 203 – 208.
[2]R.J. Anderson, 1993, “Faster attack on certain stream ciphers”, Electronics Letters, Vol. 29, pp.1322 – 1323.
[3]D. R. Stinson, 1995, Cryptography - Theory and Practice, CRC Press.
[4]D. Gollmann, 1985, “Pseudo Random Properties of Cascade Connections of Clock Controlled Shift Registers”, Advances in Cryptology-EUROCRYPT ''84, Springer- Verlag, pp. 93-98.
[5]D. Gollmann and W. G. Chambers, 1989, “Clock-controlled shift registers: A review”, IEEE Journal on Selected Areas in Communications, vol. 7, no. 4, pp. 525–533.
[6]B. Schneier, 1996, Applied Cryptography: Protocols, Algorithms, and Source Code in C, Wiley, New York.
[7]S. W. Golomb, 1982, Shift Register Sequences, Aegean Park Press, Laguna Hills.
[8]L. Xian, X. Guozhen, 1992, “Linear complexity of a type of clock controlled sequence”, Electronics Letters, vol. 28, no. 8, pp. 709–710.
[9]R.A. Rueppel, 1984, New approaches to stream ciphers, Swiss Federal Institute of Technology, Ph. D. dissertation.
[10] R. A. Rueppel, 1986, Analysis and Design of Stream Ciphers, Springer-Verlag, New York.
[11]NIST Special Publication 800-22, 2001, “A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications”, http://csrc.nist.gov/rng/rng2.html.
[12]W.G. Chambers and D. Gollmann, 1988, “Lock-In Effect in Cascades of Clock- Controlled Shift-Registers”, Advances in Cryptology EUROCRYPT ''88, pp. 331-343.
[13]R. Menicocci, 1993, “Cryptanalysis of a two-stage Gollmann cascade generator”, Proceedings of SPRC ''93, pp. 62–69.
[14]R. Menicocci, 1995, “Short Gollmann cascade generators may be insecure”, In Proceedings of the 4th IMA Conference on Cryptography and Coding, pp. 281–297.
[15]R. Menicocci, 1995, “A systematic attack on clock controlled cascades”, Advances in Cryptology EUROCRYPT’94, Springer-Verlag, vol. 950, pp. 450–455.
[16]W. Meier, O. Staffelbach, 1992, “Correlation properties of combiners with memory in stream ciphers”, Journal of Cryptology, vol. 5, no. 1, pp. 67–86.
[17]S. J. Lee, S. J. Park, S. C. Goh, 1995, “On the security of the Gollmann cascades”, Advances in Cryptology CRYPTO’95, Springer-Verlag, vol. 963, pp. 148–157.
[18]R. Menicocci, J. D. Golic, 1999, “Correlation Attacks on Up/Down and Stop/Go Cascades”, IEEE Transactions on Information Theory, vol. 45, no. 2, pp. 486–498.
[19]N. Koblitz, 1987, A Course in Number Theory and Cryptography, Springer-Verlag.
[20]D. Gollmann, W. G. Chambers, 1990, “A cryptanalysis of stepk,m-cascades,” Advances in Cryptology EUROCRYPT’89, Springer-Verlag, vol. 434, pp. 680–687.
[21]A. Klapper, M. Goresky, “Feedback Shift Registers, 2-Adic Span, and Combiners with Memory”, Journal of Cryptology, 1997, vol. 10, no. 2, pp.111–147.