第四节 关于非对称加密算法
不对称加密算法要用到两个密钥，一个是公共的，一个是私人的。一个密钥负责加密（编码），另一个负责解密（译码）。在仅知公共密钥的前提下，不可能推导出私人密钥是什么，根据前面的定义，我们认为公共密钥算法是“计算安全”的，好的非对称密钥算法是建立在单向函数基础上的。
一般认为非对称密钥加密算法是由Whitfield Diffie和Martin Hellman发明的。详情可见其论文“加密新思路（New Directions in Cryptography）”，由IEEE的“信息理论学报”于1976年出版。近年来，英国政府的“通信电子安全协会（CESG）”公开了一些文件，显示出其密码专家实际提出这一概念是1970年，James Ellis草拟了一份CESG内部报告，以“保证不安全的数字加密的安全可能”为标题，其中讨论了一种可行的理论。后来，Clifford Cocks和Malcolm Williamson分别撰写论文，对实际的方案进行了描述，其内容已基本接近后来的RSA以及Diffie-Hellman方案。但无论如何，Diffie-Hellman论文的出版是一个异常重要的事件，相比推迟了20多年才公开的英国政府文件，它要重要得多。
一、RSA算法
目前最流行的非对称密钥算法是RSA，名称来源于它的发明者：Ron Rivest、Adi Shamir以及Leonard Adleman。RSA之所以能够保密，关键在于大质数的乘积因子的分解困难。RSA的重要特点是其中一个密钥可用来加密数据，另一个密钥可用来解密。这意味着任何人都能用密钥持有者的公共密钥对一条消息进行加密，而只有密钥持有者才能对它进行解密。另外，密钥持有者也可用自己的私有密钥对任何东西进行加密，而拿到密钥持有者的公共密钥的任何人都能对其解密。这样做的实际意义在不可否认及数字签名中非常重要。
RSA算法运用了数论中的Euler同余定理，即a、r是两个互质的自然数，则az=1（mod r），其中z为与r互质的且不大于r的自然数，即z为r的Euler指标函数（数论中记为（r Φ））。RSA的工作原理如下。
寻找两个大素数：p、q（保密）。
计算它们的积：
r = p*q(公开)
计算：
z =(p-1)*(q-1)(保密)
选取e，使得：
gcd(e, z)=1(公开)
计算d，使得：
e*d = 1(mod z)(保密), gcd(d, z)= 1
e和d分别被称为公开指数和秘密指数。（e, r）是公共密钥，（d, r）是私有密钥，因子p和q必须保密或被销毁。
实施RSA算法的基本步骤为设计密钥、设计密文、恢复明文。下面通过一个简单例子来说明。
例如，用户A需要将明文信息“HI”通过RSA加密传递给用户B，则其操作过程如下。
1．设计密钥（e, r）和（d, r）
令P=5, Q=11，取e=3；计算
r = P*Q = 5*11 = 55；
求
z =(P-1)*(Q-1)=(5-1)*(11-1)= 40；
由e*d = 1（mod z），即3*d = 1（mod 40），可得d = 27。
至此，得到公有密钥（e, r）为（3, 55），私有密钥（d, r）为（27, 55）。
2．设计密文
将明文信息数字化，并按每块两个数字进行分组。假定明文编码为空格=00, A=01……Z=26，则数字化后的明文信息为08,09。
用加密密钥（3, 55）将明文加密。由C=Me(mod r)得：
C1=M1e(mod r)=(08)3(mod 55)=17
C2=M2e(mod r)=(09)3(mod 55)=14
因此，得到的密文信息为17,14。
3．恢复明文
用户B收到密文后，对其进行解密处理：M=Cd(mod r)，即
M1=C1d(mod r)=1727(mod 55)=08
M2=C2d(mod r)=1427(mod 55)=09
用户B得到的明文信息为08,09。将其转化为源码即为“HI”。
据推测，很难由公共密钥（e, r）推导出私有密钥d，如果能够将r分解为p和q，那么就能得到私有密钥d。因此整个RSA的安全性建立在大数分解很难这一假设基础之上。
RSA算法的安全性完全取决于两个大质数。因此一般这两个大质数超过100位（十进制）。为确认某数n是否为质数，最简单的方法是用所有小于sqrt(n)的数去整除，然而这种方法基本是不可行的。因此，在实际使用中，可考虑使用费马定理：
mP-1=1(mod P)
其中，P为质数。取大数n（100位以上的整数）和整数a＜n，计算an-1(mod n)。若结果不为1，则n必定不是质数（费马定理的逆否命题）；若结果为1，则n不为质数的概率约为10-13。这对于许多应用来说，其风险已经足够小了，然而相应的计算量就大大减小了。如果n不是质数，则意味着存在比e、d更小的等价密码对，从而降低了算法的安全强度。
通过对RSA的研究发现，选择固定并较小的加密密钥（一般用于公有密钥）并不降低整个系统的安全性，但却明显提高了加密运算的处理速度，如取65537作为公有密钥，私有密钥则可通过Euclid算法得到。
RSA的一个缺点是速度较慢，而且能处理的数据最多只能有它的密钥的模数大小。例如，一个1024位的RSA公共密钥只能对少于或等于那个长度的数据进行加密（实际最多只能有1013位，因为用RSA定义如何加密时，还要进行编码，这又要用去11位的长度）。RSA算法的处理速度并不适合进行大批量的数据加密，而非常适用于密钥交换和数字签名这样的重要技术。
二、El-Gamal算法
另一种非对称密钥加密系统是El-Gamal，名称也是由其发明者得来的。El-Gamal加密系统建立在“离散对数问题”的基础上，其基础是Diffie-Hellman密钥交换算法，使通信双方能通过公开通信推导出只有他们知道的私有密钥值。它的主要缺点是密文长度达到了明文的两倍，对于已经非常饱和的网络来说，这无疑是一个致命缺点，并且算法在应对中间人攻击时表现明显比RSA脆弱。
其他的常见公共密钥加密算法还有背包算法、Rabin和ECC（Elliptic Curve Cryptography，椭圆曲线加密算法）等，限于篇幅与理论知识的要求，这里不作介绍，需要了解请参阅有关资料。