3.3 非对称密钥加密算法详解

非对称加密算法是一种密钥的保密方法，它使用了两个具有数学关系的不同密钥来加密和解密数据，这两个密钥分别称为私钥和公钥，合称为密钥对。在现在实际应用中，由于非对称加密使用的算法比对称加密更复杂，并且还使用了密钥对，因此在使用非对称加密时，在加密速度上就比不上对称加密算法了。

3.3.1 非对称密钥算法

非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其他方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

另外，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私钥对数据进行验签。

甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。

非对称密码体制的特点是：算法强度复杂、安全性依赖于算法与密钥，但是由于其算法复杂，而使得加密解密，速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密，就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。

非对称密钥算法不太适用于加密大量数据，常用于将对称密钥和初始化向量加密并传输给对方，再在双方之间来回发送的消息中，使用对称算法加密和解密数据。非对称算法主要有RSA、DSA等，主要用于网络数据的加密。

非对称加密算法的保密性比较好，它不像对称加密那样，每次都需要安全通道才能交换密钥，但加密和解密速度很慢，而且同样的密钥长度安全性更低一些。使用它对于大型文件加密就显得很不合适，而只适用于对少量数据进行加密。

另外，非对称加密也同样面临着公钥的交换问题，也同样需要安全通道才能彼此交换公钥，只是适当运用的话只需要交换一次就可以。非对称加密技术一般不单独使用，往往作为辅助对称加密技术的一种手段，可以用来传递对称加密的密钥。

3.3.2 RSA公钥加密算法

所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。

正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥长至少为500位，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的30多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

SET（Secure Electronic Transaction）协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。RSA密钥长度随着保密级别提高，增加很快。

这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir和Leonard Adleman。早在1973年，英国国家通信总局的数学家Clifford Cocks就发现了类似的算法。但是他的发现被列为绝密，直到1998年才公之于世。

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。

RSA的算法涉及3个参数：N、e、d。

1．产生所需密钥

① 选取两个素数p、q。

② 计算N=p＊q。

③ 随机选取加密密钥e，并使其满足1<e<ϕ（n）, GCD（e, ϕ（n））=1，那么公钥就是（e, n）。

④ 计算解密密钥d，需要满足条件e＊d=1（modϕ（n））。

自己保存好私钥（d, n）和公开公钥，其中ϕ是Euler函数：ϕ（n）=（p-1）（q-1）。

2．加密过程

在要加密明文M之前，需要先得到公钥e和N，并进行一次计算，以获得密文C，具体可表示为C=Memod N。

3．解密过程

收到密文C后，用自己的密钥d去解密出明文M，具体可表示为M=Cdmod N

RSA系统执行数字签名的运算正好与加密过程是互逆的。

RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。

RSA的缺点如下。

① 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

② 安全性，RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NP问题。现今，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息做一下伪装（Blind），让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：

(XM)d = Xd ＊Md mod n

前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征——每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或ϕ（n）等攻击。

③速度太慢，由于RSA的分组长度太大，为保证安全性，n至少也要在600比特以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。SET协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。为了速度问题，人们广泛使用单钥，公钥密码结合使用的方法，优缺点互补，单钥密码加密速度快，人们用它来加密较长的文件，然后用RSA来给文件密钥加密，极好地解决了单钥密码的密钥分发问题。

RSA算法的优点是密钥空间大，如果RSA加密算法和DES加密算法结合使用，则正好弥补RSA的缺点。即DES用于明文加密，RSA用于DES密钥的加密。由于DES加密速度快，适合加密较长的报文，而RSA可解决DES密钥分配的问题。

伴随网络技术的发展，电子商务的广泛开展，电子邮件也被普遍采用，数字签名技术也就显得越来越重要。RSA算法虽然有点复杂，速度慢，但目前还是被广泛地应用于数字签名中。随着对RSA的深入研究，目前RSA正在走向实用化、商业化的道路，可以看到，在网络安全中基于RSA网络安全系统的设计将会被人们广泛接受。

3.3.3 ElGamal公钥算法

ElGamal算法是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系，既能用于数据加密，也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K，在密码中主要应用离散对数问题的几个性质：求解离散对数（可能）是困难的，而其逆运算指数运算可以应用平方—乘的方法有效地计算。也就是说，在适当的群G中，指数函数是单向函数。

密钥对产生办法：首先选择一个素数p，获取一个素数p的一个原根g（若g模p的阶等于ϕ（p），则称g为模p的一个原根。（其中ϕ（p）表示p的欧拉函数，即所有<=p的正整数中和p互质的整数的个数）和一个随机数x，且g和 x 均小于 p，计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。

ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p-1互质，计算

