现在的位置: 首页 > 综合 > 正文

非对称加密（2）非对称加密算法

2013年05月09日 ⁄ 综合 ⁄ 共 4354字 ⁄ 字号小中大 ⁄ 评论关闭

非对称加密（2）非对称加密算法

基本流程很简单，那么公钥加密，私钥解密的算法原理到底是什么呢？本节简要阐述RSA算法、DSA算法、ECC算法、Diffie-Hellman算法的基本原理，其中涉及很多数论、离散数学以及解析几何方面的数学知识，感兴趣的读者可以借此加强相关理论基础。

RSA算法

RSA算法是当前最著名、应用最广泛的公钥系统，1978年由美国麻省理工学院的Ron Rivest、 Adi Shamir 和Leonard Adleman在论文《获得数字签名和公开钥密码系统的方法》中提出的。这是一个基于数论的非对称（公开钥）密码体制，采用分组加密方式。其名称来自于三个发明者的姓名首字母。它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。

RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，一个是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接收。为提高保密强度，RSA密钥一般为1024或者2048位。

RSA算法的工作原理如下：

步骤 1 任意选取两个不同的大质数p和q，计算乘积r=p*q。

步骤 2 任意选取一个大整数e，e与（p-1）*（q-1）互质，整数e用做加密密钥。注意：e的选取是很容易的，所有大于p和q的质数都可用。

步骤 3 确定解密密钥d： d * e = 1 mod（p - 1）*（q - 1）根据e、p和q可以容易地计算出d。

步骤 4 公开整数r和e，但是不公开d。

步骤 5 将明文P（P是一个小于r的整数）加密为密文C，计算方法为C = P^e mod r 。

步骤 6 将密文C解密为明文P，计算方法为： P = C^d modulo r 。

然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

如果你对RSA算法的数学证明感兴趣的话，可以看扩展阅读。

扩展阅读 RSA算法的数学证明

定理若 p, q 是相异质数, rm == 1 mod （p-1）（q-1）； a 是任意一个正整数，b == a^m mod pq, c == b^r mod pq, 则 c == a mod pq 。

费马小定理 m 是任一质数, n 是任一整数, 则 n^m = = n mod m 。（或者如果 n 和 m 互质, 则 n^（m-1） = = 1 mod m）。
证明
因为 rm = = 1 mod （p-1）（q-1）, 所以 rm = k（p-1）（q-1） + 1, 其中 k 是整数。
因为在 modulo 中是 preserve 乘法的

x = = y mod z and u =
= v mod z => xu = = yv mod z

所以

c = = b^r =
= （a^m）^r = = a^（rm） = = a^（k（p-1）（q-1）+1） mod pq
1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时, 则

a^（p-1） = = 1 mod p （费马小定理）  =>  a^（k（p-1）（q-1）） = = 1 mod p
       a^（q-1） = = 1 mod q （费马小定理）  =>  a^（k（p-1）（q-1）） = = 1 mod q
   所以 p, q 均能整除

a^（k（p-1）（q-1）） - 1 => pq | a^（k（p-1）（q-1）） - 1
即

a^（k（p-1）（q-1）） == 1 mod pq => c =
= a^（k（p-1）（q-1）+1） = = a mod pq
2. 如果 a 是 p 的倍数, 但不是 q 的倍数时, 则

a^（q-1） == 1 mod q （费马小定理）
   =>  a^（k（p-1）（q-1）） = = 1 mod q
   =>  c = = a^（k（p-1）（q-1）+1） = = a mod q
   =>  q | c - a
   因 p | a
   =>  c = = a^（k（p-1）（q-1）+1） = = 0 mod p
   =>  p | c - a
   所以

pq | c - a => c =
= a mod pq
3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上。
4. 如果 a 同时是 p 和 q 的倍数时, 则

pq | a
=> c = = a^（k（p-1）（q-1）+1） == 0 mod pq
=> pq | c - a => c =
= a mod pq

在做编码解码时, 限制 0 <= a < n, 0 <= c < n, 这就是说 a = =c, 所以这个过程确实能做到编码解码的功能。

为了说明该算法的工作过程，下面给出一个简单例子。显然，这里只能取很小的数字，但是如上所述，为了保证安全，在实际应用上所用的数字要大得多。

例
选取p=3, q=5，则r=15，（p-1）*（q-1）=8。选取e=11（大于p和q的质数），通过d * 11 = 1 modulo 8，计算出d =3。

假定明文为整数13。则密文C为：

C = P^e mod r

= 1311 mod 15

= 1,792,160,394,037 mod 15

= 7

复原明文P为：

P = C^d mod r

= 73 mod 15

= 343 mod 15

= 13

因为e和d互逆，公开密钥加密方法也允许采用这样的方式对加密信息进行"签名"，以便接收方能确定签名不是伪造的。

RSA算法解决了大量网络用户密钥管理的难题，这是公钥密码系统相对于对称密码系统最突出的优点。但是它同时也存在一定的缺点：

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

2）安全性。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某信息伪装（Blind），让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：
（ XM ）d = Xd *Md mod n。前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征：每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或φ（n）等攻击。

3）速度慢。由于RSA 的分组长度太大，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET（Secure
Electronic Transaction）协议要求CA采用2048比特的密钥，其他实体使用1024比特的密钥。为了速度问题,目前人们广泛采取单、公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA给文件密钥加密，极好地解决了单钥密码的密钥分发问题。

DSA算法

DSA（Digital Signature
Algorithm，数字签名算法）是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS（DigitalSignature Standard，数字信号标准）。DSA算法是基于整数有限域离散对数难题的，其安全性与RSA相似。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，也能确认它们是否是随机产生的，还是作了手脚。RSA算法却做不到。

（1） DSA算法参数

p：L bits长的素数。L是64的倍数，范围是512到1024；

q：p - 1的160bits的素因子；

g：g = h^（（p-1）/q） mod p，h满足h < p - 1, h^（（p-1）/q） mod p > 1；

x：x < q，x为私钥；

y：y = g^x mod p ，（ p, q, g, y ）为公钥；

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

其中，p、 q、g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。

（2）签名及验证协议

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 ） mod q

u2 = （ r * w ） mod q

v = （（ g^u1 * y^u2 ） mod p ） mod q

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

（3）安全性

DSA主要依赖于整数有限域离散对数难题。素数 P 必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig &
Hellman算法的攻击。M一般都应采用信息的HASH值（官方推荐为SHA算法）。DSA的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。个人认为：DSA的安全性要次于ECC，与RSA不相上下。但是，在DSA算法的验证过程中， R和S 是以明文形式出现的，这点很容易被恶意攻击者利用。