椭圆曲线与伪随机序列的构造

论文摘要

伪随机序列在扩频通信、多址通信（CDMA）、测量测距、软件测试、雷达导航、序列密码与公钥密码等领域都有广泛的应用．特别在序列密码中，密钥流序列的随机性与不可预测性完全决定了序列密码系统的安全性．构造适合各种用途的伪随机序列一直是研究的热点．本文研究利用椭圆曲线构造的伪随机序列（伪随机数），主要利用有限域上椭圆曲线有理点群的指数和估计讨论椭圆曲线序列的密码性质——分布、相关性、（非）线性复杂度等，得到如下主要结果： （1）系统讨论椭圆曲线-线性同余序列的一致分布性质，即该类序列是渐近一致分布的，并给出了它的非线性复杂度下界； （2）讨论两类由椭圆曲线构造的二元序列的“良性”分布（well distribution）与高阶（κ阶）相关性（correlation of order κ），这两类序列具有“优”的密码性质，也正面回答了Goubin等提出的公开问题； （3）利用椭圆曲线及其挠曲线构造一类二元序列，其周期为4p（其中椭圆曲线定义在有限域Fp上），0-1分布基本平衡，线性复杂度至少为周期的四分之一； （4）讨论了剩余类环Zpq上的椭圆曲线的有理点的分布估计，并用于分析一类由剩余类环Zpq上椭圆曲线构造的二元序列的伪随机性； （5）讨论椭圆曲线-幂生成器序列的相关性及椭圆曲线-二次生成器序列的一致分布； （6）讨论椭圆曲线-子集和序列的一致分布； （7）讨论椭圆曲线上的线性反馈移位寄存器序列的分布，线性复杂度等性质．

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 伪随机序列的应用背景
• 1.2 伪随机序列的研究背景
• 1.3 论文的内容安排和主要结果
• 第二章 背景知识
• 2.1 伪随机序列基础知识
• 2.1.1 线性反馈移位寄存器序列
• 2.1.2 序列的伪随机性指标
• 2.2 数学基础知识
• 2.2.1 指数和基本理论
• 2.2.2 椭圆曲线基础知识
• 第三章 椭圆曲线-线性同余序列生成器
• 3.1 线性同余序列
• 3.2 椭圆曲线-线性同余序列（Ⅰ）
• 3.2.1 序列的分布
• 3.2.2 序列的多维分布
• 3.2.3 序列的线性与非线性复杂度
• 3.3 椭圆曲线-线性同余序列的分布（Ⅱ）
• 3.3.1 素域上的序列分布
• 3.3.2 扩张域上序列的坐标向量的分布
• 3.4 椭圆曲线-二元序列（Ⅰ）
• 3.4.1 序列的构造
• 3.4.2 序列的分布与相关性
• 3.5 椭圆曲线-二元序列（Ⅱ）
• 3.5.1 椭圆曲线上的乘法特征和
• 3.5.2 序列的构造
• 3.5.3 序列的分布与相关性
• 3.6 基于椭圆曲线的交错序列
• 3.6.1 交错序列的基本概念
• 2ⁿ上超奇异椭圆曲线的交错序列'>3.6.2 F_2ⁿ上超奇异椭圆曲线的交错序列
• 2ⁿ上非超奇异椭圆曲线的交错序列'>3.6.3 F_2ⁿ上非超奇异椭圆曲线的交错序列
• 3.7 基于椭圆曲线及其挠曲线的交错序列
• 3.7.1 椭圆曲线的挠曲线
• 3.7.2 交错序列的构造
• 3.7.3 序列的伪随机性质
• 3.7.4 椭圆曲线的选择
• 3.7.5 安全性
• 3.8 本章小结
• 第四章 椭圆曲线-指数序列生成器
• 4.1 椭圆曲线-幂生成器
• 4.1.1 幂指数生成器
• 4.1.2 椭圆曲线-幂生成器
• 4.2 椭圆曲线-二次生成器
• 4.2.1 二次同余生成器序列
• 4.2.2 椭圆曲线-二次生成器序列
• 4.3 本章小结
• 第五章 基于环上椭圆曲线的序列
• N上的椭圆曲线及其指数和'>5.1 Z_N上的椭圆曲线及其指数和
• 5.2 二元序列的构造
• 5.3 本章小结
• 第六章 椭圆曲线上的线性反馈移位寄存器序列
• 6.1 EC-线性反馈移位寄存器序列
• 6.1.1 EC-线性反馈移位寄存器序列的定义
• 6.1.2 EC-线性反馈移位寄存器序列的周期与分布
• 6.1.3 EC-线性反馈移位寄存器序列的迹表示
• 6.2 基于EC-LFSR的交错二元序列
• 6.3 本章小结
• 第七章 椭圆曲线-子集和与子集积序列生成器
• 7.1 子集和序列
• 7.2 椭圆曲线-子集和序列
• 7.3 Naor-Reingold序列
• 7.4 椭圆曲线-Naor-Reingold序列
• 7.5 本章小结
• 第八章 其他与椭圆曲线有关的序列
• 8.1 具有几乎优的线性复杂度轮廓的序列
• 8.1.1 具有几乎优的线性复杂度轮廓的序列的构造
• 8.1.2 具有几乎优的线性复杂度轮廓的多维序列的构造
• 8.2 椭圆可除序列（Elliptic Divisibility Sequences）
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果
• 参加、主持的科研项目