a=g^k(modp)

再用扩展Euclidean算法对下面方程求解b：

M=xa+kb(mod p-1)

签名就是( a, b )。随机数k须丢弃。

验证时要验证下式：

y^a＊a^b(modp)=g^M(modp)

同时一定要检验是否满足1<= a < p。否则签名容易伪造。

ElGamal用于加密。被加密信息为M，首先选择一个随机数k, k与 p-1互质，计算

a = g^k ( mod p )

b = y^k M ( mod p )

( a, b )为密文，是明文的两倍长。解密时计算：

M = b / a^x ( mod p )

ElGamal签名的安全性依赖于乘法群(IFp)＊上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数，因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值（如SHA算法）。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。

ElGamal数字签名方案：在系统中有两个用户A和B, A要发送消息到B，并对发送的消息进行签名。B收到A发送的消息和签名后进行验证。

1．系统初始化

选取一个大的素数p, g是GF(p)的本原元。h:GF(p)→GF(p)，是一个单向Hash函数。系统将参数p、g和h存放于公用的文件中，在系统中的每一个用户都可以从公开的文件中获得上述参数。

2．对发送的消息进行数字签名的过程

假定用户A要向B发送消息m [1, p-1]，并对消息m签字。第一步是用户A选取一个x [1, p-1]作为秘密密钥，计算y= (modp)作为公钥。将公钥y存放于公用的文件中。第二步是随机选取k [1, p-1]且gcd(k, ( p-1))=1，计算r= (mod p)。对一般的ElGamal型数字签名方案有签名方程（Signature Equation）:ax=bk+c(mod(p-1))。

其中（a, b, c）是（h(m), r, s）数学组合的一个置换。由签名方程可以解出s。那么(m, (r, s))就是A对消息m的数字签名。第三步是A将（m, (r, s)）发送到B。

3．数字签名的验证过程

当B接收到A发送的消息（m, (r, s)），再从系统公开文件和A的公开文件中获得系统公用参数p, g, h和A的公钥y。由（m, (r, s)）计算出（a, b, c）验证等式： = (mod p)是否成立。

D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。

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

3.3.4 Diffi e-Hellman密钥交换系统

Diffie-Hellman是一种确保共享KEY安全穿越不安全网络的方法，它是OAKLEY的一个组成部分。Whitefield与Martin Hellman在1976年提出了一个奇妙的密钥交换协议，称为Diffie-Hellman密钥交换协议/算法（Diffie-Hellman Key Exchange/Agreement Algorithm）。这个机制的巧妙在于需要安全通信的双方可以用这个方法确定对称密钥，然后可以用这个密钥进行加密和解密。但是注意，这个密钥交换协议/算法只能用于密钥的交换，而不能进行消息的加密和解密。双方确定要用的密钥后，要使用其他对称密钥操作加密算法实际加密和解密消息。

由于该算法本身限于密钥交换的用途，被许多商用产品用作密钥交换技术，因此该算法通常称为Diffie-Hellman密钥交换（简写为DH算法，基于DH算法的密钥交换通常也称为DH交换）。这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密。Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。简言之，可以如下定义离散对数：首先定义一个素数p的原根，为其各次幂产生从1到p-1的所有整数根，也就是说，如果a是素数p的一个原根，那么数值 a mod p, a2 mod p, ..., a（p-1）mod p是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数。对于一个整数b和素数p的一个原根a，可以找到唯一的指数i，使得 b = a^i mod p，其中0 ≤ i ≤（p-1），指数i称为b的以a为基数的模p的离散对数或者指数，该值被记为inda, p(b)。

基于原根的定义及性质，可以定义Diffie-Hellman密钥交换算法，该算法描述如下。

① 有两个全局公开的参数，一个素数q和一个整数a, a是q的一个原根。

② 假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XA(XA<q)，并计算公开密钥YA=a^XA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地，用户B选择一个私有的随机数XB<q，并计算公开密钥YB=a^XB mod q。B对XB的值保密存放而使YB能被A公开获得。

③ 用户A产生共享秘密密钥的计算方式是K = (YB)^XA mod q。同样，用户B产生共享秘密密钥的计算是K = (YA)^XB mod q。这两个计算产生相同的结果。K = (YB)^XA mod q =(a^XB mod q)^XA mod q = (a^XB)^XA mod q（根据取模运算规则得到）= a^(XBXA) mod q =(a^XA)^XB mod q = (a^XA mod q)^XB mod q = (YA)^XB mod q，因此相当于双方已经交换了一个相同的秘密密钥。

