公钥密码体制剖析.docx

数学文化课程报告???论文题目：公钥密码体制的现状与发展????公钥密码体制的现状与发展摘要：文中对公钥密码体制的现状与发展进行了介绍，其中着重讨论了几个比较重要的公钥密码体制Ｍ－Ｈ背包算法、RSA、ECC、量子密码、NTRU密码体制和基于辫群上的密码体制。 关键词：公钥密码体制;离散对数问题；格基归约；量子密码1949年，Claude Shannon在《Bell System Technical Journal》 上发表了题为“Communication Theory of Secrecy Systems”的论文，它是现代密码学的理论基础，这篇论文将密码学研究纳入了科学轨道，但由于受到一些因素的影响，该篇论文当时并没有引起人们的广泛重视。直到20世纪70年代，随着人类社会步入信息时代才引起人们的普遍重视，那个时期出现了现代密码的两个标志性成果。一个是美国国家标准局公开征集，并于1977年正式公布实施的美国数据加密标准；另一个是由Whitfield Diffie和Martin Hellman，在这篇文章中首次提出了公钥密码体制，冲破了长期以来一直沿用的私钥体制。自从公钥密码体制被提出以来，相继出现了许多公钥密码方案，如RSA、Elgamal密码体制、背包算法、ECC、XTR和NTRU等。 公钥密码体制的发现是密码学发展史上的一次革命。从古老的手工密码，到机电式密码，直至运用计算机的现代对称密码，这些编码系统虽然越来越复杂，但都建立在基本的替代和置换工具的基础上，而公钥密码体制的编码系统是基于数学中的单向陷门函数。更重要的是，公钥密码体制采用了两个不同的密钥，这对在公开的网络上进行必威体育官网网址通信、密钥分配、数字签名和认证有着深远的影响。 文章共分为5部分：第１部分首先介绍了Merkle－Ｈellmen背 包算法，第2,3,4,5,5部分分别讨论了RSA、ECC、量子密码、NTUR，同时对公钥密码体制进行了展望。1、Merkle－Hellmen背包算法 1978年，Ralph Merkle和Martin Hellmen提出的背包算法是公钥密码体制用于加密的第一个算法，它起初只能用于加密，但后来经过Adi Shamtr的改进使之也能用于数字签名。其安全性基于背包难题，它是个NP完全问题，这意味着没有多项式时间算法来解决这个问题。虽然后来这个算法被证明是不安全的，但由于它证明了如何将NP完全问题应用于公钥密码体制，其设计思想及其攻破方法给人们认识公钥密码体制以很多启示，因而在这里我们提到此算法。 背包问题（或子集和问题）描述起来非常简单。给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中使之等于一个给定的重量？给一个公式化的描述：给定一系列值M1，M2，…，Mn和一个和S，计算ｂ使之满足ｂ的值可为０或１，０代表这个物品不在背包中，１表示在，Ｍ和Ｓ均是正整数，ｉ＝１，２，…，ｎ。 一个正整数序列，如果它的每一项都大于它前面所有项之和，则称序列为超递增序列。如，｛1，3，6，13，27，52｝是一个超递增序列，而｛1，3，4，9，15，25｝不是超递增序列。一个背包问题称为是易解的，如果其重量序列是一个超递增序列。超递增背包问题可在时间O(n)内很容易地解决，如果有解，解一定是唯一的。 实际上存在两类不同的背包问题，一类在线性时间内可解，即易解的背包，而另一类只能在指数时间内可解。背包体制的思想是选取一个易解的背包问题，然后将它伪装成非常难解的一般的背包问题，则原来的背包集可以当作私钥，变换后的背包集作为公开密钥。Merkle－Hellmen背包算法的思想就是将消息编码为背包问题的解，明文分组长度等于堆中物品的个数，且明文位与ｂ的值相对应，密文是计算得到的值。Merkle－Hellmen背包算法的公开密钥是有相同解的普通的背包问题的重量序列，私人密钥是一个超递增背包问题的重量序列。Merkle和Hellmen应用了一个模变换将超递增背包变换成一个在没有辅助信息下难于求解的陷门背包。关于Merkle－Hellmen背包算法大家可参阅文献［１］。 2、RSARSA是当前最著名、应用最广泛的公钥系统RSA是在1978年由美国麻省理工学院的Rivest、Shamir和Adleman提出的，它是一个基于数论的非对称密码体制，是一种分组密码体制。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，它容易理解和操作，非常的流行，其名称来自于三个发明者的姓名首字母。 RSA的安全性基于大整数素因子分解的困难性，而大整数因子分解问题是数学的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA算法是第一个能同