配備非線性前饋邏輯的線性反饋移位暫存器之研究

Abstract

近年來，串流密碼的理論得到快速的發展。一個理想的串流加密器，其設計上的主要關鍵在於密鑰流產生器，即密鑰流序列的週期要大、隨機性要好、線性複雜度要高等等。 本論文主要研究以線性反饋移位暫存器(LFSR)為基本架構的密鑰流產生器，我們採用傳統的方法建構可產生最長週期序列( 序列)之LFSR，但是 序列線性複雜度過低，於是利用非線性前饋網路來提高線性複雜度。另外介紹衡量序列隨機性的標準、檢測方法，以及隨機序列的特性，透過這些理論，幫助我們檢定密鑰流序列是否有良好隨機性。

The theory of the stream cipher has developed quickly these years. The most important part of the architecture of the stream cipher is the Running Key Generator(RKG). For security reasons, the key stream generated by the RKG should satisfy a few demands such as long period, high linear complexity, good randomness, etc. The primary objective of this thesis is to study the RKG which is based on the Linear Feedback Shift Register(LFSR). We adopt a conventional method to construct the maximal-length LFSR which can generate the sequence with very long period. But these sequences do not have high linear complexity. To overcome the drawback, we give another model which is based on the LFSR with nonlinear feedforward logic. By this model, we can promote the linear complexity of the output sequences easily. Moreover, we also introduce some methods to test the randomness of any sequence.