④ 因为XA和XB是保密的，一个敌对方可以利用的参数只有q, a, YA和YB。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户B的秘密密钥，敌对方必须先计算XB =inda, q(YB)，然后再使用用户B采用的同样方法计算其秘密密钥K。Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。下面给出例子。密钥交换基于素数q = 97和97的一个原根a = 5。A和B分别选择私有密钥XA = 36和XB = 58。每人计算其公开密钥YA = 5^36 = 50 mod 97 YB = 5^58 = 44 mod 97。在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下：K = (YB)^XA mod 97 = 44^36 = 75 mod 97, K = (YA)^XB mod 97 = 50^58 = 75 mod 97，从|50,44|出发，攻击者要计算出75很不容易。下面给出了一个利用Diffie-Hellman计算的简单协议。

假设用户A希望与用户B建立一个连接，并用一个共享的秘密密钥加密在该连接上传输的报文。用户A产生一个一次性的私有密钥XA，计算出公开密钥YA并将其发送给用户B。用户B产生一个私有密钥XB，计算出公开密钥YB并将它发送给用户A作为响应。必要的公开数值q和a都需要提前知道。另一种方法是用户A选择q和a的值，并将这些数值包含在第一个报文中。下面再举一个使用Diffie-Hellman算法的例子。假设有一组用户（例如一个局域网上的所有用户），每个人都产生一个长期的私有密钥XA，并计算一个公开密钥YA。这些公开密钥数值，连同全局公开数值q和a都存储在某个中央目录中。在任何时刻，用户B都可以访问用户A的公开数值，计算一个秘密密钥，并使用这个密钥发送一个加密报文给A。如果中央目录是可信任的，那么这种形式的通信就提供了保密性和一定程度的鉴别功能。因为只有A和B可以确定这个密钥，其他用户都无法解读报文（保密性）。接收方A知道只有用户B才能使用此密钥生成这个报文（鉴别）。Diffie-Hellman算法具有两个吸引力的特征：仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。除对全局参数的约定外，密钥交换不需要事先存在的基础结构。

然而，该技术也存在许多不足：没有提供双方身份的任何信息。它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥。受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作，没办法防止重演攻击，容易遭受中间人的攻击，第三方C在和A通信时扮演B；和B通信时扮演A。A和B都与C协商了一个密钥，然后C就可以监听和传递通信量。中间人的攻击按如下进行：B在给A的报文中发送他的公开密钥，C截获并解析该报文，C将B的公开密钥保存下来并给A发送报文，该报文具有B的用户ID但使用C的公开密钥YC，仍按照好像是来自B的样子被发送出去。A收到C的报文后，将YC和B的用户ID存储在一块。类似地，C使用YC向B发送好像来自A的报文。B基于私有密钥XB和YC计算秘密密钥K1。A基于私有密钥XA和YC计算秘密密钥K2。C使用私有密钥XC和YB计算K1，并使用XC和YA计算K2。从现在开始，C就可以转发A发给B的报文或转发B发给A的报文，在途中根据需要修改它们的密文，使得A和B都不知道他们在和C共享通信。

3.3.5 DSA数字签名算法

数字签名是保证电子商务安全性的关键技术之一，在保证数据的完整性、私有性、不可抵赖性等方面起着极其重要的作用。本节探讨了基于DSA（Digital Signature Algorithm）的数字签名技术，包括DSA的产生与验证过程及算法的应用、改进与发展。

算法中应用了下述参数。

p:Lbits长的素数。L是64的倍数，范围是512～1024。

q:p-1的160bits的素因子。

g:g=h^((p-1)/q)modp, h满足h<p-1, h^((p-1)/q)modp>1。

x:x < q, x为私钥。

y:y=g^xmodp, (p, q, g, y)为公钥。

H( x ):One-Way Hash函数。DSS中选用SHA（Secure Hash Algorithm）。

p, q, g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名及验证协议如下。

（1）P产生随机数k, k<q。

（2）P计算 r = ( g^k mod p ) mod q。

s=(k^(-1)(H(m)+xr))mod q。

签名结果是( m, r, s )。

（3）验证时计算 w = s^(-1)mod q。

u1=(H(m)＊w)modq。

u2=(r＊w)modq。

v=((g^u1＊y^u2)modp)modq。

若v = r，则认为签名有效。

DSA是基于整数有限域离散对数难题，所以它的安全性与RSA差不多。DSA的一个重要特点就是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，也能确认它们是否是随机产生的，但使用RSA算法就做不到这一点。