2.2 公钥密码学
在密码学中，公开密钥密码学，简称公钥密码学，又称非对称密码学，是使用一对公钥和私钥的密码学，与只用一个秘密密钥的密码学相对应。
2.2.1 公钥加密算法原理与特点
公钥密码出现前，几乎所有的密码体制都是基于替换和置换这些初等方法。轮转机和DES是密码学发展的重要标志，但还是基于替换和置换。公钥密码学与其前的密码学完全不同。首先，公钥算法是基于数学函数而不是基于替换和置换，更重要的是公钥密码是非对称的，它使用两个独立的密钥。使用两个密钥在消息的保密性、密钥分配和认证领域有着重要的意义。
1.公钥加密算法的原理
用抽象的观点来看，公钥密码就是一种陷门单向函数（trapdoor one-way function）。在公钥密码中，加密密钥和解密密钥是不一样的，加密密钥为公钥，解密密钥为私钥。在公钥密码机制之中，破译已经加密后的密码应该是一个难解问题。一个问题是难解的，直观上讲，就是不存在一个计算该问题的有效算法，也可称之为按照目前的计算能力，无法在一个相对的短时间内完成，即解决这个问题所付出的成本远远超过了解决之后得到的结果。计算一个难解的问题所需要的时间一般是以输入数据长度的指数函数形式递增，所以随着输入数据的增多，复杂度会急剧增大。对于一个问题，如果存在一个求其解的有效算法，则称其为有效问题，否则为无效问题。
公钥密码的理论基础是陷门单向函数：设f是一个函数，如果对于任意给定的x，计算y=f(x)是容易的，但对于任意给定的y，计算f(x)=y是难解的，则称f是一个单向函数。
另外，设f是一个函数，t是与f有关的一个参数，对任意给定的x，计算y使得y=f(x)是容易的，如果当不知参数t时，计算f的逆函数是难解的，但当知道参数t时，计算f的逆函数是容易的，则称f是一个陷门单向函数，参数t称为陷门。
在公钥密钥中，加密变换是一个陷门单向函数，只有带陷门的人可以容易地进行解密变换，而不知道陷门的人则无法有效地进行解密变换。
2.公钥加密算法的特点
传统对称密码存在的主要问题有两个：一是密钥分配问题（加密之后，我怎么把密钥告诉你才是安全的？）；另一个是数字签名问题，否则会出现抵赖和伪造。公钥加密算法正好可以进行秘钥交换和数字签名。
通常对公钥密码有两种误解。
（1）公钥密码比传统密码更加安全。事实上，任何加密方法都依赖于密钥的长度和破译密文所需要的计算量，所以公钥密码并不比传统密码更加安全
（2）公钥密码是一种通用密码，传统密码已经过时了。其实正相反，由于现在公钥密码的计算量大，所以取消传统密码似乎不太可能，公钥密码的发明者也说“公钥密码学仅用在密钥管理和签名这类应用上”。
2.2.2 公钥加密算法举例
常见的公钥加密算法包括RSA、El Gamal、背包算法、Rabin（Rabin加密法是RSA方法的特例）、Diffie-Hellman（D-H）密钥交换协议中的公钥加密算法、Elliptic Curve Cryptography（ECC，椭圆曲线加密算法）等。
当前最著名、应用最广泛的公钥系统RSA是在1978年由美国麻省理工学院的Rivest、Shamir和Adleman提出的。RSA正是这三个人名的首字母。RSA是一个基于数论的非对称密码体制，是一种分组密码体制。RSA算法是第一个既能用于数据加密也能用于数字签名的算法。
RSA使用一个公钥和一个私钥。公钥加密，私钥解密，密钥长度从40到2048bit可变，加密时也把明文分成块，块的大小可变，但不能超过密钥的长度。RSA算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效果越好，但加密解密的开销也大，所以要在安全与性能之间折中考虑，一般64位是较合适的。RSA的一个比较知名的应用是SSL，在美国和加拿大SSL用128位RSA算法，由于出口限制，在其他地区（包括中国）通用的则是40位版本。
RSA的安全性基本大于大整数的因子分解，其基础是数论中的欧拉定理。因子分解可以破解RSA密码系统，但是目前尚无人证明RSA的解密一定需要分解因子。
RSA密钥生成过程如下。
（1）选择一对不同的、足够大的素数p，q。
（2）计算n=pq。
（3）计算f(n)=(p-1)(q-1)，同时对p，q严格保密，不让任何人知道。
（4）找一个与f(n)互质的数e，且1<e<f(n)。
（5）计算d，使得de≡1 mod f(n)。这个公式也可以表达为d≡e-1 mod f(n)。
（6）公钥PU=(e,n)，私钥PR=(d,n)。
（7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，则加密过程为：C=Me(mod n)。
（8）解密过程为：M=Cd(mod n)。
在RSA密码应用中，公钥PU是被公开的，即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值，求出d的数值，这样就可以得到私钥来破解密文。密码破解的实质问题是：只要求出p和q的值，就能求出d的值而得到私钥。
一个RSA算法加密解密的例子如下。
加密生成密文：
比如甲向乙发送汉字“中”，就要使用乙的公钥加密汉字“中”，以utf-8方式编码为[e4 b8 ad]，转为十进制为[228,184,173]。要想使用公钥(n,e)=(4757,101)加密，要求被加密的数字必须小于n，被加密的数字必须是整数，字符串可以取ascii值或unicode值，因此将“中”字拆为三个字节[228,184,173]，分别对三个字节加密。
假设a为明文，b为密文，则按下列公式计算出b
ae%n=b
计算[228,184,173]的密文：
228^101%4757=4296
184^101%4757=2458
173^101%4757=3263
即[228,184,173]加密后得到密文[4296,2458,3263]，如果没有私钥d，很难从[4296,2458, 3263]中恢复[228,184,173]。
解密生成密文：
乙收到密文[4296,2458,3263]，并用自己的私钥（n,d)=(4757,1601)解密。解密公式如下：
ad%n=b
密文[4296,2458,3263]的明文如下：
4296^1601%4757=228
2458^1601%4757=184
3263^1601%4757=173
即密文[4296,2458,3263]解密后得到[228,184,173]，将[228,184,173]再按utf-8解码为汉字“中”，至此解密完毕。