非对称密码技术

2.3.2　非对称密码技术

20世纪70年代，一个数学上的突破震惊了世界密码学界，这就是公钥加密技术。与传统的加密方法不同，它使用两把钥匙：一把公开钥匙和一把秘密钥匙。前者用于加密，后者用于解密，它也称为“非对称式”加密方法。公钥加密技术解决了对称加密方法的根本性问题，极大地简化了钥匙分发过程。它若与对称加密方法结合，可以进一步增强对称加密方法的可靠性。此外，还可能利用公钥加密技术来进行数字签名。

1.公钥加密技术原理概述

1976年Diffie和Hellman在其划时代的文献New Directions in Cryptography（密码学新方向）中提出公钥加密的概念，公钥加密是基于单向陷门（trap door）函数来实现的，单向陷门函数是指满足下列条件的函数f（x）：

（1）给定x，计算y＝f（x）是容易的；

（2）给定y，计算x＝f^－1（y）是困难的；

（3）存在d，已知d时，对给定的任何y，若相应的x存在，则计算x＝f^－1（y）是容易的。

仅满足第（1）条、第（2）条的称为单向函数，第（3）条称为陷门性，d称为陷门信息。当用陷门函数f（x）作为加密函数时可将f（x）公开，这相当于公钥。f（x）函数的设计者将d保密，用作解密密钥，这相当于私钥。由于加密函数是公开的，任何人都可以将信息x加密成y＝f（x），然后送给函数的设计者，当然可以通过不安全信道传送，由于设计者拥有d（私钥），他可以容易地解出x＝f^－1（y）。单向陷门函数的第（2）条性质表明窃听者由截获的密文y＝f（x）推测x是不可行的。

目前公钥密码系统单向陷门函数的设计主要依赖下面三种数学难题：

（1）背包问题；

（2）大整数因子分解问题；

（3）离散对数问题。

第1类公钥系统的安全性依赖于背包问题的NP完全性。背包问题可以这样描述：已知一容积为C的背包及体积分别为k₁，k₂，…，k_n的n个物品，若从这些物品中选出若干个正好装满这个背包，那么究竟选哪些物品？即求m_i（1≤i≤n），使得C＝k₁m₁＋k₂m₂＋…＋k_nm_n，其中k_i和C都是正整数，m_i取0或1。背包问题是著名的NP完全问题，至今没有很好的求解方法。穷举搜索的复杂度为O（2ⁿ）。第一个背包公钥算法是由Merkle和Hellman于1978年提出的MH算法。选取正整数k₁，k₂，…，k_n作为密钥，设明文分组位串为M＝m₁m₂…m_n，则加密后的密文为C＝k₁m₁＋k₂m₂＋…＋k_nm_n。那么如何进行解密呢？奥妙在于存在一类特殊的背包问题，其物品体积序列k₁，k₂，…k_n的每一项都大于它之前的所有项之和，这就是著名的超递增背包问题，超递增背包问题的复杂度为O（n）（读者可想一想为什么）。Merkle和Hellman设计了一种可以将超递增背包问题转换为同解非超递增背包问题的方法。MH算法用超递增背包问题的体积序列作私钥，而用同解的非超递增背包问题的体积序列作公钥，这样就很容易用私钥进行解密了。MH算法后来被证明是不安全的，但这种算法首次将NP完全问题用于公钥密码学，在密码学史上具有开创意义。

第2类公钥系统是由麻省理工大学的三位科学家Ron Rivest，Adi Shamir和Leonard Adleman于1978年提出的，简称为RSA系统。它的安全性是基于大整数因子分解的困难性，其公钥和私钥是一对大素数（100到200位的十进制数或更大）的函数。从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积，而大整数因子分解问题是数学上的著名难题，因而可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，自提出以来就一直是人们研究的焦点，经受住了多年来许多资深密码学家的密码分析，说明该算法是有相当的可信度的。本节将重点介绍RSA算法。

第3类公钥系统的安全性依赖于离散对数的计算困难性。离散对数问题可细分为两类：一类为有限域上的离散对数问题；一类为椭圆曲线上的离散对数问题。下面举一个简单的有限域上离散对数的例子，设p为素数，g小于p，如果对每个b从l到p－1都存在x，使得g^x≡b mod p，则称g为模p的原根（primitive root）。例如5是模7的原根，这是因为

