非線性反饋移位寄存器序列若干問題研究
發(fā)布時間：2019-02-13 07:32
【摘要】：采用非線性反饋移位寄存器(簡稱NFSR)序列取代線性反饋移位寄存器(簡稱LFSR)序列作為驅(qū)動序列逐漸成為序列密碼設(shè)計的主流趨勢,因此NFSR序列也成為當(dāng)前序列密碼研究領(lǐng)域的一個熱門課題.雖然研究歷史已達(dá)半個世紀(jì)之久,然而由于非線性問題的困難性,目前NFSR序列很多基本的密碼性質(zhì)尚不清楚,如圈結(jié)構(gòu)、串聯(lián)分解以及子簇求解等問題.圍繞上述問題,本文主要取得了以下研究成果:1.稱周期達(dá)到2n的n級NFSR序列為n級de Bruijn序列,它具有比較理想的偽隨機(jī)性質(zhì).本文給出了能夠生成n級de Bruijn序列NFSR的一個新的必要條件,并對該條件能夠涵蓋的NFSR進(jìn)行了計數(shù),計數(shù)結(jié)果表明該條件可以涵蓋大量的NFSR.進(jìn)一步地,基于布爾函數(shù)的BDD表示,給出了該必要條件的一個驗證算法并分析了該算法的復(fù)雜度.2.NFSR的圈結(jié)構(gòu)是指該NFSR可以生成多少個圈及每個圈的圈長是多少.1976年,K.Kjeldsen基于抽象代數(shù)的方法完全確定了一類對稱NFSR的圈結(jié)構(gòu).本文首先確定了兩類NFSR生成的部分圈的圈長,在此基礎(chǔ)上,完全刻畫了更大一類對稱NFSR的圈結(jié)構(gòu).這一結(jié)果涵蓋了K.Kjeldsen的結(jié)果而且方法更加初等直觀.此外,計數(shù)結(jié)果表明,超過一半的對稱NFSR具有本文所刻畫的圈結(jié)構(gòu).3.討論了NFSR串聯(lián)分解是否唯一的問題.具體地,針對給定NFSR可以分解為更低級數(shù)NFSR到LFSR串聯(lián)的情形,給出了其具有此種分解的一個充要條件,并據(jù)此證明了所有這樣分解中,級數(shù)最大的LFSR是唯一的.最后,構(gòu)造了一類反例表明,一般的串聯(lián)分解并不唯一.4.記以f為特征函數(shù)的NFSR為NFSR(f),并記NFSR(f)全體生成序列的集合為G(f).給定NFSR(f)和NFSR(h),如果G(h)?G(f),則稱G(h)是G(f)的一個子簇.若G(f)含有子簇,那么NFSR(f)生成的部分序列可以由更低級數(shù)的NFSR(h)來生成,這是一種退化性質(zhì).給定NFSR(f),求取G(f)的所有子簇是極有意義的,不過也是十分困難的.給定NFSR(f)和NFSR(g),本文討論G(f)和G(g)最大公共子簇的求取問題.不同于LFSR的是,此時最大公共子簇未必唯一.在G(f)和G(g)最大公共子簇G(h)存在且唯一的假定下.如果G(h)?G(f)?G(g),那么基于Gr?bner基理論可以得到一個計算G(h)的方法.否則,如果G(h)?G(f)?G(g),那么在一定的假設(shè)條件下也給出了求取G(h)的方法.
[Abstract]:Using nonlinear feedback shift register (NFSR) sequence to replace linear feedback shift register (LFSR) sequence as driving sequence has gradually become the mainstream trend of sequence cryptographic design. Therefore, NFSR sequences have become a hot topic in the field of sequence cryptography. Although it has been studied for half a century, however, due to the difficulty of nonlinear problems, many basic cryptographic properties of NFSR sequences are still unclear, such as cycle structure, series decomposition and subcluster solution. Around the above problems, this paper has made the following research results: 1. An n-order NFSR sequence with a period of 2n is said to be an n-order de Bruijn sequence, which has ideal pseudorandom properties. In this paper, we give a new necessary condition for generating n order de Bruijn sequence NFSR, and count the NFSR that this condition can cover. The counting result shows that this condition can cover a large number of NFSR.. Furthermore, based on the BDD representation of Boolean functions, an algorithm for verifying the necessary conditions is given and the complexity of the algorithm is analyzed. The cycle structure of the 2.NFSR refers to the number of cycles that the NFSR can generate and the cycle length of each cycle. K.Kjeldsen completely determines the cycle structure of a class of symmetric NFSR based on abstract algebra. In this paper, we first determine the cycle length of two classes of NFSR generated partial cycles. On this basis, we completely characterize the cycle structure of a larger class of symmetric NFSR. This result covers the results of K.Kjeldsen and the method is more elementary and intuitive. In addition, the counting results show that more than half of the symmetric NFSR have the cycle structure described in this paper. This paper discusses whether the NFSR series decomposition is unique. Specifically, a sufficient and necessary condition for a given NFSR to decompose into lower series NFSR to LFSR in series is given, and it is proved that the LFSR with the largest series is unique among all such decompositions. Finally, a counterexample is constructed to show that the general series decomposition is not unique. Denote the NFSR with f as the characteristic function as NFSR (f), and the set of all generating sequences of NFSR (f) as G (f). Given NFSR (f) and NFSR (h), if G (h)? G (f), says G (h) is a subfamily of G (f). If G (f) contains subclusters, then some sequences generated by NFSR (f) can be generated by lower order NFSR (h), which is a degenerate property. It is very meaningful for a given NFSR (f), to obtain all subclusters of G (f), but it is also very difficult. Given NFSR (f) and NFSR (g), this paper discusses the problem of finding the largest common subfamily of G (f) and G (g). Unlike LFSR, the largest common subcluster may not be unique at this time. Under the assumption that the largest common subfamily G (h) of G (f) and G (g) exists and is unique. If G (h)? G (f)? G (g), is based on Gr?bner basis theory, a method for calculating G (h) can be obtained. Otherwise, if G (h)? G (f)? G (g), is given, the method of finding G (h) is also given under certain assumptions.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TN918.1
本文編號：2421322
[Abstract]:Using nonlinear feedback shift register (NFSR) sequence to replace linear feedback shift register (LFSR) sequence as driving sequence has gradually become the mainstream trend of sequence cryptographic design. Therefore, NFSR sequences have become a hot topic in the field of sequence cryptography. Although it has been studied for half a century, however, due to the difficulty of nonlinear problems, many basic cryptographic properties of NFSR sequences are still unclear, such as cycle structure, series decomposition and subcluster solution. Around the above problems, this paper has made the following research results: 1. An n-order NFSR sequence with a period of 2n is said to be an n-order de Bruijn sequence, which has ideal pseudorandom properties. In this paper, we give a new necessary condition for generating n order de Bruijn sequence NFSR, and count the NFSR that this condition can cover. The counting result shows that this condition can cover a large number of NFSR.. Furthermore, based on the BDD representation of Boolean functions, an algorithm for verifying the necessary conditions is given and the complexity of the algorithm is analyzed. The cycle structure of the 2.NFSR refers to the number of cycles that the NFSR can generate and the cycle length of each cycle. K.Kjeldsen completely determines the cycle structure of a class of symmetric NFSR based on abstract algebra. In this paper, we first determine the cycle length of two classes of NFSR generated partial cycles. On this basis, we completely characterize the cycle structure of a larger class of symmetric NFSR. This result covers the results of K.Kjeldsen and the method is more elementary and intuitive. In addition, the counting results show that more than half of the symmetric NFSR have the cycle structure described in this paper. This paper discusses whether the NFSR series decomposition is unique. Specifically, a sufficient and necessary condition for a given NFSR to decompose into lower series NFSR to LFSR in series is given, and it is proved that the LFSR with the largest series is unique among all such decompositions. Finally, a counterexample is constructed to show that the general series decomposition is not unique. Denote the NFSR with f as the characteristic function as NFSR (f), and the set of all generating sequences of NFSR (f) as G (f). Given NFSR (f) and NFSR (h), if G (h)? G (f), says G (h) is a subfamily of G (f). If G (f) contains subclusters, then some sequences generated by NFSR (f) can be generated by lower order NFSR (h), which is a degenerate property. It is very meaningful for a given NFSR (f), to obtain all subclusters of G (f), but it is also very difficult. Given NFSR (f) and NFSR (g), this paper discusses the problem of finding the largest common subfamily of G (f) and G (g). Unlike LFSR, the largest common subcluster may not be unique at this time. Under the assumption that the largest common subfamily G (h) of G (f) and G (g) exists and is unique. If G (h)? G (f)? G (g), is based on Gr?bner basis theory, a method for calculating G (h) can be obtained. Otherwise, if G (h)? G (f)? G (g), is given, the method of finding G (h) is also given under certain assumptions.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TN918.1
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 李斌;宋震;;不規(guī)則采樣序列的平移等價性[J];計算機(jī)工程與設(shè)計;2007年21期
2 朱士信;一種快速生成k元de Bruijn序列的算法[J];電子科學(xué)學(xué)刊;1995年06期
3 肖鴻;張串絨;肖國鎮(zhèn);王新梅;;互控-鐘控移位寄存器序列[J];通信學(xué)報;2008年10期
4 李志鈞;在微型機(jī)上構(gòu)成任意級M序列[J];南京航空航天大學(xué)學(xué)報;1985年03期
5 田甜;戚文峰;;非線性反饋移位寄存器序列子簇的研究進(jìn)展[J];密碼學(xué)報;2014年01期
6 錢建發(fā),朱士信;2元de Bruijn-Good圖的推廣[J];通信技術(shù);2002年10期
7 郭寶安;蔡長年;;p元多項式序列[J];北京郵電學(xué)院學(xué)報;1993年03期
8 朱士信;De Bruijn序列的升元算法[J];電子科學(xué)學(xué)刊;2000年01期
9 王旭峰,李超;進(jìn)位移位寄存器序列的密碼學(xué)性質(zhì)[J];計算機(jī)工程與科學(xué);2005年02期
10 周漢林 ,王淑嬡;非線性移位寄存器的綜合及其有關(guān)問題的討論[J];通信保密;1986年02期
相關(guān)博士學(xué)位論文 前2條
1 王中孝;非線性反饋移位寄存器序列若干問題研究[D];解放軍信息工程大學(xué);2014年
2 田甜;帶進(jìn)位反饋移位寄存器序列的分析[D];解放軍信息工程大學(xué);2010年
相關(guān)碩士學(xué)位論文 前3條
1 亓震;反饋移位寄存器序列的計算機(jī)實現(xiàn)研究[D];大連海事大學(xué);2009年
2 王旭峰;進(jìn)位反饋移位寄存器序列的密碼學(xué)性質(zhì)[D];國防科學(xué)技術(shù)大學(xué);2003年
3 劉月嬋;Z_（pe）上本原序列最高權(quán)位序列的元素分布及Z_4上循環(huán)移位寄存器[D];中國人民解放軍信息工程大學(xué);2005年
，本文編號：2421322
本文鏈接：http://sikaile.net/kejilunwen/wltx/2421322.html
最近更新
教材專著
