《序列密码中k错线性复杂度算法与位置错误谱的研究》由会员分享，可在线阅读，更多相关《序列密码中k错线性复杂度算法与位置错误谱的研究（38页珍藏版）》请在金锄头文库上搜索。
1、南京航空航天大学 硕士学位论文 序列密码中k错线性复杂度算法与位置错误谱的研究 姓名：郝年朋 申请学位级别：硕士 专业：应用数学 指导教师：岳勤 20090201 南京航空航天大学硕士学位论文 i 摘 要 序列密码是密码学中最主要和最重要的组成部分之一，也是保密通信中的一个重要的密码 体制，而线性复杂度和k-错线性复杂度是衡量伪随机序列的密码强度的重要指标。如果改变一 个周期序列中的某几个位置值后，该序列的线性复杂度急剧下降，则我们认为这种周期序列是 极不稳定的，用来作为密钥序列是很不安全的。因此，可用k-错线性复杂度来衡量周期序列的 稳定性。继 Stamp-Martin 算法后，推广周期序列
2、的k-错线性复杂度算法是有意义的，设计出新 的k-错线性复杂度算法也具有一定的应用价值。 另外，对于一些完全不相同的周期序列，却有相同的k-错线性复杂度，是因为在描述周期 序列稳定性的k-错线性复杂度的概念中，忽略了k个位置的不同对改变后的周期序列的线性复 杂度也是会产生影响的，给出其k位置错误谱将能很好地刻画序列的线性复杂度的变化情况。 在本文中主要给出两个结果。 首先， 设 S 为有限域( )GF q上周期为 n Nup=的序列， 其中q， p是不同的素数，q是模 2 p的一个本原根，并且|1u q ，, u p互素 ，u是正整数，我们运用 广义离散傅立叶变换的方法，提出了预估周期序列的k
3、错线性复杂度的算法。其次，设 S 为一 条二元2 n -周期序列，其一个周期的Hamming重量为偶数，我们描述当其一个周期上2个位置 发生错误时，其线性复杂度的变化情况，即该序列线性复杂度的2位置错误谱的分布情况。 关键词关键词：序列密码，周期序列，线性复杂度，k-错线性复杂度， k位置错误谱 序列密码中 k 错线性复杂度算法与位置错误谱的研究 ii Abstract Stream cipher is a part of the most important and primary composing in cryptology and it is also an important cry
4、ptography system in secrecy communications. Linear complexity and k-error linear complexity are the most important indexes which measure the intensity of the cipher in pseudorandom sequences. If some bits are changed in the periodic sequences and the linear complexity of those sequences decreases ra
5、pidly, we think that these sequences are not steady. They are also very insecure at all for private key sequence. Thus, we can use the concept of “k-error linear complexity” to describe the stability of periodic sequence. After Stamp-Martin algorithm, it is significant to expand k-error linear compl
6、exity algorithm for different periodic sequences and designing the new algorithm is valuable at the same time. In addition, some sequences have the same k-error linear complexity while they are different from each other. Here, for k-error linear complexity, it is neglected that the linear complexity
7、 of a periodic sequence will be influenced when the values in some different positions are changed. The k-position error spectrum will depict the variety of periodic sequences linear complexity exactly. There are two main results in the paper. Firstly, let S be a sequence with period n Nup= over fin
8、ite field( )GF q, whereq,p are distinct primes and q is a primitive root modulo 2 p,|1u q , gcd()1, u p=, u is a positive integer. We use the method of generalized Discrete Fourier Transform to propose an algorithm to estimate the k-error linear complexity of a periodic sequence. Sencodly, let S be
9、a binary sequence with period2 n and the Hamming weight of its period is even. We describe the influence of linear complexity while changing its two positions, i.e. we get distribution of its 2-position error spectrum. Keywords: stream ciphers, periodic sequence, linear complexity, k-error linear co
10、mplexity, k-position error spectrum 序列密码中 k 错线性复杂度算法与位置错误谱的研究 iv 图表清单 图1.1 S的1位置错误谱.5 图1.2 序列的2位置错误谱.6 图 1.3 序列的2位置错误谱（ 2( )vjink）.7 图1.4 序列的2位置错误谱（ 2( )vjink=）7 图2.1 线性移位寄存器.8 图3.1 周期序列k-错线性复杂度曲线12 图4.1 二元序列(10010000)s =线性复杂度的2位置错误谱23 图4.2 序列的2位置错误谱.25 图4.3 序列的2位置错误谱（ 2( )vjink）.26 图4.4 序列的2位置错误谱（
11、2( )vjink=）26 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 （保密的学位论文在解密后适用本承诺书） 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 1.1 引言 20世纪从始至终，密码都对于世界上的主要事件起着举足轻重的作
12、用。1929年，美国国务 卿Henry L. Stimson为了印证 “绅士不偷看别人的书信” ， 终止了美国政府官方的密码分析行为， 这在后来的日本偷袭珍珠港事件中被证明是一个代价昂贵的错误。在1941年12月7日珍珠港 事件后不久，美国重新启动了早期的密码分析计划。第二次世界大战中盟军的密码分析工作战 功卓著，这个时期也被称为密码分析的“黄金时期” 。在太平洋战场，美国密码分析者破译了日 本海军的JN-25密码得到的信息成为决定中途岛海战胜负的关键； 在欧洲，Enigma密码 （ULTRA 编码）的破译也在二战中给盟军提供了极大的帮助。二战后的一段时期，密码从“黑色艺术” 进入了科学研究领
13、域 28,29。1949 年，Claude Shannon发表了论文保密系统的信息基础 （Information Theory of Secrecy Systems） ， 这为单钥密码系统建立了理论基础， 而微电子学的发 展，为密码学思想提供了实际手段。1976年，Diffie和Hellman发表了论文 密码学的新方向 ， 这揭开了密码学历史上新的一页，开创了一种崭新的密码体制-公钥密码体制，为解决通信网 络中的信息安全提供了新的理论和技术基础；另外，美国国家标准局经过公开征集、遴选并于 1977年正式公布实施了美国数据加密标准（DES） 。这两个事件标志着现代密码学的诞生。随 着网络技术和通
14、信技术的发展，现在已步入信息化时代，每天都有大量的信息需要通过通信设 施和计算机网络等途径进行传播或交换，每个人都将与信息的使用、存储、处理和传递密切相 关，其中如何防止敏感信息的泄漏或保证重要的信息不被篡改等问题都需要用密码学的知识来 解决，信息安全与保密成为人们关心的事情，这使得密码学得到空前的发展。现在，密码学的 应用不在局限于军事或外交，它的应用己广泛地渗透在商业、网络以及个人日常生活之中。 现代密码学总体上可分为密码编码和密码分析，通常都是先通过密码编码建立一套密码系 统，再通过密码分析来对这个密码系统进行分析和攻击，只有经过证明和检验的密码系统才能 被认为是安全可靠的，从而应用于实
15、际中，而且使用的密码系统一直受到密码分析者的检验， 直到系统被破译或者出现更好更安全的密码系统取代当前的系统。密码编码分为私钥密码体制 和公钥密码体制。根据对明文加密方式的不同，私钥密码体制又分为序列密码和分组密码。 序列密码也称作为流密码，它的加密方式是先把报文、语音、图像和数据等原始明文转化 为明文数据序列，然后将明文序列与密钥序列进行逐位加密生成密文序列进行发送，接收者在 收到密文后，再用相同的密钥序列进行逐位解密恢复出明文序列40。因此，从序列密码的加密 方式可以看出，序列密码的安全可靠性主要依赖于密钥序列的选定，判断什么样的伪随机序列 是安全可靠的密钥，以及如何选取合适的伪随机序列从而得到安全可靠的密钥序列就成为了密 序列密码中 k 错线性复杂度算法与位置错误谱的研究 2 钥序列密码中研究的主要问题。通常认为一个安全的密钥序列至少要满足三个基本条件：周期 充分长，良好的随机统计特性，不可预测性充分大。 1.2 序列密码的研究背景、意义和现状 序列密码是保密通信中的一个重要的密码
