公钥密码体制总结及展望.docx

公钥密码体制总结及展望 摘 要：计算机网络的发展突飞猛进，与此同时产生了 公钥密码体制，本文重点介绍了当前公钥密码体制的几种 常见的算法以及公钥密码体制的未来发展趋势。 关键词 公钥密码体制 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 im i k (p - 1) (q- 1)= m i1= 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 为一个域，其中 aiF，i1,2，6。F 可为有理解域、实数域、复数域， 也可为有限域 GF(q)。在椭圆曲线密码体制中，F 一般为有 限域。由有限域椭圆曲线上的所有点外加无穷远点组成的 集合，连同按照“弦切法”所定义的加法运算构成一个有 限 Abel 群。在此有限 Abel 群上，定义标量乘法(Scalar Multiplication)为：mPP+P+P(m 个 P 相加)；若 mPQ，定义： mlogpQ 为椭圆曲线点群上的离散对数问 题，此问题无多项式时间内的求解算法。ECDSA 的设计正是 基于这一问题的难解性。 在此，我们讨论定义在有限域 GF(2m)上的椭圆曲线数 字签名算法。今定义椭圆曲线方程为：y2+xyx3+ax2+b a,bGF(2m)；则椭圆曲线的域参数为 D(m,f(x),a,b,P,n) 其中,f(x)为 GF(2m)的多项式基表示的不可约多项式。 P 表示椭圆曲线上的一个基点，n 为素数且为点 G 的阶。 ECDSA 算法密钥对的生成过程为：在区间1，n-1上选 择一个随机数 d，计算 QdP，则 Q 为公钥，d 为私钥。 ECDSA 算法的签名生成过程可简述如下：若签名的消息 为 e，则在区间1，n-1上选择一个随机数 k，计算 kG(xl，y1)； rxl mod n；sk-1(e+dr) mod n。如 果 r 或 s 为零，则重新计算，否则生成的签名信息为(r，s)。 ECDSA 算法的签名验证过程可简述如下：若公钥为 Q， 签名的消息为 e 计算： ws-1 mod n ；u1ew mod n ；u2rw mod n ；Xu1P + u2Q(xl，y1)。如果 X 为无 穷远点，则拒绝签名，否则计算：vxl mod n；如果 vr，则接受签名，否则拒绝签名。 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 (1aP-1) 予以保密, 并 计算 Qa=gamod PZp； (2) Bob 随机选取整数 b (1bp-1) 予以保密, 并计 算 Qb=gbmod PZp； (3) Alice 将 Qa 传送给 Bob, 而 Bob 将 Qb 传送 Alice； (4) Alice 收到 Qb 后, 计算 K=Qbamod PZp；Bob 收 到 Qa 后, 计算 K=Qabmod PZp； 则 KZp 就可作为 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 cryptosystemsJ. 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 Cr