基于树形奇偶机的神经网络同步方案.doc

基于树形奇偶机的神经网络同步方案重庆大学硕士学位论文(学术学位) 学生姓名：刘忆璐指导教师：廖晓峰教授专业：计算机系统结构学科门类：工学重庆大学计算机学院二 O一四年四月 Schemes for Neural Synchronization Based on Tree Parity Machine A Thesis Submitted to Chongqing Universityin Partial Fulfillment of the Requirement for theMasters Degree of Computer ArchitectureByYilu LiuSupervised by Prof. Xiaofeng Liao Specialty: Computer Architecture College of Computer Science of Chongqing University, Chongqing, China April, 2014 重庆大学硕士学位论文中文摘要摘要众所周知，密码技术和安全协议是保证通信安全的关键所在。但是随着计算机和通信技术的迅猛发展，各种密码破解方法和协议攻击算法不断出现，传统的密码技术和安全协议已不能满足日益增长的安全通信需求。因此，研究新型的密码协议已成为当今互联网领域的热点。在此基础上，W. Kinzel等国外学者提出了神经密码模型，该模型是基于两个具有相同结构的神经网络相互学习，最终达到权值相同即完全同步。本论文采用的树形奇偶机模型（Tree Parity Machine，简称 TPM），它是一个拥有特殊结构的且更为复杂的神经网络。我们发现其相互学习效率要比单向学习效率更高。在相互学习的情况下，同步时间是以突触深度（即参数 L）的平方级来长；而在单向学习的情况下，同步时间以 L的指数级增长。因此，神经网络可用于构建密码协议中的密钥交换协议。本论文首先讨论了神经网络密码学的研究背景和发展现状，对该领域的相关概念及理论基础、主流的神经网络同步模型和现有的攻击算法进行了综述，在分析现状的基础上，重点针对神经网络同步过程中通信次数过多的问题，设计了一个新颖的方案。本论文的工作主要涉及以下几个方面：详细分析了现有的神经网络同步模型（TPM）。首先作者编程实现了树形奇偶机模型，并通过大量仿真实验分析其动力学特性。实验结果发现，神经网络模型的同步在同步效率上存在着重要的瓶颈问题，也即是，其同步效率与某些参数有关；针对以上问题，作者首先提出了基于 Hash函数的同步判定算法，以此提高了同步判定效率；对神经元初始权值的选取范围进行修正，进而提出了一个新颖的改进方案，大大加快了同步速度，同时与几种经典学习规则相比，在极限情况下同步性能增加了 50%左右；利用主流的攻击算法，对新颖的改进方案进行了安全实验与对比性分析，大量仿真实验结果表明：新的改进方案能有效地保证通信安全。关键词：树形奇偶机，神经网络，同步，神经密码I 重庆大学硕士学位论文英文摘要ABSTRACT It is well-known that cryptography techniques and security protocols are the keypoint to ensure the communication security. However, with the rapid development of thecomputer and the communication technology, various methods of password crackingand security protocol attacking algorithm come forth constantly, so that the traditionalcryptography technique and the security protocols have been unable to meet thegrowing demand for secure communications. Therefore, the research on new type ofcryptography protocols has become a hotspot in the field of the Internet today.On this basis, foreign scholars such as W. Kinzel proposed the model of neuralcryptography, which is based on two neural networks having the same structure, canachieve fully synchronize by learning from each other. Tree Parity Machines (TPM forshort) used in the paper, are more complex neural networks with a special structure.Synchronization by mutual learning is much faster than learning by adapting toexamples. In the case of bidirectional interaction, the increase of the synchronizationtime is proportional to the square of the synaptic depth (parameter L, namely L-layerneural network); however, it exponentially grows, only when information is transmittedin one direction only. Based on the above advantages, neural synchronization can beused to construct a cryptographic key-exchange protocol.This paper firstly discusses research background and research status of neuralcryptography, and then gives an overview about related concepts and theoretical basis,mainstream model of the neural synchronization, and existing attack algorithms. On thisbasis, a new scheme is designed to solve the low speed of synchronization effectively.The main work of this paper is as follows: Synchronization of the existing neural network model (namely TPM) isanalyzed in detail. Firstly in this paper, TPM is implemented by programming,and through a lot of simulation experiments the dynamics of neuralsynchronization is discussed. Experimental results demonstrate that there aresome essential problems on the efficiency of TPM, which is related to certainparameters. Furthermore, a scheme of synchronization decision algorithm based on Hashfunctions is proposed to improve the efficiency of synchronizationdetermination.II 重庆大学硕士学位论文英文摘要 By appropriately reducing the range of initial weights of neural units, a novelscheme is also designed. After the careful analysis, synchronization efficiencyis greatly improved by applying the novel improved scheme. At the same time,compared with several kinds of classical learning rules, in the extreme casesynchronization performance is increased by about 50%. Mainstream attack algorithms are implemented by programming. In addition,the security of new schemes is analyzed. Lots of simulation experimentsdemonstrate that the novel scheme can effectively ensure the communicationsecurity.Key words：Tree Parity Machine (TPM), neural network, synchronization, neuralcryptographyIII 重庆大学硕士学位论文目录目录中文摘要.I英文摘要. II1绪论. 11.1密码协议的研究现状与发展 . 11.1.1对称密码体制 . 21.1.2非对称密码体制 . 31.2密码协议研究新方向 . 41.3神经密码研究与发展 . 41.3.1人工神经网络研究现状与发展 . 41.3.2神经密码渊源及研究现状 . 61.4研究内容及论文结构 . 71.4.1研究内容 . 71.4.2论文组织及安排 . 72相关理论及研究. 92.1密钥交换协议 . 92.2基本的神经网络模型 . 112.2.1神经元的基本模型 . 112.2.2几种典型的激活函数 . 132.2.3感知器模型 . 142.3本章小结. 153神经网络同步及模型 . 163.1神经密码同步 . 163.2树形奇偶机模型 . 183.2.1树形奇偶机的结构 . 183.2.2学习规则 . 203.2.3同步程度参数 . 213.3神经密码攻击 . 223.3.1简单攻击 . 223.3.2几何攻击 . 233.3.3多数人攻击 . 233.3.4遗传攻击 . 24IV 重庆大学硕士学位论文目录3.4本章小结. 254新方案及仿真实验 . 264.1研究概述. 264.1.1研究目标 . 264.1.2实验环境 . 264.1.3研究内容 . 274.1.4实现途径 . 274.2本论文工作. 284.3神经同步过程的动力学分析 . 284.3.1学习规则的影响 . 294.3.2转移概率 . 364.4新方案设计. 414.4.1同步判定算法的改进及实验 . 414.4.2同步性能的改进及实验 . 474.5新方案安全性分析 . 514.6本章小结. 535总结及展望 . 545.1全文总结. 545.2展望. 55致谢. 56参考文献. 57录. 61附A.作者在攻读学位期间发表的论文目录： . 61V 重庆大学硕士学位论文1绪论1 绪论1.1密码协议的研究现状与发展随着计算机和通信技术的发展，网络安全越来越受到人们的重视，它是互联网研究的关键问题之一。而密码学特别是密码协议，则是保证通信安全的关键所在。所谓协议，就是两个或多个参与者为完成某项特定的任务而采取的一系列的步骤。而密码协议，有时也作安全协议，是以密码学为基础的信息交换协议，其目的是在网络环境中提供各种安全服务。密码学是网络安全的基础，但网络安全不能单纯依靠安全的密码算法。密码协议是网络安全的一个重要组成部分，我们需要通过安全协议进行实体之间的认证、在实体之间安全地分配密钥或其它各种秘密、确认发送和接收的消息的非否认性等。当前系统通信中的密码协议按功能可以分成三大类：身份认证协议、数字签名协议、密钥交换协议。主要基于密钥共享和公钥密码两大技术。它们的安全性通常取决于算法本身的安全强度。例如DH密钥协商协议的安全性是基于离散对数问题。然而，随着分布式计算机和新型计算技术的迅猛发展，传统的密码技术和密码协议迎来了新一轮的挑战，许多广泛应用的密码协议都被发现存在安全缺陷。造成协议存在安全缺陷的原因主要有两个：一是协议设计者失误或者采用了不恰当的密码技术；二是协议设计者对整体系统的安全需求考虑不足。因此，新型密码协议的研究迫在眉睫。近年来，非传统密码学的发展蒸蒸日上，在不同领域都已取得了不少成果，例如混沌密码的研究已步入应用研究。本论文涉及到的神经密码学，其设想自提出后就吸引了许多专家学者们的目光，越来越多的研究机构和组织也纷纷投入其中。实际上，密码学有着悠久的历史，经历了手工阶段、机械阶段、电子与计算机阶段这三个阶段。密码学按照时间又分为古典密码学和现代密码学。在古典密码学中有代表性的算法有凯撒密码、单表替换密码、playfair密码、希尔密码、移位密码、维吉利亚密码等。但是这些经典密码算法往往只考虑了保密性（即可以直接理解的消息按照一定的规则转化为无法理解的消息），一旦攻击者得知使用的算法和截获传递的密文则可以轻松地得到明文消息。并且随着近代科技的进步，计算机进入我们的视野，密码分析技术在计算机的帮助下飞速发展，古典密码学已无法保证信息的保密性。同时 Internet的出现使得我们对安全的要求也愈来愈高，因此密码学也开始不断地发展，现代密码学应运而生。Mebezes等人 2提出了现代密码学中信息安全的四个基本的目标：保密性1 重庆大学硕士学位论文1绪论（Confidentiality）、数据完整性（Data Integrity）、数据源认证（Data OriginAuthentication）、不可抵赖性（Non-repudiation）。现代密码学的研究其实是多个学科交叉的研究，涉及到数学、物理、量子力学、电子学和语言学等领域。一般而言，根据加密密钥能否公开和密钥的数量而言，密码体制可分为两大类：对称密码体制和非对称密码体制。1.1.1对称密码体制对称密码体制是一种传统密码体制，也称为私钥密码体制。对称密码体制的特点是用于加密和解密的密钥是相同的或者是相互存在关系容易推出的。因为加解密密钥相同，需要通信的双方必须选择和保存他们共同的密钥，各方必须信任对方不会将密钥泄密出去，这样就可以实现数据的机密性和完整性。传统的对称密码体制加密有两种方法：替代（Substitution）：明文的字母由其他字母或数字或符号所代替；置换（Permutation）：通过执行对明文字母的某种置换，取得一种类型完全不同的映射。从加密模式上，对称密码体制又分为两种，即序列密码（流密码）和分组密码。在序列密码中，将明文消息按字符逐位加密；而在分组密码中，将明文消息分组（每组含有多个字符），再逐组进行加密。最初出现的密码实质上是序列密码。曾经序列密码被广泛应用于军事领域中，而现代分组密码的研究始于 20世纪 70年代，至今已有 40余年的历史。在此期间，人们对于这一领域的研究成果丰硕。比较典型的算法有 DES算法及其变形 Triple DES（三重 DES）、GDES（广义 DES）、欧洲的 IDEA、日本的 FEAL-N、RC5等。DES（数据加密标准 Data Encryption standard）是一种典型的按分组方式工作的密码。它的基本思想是将明文分组，每一组为 64bits（8bytes），经过初试置换 IP，然后进行 16轮迭代的乘积变换等加密后，最后形成密文。对称密码算法的优点是计算开销小、算法简单、加密速度快，是目前用于信息加密的主要算法。尽管对称密码术有一些很好的特性，但它也存在着明显的缺陷，包括：密钥管理和分配规模复杂。在多个通信方需要通信时，密钥的管理和分配)呈平方级快速增长，密钥空间急剧增大。按照公式Cn= n(n-1) / 2 = O(n2 2进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行的，但在某些情况下会非常困难，甚至无法实现。例如，某贸易方有几个贸易关系，他就要维护几个专用密钥。对称密码算法也没法鉴别贸易发起方或贸易最终方，因为贸易的双方的密钥相同。另外，由于对称加密系统仅能用于对数据进行加解密处理，提供数据的保密性，不能用于数字签名。因而人们迫切需要2 重庆大学硕士学位论文1绪论寻找新的密码体制。公钥密码体制随之而诞生。1.1.2非对称密码体制1976年，Diffie和 Hellman发表了著名的密码学新方向（New Direction inCryptography）3。首次公开提出了“公开密钥密码编码学”的概念，开创了公钥密码学新方向。非对称密码体制，又称为公钥密码体制。从抽象的观点上认为，公钥密码就是一种陷门单向函数。单向陷门函数是满足下列条件的函数 f：给定 x，计算 y = f (x)是容易的；给定 y，计算 x = f - (x)是几乎不可能的，因为在计算上的复杂性，是一个1难以求解的数学问题；存在J，已知J时，对给定的任意 y，若相应的 x存在，则计算 x = f - ( y)1是容易的。仅仅满足、两条的称为单向函数；第条称为陷门性，J称为陷门信息；满足以上三条即为单向陷门函数，公钥密码就是基于此原理设计出来的。当函数 f作为加密函数时，f是公开的，相当于公开加密密钥，即公钥（KU）。f函数的设计者将J保密，用作解密密钥，即私钥（KR）。由于加密函数是公开的，任何人都可以将信息 x加密成 y = ( )f x，然后可以通过公共信道送给设计者；由于设计者拥有 KR，他自然可以解出 x = f - ( y)。而由单向陷门函数的第条性质1表明攻击者由截获的密文 y = f (x)推测出 x是不可行的。公钥密码体制的算法中最著名的代表是 RSA算法，此外还有背包密码、McEliece密码、Rabin、椭圆曲线、ElGamal算法等。公钥密码体制的密钥管理比较简单，每个人只需要维护自己的公钥与私钥对。当需要进行保密的通信时，只需要知晓自己的公钥与私钥和对方公布的公钥即可。( )我们发现密钥管理数目和通信方数目 n呈O n线性关系，而对称密钥呈O(n2)平方级关系。由此可见，只有公钥密码体制才能方便可靠地解决大规模网络应用中密钥分发和管理的问题。并且公钥密码体制可以方便地实现数字签名和验证，这是对称密码体制做不到的。但是公钥密码体制在算法计算上非常复杂，加密数据的速率较低。所以如何快速实现公钥加密成了公钥密码体制研究中的关键问题，并且随着计算机运算速度的大幅度提高，目前的密码体制正在经受威胁，传统的密码学已不能满足安全需求。研究者们已在不同领域上探求可用于密码协议的新方向。3 重庆大学硕士学位论文1绪论1.2密码协议研究新方向自 1949年香农发表奠基性论著保密系统的通信理论（Communication Theoryof Secrecy Systems）标志着现代密码学的诞生以来，密码学在“设计破译设计”的模式下迅速发展起来。近 30年来，涌现出了许多新的密码学思想。1984年，IBM公司的 Brassard首次提出了量子密码学方案。1975年，李天岩和 Yoke发表了著名的论文周期 3意味着混沌（Period Three Implies Chaos），首次提出了混沌的概念，混沌密码学也应运而生。近年来，多变量公钥密码体制逐渐成为现代密码学研究的热点；基于格的公钥密码体制也是一类高效的公钥密码体制。1994年，Adieman利用 DNA计算解决了一个有向哈密尔顿路径问题，DNA密码学诞生。因为公钥密码体制基于数学难题，所以随着计算机处理能力和处理时间的优化其安全性反而会降低。因此快速实现公钥加密是当前研究的一个热门，而人工神经网络在密码学上的应用也成为一种可能。1.3神经密码研究与发展在 20世纪 40年代，神经解剖学、神经生理学以及神经元的电生理过程等的研究取得突破性进展，人们对人脑的结构、组成及最基本工作单元取得了充分的认识，在此基础上，综合数学、物理学以及信息处理等学科的方法对人脑神经网络进行抽象，建立了简化的模型，称为人工神经网络 ANN（Artificial NeuralNetwork）。按照 Hecht Nielsen的观点，神经网络的定义是由多个简单处理单元彼此按照某种方式相互连接而形成的计算机系统。该系统通过对外部输入信息的动态响应来处理信息。综合神经网络的来源、特点和各种解释，它可简单地表述为：人工神经网络是一种旨在模仿人脑结构及其功能的信息处理系统1。作为一门活跃的交叉学科，神经网络的研究与应用正成为人工智能、认知科学、神经生理学和密码学等相关专业的热点。近二十年来，针对神经网络的学术研究非常活跃，且提出上百种的神经网络模型，涉及密码学、信号处理、故障诊断及计算机视觉等众多方面，取得了引人注目的进展。1.3.1人工神经网络研究现状与发展纵观神经网络的发展历史，其发展过程大致可以归纳为如下三个阶段：第一阶段启蒙时期这是神经网络理论研究的奠基阶段。1943年，神经生物学家 MeCulloch和青年数学家 Pitts提出了第一个人工神经元模型，并抽象出神经元的数理模型（神经元的阀值模型，简称 MP模型4）。为了模拟突触的可塑性，神经生物学家 Hebb4 重庆大学硕士学位论文1绪论于 1949年提出了连接权值强化的 Hebb规则5。1954年，生物学家 Eccles提出了真实突触的分流模型6，此模型为神经网络模拟突触的功能提供了原型和生理学的证据。1958年 Rosenblatt在原有 MP模型的基础上增加了学习机制7。Rosenblatt的神经网络模型包含了一些现代神经计算机的基本原理，对神经网络方法和技术有重大的贡献。神经网络的研究迎来了第一次高潮期。1960年 Widrow和 Hoff提出了 ADALINE网络模型8，Grossberg从信息处理的角度，研究了自组织性、自稳定性和自调节规律9；Willshaw等人提出了一种称为全息音的模型10，为利用光学原理实现神经网络奠定了理论基础；Nilsson对多层机即有隐藏层的广义认知机作了精辟的论述等 11研究已获得了广泛的成功。上述成果足以表明神经网络第二阶段低潮时期正当一些科学家对神经网络抱有极大热情时，人工智能的创始人之一 Minsky和 Papert于 1969年出版了轰动一时Perceptrons一书，书中指出简单的线性感知器的功能是非常有限的，它无法解决线性不可分的两类样本的分类问题。这一论断给当时神经网络的研究带来了沉重地打击，由此出现了神经网络发展史上长达 10年的低潮期。但可喜的是，仍有少数具有远见卓识的科学家持之以恒地继续这一领域的研究，成为低潮期神经网络研究的亮点。1976年，美国 Grossberg教授提出了著名的自适应共振理论（AdaptiveResonance Theory，简称 ART）。日本的 Fukushima开发了一些神经网络结构和训练算法，其中最有名的是 1980年发表的“新认知机”（Neocognitron）。在整个低潮时期，上述一些重要研究成果虽然未能得到应有的重视，但他们的工作为日后神经网络理论研究的又一次高涨打下了坚实的基础。第三阶段复兴时期这是神经网络研究的主要发展时期。1982年，美国国家科学院的刊物上发表了著名的 Hopfield模型的理论12。在 Hopfield模型的影响下，大量学者积极投身于这一学术领域中，神经网络的理论研究很快便迎来了第二次高潮。同年， Marr开辟了视觉和神经科学研究的新篇章，他对视觉信息加工和过程进行了全面、系统和深刻的描述13。1983年，Kirkpatrick等人认识到模拟退火算法可用于 NP完全组合优化问题的求解14。1984年，Hinton与年轻学者 Sejnowski等合作提出了大规模并行网络学习机Boltzmann机15，并明确提出隐藏单元的概念。Piggio等人提出了初级视觉的正则化方法 16。中国生物物理学家汪云九提出了视觉神经元的广义 Gabor函数模型以及有关立体视觉、运动方向检测、纹理检测等计算模型。1986年，由 Rumelhart和 McCkekkand主编、共 16位作者参与撰写的ParallelDistributed Processing：Exploration in the Microstructures of Cognition17一书出版，5 重庆大学硕士学位论文1绪论该书建立了并行分布处理理论，解决了长期以来没有权值调整有效算法的难题，并回答了Perceptrons一书中关于神经网络局限性的问题，从实践上证明了人工神经网络有很强的运算能力。1988年，Chua和 Yang提出了细胞神经网络（CNN）模型18，它是一个具有局部互连特性的大规模非线性计算机仿真系统。同年 Kosko建立了双向联想存储模型（BAM）19，它具有非监督学习能力。20世纪 90年代中后期，神经网络研究步入了一个新的发展时期，一方面已有的理论在不断深化和得到进一步发展；另一方面，新的理论和方法也从未停止过其不断开拓的步伐。1990年 Narendra和 Parthasarathy提出了一种推广的动态神经网络系统即其连接权的学习算法 20，增强了非线性系统控制的鲁棒性。戴先中等人提出了