5¹≡5（mod 7）　　　

5²＝5×5≡4（mod 7）

5³＝4×5≡6（mod 7）

5⁴＝6×5≡2（mod 7）

5⁵＝2×5≡3（mod 7）

5⁶＝3×5≡1（mod 7）

如果g为模p的原根，则对任意y，总是可以找出y＝g^xmod p的解，x称为y模p的离散对数解（形如g^xmod p的运算称为模乘运算）。当p很小时，已知y和p可以用观察法求出x，但是当p为很大的随机素数时，就很难计算了。所以可以认为y＝g^xmod p是一个单向函数。其他类型的离散对数问题可以参考有关文献。

著名的椭圆曲线加密算法ECC（Elliptic Curve Cryptography）的安全性就是依赖于定义在椭圆曲线点上的离散对数问题的难解性。ECC算法是由Neal Koblit和Victor Miller于1985年首先提出，从那时起ECC的安全性和实现效率就被众多的数学家和密码学家所广泛研究。所得的结果表明，较之RSA算法，ECC具有密钥长度短，加解密速度快，对计算环境要求低，在需要通信时，对带宽要求低等特点。近年来，ECC被广泛应用于商用密码领域，这可由ECC被许多著名的国际标准组织所采纳佐证，如ANSI、IEEE、ISO、NIST。此外，基于离散对数的公钥系统还有Massey－Omura公钥系统，EIGamal公钥系统等。

2.RSA加密系统

RSA因其创始人Ronald L Rivest、Adi Shamir和Leonard M Adleman而得名。RSA的难度是基于因式分解，RSA的安全性建立在几乎所有重要数学家构造的假设的基础之上，它至今仍是一条数学家相信存在但缺乏正式证明的未证定理。

RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题，还可利用RSA来完成对电文的数字签名以对抗电文的否认与抵赖，同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。

RSA是第一个比较完善的公开密钥算法，它既能用于加密也能用于数字签名。在已公开的公钥算法中，RSA是最容易理解和实现的。

（1）RSA算法的描述

RSA算法的实现步骤如下：（B为实现者）

①B寻找出两个大素数p和q。

②B计算出n＝pq和f（n）＝（p－1）（q－1）。

③B选择一个随机数e（0＜e＜j（n）），满足（e，f（n））＝1。

④B使用欧几里德扩展算法计算d＝e^－1（mod f（n））。

⑤B在目录中公开n和e作为他的公开钥，保密p、q和d。

密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n＝pq，则可以算出f（n）＝（p－1）（q－1），然后由公开的e解出秘密的d。

加密时，对每一明文分组如下计算：c_i＝m_i^e（mod n）；

解密时，取每一密文分组c并计算：m_i＝c_i^e（mod n）。

RSA算法主要用于数据加密和数字签名。RSA算法用于数字签名时，将公钥和私钥的角色变换即可。即将消息用d加密签名，用e验证签名。

（2）RSA算法实例

若B选择了p＝101和q＝113，那么，n＝11 413，f（n）＝100×112＝11 200；再用辗转相除法（Euclidean算法）来求得e，使（e，f（n）＝1）。假设B选择了e＝3 533，那么用辗转相除法将求得d＝e^－1（mod 11 200），于是B的解密密钥d＝6 597。

B在一个目录中公开n＝11 413和e＝3 533，现假设A想发送明文9 726给B，他计算：9 726^{3 533}（mod 11 413）＝5 761，且在一个信道上发送密文5 761。当B接收到密文5 761时，他用他的秘密解密指数（私钥）d＝6 597进行解密：

5 761^{6 597}（mod 11 413）＝9 726。

（3）关于RSA的讨论

RSA的基础是数论的欧拉定理，它的安全性依赖于大数的因数。RSA的发明者Rivest、Shamir和Adleman建议取p和q为100位以上的十进制数，这样，n为200位的十进制数。按每秒10⁹次运算的高速计算机也要计算106年。估计对200位十进制数的因数分解，在上亿次的计算机上要进行55万年。

三种可能攻击RSA算法的方法是：①强行攻击。这包含对所有的私有密钥都进行尝试。②数学攻击。有几种方法，实际上都等效于对两个素数乘积的因子分解。③定时攻击。这依赖于解密算法的运行时间。

