基于非线性反馈移位寄存器的de Bruijn序列的设计

摘要

移位寄存器序列中的M序列又称de Bruijn序列，由于有着良好的随机性质及密钥量大与难以破解的特点，在保密通信中具有非常重要的地位。近年来，诸如相关攻击与代数攻击的密码分析技术的发展，使得非线性反馈移位寄存器有取代线性反馈移位寄存器、成为相关学界的研究主流之势。 本文着眼于移位寄存器的几何结构，以分析它们的状态图为出发点，尝试构造de Bruijn序列，取得了以下成果： （1）在MATLAB平台实现了依据反馈函数对任意反馈移位寄存器的状态图进行整体上的刻画，并统计相关特征，包括圈个数、连通分支个数、三叉点和叶子点等。实验数据显示，在小于17阶的情况下，该程序可以相当快速得到结果。 （2）在Golomb给出的PSR和CSR的圈个数公式的基础上，给出并证明了PSR和CSR的圈长分布公式，完全确定了这两类经典移位寄存器的几何结构。 （3）引入Etzion和Lempel提出的圈的扩展表示和扩展重量的概念，对CSR的圈结构展开讨论，由它的特殊性质提出了一个利用CSR生成de Bruijn序列的算法。利用该算法，n阶CSR可产生([)n/2」∏k=1(n?12k?1)条de Bruijn序列，运行内存约为n2/2，产生下一比特最多需要n个循环移位操作和n个n比特按位比较操作。利用图论方法，给出了关于圈扩展重量的局限性的证明，圈扩展重量仅适用于PSR和CSR. （4）利用编写的MATLAB程序，给出了两个奇异反馈移位寄存器的具体实例，通过对二者的状态图进行严格的数学证明，提供了分析这一类具有满二叉树组合形式的状态图的奇异反馈移位寄存器的思路。

目录

第一个书签之前

摘要

ABSTRACT

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 研究背景与意义

1.2 研究历史与现状

1.2.1 de Bruijn序列的生成

1.2.2 反馈移位寄存器的几何结构

1.3 本文内容安排及主要结果

第二章 基础知识

2.1 关于布尔函数

2.2 关于反馈移位寄存器

2.3 关于并圈法

第三章 PSR和CSR的圈结构

3.1 利用MATLAB刻画状态图

3.1.1 可逆对称二元配对函数的构造

3.1.2 程序简介与效率测试

3.2 PSR的圈结构

3.3 CSR的圈结构

3.4 本章小结

第四章 基于CSR的de Bruijn序列生成算法

4.1 CSR的若干几何性质

4.2 从圈扩展重量出发的并圈法

4.3 圈扩展重量的适用范围

4.4 本章小结

第五章 一类奇异反馈移位寄存器的几何结构

5.1 Gf1(n)的几何结构

5.2 Gf2(n)的几何结构

5.3 本章小结

第六章 结束语

附录 A

A.1 主函数SubgCal

A.2 子函数SuccCal

A.3 子函数CalFreq

附录 B

B.1 主函数deBruCSR

B.2 子函数CheckRunCycle

B.3 子函数PrefState

B.4 子函数CheckRun

B.5 子函数CheckNCRun

B.6 子函数CheckU

参考文献

致谢

作者简介