非线性反馈移位寄存器序列若干问题研究
发布时间：2019-02-13 07:32
【摘要】：采用非线性反馈移位寄存器(简称NFSR)序列取代线性反馈移位寄存器(简称LFSR)序列作为驱动序列逐渐成为序列密码设计的主流趋势,因此NFSR序列也成为当前序列密码研究领域的一个热门课题.虽然研究历史已达半个世纪之久,然而由于非线性问题的困难性,目前NFSR序列很多基本的密码性质尚不清楚,如圈结构、串联分解以及子簇求解等问题.围绕上述问题,本文主要取得了以下研究成果:1.称周期达到2n的n级NFSR序列为n级de Bruijn序列,它具有比较理想的伪随机性质.本文给出了能够生成n级de Bruijn序列NFSR的一个新的必要条件,并对该条件能够涵盖的NFSR进行了计数,计数结果表明该条件可以涵盖大量的NFSR.进一步地,基于布尔函数的BDD表示,给出了该必要条件的一个验证算法并分析了该算法的复杂度.2.NFSR的圈结构是指该NFSR可以生成多少个圈及每个圈的圈长是多少.1976年,K.Kjeldsen基于抽象代数的方法完全确定了一类对称NFSR的圈结构.本文首先确定了两类NFSR生成的部分圈的圈长,在此基础上,完全刻画了更大一类对称NFSR的圈结构.这一结果涵盖了K.Kjeldsen的结果而且方法更加初等直观.此外,计数结果表明,超过一半的对称NFSR具有本文所刻画的圈结构.3.讨论了NFSR串联分解是否唯一的问题.具体地,针对给定NFSR可以分解为更低级数NFSR到LFSR串联的情形,给出了其具有此种分解的一个充要条件,并据此证明了所有这样分解中,级数最大的LFSR是唯一的.最后,构造了一类反例表明,一般的串联分解并不唯一.4.记以f为特征函数的NFSR为NFSR(f),并记NFSR(f)全体生成序列的集合为G(f).给定NFSR(f)和NFSR(h),如果G(h)?G(f),则称G(h)是G(f)的一个子簇.若G(f)含有子簇,那么NFSR(f)生成的部分序列可以由更低级数的NFSR(h)来生成,这是一种退化性质.给定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),那么在一定的假设条件下也给出了求取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.
【学位授予单位】：解放军信息工程大学
【学位级别】：博士
【学位授予年份】：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.
【学位授予单位】：解放军信息工程大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN918.1
【相似文献】
相关期刊论文 前10条
1 李斌;宋震;;不规则采样序列的平移等价性[J];计算机工程与设计;2007年21期
2 朱士信;一种快速生成k元de Bruijn序列的算法[J];电子科学学刊;1995年06期
3 肖鸿;张串绒;肖国镇;王新梅;;互控-钟控移位寄存器序列[J];通信学报;2008年10期
4 李志钧;在微型机上构成任意级M序列[J];南京航空航天大学学报;1985年03期
5 田甜;戚文峰;;非线性反馈移位寄存器序列子簇的研究进展[J];密码学报;2014年01期
6 钱建发,朱士信;2元de Bruijn-Good图的推广[J];通信技术;2002年10期
7 郭宝安;蔡长年;;p元多项式序列[J];北京邮电学院学报;1993年03期
8 朱士信;De Bruijn序列的升元算法[J];电子科学学刊;2000年01期
9 王旭峰,李超;进位移位寄存器序列的密码学性质[J];计算机工程与科学;2005年02期
10 周汉林 ,王淑嫒;非线性移位寄存器的综合及其有关问题的讨论[J];通信保密;1986年02期
相关博士学位论文 前2条
1 王中孝;非线性反馈移位寄存器序列若干问题研究[D];解放军信息工程大学;2014年
2 田甜;带进位反馈移位寄存器序列的分析[D];解放军信息工程大学;2010年
相关硕士学位论文 前3条
1 亓震;反馈移位寄存器序列的计算机实现研究[D];大连海事大学;2009年
2 王旭峰;进位反馈移位寄存器序列的密码学性质[D];国防科学技术大学;2003年
3 刘月婵;Z_（pe）上本原序列最高权位序列的元素分布及Z_4上循环移位寄存器[D];中国人民解放军信息工程大学;2005年
，本文编号：2421322
本文链接：https://www.wllwen.com/kejilunwen/wltx/2421322.html
