公钥密码体制总结及展望
摘要：计算机网络的发展突飞猛进，与此同时产生了公钥密码体制，本文重点介绍了当前公钥密码体制的几种常见的算法以及公钥密码体制的未来发展趋势。
关键词公钥密码体制 RSA DSA ECDSA SHA-1 数字签名身份认证
1 引言
公开密钥密码体制的概念是1976年由美国密码学专家狄匪(Diffie)和赫尔曼(Hellman)[1]提出的，有两个重要的原则：第一，要求在加密算法和公钥都公开的前提下，其加密的密文必须是安全的；第二，要求所有加密的人和掌握私人秘密密钥的解密人，他们的计算或处理都应比较简单，但对其他不掌握秘密密钥的人，破译应是极困难的。随着计算机网络的发展，信息保密性要求的日益提高，公钥密码算法体现出了对称密钥加密算法不可替代的优越性。近年来，公钥密码加密体制和PKI、数字签名、电子商务等技术相结合，保证网上数据传输的机密性、完整性、有效性、不可否认性，在网络安全及信息安全方面发挥了巨大的作用。本文详细介绍了公钥密码体制常用的算法及其所支持的服务。
2 公钥密码算法
公钥密码算法中的密钥依性质划分，可分为公钥和私钥
两种。用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。在近代公钥密码系统的研究中, 其安全性都是基于难解的可计算问题的。如:
(1)大数分解问题；(2)计算有限域的离散对数问题；(3)平方剩余问题；(4)椭圆曲线的对数问题等。
基于这些问题, 于是就有了各种公钥密码体制。关于公钥密码有众多的研究, 主要集中在以下的几个方面:
(1)RSA 公钥体制的研究；(2)椭圆曲线密码体制的研究；(3)各种公钥密码体制的研究；(4)数字签名研究。
公钥加密体制具有以下优点:
(1)密钥分配简单；(2)密钥的保存量少；(3)可以满足互不相识的人之间进行私人谈话时的保密性要求；(4)可以完成数字签名和数字鉴别。
2.1 RSA算法
RSA算法[2]是Ron Rivest, Adi Shamir和Len Adleman 在1978年提出的，是一种公认十分安全的公钥密码算法。RSA算法是目前网络上进行保密通信和数字签名的最有效安全算法。RSA算法的安全性基于数论中大素数分解的困难性。
所以，RSA需采用足够大的整数。因子分解越困难，密码就越难以破译，加密强度就越高。其公开密钥和私人密钥是一对大素数的函数。从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。因式分解理论的研究现状表明：所使用的RSA密钥至少需要1024比特，才能保证有足够的中长期安全。
为了产生两个密钥，选取两个大素数p和q。为了获得最大程度的安全性，两数的长度一样。计算乘积：N=pq，然后随机选取加密密钥e，使e和互素。最后用欧几里得扩展算法计算解密密钥d，以满足：ed=1mod则 d=e-1mod注意：d和n也互素。e和n是公开密钥，d是私人密钥。两个素数p和q不再需要，可以舍弃，但绝不能泄漏。
加密消息m时，首先将它分成比n份小的数据分组。加密后的密文c，将由相同长度的分组ci组成。加密公式可表示为：ci=mie ×(mod n) 解密消息时，取每一个加密后的分组ci并计算：mi= cdi ×(mod n)。
由于：cdi= (mei ) d= medi = mi k (p - 1) (q- 1) + 1= m i×m i k (p - 1) (q- 1)= m i×1= m i (mod n)这个公式能恢复出全部明文。公开密钥 n：两个素数p和q的乘积；e：与互素。私人密钥 d：与n互素。加密 c=me×(mod n)；解密 m=cd×(mod n)。
2.2 ECDSA算法
椭圆曲线数字签名算法(ECDSA) [5]设计的数学原理是基于椭圆曲线离散对数问题的难解性。EC点上离散对数的研究现状表明:所使用的ECDSA密钥至少需要192比特,才能保证有足够的中长期安全。椭圆曲线是指由韦尔斯特拉斯(Weierstrass)方程：
y2+a1xy+a3y=x3+a2x2+a4x+a6
所确定的平面曲线。定义F为一个域，其中ai∈F，i ＝1,2，…6。F可为有理解域、实数域、复数域，也可为有限域GF(q)。在椭圆曲线密码体制中，F一般为有限域。由有限域椭圆曲线上的所有点外加无穷远点组成的集合，连同按照“弦切法”所定义的加法运算构成一个有限Abel群。在此有限Abel群上，定义标量乘法(Scalar Multiplication)为：mP＝P+P+…P(m个P相加)；若mP＝Q，定义： m＝logpQ 为椭圆曲线点群上的离散对数问题，此问题无多项式时间内的求解算法。ECDSA的设计正是基于这一问题的难解性。
在此，我们讨论定义在有限域GF(2m)上的椭圆曲线数字签名算法。今定义椭圆曲线方程为：y2+xy＝x3+ax2+b a,b ∈GF(2m)；则椭圆曲线的域参数为 D(m,f(x),a,b,P,n) 其中,f(x)为GF(2m)的多项式基表示的不可约多项式。P 表示椭圆曲线上的一个基点，n为素数且为点G的阶。
ECDSA算法密钥对的生成过程为：在区间[1，n-1]上选择一个随机数d，计算Q＝dP，则Q为公钥，d为私钥。
ECDSA算法的签名生成过程可简述如下：若签名的消息为e，则在区间[1，n-1]上选择一个随机数k，计算 kG＝(xl，y1)； r＝xl mod n；s＝k-1(e+dr) mod n。如果r或s为零，则重新计算，否则生成的签名信息为(r，s)。
ECDSA算法的签名验证过程可简述如下：若公钥为Q，签名的消息为e计算： w＝s-1 mod n ；u1＝ew mod n ；u2＝rw mod n ；X＝u1P + u2Q＝(xl，y1)。如果X为无穷远点，则拒绝签名，否则计算：v＝xl mod n；如果v＝r，则接受签名，否则拒绝签名。
2.3 SHA-1算法
SHA-1杂凑算法[4]起初是针对DSA算法而设计的，其设计原理与Ron Rivest提出的MD2，MD4，尤其是MD5杂凑函数的设计原理类似。当输入长度<264bit的消息时，输出160bit的摘要，其算法分为5步：
(1)填充消息使其长度为512的倍数减去64，填充的方法是添一个“1”在消息后，然后添加“0”直至达到要求的长度，要求至少1位，至多512位填充位；
(2)完成第1步后，在新得到的消息后附加上64bit填充前的消息长度值；
(3)初始化缓存，SHA-1用5字的缓存，每个字均是32bit；
(4)进入消息处理主循环，一次循环处理512bit，主循
环有4轮，每轮20次操作；
(5)循环结束后，得到的输出值即为所求。
3 公钥密码的服务
3.1 数据加密
一般说来，公钥密码中的计算是很慢的，以至于在很多情况下是不可行的。可以用一个两步过程来代替。
(1)用随机生成的对称密钥来加密数据。
(2)用授权接收者的公钥来加密这个对称密钥。
当授权接收者收到加过密的数据后，也采取一个类似的两步过程：
(1)授权接收者用自己的私钥来解出对称密钥。
(2)接着用对称密钥进行解密获得原始数据。
3.2 数字签名
数字签名在公钥密码体制下是很容易获得的一种服务，但在对称密码体制下很难获得。数字签名从根本上说是依靠密钥对的概念。发送方必须拥有一个只有自己知道的私钥，这样当他签名一些数据时，这些数据唯一而又明确地和他联系在一起，同时，应该有一个或更多实体都知道的公钥，以便大家验证，并确认签名是发送方的。因此，可以把数字签名操作看作是在数据上的私钥操作。整个签名操作就是一个两步过程：
(1)签名者通过杂凑函数把数据变成固定大小。
(2)签名者把杂凑后的结果用于私钥操作。
验证操作也是一个类似的两步过程：
(1)验证者通过杂凑函数把数据变成固定大小。
(2)验证者检查杂凑后的结果，传输来的签名，如果传输来的签名用公钥解密后的结果和验证者计算的杂凑结果相匹配，签名就被验证，否则，验证失败。
从而，数字签名不仅提供了数据起源认证服务，还有数据完整性及不可否认性的服务。
3.3 密钥的建立
公钥密码体制也可以用来实现两个实体间的密钥建立的功能，也就是说，一个协议用到公钥和私钥，协议的结果是两个实体共享一个对称密钥，而这个密钥不为其他的实体所知。密钥的建立可以通过以下两种途径：
(1)密钥传递：一个实体产生一个对称密钥送给其他的实体，公钥密码体制可以用来保证传送的机密性。如发送方用接收方的公钥来加密对称密钥，使得只有接收方才能得到。
(2)密钥协定：两个实体共同来完成对称密钥的产生，公钥密码体制把这个过程变得相对简单。如Diffie-Hellman [6]体制是第一个利用公钥密码的特点来选取双方共同约定的对称密码体制中密钥的方案。
其具体方法如下: 假设Alice和Bob 两个用户打算选取
一个高阶有限域Zp 中某一个数作为会话密钥。设P是一个质数, g是P 的一个本原元: 0< a< P, 当k= 1,2,…,P-1 时gKmod P 的值, 可以使1,2,…,P-1 中的每一状态都出现一次。选定g 和P,由网络中的所有用户和主机共享。Alice和Bob可以通过如下的交换过程建立相同的密钥:
(1) Alice 随机选取整数a (1 (2) Bob 随机选取整数b (1 (3) Alice 将Qa传送给Bob, 而Bob 将Qb传送Alice； (4) Alice 收到Qb后, 计算K=Qbamod P∈Zp；Bob 收到Qa后, 计算K=Qabmod P∈Zp； 则K∈Zp 就可作为Alice 和Bob所使用对称密码体制中的密钥。 3.4 身份标识和认证 在对称密码环境下，通信双方的身份认证是十分困难的，这就成了推动公钥密码体制发展的巨大动力之一。通信或交易时，应该保证信息的接收方和发送方能够被唯一地标识出来，让通信双方都能够知道信息从哪里来或者到哪里去。我们也将这种安全保障简称为真实性。按照被验证对象可以将真实性问题分成三种，一种是设备真实性，其二是人的真实性，其三是信息的真实性。通过主机地址，主机名称， 拥有者的口令等都在一定的程度上保证了对设备的验证，但都不能很好地满足安全的要求。非对称算法或数字签名是人员、设备或信息验证的一种好方法。原理上说，没有人能够假冒数字签名。基于公钥体制的身份认证主要利用数字签名和hash 函数实现。设A 对信息M 的hash 值H(M) 的签名为SigSA(H(M)) ,其中SA 为A 的私钥. A 将M 及SigSA (H(M)) 发送给用户B。B 通过A 的公钥PA进行解密：PA的完整性得到保障。 (2)公钥以一种可信的方式和它的声称者绑定在一起。 公私证书机制很好的解决了通信双方相互确定身份的问题。 4 结束语 公钥密码体制是非常重要的一种技术，它实现了数字签名的概念，提供了对称密钥协定的切实可行的机制，使安全通信成为可能。密钥对的思想也实现了其他的服务和协议，包括：机密性、数据完整性、安全伪随机数发生器和零知识证明等。目前，公钥密码的重点研究方向,理论方面[7]: (1)用于设计公钥密码的新的数学模型和陷门单向函数的研究； (2)公钥密码的安全性评估问题，特别是椭圆曲线公钥密码的安全性评估问题。 应用方面: (1)针对实际应用环境的快速实现的公钥密码设计； (2)公钥密码在当今热点技术如网络安全、电子商务、PKI、信息及身份认证等中的应用，这方面还将是持续研究热点。 参考文献 [1] Diffie, W.and M.Hellman. New directions in Cryptography. IEEE Transactions on Information Theory 22(1976):644-654. [2] Rivest R , Shamir A , Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM,1976 ,21(2) :120-126. [3] 谭凯军,诸鸿文,顾尚杰. 基于数字签名方案DSS/DSA 的几种应用方案[J].计算机研究与发展.1999,36(5):632-638. [4] 吴世忠，祝世雄等.应用密码学-协议、算法与C源程序[M].机械工业出版社,XX. [5] M J B Robshaw, Yiqun Lisa Yin. Elliptic Curve Cryptosystems. An RSA laboratories Technical Note, Revised,1997: URL-https://www.doczj.com/doc/ab7886949.html,/rsalabs.ecc/elliptic_curve.h tml. [6] 庞南,戴英侠,李镇江.因特网密钥交换协议研究[J].计算机工程,XX,28(5):67-70. [7] 冯登国.国内外密码学研究现状及发展趋势[J].通信学报,XX,23(5):18-27. [8] 冯登国等译. 公开密钥基础设施——概念、标准和实施[M].XX：人民邮电出版社,XX. 作者简介：毕仁平男，汉族，湖南XX人，长江大学教育技术与服务中心， 数学文化课程报告论文题目：公钥密码体制的现状与发展 公钥密码体制的现状与发展 摘要：文中对公钥密码体制的现状与发展进行了介绍，其中着重讨论了几个比较重要的公钥密码体制Ｍ－Ｈ背包算法、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完全问题，这意味 目录 第一章绪论 (1) 1.1 研究背景与意义 (1) 第二章预备知识 (7) 2.1 复杂性理论 (7) 2.2 可证明安全理论 (8) 2.2.1 困难问题假设 (8) 2.2.2 形式化证明方法 (10) 2.3 公钥密码体制 (11) 2.3.1 PKE形式化定义 (11) 2.3.2 PKE的安全模型 (12) 2.5 密钥泄露 (12) 2.5.1 问题描述 (12) 2.5.2 解决方法 (13) 2.6 本章小结 (14) 致谢 (16) 第一章绪论 第一章绪论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段： 第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》错误！未找到引用源。后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》错误！未找到引用源。以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐位加密，二者之间也不是有着不可逾越的鸿沟，很多时候，分组加密算法也可以用于构建流密码算法。目前，世界上存在的分组密码算法可能有成千上万种，而其中最有名的就是美国的DES、AES以及欧洲的IDEA算法。 公钥密码体制原理及展望 ----读《New Directions in Cryptography》 姓名 学号 指导教师 时间2010年11月19日星期五 公钥密码体制原理及展望 ----读《New Directions in Cryptography》 摘要：本文通过读《New Direction in Cryptography》一文，简述了密码学的发展，重点讨论了公钥密码体制的算法及安全性。并在此基础上介绍了ECC和量子密码，了解了非对称密码体制的应用，展望了密码学未来的发展方向。 关键字：公钥密码体制，单向陷门函数、ECC、量子密码 一概述 密码学是研究如何隐密地传递信息的学科。在现代特別指对信息以及其传输的数学性研究，常被认為是数学和计算机科学的分支，和信息论也密切相关。回顾密码学的发展历程： 第一个阶段是古典密码学（19世纪以前），主要包括代替密码、换位密码以及代替密码与换位密码的组合方式等。 第二阶段是中世纪密码学，它是宗教上被刺激的原文分析对Quran那些导致了发明频率分析打破的技术替换密码。它是最根本的cryptanalytic前进直到WWII。所有暗号根本上依然是脆弱直到这个cryptanalytic技术发明polyalphabetic暗号。 第三阶段是从1800到第二次世界大战，由第二次世界大战机械和机电暗号机器在宽用途，虽然这样机器是不切实际的地方继续的人工制在使用中。巨大前进被做了暗号打破所有在秘密。 第四阶段是现代密码学，C.E.Shannon于1949年发表的划时代论文“The Communication Theory of Secret Systems”，这是现代密码学的第一次发展也是开端。而更重要的一次发展是1976年，当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人提出了公开密钥密码的新思想，论文《New Direction in Cryptography》把密钥分为加密的公钥和解密的私钥，这是现代密码学的经典之作，是密码学的一场革命。 《New Direction in Cryptography》一文为解决传统密码体制（主要针对对称密码体制）密钥分发困难、密钥集中了密文的安全性等缺陷，设计了公钥密码体制，是非对称密码学的开山之作。下面简要地介绍一下这篇文章的主要内容。 二公钥密码体制基本原理 公钥密码算法中的密钥依性质划分，可分为公钥和私钥两种。用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。所以在公钥密码系统中，首先要求加密函数具有单向性，即求逆的困难性。即： 一个可逆函数f：A→B，若它满足： 1o对所有x∈A，易于计算f(x)。 2o对“几乎所有x∈A”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。 但是，要做加密处理，对加密函数仅有单向的要求还不够，必须还要满足， ElGamal公钥密码体制 1、问题描述 设计ElGamal公钥密码体制算法。 2、算法设计 (1)选取大素数p和p的一个原根a，(a,p)=1,1 r[j+1]=r[j-1]-q[j]*r[j]; if(j>=2) { s[j]=s[j-2]-q[j-1]*s[j-1]; t[j]=t[j-2]-q[j-1]*t[j-1]; } } return s[j-1]; } int gcd(int a,int b) { int c; if(a 公钥密码体制的研究 目录 第一章绪论 (1) 1.1 研究背景与意义 (1) 第二章预备知识 (7) 2.1 复杂性理论 (7) 2.2 可证明安全理论 (8) 2.2.1 困难问题假设 (8) 2.2.2 形式化证明方法 (10) 2.3 公钥密码体制 (11) 2.3.1 PKE形式化定义 (11) 2.3.2 PKE的安全模型 (12) 2.5 密钥泄露 (12) 2.5.1 问题描述 (12) 2.5.2 解决方法 (13) 2.6 本章小结 (14) 致谢 (17) 第一章绪论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段： 第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》错误!未找到引用源。后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》错误!未找到引用源。以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐位加密，二者之间也不是有着不可逾越的鸿沟，很多时候，分组加密算法也可以用于构建流密码算法。目前，世界上存在的分组密码算法可能有成千上万种，而其中最有名的就是美国的DES、AES以及欧洲的IDEA算法。 关键词公钥密码体制－数字签名身份认证 引言 公开密钥密码体制地概念是年由美国密码学专家狄匪（）和赫尔曼（）提出地，有两个重要地原则：第一，要求在加密算法和公钥都公开地前提下，其加密地密文必须是安全地；第二，要求所有加密地人和把握私人秘密密钥地解密人，他们地计算或处理都应比较简单，但对其他不把握秘密密钥地人，破译应是极困难地.随着计算机网络地发展，信息保密性要求地日益提高，公钥密码算法体现出了对称密钥加密算法不可替代地优越性.近年来，公钥密码加密体制和、数字签名、电子商务等技术相结合，保证网上数据传输地机密性、完整性、有效性、不可否认性，在网络安全及信息安全方面发挥了巨大地作用.本文具体介绍了公钥密码体制常用地算法及其所支持地服务.文档来自于网络搜索 公钥密码算法 公钥密码算法中地密钥依性质划分，可分为公钥和私钥两种.用户或系统产生一对密钥，将其中地一个公开，称为公钥；另一个自己保留，称为私钥.任何获悉用户公钥地人都可用用户地公钥对信息进行加密与用户实现安全信息交互.由于公钥与私钥之间存在地依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息地发送者都无法将此信息解密.在近代公钥密码系统地研究中，其安全性都是基于难解地可计算问题地.如：文档来自于网络搜索 （）大数分解问题；（）计算有限域地离散对数问题；（）平方剩余问题；（）椭圆曲线地对数问题等. 基于这些问题，于是就有了各种公钥密码体制.关于公钥密码有众多地研究，主要集中在以下地几个方面： （）公钥体制地研究；（）椭圆曲线密码体制地研究；（）各种公钥密码体制地研究；（）数字签名研究.文档来自于网络搜索 公钥加密体制具有以下优点： （）密钥分配简单；（）密钥地保存量少；（）可以满足互不相识地人之间进行私人谈话时地保密性要求；（）可以完成数字签名和数字鉴别.文档来自于网络搜索 .算法 算法是，和在年提出地，是一种公认十分安全地公钥密码算法.算法是目前网络上进行保密通信和数字签名地最有效安全算法.算法地安全性基于数论中大素数分解地困难性.所以，需采用足够大地整数.因子分解越困难，密码就越难以破译，加密强度就越高.其公开密钥和私人密钥是一对大素数地函数.从一个公开密钥和密文中恢复出明文地难度等价于分解两个大素数之积.因式分解理论地研究现状表明：所使用地密钥至少需要比特，才能保证有足够地中长期安全.文档来自于网络搜索 为了产生两个密钥，选取两个大素数和.为了获得最大程度地安全性，两数地长度一样.计算乘积：＝，然后随机选取加密密钥，使和互素.最后用欧几里得扩展算法计算解密密钥，以满足：＝则＝－注重：和也互素.和是公开密钥，是私人密钥.两个素数和不再需要，可以舍弃，但绝不能泄漏.文档来自于网络搜索 加密消息时，首先将它分成比份小地数据分组.加密后地密文，将由相同长度地分组组成.加密公式可表示为：＝×（）解密消息时，取每一个加密后地分组并计算：＝×（）.文档来自于网络搜索 由于：＝（）＝＝（－）（－）＝×（－）（－）＝×＝（）这个公式能恢复出全部明文.公开密钥：两个素数和地乘积；：与互素.私人密钥：与互素.加密＝×（）；解密＝×（）.文档来自于网络搜索 .算法 目录 第一章绪论 1.1 研究背景与意义 第二章预备知识 2.1 复杂性理论 2.2 可证明安全理论 2.2.1 困难问题假设 2.2.2 形式化证明方法 2.3 公钥密码体制 2.3.1 PKE形式化定义 2.3.2 PKE的安全模型 2.5 密钥泄露 2.5.1 问题描述 2.5.2 解决方法 2.6 本章小结 致谢 第一章绪论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段：第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》[1]后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》[2]以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐 公钥密码体制的核心思想是：加密和解密采用不同的密钥。这是公钥密码体制和传统的对称密码体制最大的区别。对于传统对称密码而言，密文的安全性完全依赖于密钥的保密性，一旦密钥泄漏，将毫无保密性可言。但是公钥密码体制彻底改变了这一状况。在公钥密码体制中，公钥是公开的，只有私钥是需要保密的。知道公钥和密码算法要推测出私钥在计算上是不可行的。这样，只要私钥是安全的，那么加密就是可信的。 显然，对称密码和公钥密码都需要保证密钥的安全，不同之处在于密钥的管理和分发上面。在对称密码中，必须要有一种可靠的手段将加密密钥（同时也是解密密钥）告诉给解密方；而在公钥密码体制中，这是不需要的。解密方只需要保证自己的私钥的保密性即可，对于公钥，无论是对加密方而言还是对密码分析者而言都是公开的，故无需考虑采用可靠的通道进行密码分发。这使得密钥管理和密钥分发的难度大大降低了。 加密和解密:发送方利用接收方的公钥对要发送的明文进行加密,接受方利用自己的 私钥进行解密,其中公钥和私钥匙相对的,任何一个作为公钥,则另一个 就为私钥.但是因为非对称加密技术的速度比较慢,所以,一般采用对称 加密技术加密明文,然后用非对称加密技术加密对称密钥,即数字信封技术. 签名和验证:发送方用特殊的hash算法，由明文中产生固定长度的摘要，然后利用 自己的私钥对形成的摘要进行加密，这个过程就叫签名。接受方利用 发送方的公钥解密被加密的摘要得到结果A，然后对明文也进行hash操 作产生摘要B.最后,把A和B作比较。此方式既可以保证发送方的身份不 可抵赖，又可以保证数据在传输过程中不会被篡改。 首先要分清它们的概念: 加密和认证 背包密码体制之背包算法 姓名：张全英 学号：20143967 专业：信息与计算科学1班 学院：数学与信息科学 摘要：网络和信息安全正在成为一个国家政治、军事、经济以及社会生活正常运行的基础,它将是一个国家综合实力的重要体现。而密码学是信息安全的核心。公钥密码又是将加密、解密密钥甚至加密、解密函数分开,用户只保留解密密钥,而将加密密钥和加密函数一起公之于众,是密码学的重要组成部分。背包公钥和RSA一样是著名的公钥体制之一,特别是背包公钥的安全基础是背包问题,这是一个NP难问题。虽然在提出不久就遭到破解,但是在提出的背包公钥系统的改进方案中依然有几个被证明是安全的。背包公钥是首个把NP问题用于公钥密码的密码体制,而其他现阶段应用的公钥密码体制都是基于因式分解或离散对数问题的,他们都不是NP问题构造的,因此背包公钥体制的研究是十分有意义的。本文从背包体制的常用攻击方法入手,寻找被破解的原因,并针对这些原因提出了新的构造思路,利用非超递增序列构造背包体制。利用非超递增序列构造背包公钥有2个必须解决的问题是加密结果的不唯一性和解密的困难性。本文对一种同余多模背包序列进行分析,并利用得出的性质构造一种新的L序列,并证明了L序列能解决以上2个问题,并提出了利用L序列构造背包公钥体制的方案。为了加快加解密速度,还提出了模M和W-1的逆向构造算法。然后给出了非超递增背包公钥体制的模拟实现。 关键字：模逆，欧几里德算法，同余式，超递增序列 目录： 1.公钥密码的原理 2.公钥密码的数学基础： 一个公开密钥密码系统必须满足的条件是： A.通讯双方A和B容易通过计算产生出一对密钥（公开密钥K1，私钥密钥K2）。 B.在知道公开密钥K1和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文： C.C = Ek1（M） D.接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文： E.M = Dk2（C）= Dk2[Ek1（M）] F.除A和B以外的其他人即使知道公钥k1，要确定私钥K2在计算上也是不可行的。 G.除A和B以外的其他人即使知道公钥k1和密文C，要想恢复原来的明文C在计算上也是不可行的。 3.数论基础知识： 这些要求最终可以归结到设计一个单向陷门函数。 4.单向函数：单项陷门函数： 一个单向函数是满足下列条件的函数：它将一个定义域映射到值域，使得每个函数值有一个唯一的原像，同时还要满足下列条件：函数值计算很容易，而逆计算是不可行的。 所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在另外的方向上要计算是不可行的。有了附加的信息，函数的逆就可以在多项式时间内计算出来。 一个实用的公开密钥密码系统的建立和发展依赖于找到一个单向陷门函数。 公钥密码体制总结及展望 摘要：计算机网络的发展突飞猛进，与此同时产生了公钥密码体制，本文重点介绍了当前公钥密码体制的几种常见的算法以及公钥密码体制的未来发展趋势。 关键词公钥密码体制 RSA DSA ECDSA SHA-1 数字签名身份认证 1 引言 公开密钥密码体制的概念是1976年由美国密码学专家狄匪(Diffie)和赫尔曼(Hellman)[1]提出的，有两个重要的原则：第一，要求在加密算法和公钥都公开的前提下，其加密的密文必须是安全的；第二，要求所有加密的人和掌握私人秘密密钥的解密人，他们的计算或处理都应比较简单，但对其他不掌握秘密密钥的人，破译应是极困难的。随着计算机网络的发展，信息保密性要求的日益提高，公钥密码算法体现出了对称密钥加密算法不可替代的优越性。近年来，公钥密码加密体制和PKI、数字签名、电子商务等技术相结合，保证网上数据传输的机密性、完整性、有效性、不可否认性，在网络安全及信息安全方面发挥了巨大的作用。本文详细介绍了公钥密码体制常用的算法及其所支持的服务。 2 公钥密码算法 公钥密码算法中的密钥依性质划分，可分为公钥和私钥 两种。用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。在近代公钥密码系统的研究中, 其安全性都是基于难解的可计算问题的。如: (1)大数分解问题；(2)计算有限域的离散对数问题；(3)平方剩余问题；(4)椭圆曲线的对数问题等。 基于这些问题, 于是就有了各种公钥密码体制。关于公钥密码有众多的研究, 主要集中在以下的几个方面: (1)RSA 公钥体制的研究；(2)椭圆曲线密码体制的研究；(3)各种公钥密码体制的研究；(4)数字签名研究。 公钥加密体制具有以下优点: (1)密钥分配简单；(2)密钥的保存量少；(3)可以满足互不相识的人之间进行私人谈话时的保密性要求；(4)可以完成数字签名和数字鉴别。 2.1 RSA算法 RSA算法[2]是Ron Rivest, Adi Shamir和Len Adleman 在1978年提出的，是一种公认十分安全的公钥密码算法。RSA算法是目前网络上进行保密通信和数字签名的最有效安全算法。RSA算法的安全性基于数论中大素数分解的困难性。 多变量公钥密码体制的设计与安全性分析研究随着量子计算研究的进展,后量子公钥密码逐渐成为了密码学研究的热点之一。多变量公钥密码学是后量子公钥密码学的研究分支之一。由于多变量公钥密码体制尚未有适当的可证明安全方法,因此衡量多变量公钥密码体制的安全性依赖于抵抗现有的攻击方法。目前,多数二次多变量公钥密码算法遭受到了各种代数工具的分析,难以确保体制既高效又安全。本文的研究工作首先对现有的一些公钥密码体制进行了安全性分析,然后针对现有攻击方法,考虑将体制的次数提高到三次来抵抗现有的攻击,提出了一系列的三次多变量公钥密码体制。具体如下:(1)利用线性化方程结合差分攻击破解了一类l-可逆循环类的公钥加密体制。该体制和l-可逆循环公钥加密体制一样满足线性化方程,在找到所有的线性化方程后,给定合法密文,可将原体制退化为Square加密体制,从而可用差分攻击破解,找到合法密文相应的明文。利用二次化方程结合直接攻击方法破解了扩展的多变量公钥密码体制的两个实例。在找到所有的二次化方程后,给定合法密文,就可得到明文变量的二次多项式方程,从而降低了求解过程中的正则次数,使得直接攻击方法可以找到合法密文相应的明文。(2)提出了三次中间域方程公钥加密体制和数字签名体制。方案中设计使用三个二阶矩阵的乘积来构造中心映射中的三次多项式,而且采用二阶矩阵的行列式来作为锁多项式隐藏其中的三角形结构。当公钥多项式的次数从二次提高到三次,有效地避免线性化方程的出现,也能够抵抗直接攻击。和三次简单矩阵多变量公钥密码体制相比,在同等安全强度下, 本文提出的体制密钥规模较小。(3)提出了三次不平衡油醋签名体制。三次不平衡油醋体制中存在大量的油变量的二次项,可以抵抗油醋分 离攻击,而且醋变量个数可以少于油变量的个数。相比于二次不平衡 油醋签名体制,三次方案的签名长度要短得多,密钥生成的时间也更短。选择合适的参数之后,该方案同样可以抵抗秩攻击和直接攻击。(4)提出了两个三次多变量数字签名体制。第一个三次签名体制使用 的中心映射是立方映射,结合投影方法和减方法可使得构造的签名体 制能够抵抗差分攻击,同时合适的参数选择可使得体制能够抵抗现有 的其他攻击方法。第二个三次签名体制的中心映射类似于l-循环公 钥密码体制,不过l-循环体制的中心映射是二次的,而本文的方案中 心映射是三次的,合适选择参数后,可抵抗差分攻击、线性化方程攻击、直接攻击等现有攻击。本文中所提出的密码体制和攻击及安全性分析过程均在普通PC机上通过Magma来实现,验证了文中的理论分析结果。论文的工作为多变量公钥密码体制的设计与分析提供了新的思路。 毕业设计（论文）开题报告 题目公钥密码体制RSA安全分析及应用 系（院）数学与信息科学系年级 专业数学与应用数学班级 学生姓名学号 指导教师职称 学院教务处 二〇一二年三月 一、课题的目的意义： 随着计算机和电子通讯技术,包括因特网的迅猛发展,金融电子化的步伐大大加快,这种电子化、数字化的趋势已经波及社会生活的几乎所有的方面。人与人之间的许多交往活动,包括商业贸易、金融财务和其他经济活动中,不少已以数字化信息的方式在网上流动着。"数字化经济"（Economy Digital）的图景已经浮现,电子商业、电子银行和电子货币的研究、实施和标准化正在紧锣密鼓地进行中。许多传统上基于纸面的,常常需要签名盖章的重要凭证,诸如纸币、存单、支票、股票、公函、合同、租约、遗嘱、选票、法律文书、身份证件、学历证书等等,已陆续转化为数字电子媒体的形式出现。 那些机密的、甚至价值连城的重要信息常常需要在公开的网络上传送。怎样才能确保原始信息不会被窃取、窃听不能被伪造、篡改怎样才能确认信息发送者的真实性怎样才能保证信息发送者无法抵赖？。"公开密钥密码系统"ystem keycryptos public ,或称"公开密钥密码体制")的巧妙方法比较成功地解决了上述问题,并已在业界得到了广泛的应用。 公开密钥密码体制是现代密码学的最重要的发明和进展。说起密码学在大家的印象中主题应该是保护信息传递的机密性。确实,保护敏感的通讯一直是密码学多年来的重点。但这仅仅是当今密码学的主题的一个方面,对信息发送人的身份的验证,正是密码学主题的另一方面。公开密钥密码体制为这两方面的问题都给出了出色的答案,并正在继续产生许多新的思想和方案。目前公钥密码体制最典型的代表是RSA体制。 二、文献综述： 中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。 公开密钥密码体制的概念是由ford S tan大学的研究人员Diffie及Hellman于1976年提出的。公开密钥密码体制的产生主要有两方面的原因：一是由于常规密钥密码体制的密钥分配问题；而是由于对数字签名的需求。目前比较流行的公钥密码体制主要有两类:一类是基于大整数因子分解问题的,其中RSA算法是公钥密码体制中的重要成员，也是目前最流行的公钥密码体制之一。另一类是基于离散对数问题的,如ElGamal公钥密 浅析几种公钥密码体制 摘要：论述了RSA、Merkle-Hellman背包加密体制和椭圆曲线密码体制的基本原理，以及它们的优缺点，通过对比指出椭圆曲线密码体制的明显优点。 关键词：RSA；Merkle-Hellman背包加密体制；ECC；优缺点 1引言 公钥密码体制于1976年由W.DIffie和M.Hellman提出，同时R.Merkle在1978年也独立的提出这一体制[2]。该密码体制就是针对私钥密码体制的缺陷被提出来的。在公钥加密系统中，加密和解密是相对独立的，加密和解密会使用两把不同的密钥。加密密钥向公众公开，谁都可以使用。解密密钥只有解密人自己知道，非法使用者根据公开的加密密钥无法推算出解密密钥。故其可称为公钥密码体制。 自从公钥密码体制被提出以来，出现了许多公钥密码方案如RSA、ELGamal 密码体制、背包算法和ECC、XTR、NTRU等。 下面就介绍一下各种密码体制的优缺点，并进行比较。 2RSA 在Diffie和Hellman提出公钥系统观点以后，1977年麻省理工大学的Rivest、Shamir和Adleman提出了第一个比较完善的公钥密码算法,即RSA算法[2]。 RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已经二十多年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NP问题。 RSA的缺点主要有：（1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。（2）分组长度太大，为保证安全性，至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级，且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化[6]。 3Merkle-Hellman背包加密体制 基于公钥密码体制的数据加密 摘要：公开密钥算法的原理是加密密钥和解密密钥分离，可将加密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。如用其中一个加密，则可用另一个解密。本文综述了公钥体系及其应用RSA算法，也讨论了相关的攻击手段。 关键字：公钥密码加密技术 RSA Abstrat：Public-key algorithm encryption and decryption key principle is key separation, but will encryption key in the open, who can use; And decryption decryption key only themselves know. Any person to use the encryption key and to the user to send the algorithm of the encrypted information, the user can be will restore. Public key encryption algorithm used in the most extensive is RSA. RSA use two keys, a public key, a special key. If use one of the encryption, usable another decryption. This paper reviewed the application of RSA public key system and its algorithm, and also discussed the related attack means. Key：Public key password Encryption technology RSA 1 公钥密码体系背景 通常信息安全的目标可以概括为解决信息的以下问题：保密性(Confidentiality)保证信息不泄露给未经授权的任何人；完整性（Integrity）防止信息被未经授权的人篡改；可用性（Availability）保证信息和信息系统确实为授权者所用；可控性（Controllability）对信息和信息系统实施安全监控，防止非法利用信息和信息系统。 密码是实现一种变换，利用密码变换保护信息秘密是密码的最原始的能力，然而，随着信息和信息技术发展起来的现代密码学，不仅被用于解决信息的保密性，而且也用于解决信息的完整性、可用性和可控性。可以说，密码是解决信息安全的最有效手段，密码技术是解决信息安全的核心技术。 公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文"New Direction in Cryptography"），思想不同于传统的对称密钥密码体制，它要求密钥成对出现，一个为加密密钥(e)，另一个为解密密钥(d)，且不可能从其中一个推导出另一个，其原理是加密密钥和解密密钥分离。在公钥体制中，加密密钥不同于解密密钥。人们将加密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。这样，一个具体用户就可以将自己设计的加密密钥和算法公诸于众，而只保密解密密钥。任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。 自1976年以来，已经提出了多种公开密钥密码算法，其中许多是不安全的，一些认为是安全的算法又有许多是不实用的，它们要么是密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学难题，这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因子分解问题)至今已有数千年的历史了。 一般理解密码学(Cryptography)就是保护信息传递的机密性，而对信息发送与接收人的真实身份的验证、对所发出/接收信息在事后的不可抵赖以及保障数据的完整性是现代密码学主题的另一方面。公开密钥密码体制对这两方面的问题都给出了出色的解答，并正在继续产生许多新的思想和方案。 公用密钥的优点就在于，也许你并不认识某一实体，但只要你的服务器认为该实体的CA是可靠公钥密码体制
公钥密码体制的介绍
公钥密码体制原理及展望---读《New Directions in Cryptography》
ElGamal公钥密码体制
公钥密码体制的研究
公钥密码体制综述及展望
公钥密码体制的研究
公钥密码体制的核心思想是
浅谈背包公钥密码体制全解
公钥密码体制总结及展望
多变量公钥密码体制的设计与安全性分析研究
RSA公钥密码体制开题报告
浅析几种公钥密码体制
基于公钥密码体制的数据加密
相关主题
文本预览