序列线性复杂度谱的分析.docVIP

信息工程大学硕士学位论文 摘要 序列，的线性复杂度上ｅＯ就是生成序列，的最小线性移位寄存器的长度，它是衡量 序列伪随机性和不可预测性的一个重要参数．一条好的伪随机序列的线性复杂度应该足 够高并且其线性复杂度谱应该不规则地靠近ｈｉ２．线．对于一条有限序列，考虑其线性复杂 度固然重要，但是更重要的是研究其子序列线性复杂度的变化情况，即研究序列的线性复 杂度谱． 为了更加深刻地刻画序列线性复杂度谱的特性，本文给出了给定线性复杂度谱的序 列的条数，并且计算出了长为ｎ、线性复杂度为上、线性复杂度的最大跳跃幅度为Ｄ的序 列的条数．１ｌＬ＃ｌ，，本文还讨论了长为ｎ的序列其线性复杂度的最大跳跃幅度的均值．对长 为Ｈ、线性复杂度为三的随机序列，计算了其跳跃复杂度的均值和方差． 关键词序列密码线性复杂度线性复杂度谱跳跃复杂度 第１页 信息１Ｔ程大学硕士学位论文 Ａｂｓｔｒａｅｔ Ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｓｅｑｕｅｎｃｅ  ｒ ｉｓ  ｄｅｆｉｎｅｄ  ａｓ  ｔｈｅ ｌｅｎｇｔｈ ｏｆ ｔｈｅ ｓｈｏｒｔｅｓｔ ｌｉｎｅａｒ ｆｅｅｄｂａｃｋ ｓｈｉｆｔ－ｒｅｇｉｓｔｅｒ ｔｈａｔ  ｃａｎ ｇｅｎｅｒａｔｅ ｔｈｅ ｓｅｑｕｅｎｃｅ ｇ，ｗｈｉｃｈ ｉｓ  ａ ｖｅｒｙ ｉｍｐｏｒｔａｎｔ ｐａｒａｍｅｔｅｒ ｔｏ ｍｅａｓｕｒｅ ｔｈｅ ｒａｎｄｏｍｎｅｓｓ ａｎｄ ｕｎｐｒｅｄｉｃｔａｂｌｅ ｏｆ ｓｅｑｕｅｎｃｅｓ．Ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｏｆ  ａ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ ｓｈｏｕｌｄ ｂｅ ｈｉｇｈ ｅｎｏｕｇｈ ａｎｄ ｉｔｓ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｐｒｏｆｉｌｅ ｓｈｏｕｌｄ ｆｏｌｌｏｗ ｃｌｏｓｅｌｙ ｂｕｔ ｉｒｒｅｇｕｌａｒｌｙ ｔｈｅ ｎ／２一ｌｉｎｅ．Ｆｏｒ  ａ ｆｉｎｉｔｅ ｓｅｑｕｅｎｃｅ，ｉｔ ｉｓ ｖｅｒｙ ｉｍｐｏｒｔａｎｔ ｔｏ ｓｔｕｄｙ ｉｔｓ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ，ｂｕｔ ｉｔ ｉｓ ｍｏｒｅ ｉｍｐｏｒｔａｎｔ ｔＯ ｓｔｕｄｙ ｔｈｅ ｃｈａｎｇｅｓ ｉｎ ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｉｔｓ ｓｕｂ—ｓｅｑｕｅｎｃｅ，ｔｈａｔ ｉｓ ｔｏ ｓａｙ，ｗｅ ｓｈｏｕｌｄ ａｕｄｙ ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｐｒｏｆｉｌｅ ｏｆｔｈｅ ｓｅｑｕｅｎｃｅ． Ｉｎ ｏｒｄｅｒ ｔｏ ｄｅｐｉｃｔ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｏｆ ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｐｒｏｆｉｌｅｓ ｏｆ ｓｅｑｕｅｎｃｅｓ，ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｇｅｔ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｇｉｖｅｎ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ．Ｇｉｖｅｎ ｔｈｅ ｍａｘｉｍａｌ ｊｕｍｐ ｅｘｔｅｎｔ ｏｆ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ Ｄ，Ｗｅ ａｌｓｏ ｇｅｔ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｇｉｖｅｎ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ Ｌ ｏｆ ｌｅｎｇｔｈ＂．Ｆｕｒｔｈｅｒｍｏｒｅ，ｗｅ ｇｅｔ ｔｈｅ ｅｘｐｅｃｔｅｄ ｍａｘｉｍａｌ ｊｕｍｐ ｅｘｔｅｎｄ ｏｆ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｌｅｎｇｔｈ ｎ． ａｎｄ ｗｅ ａｌｓｏ ｇｅｔ ｔｈｅ ｅｘｐｅｃｔａｔｉｏｎ ａｎｄ ｖａｒｉａｎｃｅ ｏｆ ｔｈｅ ｊｕｍｐ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ ｏｆ ｌｅｎｇｔｈ  ｎ ａｎｄ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ Ｌ． Ｋｅｙ ｗｏｒｄｓ：ｓｔｒｅａｍ ｃｉｐｈｅｒ＇ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ，ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ 第１Ｉ页  ｐｒｏｆｉｌｅｓ，ｊｕｍｐ  ｃｏｍｐｌｅｘｉｔｙ 信息工程大学硕士学位论文 第一章引言 伪随机序列在诸多通信和计算机领域中都有十分重要的应用．例如，密码学、扩频通 信、纠错码等．序列密码是密码学的一个重要分支．由于序列密码实现简单，加密速度快， 使得序列密码被广泛的采用．因此，序列密码体制的理论问题就一直为人们所关注． 在序列密码理论中，密钥序列的伪随机性和不可预测性是密钥序列安全性的一个重 要指标．如何衡量产生密钥序列的伪随机性质和不可预测性是密码设计者和密码分析者 关注的重要问题． 对于密码意义下“好”的伪随机序列，Ｓ．Ｗ．Ｇｏｌｏｍｂ提出三个伪随机性假设吼（１）元素 分布均衡；（２）理想的自相关特性［９］；（３）良好的游程分布．他认为满足这三个条件的序列 是“好”的伪随机序列，此后，随着伪随机序列研究的不断深入，许多新的研究成果不断出 现，对