检索结果-南通市图书馆

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

缩短置换的广义圈的生成算法研究

缩短置换的广义圈的生成算法研究

作者：李欣欣郑州大学

学位级别：硕士

k元n阶de Bruijn序列是一条周期为k的k元循环串,且每个k元n长字符串作为其子串恰出现一次.因其具有良好的密码学特性,在军事、外交、通讯等领域有着广泛的应用.广义圈实际上是de Bruijn序列的一种推广,对于任意对象的集合S,其广义圈就... 详细信息

k元n阶de Bruijn序列是一条周期为k的k元循环串,且每个k元n长字符串作为其子串恰出现一次.因其具有良好的密码学特性,在军事、外交、通讯等领域有着广泛的应用.广义圈实际上是de Bruijn序列的一种推广,对于任意对象的集合S,其广义圈就是一条周期为|S|的循环串,其中集合S中的每个元素作为其子串恰出现一次.广义圈能应用在许多组合对象上,例如:k元n长串的集合、置换的集合、弱序的集合以及有限集合的子集等等.它们具有良好的组合结构和伪随机性,在数学和密码等方面有着广泛的应用.设集合[n]={1,2,...,n},P(n,k)是所有[n]的k-置换的集合.当k=n-1时,P(n,n-1)就是缩短置换的集合.本文主要研究了当S=P(n,n-1)时,其广义圈的快速生成算法.广义圈的生成方法可以由de Bruijn序列的生成方法推广得到,其中一个重要的方法就是并圈法思想.并圈法就是通过交换共轭状态对的后继,将反馈移位寄存器(FSR)生成的不同的圈并成一个圈的方法.本文主要利用并圈法的思想给出了一种快速生成缩短置换广义圈的新方法.易知P(n,n-1)关于移位形成n(n-2)!个不同的圈,在这些圈上采用适当的规则来确定一些共轭状态对,使得以这些圈为结点,以共轭状态对为边的图是一个扩展树.为了更清楚地描述这种方法,我们分成两步来进行说明.第一步给出一个基本后继规则来实现部分圈的并,并且保证以这些圈为点,以基本后继规则确定的共轭状态对为边构成一个子树.第二步在基本后继规则的基础上,以子树为结点给出构造共轭状态对的方法,使得子树连接形成树.这样就可以根据并圈法把所有的圈并成一个圈,从而得到包含所有缩短置换的广义圈.目前已有的生成方法大部分根据图论知识,理论非常复杂.有些生成方法的时间复杂度很高,至少是O(n),空间复杂度为O(n).本文给出的方法的时间复杂度只有O(1),空间复杂度为O(n),具有重要的应用价值.

关键词：置换广义圈扩展树并圈法后继规则

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

具有重量限制的广义圈快速生成算法研究

具有重量限制的广义圈快速生成算法研究

作者：李娜郑州大学

学位级别：硕士

k元de Bruijn序列是以kn为周期并且在一个周期中所有k元n长状态都恰好出现一次的序列,因具有良好的伪随机性而在密码学以及移动通信技术等领域有着广泛的应用。广义圈是de Bruijn序列的一种推广,对于任意对象的集合S,其广义圈是以|S|为... 详细信息

