本文關(guān)鍵詞： Fibonacci NFSR 串聯(lián) 仿射子簇 Grain v1　出處：《解放軍信息工程大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著近十年國際序列密碼設(shè)計思想的轉(zhuǎn)變,非線性反饋移位寄存器(NFSR)逐漸成為序列密碼算法中重要的序列源生成器,因此對NFSR序列密碼性質(zhì)的研究受到很多關(guān)注.然而NFSR序列的基礎(chǔ)理論還很不完善,許多基本的密碼性質(zhì)仍不清楚.例如,NFSR的輸出序列中是否包含線性復(fù)雜度較低的序列.如果NFSR的輸出序列中包含大量低線性復(fù)雜度的序列,則基于該NFSR的密碼體制可能受到相關(guān)攻擊,代數(shù)攻擊或者是基于線性逼近的其它攻擊.特別地,如果一個n級NFSR的輸出序列包含一個級數(shù)小于n的線性反饋移位寄存器(LFSR)的輸出序列全體,則稱該n級NFSR有一個仿射子簇.如果一個NFSR_1能夠分解為一個NFSR2到一個LFSR的串聯(lián),并且NFSR2的特征函數(shù)常數(shù)項為0,則該LFSR是NFSR_1的仿射子簇.NFSR包括Fibonacci NFSR和Galois NFSR.本文研究的是Fibonacci NFSR的仿射子簇問題,取得了以下主要結(jié)果:1.對于一個NFSR_1,給出了NFSR_1分解為一個NFSR2到一個LFSR串聯(lián)的算法,并求出所有這樣的分解.本文說明了所有這樣的分解可以通過二元有限域上的單變元多項式分解得到.進一步,證明了如果NFSR_1有如上分解,則當(dāng)NFSR2輸出序列集中有一條低線性復(fù)雜度的序列時,NFSR_1的輸出序列集中包含大量低線性復(fù)雜度的序列.特別地,當(dāng)NFSR2的特征函數(shù)常數(shù)項為0時,NFSR_1的輸出序列集中包含LFSR的輸出序列全體.2.如果一個NFSR包含仿射子簇,稱能夠生成該仿射子簇的最短LFSR的級數(shù)為該仿射子簇的階.本文給出了一個新的估計NFSR仿射子簇最大階上界的方法,說明了該上界是緊的并且證明了該上界可以通過NFSR特征函數(shù)的代數(shù)正規(guī)型直接得到.3.Grain v1的160級NFSR是由一個80級LFSR到一個80級NFSR串聯(lián)而成.本文研究了如何求取該160級NFSR仿射子簇的問題.首先,本文證明了如果160級NFSR包含仿射子簇,則該仿射子簇必然是80級NFSR的仿射子簇.其次,利用2的結(jié)果,得到80級NFSR不包含階大于31的仿射子簇.最后,設(shè)計了兩個算法求解80級NFSR階小于32的仿射子簇.實驗結(jié)果表明除了包含一個2階仿射子簇,Grain v1的160級NFSR不包含其它仿射子簇.
[Abstract]:With the change of the international sequence cipher design idea in recent ten years, the nonlinear feedback shift register (NFSRs) has gradually become an important sequence source generator in the sequence cipher algorithm. Therefore, much attention has been paid to the study of the cryptographic properties of NFSR sequences. However, the basic theory of NFSR sequences is not perfect. Many basic cryptographic properties are still unclear. For example, whether the output sequence of NFSR contains a sequence with lower linear complexity. If the output sequence of NFSR contains a large number of sequences with low linear complexity, Then the cryptosystem based on the NFSR may be attacked by correlation attack, algebraic attack or other attack based on linear approximation. If the output sequence of an n-order NFSR contains all the output sequences of a linear feedback shift register with a series less than n, then the n-order NFSR has an affine subfamily. If a NFSR_1 can be decomposed into a series of NFSR2 to a LFSR, And the characteristic function constant term of NFSR2 is 0, then the LFSR is an affine subfamily of NFSR_1. NFSR includes Fibonacci NFSR and Galois NFSR. In this paper, we study the affine subcluster of Fibonacci NFSR. The following main results are obtained: 1. For an NFS _ S _ 1, an algorithm is given to decompose NFSR_1 into a NFSR2 to a LFSR concatenation. All such decompositions are obtained. In this paper, we show that all such decompositions can be obtained by the polynomial decomposition of univariate variables over a binary finite field. Furthermore, it is proved that if NFSR_1 is like the upper decomposition, Then when there is a low linear sequence in the NFSR2 output sequence set, the output sequence set of NFSR1 contains a large number of low linear complexity sequences. When the characteristic function constant term of NFSR2 is 0:00, the output sequence set of NFS _ S _ S _ 1 contains the output sequence of LFSR. 2. If a NFSR contains an affine subfamily, The shortest LFSR series that can generate the affine subfamily is called the order of the affine subfamily. In this paper, a new method to estimate the upper bound of the maximum order of the NFSR affine subfamily is presented. This paper shows that the upper bound is compact and proves that the upper bound can be directly obtained by the algebraic normal form of the NFSR characteristic function. 3. The NFSR of grain v1 is formed in series from an 80 order LFSR to an 80 order NFSR. In this paper, we study how to obtain the NFSR of order 80. The problem of NFSR affine subclusters of order 160. first, In this paper, we prove that if the NFSR of order 160 contains an affine subfamily, the affine subfamily must be an affine subfamily of order 80 NFSR. Secondly, by using the result of 2, we obtain that the NFSR of order 80 does not contain an affine subfamily of order greater than 31. Two algorithms are designed to solve the affine subfamilies with order 80 NFSR less than 32. The experimental results show that no other affine subfamilies are included except for the 160-order NFSR containing a second-order affine cluster grain v1.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TN918.1

【相似文獻】

相關(guān)期刊論文 前10條

1 徐結(jié)綠,徐漢良,呂述望;仿射全向置換的構(gòu)造和計數(shù)[J];通信技術(shù);2003年05期

2 龔石鈺;;兩平面場仿射及其在工程上的應(yīng)用[J];成都科技大學(xué)學(xué)報;1989年06期

3 李天寶,陳文波,石世宏;仿射圖形的計算機作圖方法的研究[J];南華大學(xué)學(xué)報(理工版);2003年01期

4 劉黎,董培蓓;平行線束法的仿射研究[J];工程圖學(xué)學(xué)報;2004年04期

5 張青,李永慈,唐守正;基于仿射重構(gòu)的樹高測量[J];計算機工程與應(yīng)用;2005年31期

6 張桂梅;任偉;儲s，

本文編號：1532303