《Zpe上本原序列最高权位序列的元素分布及Z4上循环移位寄存器》由会员分享，可在线阅读，更多相关《Zpe上本原序列最高权位序列的元素分布及Z4上循环移位寄存器（39页珍藏版）》请在金锄头文库上搜索。
1、Y8 2 3 3 9 S分类号学号 UDC学位论文罾级尘五乙P 上本原序列最高权位序列的元素分布及 Z 4 上循环移位寄存器刘月婵指导教师姓名韭塞拯申请学位级别垩童堂亟专业名称窒塑堂论文提交日期2 Q Q 生垒月论文答辩日期2 Q Q 5 生曼月学位授予单位缢丝笙焦! 垦三堡太堂学位授予日期2 Q Q 5 生目答辩委员会主席学位论文评阅人感塞蝰邀塞坚型凰梅解放军信息工程大学二零零五年六月信息丁程大学硕士学位论文摘要伪随机序列有着广泛的应用，因此它的构造一直是一个重要的经典研究课题近年来由于大规模集成电路设计技术的飞速发展，如何构造密码学性质好，适合软件实现的多位( 如8 ，1 6 ，3 2 ，
2、6 4 位) 伪随机序列更是当今密码学的一个热门课题本文就环z 上导出的伪随机序列的性质和构造问题作了比较深刻的研究，得出了一些有用的结论第一部分研究了由z 。上n 次本原多项式生成的本原序列的最高权位序列的元素分布，已有的研究结果表明，本原序列的最高权位序列具有大的周期，高的线性复杂度，保熵特性等，进一步考察它的随机性质，为这种序列的应用提供进一步的理论依据，具有很大的密码学意义本文利用G a l o i s 环上的指数和估计与离散F o u r i e r 变换，得到了元素分布的一个更好的界对给定的P ，e ，元素t 0 = 0 ，l ，P 1 ) 在z 矿上本原序列的最高权位序列中出现的
3、比例渐进趋于1 p + O ( p 一2 ) 从而表明，适当选取参数，最高权位序列有好的元素分布性质具体结果如下：令 为i ( i = 0 ，l ，P 一1 ) 在最高权位序列a 。一1 的一个周期中所占的比例，则： A - 1 pb 霎( 。+ ? + 。) c z ”2 一z k 十- ，+ ( 2 三。) + 他c z ”2 + - ，+ ( ：) z 8 2 注1 1 特别的，当e = 3 时，a e l 的线性复杂度是n 的3 次函数而对应的m 序列的线性复杂度为几，是礼的线性函数此外，a 还具有很好的密码学性质一保熵特性，定理1 2 2 0 】( 保熵定理) 设，( 。) 是z 。
4、t 上扎次本原多项式，G ( ，( z ) ) 。为，( 。) 在z 2 。上生成的线性递归序列的全体设a ，h G ( ，( z ) ) 。，a 。一l ，b 。一1 分别为a ，b 的最高权位序列则a = 坠当且仅当a 。一1 = b 。一l ，即t g ：G ( ，( 。) ) 。，ah _蟹a 一1是单射定理1 3 【1 4 ，埔】设P 是奇素数，整数e 1 ，( z ) 是z p 。上本原多项式，当h G ( ，( z ) ) 。，则墨= 照当且仪当a 。一1 = b 。一1 相关性是反映序列随机性质的一个重要指标当e = 2 时，利用二次型为工具，最高权位序列a e 一，相关函数的
5、所有可能值都可以精确给出m39 | 当e 3 时，文献f 8 ，3 8 ，2 9 讨 论了自相关函数的性质第3 页信息： 程大学硕士学位论文定义1 1 设a = ( a o ，盘1 ，a L 一1 ) 为F 2 上周期为L 的序列定义a 的自相关函数为工一1 q 鼬) = ( 一1 ) 生丛一蚓，x , ：t o 茎h L 一1 m = O当h = 0 时，q ，( ) 一L 是平儿的当h 0 时，称Q ，。( h ) 为a 的非平凡自相关值序列的自相关函数值是密钥流序列随机性参数的一个重要指标，它反映了一条序列与它的移位序列之间的差异序列的自相关值越小，表明序列在一个周期内各比特间的相关性越
6、小在密码应用中，希望密钥流序列的非平凡自相关值越小越好文献 8 ，3 8 】研究了本原序列最高权位序列的非平凡自相关值，【3 8 】给出了如下定理定理1 4h3 8 l 设e23 ，( ) 是z 2 e 上饥次本原多项式，o 一( 1 + 2 矗) 为，( ) 在见，。上的根，其中为R 上的本原元，。设l = ，m o d2 若1 十1 4 1 ，则由( z ) 生成的本原序列的最高权位序列a 。一：的非平凡自相关值l 瓯。一。，。一，( ) I 2 2 e - 2 ( 2 。一1 1 ) 2 “2 + 2 8 1 其中0 3 ( e 一1 ) 时是非平凡的定理1 8表明，对给定的e 值，凡越
7、大，l ( 或0 ) 在a e - l 中所占的比例越趋近i 2 下面给出两个例子：例1 1 设e = 1 ，a 。一1 为F 2 上由n 次本原多项式生成的I l l 序列，由定理1 8 ，塑) = 篙、，、2 ”一1 ，、o l 里土J2 了百。从而定理1 8 给出了F 2 上7 1 次本原多项式生成的m 序列的0 ，1 分布例1 1 表明，当e = l 时，定理1 8 给出的界是紧的例1 2 由定理1 8 ，可得表1 1 它给出了一些情况下a 。一1 的0 ，1 分布从而表明，当e相对礼较小时，a e 一1 的0 ，1 分布较为均衡e礼A l ( a e 一1 )2 04 9 0 3 3
8、 3 A 1 ( a e 一1 ) S5 0 9 6 6 7 3 04 9 9 6 9 8 S ) x l ( a 。一1 ) 曼5 0 0 3 0 2 3 04 7 8 0 7 6 SA 1 ( a e I ) 5 2 1 9 2 4 3 54 9 6 1 4 2 A 1 ( a e 一1 ) 5 0 3 8 7 6 4 04 9 9 3 i 5 A 1 ( a e 一1 ) 5 0 0 6 8 5 表1 1 ：里土的0 ，1 分布由例1 2 ，当e 相对凡较小时，a e 一，有较好的0 ，i 分布但是当e 相对礼较大时，特别 是当礼S3 ( e 一1 ) 时，定理1 8 给出的估计较差甚至
9、是平凡的下面的定理讨论了e 相对札较大的情形定理1 9 【7 3 8 设旦 a e - J ，九( 生生) 同定理1 8 ，则对所有的1 d m i n ( L 5 J ，【；J ) ，d为整数， h ( 塑) 一互I I 嘉+ ；嘉下面也给出一个例子：例1 3 若e28 ，由定理1 9 ，第6 页信息一F 程大学硕士学位论文1n 2 4 时，4 6 8 0 9 9 A 1 ( a 。一1 ) 5 3 1 9 0 1 2 礼3 0 时，4 6 8 6 6 9 茎A 1 ( 钆一1 ) 5 3 1 3 3 1 定理1 8 给出的估计适合礼 3 ( e 一1 ) 的情形，而定理1 9 给出的估计适
10、合礼S3 ( e 一1 )的情形结合定理1 8 和定理1 9 ，作为两个估计的一个特例，可以得到当n 3 0 时，1 在巩一1 中所占的比例在4 6 8 6 6 9 和5 3 1 9 0 1 之间，此结果与e 的大小无关文献【7 ，3 8 还给出了九( 钆一) 的一个只依赖于n 的估计 定理11 0 【7 ，3 8 】设n 8 ，a ，a e 1 ，九( a 。一1 ) 同定理1 8 ，则：l h ( a 。一1 ) 一去I o 5 4 2 2 一i 定理1 1 0 表明，n 越大，a e 一1 中1 ( 或0 ) 的比例越趋近1 2 而文献【4 0 ，4 1 】则表明，e越大，钆一l 中1
11、( 或0 ) 的比例越趋近1 2 从而，定理1 1 0 与文献 4 0 ，4 1 共同刻画了a e - 1的两个参数e 和n 对a e 一1 的0 ，1 分布的影响文献 2 9 利用离散F o u r i e r 变换和文献【1 6 中指数和估计，改进了定理1 8 的结果，得到如下定理：定理1 1 1 a ，a 。一l ，九( a 。一1 ) 同定理1 8 ，则 h ( 塑) 一互1 I 茎墼燮爿等掣可以看出，对于较大的e ，定理1 1 1 与定理1 8 的结果的比值的阶为O ( e 2 1 2 ) 由此可见，适当的选取e ，札和I ( X ) ，z 。e 上由f ( x ) 生成的本原序列的
12、最高权位序列a e 一1 具有良好的统计特性，很大的周期，高的线性复杂度，因而具有很好的的密码学性质，从而为流密码中构造密钥流序列提供了一种好的选择综合以上分析可以看出，环z 2 。上本原序列最高权位序列具有良好的密码学性质自然地，对于一般的素数P ，P 3 ，环z 。上本原序列最高权位序列是否仍具有好的密码学性质呢? 本文综合利用离散F o u r i e r 变换和G a l o i s 环上的指数和估计，讨论了z 。上由n次本原多项式l 厂( z ) 生成的本原序列最高权位序列钆一。的元素分布性质得到了元素分布的一个较好结果1 3 盯一反馈移位寄存器移位寄存器序列被广泛应用于密码学和编码
13、理论中，特别是二元域F 2 上的线性反馈移位寄存器已经是密码学最基本的工具之一，大多数实际的流密码都是围绕L F S R 设计的第7 页信息工程大学硕士学位论文L F S R 的问题是用软件实现的效率非常低为了更新L F S R 的状态，具有字处理能力的处理器不得不花费很多的C P U 时钟来完成比特的抽取、合成和移位操作而且，基于L F S R 的流密码在每一个C P U 时钟只输出一个新的比特位，这使得软件实现效率非常低下因此，为了使流密码算法的软件实现更有效，充分利用计算机数据处理的基本对象是8比特、1 6 比特或3 2 比特长的字的特点，P r e n e e l l 2 4 】在1
14、9 9 4 年快速软件加密会议上提出：如何结合并行技术与现代处理器的特点，设计面向字运算的基于L F S R 的高效安全的流密码另一方面，计算机的基本指令循环移位在密码设计中被广泛应用大多数分组密码和H a s h 算法中都用到了循环移位经典的D E S 在密钥扩展体制中就用到了循环移位美国H a s h 函数国家标准S H A 制定时，在草案与修改标准之间的唯一不同是后者在原来的消息扩展后添加了一个循环移位处理，使得针对原来算法的攻击方法失效密码算法中对循环移位的采用以及具体循环移位量的选择是经过深入研究与精心挑选的，但设计者都未公布其设计细节及选择理由矧重构M D 5 模型如下，可以清晰地
15、看到循环移位的应用目前，设计基于L F S R 面向字运算的高效安全的流密码成为了研究热点适合软件实现的字流密码中大多数都用到了字内的循环移位操作其中著名的有：S E A L 2 6 】、S O B E R _t i “n 1 2 】、S S C 2 1 3 5 】、R C 4 2 5 1 、和S N O W I “最近，在文献 5 1 1 3 0 1 中T s a b a n 和V i s h n e 提出了线性变换移位寄存器( L i n e a rn a n s f o r mS h i f tR e g i s t e r ，T S R ) 的概念，给出了一类基于字运算的移位寄存器模型和求最大周期序列的算法韩文报教授将字内的循环移位操作和线性变换很好的结合到一起，提出了盯一反馈移位寄存器的概念，从而上述几种流密码的源驱动部分都可以看作是口一反馈移位寄存器的一个特例从理论上讲，盯一反馈移位寄存器是通常的线性反馈移位寄存器的推广，研究仃一反馈移位寄存器是对移位寄存器理论的完善；从实际应用上来看，这些理论为设计高效的流密码，特别是设计满足P r e n e e l 要求的面向字运算的流密码提供了更为广阔的空间因此对盯一反馈移位寄存器的研究不仅具有深