k元de Bruijn序列是以kn为周期并且在一个周期中所有k元n长状态都恰好出现一次的序列,因具有良好的伪随机性而在密码学以及移动通信技术等领域有着广泛的应用。广义圈是de Bruijn序列的一种推广,对于任意对象的集合S,其广义圈是以|S|为周期并且在一个周期内集合S中的所有元素都恰好出现一次的序列。广义圈能应用在许多组合对象上,例如k元n长状态的集合、k-置换的集合以及弱序的集合等,具有重要的密码性质和组合性质。本文主要研究当S为所有重量在w1和w2之间的二元n长状态组成的集合时,其广义圈的快速生成算法。广义圈的许多构造方法可以由de Bruijn序列的构造方法推广得到,其中一个重要的方法就是并圈法。并圈法是通过交换共轭状态的后继,将由同一个反馈移位寄存器生成的不同圈合并为唯一圈的方法,具有运行速度快、效率高的特点。本文主要通过以f(x)=zn+1为特征多项式的线性反馈移位寄存器生成不同的重量在w1和w2之间的圈,并将这些圈分为两类,分别是重量为w1(或w2)的圈和重量大于w1(或小于w2)的圈,在这两类圈上采用不同的规则来确定一些共轭对,使得以所有重量在w1和w2之间的圈为结点并且以这些共轭对为边的图是一个扩展树。这样就可以利用并圈法将所有的圈合并起来得到唯一的圈,即包含所有重量在w1和w2之间的二元n长状态的广义圈。根据上述思想,本文给出了两类算法,这些算法能够在O(n)时间内快速确定每个圈上需要改变后继的状态,并且能够得到大量不同的广义圈。与目前已有的算法相比,本文算法有效地提升了运行速度,同时也增加了生成广义圈的个数,因而具有一定的研究价值。

关键词：广义圈 de Bruijn序列反馈移位寄存器并圈法后继规则

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

De Bruijn序列的快速生成算法研究

De Bruijn序列的快速生成算法研究

作者：朱云龙郑州大学

学位级别：硕士