对RSA强行攻击的防范方式与其他秘密系统采用的方法相同，即采用一个大的密钥，因而e和d的比特数越多越好。然而因为在密钥产生和加密解密中包含的计算很复杂，密钥越大则系统运行越慢。

基于安全性考虑，一般在应用RSA时，必须做到以下几点：①绝对不要对陌生人提交的随机消息进行签名。②不要在一组用户间共享n。③加密之前要用随机值填充消息，以确保m和n的大小一样。④目前，129位十进制数字的模数是能够分解的临界数，因此，n应该大于这个数。

RSA技术既可用于加密通信又能用于数字签名和认证。由于RSA的速度大大逊于DES等分组算法，因此RSA多用于加密会话密钥、数字签名和认证中。RSA以其算法的简单性和高度的抗攻击性在实际通信中得到了广泛的应用。在许多操作平台（如Windows、Sun、Novell等）都应用了RSA算法。另外，几乎所有的网络安全通信协议（如SSL，IPSec等）也都应用了RSA算法。ISO几乎已指定RSA用作数字签名标准。在ISO9796中，RSA已成为其信息附件。法国银行界和澳大利亚银行界已使RSA标准化，ANSI银行标准的草案也利用了RSA。许多公司都采用了RSA安全公司的PKCS。RSA在目前和可预见的未来若干年内，在信息安全领域的地位是不可替代的，在没有良好的分解大数因子的方法以及不能证明RSA的不安全性的时候，RSA的应用领域会越来越广泛的。但是一旦分解大数因子不再困难，那么，RSA的时代也会成为历史。

3.EIGamal加密系统

EIGamal的安全性依赖于计算有限域上离散对数这一难题。

（1）密钥对产生方法

密钥对产生办法如下：

①选择一个素数p，两个随机数g和x，要求g，x＜p。

②计算y＝g^x（mod p），则其公钥为y、g和p；私钥是x。g和p可由一组用户共享。

（2）EIGamal用于加密

假定被加密信息为M，首先选择一个随机数k，k与p－1互质，计算

a＝g^k（mod p），b＝y^kM（mod p）

（a，b）为密文，是明文的两倍长。解密时计算

M＝b/a^x（mod p）

（3）EIGamal用于数字签名

EIGamal主要用于数字签名。假定被签信息为M，首先选择一个随机数k，k与p－1互质，计算a＝g^k（mod p），再用扩展Euclidean算法对下面方程求解b：M＝xa＋kb（mod（p－1））签名就是（a，b）。随机数k须丢弃。验证时要验证下式：y^aa^b（mod p）＝g^M（mod p）同时一定要检验是否满足1≤a＜p，否则签名容易伪造。

EIGamal签名的安全性依赖于乘法群（IFp）^＊上的离散对数计算。素数p必须足够大，且p－1至少包含一个大素数因子以抵抗Pohlig ＆Hellman算法的攻击。M一般都应采用信息的Hash值（如SHA算法）。EIGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证e对于p－1的大素数因子不可约。D.Bleichenbache在“Generating EIGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。EIGamal的一个不足之处是它的密文成倍扩张。

美国的DSS（Digital Signature Standard）的DSA（Digital Signature Algorithm）算法是经EIGamal算法演变而来的。

4.椭圆曲线密码体制

椭圆曲线第一次运用于公钥密码算法是在1985年Neal Koblitz和V S Miller提出来的。椭圆曲线数字签名算法ECDSA由IEEE工作组和ANSI（American National Standards Institute）X9组织开发。随即学者们展开了椭圆曲线密码学研究，除椭圆曲线外，还有人提出在其他类型的曲线如超椭圆曲线上实现公钥密码算法。其根据是有限域上的椭圆曲线上的点群中的离散对数问题ECDLP。ECDLP是比因子分解问题更难的问题，许多密码专家认为它有指数级的难度。从目前已知的最好求解算法来看，160比特的椭圆曲线密码算法的安全性相当于1024比特的RSA算法。

此后，有人在椭圆曲线上实现了类似EIGamal的加密算法及可恢复明文的数字签名方案。除有限域上的椭圆曲线密码算法外，人们还探索了在椭圆曲线上实现RSA算法，如KMOV等。