公钥密码体制的现状与发展.docx

公钥密码体制的现状与发展 网络通讯安全……本栏R责任编辑:冯墨 公钥密码体制的现状与发展 卓泽朋?魏仕民?曹浩’ (1,淮北煤炭师范学院数学系;安徽淮北2350002淮北煤炭师范学院计算机科学与 技术系;安徽淮北235000) 摘要:文屮对》厶\钥密码体制的现状与发展进行了介绍，其屮着重讨论了几个比较 重要的公钥密码体制M—H背包算法,P.SA,ECC, 量子密码,NTRU密码体制和基于辫群上的密码体制. 关键词:公钥密码体制;离散对数问题;格基归约;量子密码;辫群 中图分类号:TN918文献标识码:A文章编号:1009—3044(2006)35 — uuaz—uJ SurveyandTrendofPublicKeyCryptography ZHUoZe—peng, WEISl 1 i—nlin2.C AOHaol (hDepartmentofMathematics,HuaibeiCoalIndustryTcachetsCollege,Huaibei2350005C hina;2.DepartmentofComputerScienceamp; .Technique,HuaibeiCoalIndustryTcachetsCollege,Huaibei235000.China) Absttact:Asu IV evoftheresearchandimplementationofPKCispresentedintllispape 匚 withtlleemphasisons ometypicalsystemssuchas M — Hknapsackalgorithm,RS A,ECC,quantumcipher,NTRUandpublickeycryptographicsyst emsbasedonbraidgroups, Keywords:publickeycryptography;discretelogarithmproblem;latticereduction;quantum cipher;braidgroups 1949 年.ClaudeShannon 在(BellSystemTechnicalJournal))JL 发表 了题为CommunicationTheoryofSecrecySystems的论文.它 是现代密码学的理论基础，这箱论文将密码学研究纳入了科学轨 道,但由于受到一些因素的影响，该篇论文当时并没有引起人们 的广泛重视?直到20世纪70年代.随着人类社会步入信息吋代 才引起人们的普遍重视，那个时期岀现了现代密码的两个标志性 成果?一个是美国国家标准局(NBS)公开征集，并于1977年止式 公布实施的美国数据加密标准(DES):另一个是由whimeldDe 和 MartinHellman 在 1976 年发表的NewDirectioninCryptogm. phy”,在这篇文章中首次提出了公钥密码体制，冲破了长期以来 直沿用的私钥体制?自从公钥密码体制被提出以来.相继出现 了许多公钥密码方案，如RSA,ELGamal密码体制，背包算法， ECC,X1 限和 NTRU 等. 公钥密码体制的发现是密码学发展史上的一次革命.从古老 的手工密码,到机电式密码，直至运用计算机的现代对称密码?这 些编码系统虽然越来越复杂?但都建立在基本的替代和置换工具 的基础上，而公钥密码体制的编码系统是基于数学中的单向陷门 函数.更重要的是，公钥密码体制采用了两个不同的密钥?这对在 公开的网络上进行必威体育官网网址通信，密钥分配，数字签名和认证有着深 远的影响. 文章共分为7部分:第1部分首先介绍了 Merkle—Hellman背 包算法，第2,3,4,5,6部分分别讨论了 RSA,ECC,量子密码,NTRU 和基于辫群的密码体制,最后第7部分给出了结论，同时对公钥 密码体制进行了展望. IMerkle一Hellman 背包算法 1978年,RalphMerkle和MartinHellman提出的背包算法是 公钥密码体制用于加密的第一个算法,它起初只能用于加密?但 后来经过AdiShamir的改进使Z也能用于数字签名.其安全性基 于背包难题,它是个NP完全问题.这意味着没有多项式吋间算法 来解决这个问题.虽然后来这个算法被证明是不安全的,但由于 它证明了如何将NP完全问题应用于公钥密码体制.其设计思想 及其攻破方法给人们认识公钥密码体制以很多启示.因而在这里 我们提到此算法 背包问题（或子集和问题）描述起来非常简单?给定一堆物 品,每个重量不同，能否将这些物品中的儿件放人一个背包中使 之等于一个给定的重量?给个公式化的描述:给定一系列值M., ? ? ? ,M和一个和S,计算b;使之满足： I Jsl+6_2+…均 b的值可为0或1,0代表这个物品