De Bruijn序列因具有周期大、线性复杂度大、游程分布平衡等性质在密码学等领域有着广泛的应用,研究其快速生成算法具有重要意义。并圈法(CJM)是一种常用的快速生成de Bruijn序列的算法,是指通过改变共轭对的后继,将反馈移位寄存器(FSR... 详细信息

De Bruijn序列因具有周期大、线性复杂度大、游程分布平衡等性质在密码学等领域有着广泛的应用,研究其快速生成算法具有重要意义。并圈法(CJM)是一种常用的快速生成de Bruijn序列的算法,是指通过改变共轭对的后继,将反馈移位寄存器(FSR)生成的不同的周期序列合并,从而生成成一个周期序列,即de Bruijn序列。并圈法能够基于给定FSR生成后继规则,从而构造对应de Bruijn序列。该方法的时间复杂度和空间复杂度均为O(n),在硬件和软件实现上都具有明显优势,因此被认为是构造de Bruijn序列的一类重要方法。本文的研究内容主要分为两个部分。第一部分研究了以f(x)=xn+xn-1+x+1为特征多项式的二元线性反馈移位寄存器(LFSR),利用并圈法生成de Bruijn序列的方法。该类LFSR的圈结构有较好的性质,基于此本文主要给出了两类后继规则,每类后继规则都能够生成n的指数数量的de Bruijn序列。其中第一类后继规则的证明根据Jansen关于de Bruijn序列构造方法的证明演变而来,将LFSR生成的不同的二元周期序列(圈)根据代表向量(代表元)的字典序进行排序,并使得除代表元字典序序最小的圈外,其余所有圈代表元的共轭向量均在更小序的周期序列中。对于第二类后继规则,本文给出了一种更一般化的证明方法,可以推广至更多圈结构具有某些性质的LFSR应用中。在本文中所研究的LFSR是一个新的LFSR,且在de Bruijn序列构造方法的证明上也有所创新。第二部分研究了多元情况下以f(x)=xn+1为特征多项式的多元LFSR,通过构造后继规则来生成de Bruijn序列的方法。因为多元时元素较多,本文利用了一种构造集合的方法来确定圈之间的链接,目前多元de Bruijn序列领域相比成果较少,且本文中的研究涵盖了这些内容,因此该研究也具有重要的应用价值。

关键词：周期序列 de Bruijn序列反馈移位寄存器后继规则并圈法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

非线性反馈移位寄存器序列的研究

非线性反馈移位寄存器序列的研究

作者：李超云湖北大学

学位级别：硕士

反馈移位寄存器在现代通信系统、编码理论和密码学中有着广泛的应用.在密码学中,线性反馈移位寄存器是设计流密码密钥流生成器的重要组件.极大长度线性反馈移位寄存器序列,即m序列,具有长的周期和优良的伪随机性质,但它的线性复杂度却很... 详细信息

反馈移位寄存器在现代通信系统、编码理论和密码学中有着广泛的应用.在密码学中,线性反馈移位寄存器是设计流密码密钥流生成器的重要组件.极大长度线性反馈移位寄存器序列,即m序列,具有长的周期和优良的伪随机性质,但它的线性复杂度却很小.为了设计大线性复杂度的密钥流序列,人们对m序列进行非线性改造,从而提出了流密码的组合、滤波和钟控等模式.随着相关攻击和代数攻击等密码分析技术的发展,基于线性反馈移位寄存器流密码的安全受到严重威胁.2004年欧洲启动的eSTREAM计划极大推动了流密码算法设计与分析的发展,以Trivium和Grain为代表的基于硬件算法的胜出标志着非线性反馈移位寄存器逐渐成为密钥流生成器的一种重要设计原件,非线性序列作为驱动已经成为基于反馈移位寄存器的流密码设计的新趋势.基于非线性反馈移位寄存器流密码越来越受到人们的重视.然而,非线性反馈移位寄存器的基础理论研究相对实际应用而言比较滞后,许多问题仍待解决.非线性反馈移位寄存器理论中的一个基本问题是构造极大长度的非线性反馈移位寄存器序列.极大长度非线性反馈移位寄存器序列,也称为de Bruijn序列,有着很好的密码学性质：长的周期,大线性复杂度和优良的伪随机性质,因而有着很好的应用前景.目前最常用的构造方法之一是Golomb提出的并圈法,通过依次合并给定移位寄存器状态图中的所有圈得到只含一个大圈的极大长度非线性反馈移位寄存器,从而生成de Bruijn序列.人们已经利用极大长度线性反馈移位寄存器,纯轮换移位寄存器以及纯和寄存器等的特殊圈结构通过并圈法构造deBruijn序列.本文将构造几类新的de Bruijn序列.本文将综合使用组合方法和代数方法确定几类线性反馈移位寄存器的圈结构和状态图中共轭圈的分布,从而利用并圈法构造de Bruijn序列.本文还将给出构造的极大长度非线性反馈移位寄存器反馈函数代数表达式和快速生成反馈函数的算法.这些研究对发展基于反馈移位寄存器的流密码设计与分析的方法和技术具有重要的理论意义和应用价值.

关键词：反馈移位寄存器 de Bruijn序列 D-同态 m序列并圈法圈结构邻接图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

二元De Bruijn序列的构造

二元De Bruijn序列的构造

作者：林占祥郑州大学

学位级别：硕士

De Bruijn序列因其良好的伪随机性,在如今的密码设计中应用越来越广泛。本文主要通过并圈法(CJM)来交换共轭对的后继状态,使得两个不同的圈合并成一个圈,直到变成一个2长的圈为止,即可得到一个de Bruijn序列。本文主要通过一些简单的反... 详细信息

De Bruijn序列因其良好的伪随机性,在如今的密码设计中应用越来越广泛。本文主要通过并圈法(CJM)来交换共轭对的后继状态,使得两个不同的圈合并成一个圈,直到变成一个2长的圈为止,即可得到一个de Bruijn序列。本文主要通过一些简单的反馈移位寄存器来快速的生成de Bruijn序列,主要成果包含两个方面。首先,在反字典序下提出三种基于CCR(Complementary Circulating Reg-ister)构造 de Bruijn 序列的算法;定义游程序,通过在每个圈中确定不同的唯一的以1开头后跟最长0-游程的状态来构造不同的序列。另一方面,对于 CSR(Complementary Summing Register)在反字典序下定义 necklace 序,通过在每个圈中确定不同的唯一状态来构造不同的de Bruijn序列;结合necklace序和重量序定义混合序,并进一步构造不同的序列。本文提出的算法生成下一个比特所需的空间复杂度为O(n),时间复杂度为O(n)到O(nlogn)。这些算法可以生成更多的de Bruijn序列,因此也具有较高的研究价值。

关键词：反馈移位寄存器并圈法 De Bruijn序列后继规则全序