揭秘公钥加密算法 RSA

了解RSA之前，想必大家都听说过对称加密算法，也就是说信息的收发方会通过实现商订好的密钥，对数据进行加密和解密；

1、对称加密

然而这种加密方式有诸多缺陷，随着网络规模的不断增大，每多一个用户就需要保存许多额外的密钥，密钥的管理也将逐渐成为所有人的负担，更加致命的是，密钥必须通过见面协商，而没有办法直接通过网络进行交换，因为密钥的传输过程需要进行加密，而没有密钥则不能进行加密。

那有没有一种可能性，我们用不同的密钥对数据进行加密和解密，其中对数据加密的密钥是对所有人公开的，而对数据接秘密的密钥却仅为接收者持有呢？

在公钥加密算法中，由于公钥是对所有人公开的信息，我们需要保证数据被“公钥”加密之后，不能够被轻易地反推出来，那什么样的算法单向计算容易，而逆向反推却非常难呢？

2、模运算(Modular arithmetic)

又叫做求余运算，像计算机中的伪随机数、散列算法(hash)都是他的经典应用，试想一下下面这个例子：

用我们小学二年级学过的知识，3的3次方得到27，并对7取余数得到 6，但已知答案是6的情况下，我们应当如何寻找 x的值呢？

由于求余算法并不可逆，我们只能一个一个数的带进去试；

但如果出现下面这个很大很大的数，再去一一尝试就很不现实了。

这也就是为什么模运算被称作 单向函数，因为对于大数来说，对模运算求逆根本上不现实的，而公钥加密正是利用了模运算的这个特性。假设我们将原始数据表示成一个数 m(message)，然后我们对$m^e$求e次幂，这里的e(encrypt)可以看作是我们加密时用的密钥，然后我们将结果除以N并取余数，最后得到密文 c(cipher)

并且根据我们之前讲到的，正向计算出这里的密文c 很简单，但反向推出这里的原始数据却很难;

我们需要对密文c 求 d次幂，这里的d（decrypt）代表另一个用于解密的密钥，最后得到的结果是原始数据m，为了更好的理解，讲两个公式合并为一个更为简洁的形式：

m的e*d次幂，除以N取余数，将会得到原始数据m，可以发现，如何选取这里的e和d是公钥加密的关键，`欧拉定理(Euler’s Theorem）`公式：

欧拉定理表示，对于任何一个与n互斥的正整数m，取它的 φ^n ，并除以n取余数，结果都永远等于1，这里的 φ^n 是欧拉函数，它代表在小于或等于n的正整数中，有多少个与n互斥的数，举个例子：

φ^6 在小于等于6的正整数中，只有1和5互为`质数`，也就是说，他们除了1以外，并不存在其他`公约数`，所以 φ^n = 2。

在了解了 φ^n 函数之后，回到欧拉定理，又双叒叕开始变换公式了；

在等式两端同时去k次幂，k代表任意的正整数，接着在两端同时乘以m，

并简化成这样的形式：

接着将模运算移动到等式的左边

是不是有点眼熟？对了把它和上面的这个公式对比一下:

你会发现，公式的指数 kφ(n)+1 = ed，变换一下得到：

也就是说，我们选取这里的 k,n,e 来计算出解密的密钥d。实际上，要计算kφ(n)的唯一办法就是对数n做`质因数分解`，比如 27 = 3 * 3 * 3、11445 = 3 * 5 * 7 * 109 这样，然而对大数的分解是很困难的事情，所以对kφ(n)的求解，可以看作是计算上不可行的，但是如果n本身是一个质数，情况就有所不同了，比如对于kφ(7)来说，小于等于7并与7互质的数有1-6，除了7本身，因此 kφ(7)=6；同理对于kφ(13)来说，与13互质的数，除了13本身，其他的全部都是，因此kφ(13)= 12。

其实对于任何的 kφ(p) = p-1 ，除此之外，φ还有一个重要的特性，对于任意两个互质的整数 p 和 q ，φ(p) = p -1 可以拆分为 φ(p*q) = φ(p) * φ(q) ，例如我们可以选取两个质数17和23，由于 φ(17*23) = φ(17) * φ(23) = 16*32 = 352，因此可得：

φ(17*23) = φ(391) = 352 ，带入 d = (kφ(n)+1)/e 再得：

于是在`k=5`的情况下，求得用于解密的密钥`d=587`，在求出了私钥 d 以后，算法会将 e、n 公布，作为加密时的公钥，而`d`将保存下来作为解密时用的私钥，其他人由于不知道p和q这两个关键的质因数，没有办法计算出这里的 φ^n ，因而无从破解这里的私钥 `d`，公钥加密正是利用了这个信息的不对等，让加密者能够快速够着出一个 φ^n ，而其他人却无法在有限的时间内求解它。

3、举个例子

用e = 3，d = 587，n = 391 来模拟一段信息加密解密的过程，我们要加密的字符是“a”，它所对应的ascii码是97，于是 97^3 mod 391 = 79 ，79是我们加密后的密文，为了解密 79^587 mod 391 = 97 ，因此成功还原了字符“a”。

以上讲到的就是公钥加密算法的全部工作原理，这个算法在首次被发现之后，并被机密作为封了起来，后来又在1977年被三个麻省理工的数学家 Ron `R`ivest 、Adi `S`hamir 、 Leonard `A`dleman 独立发掘，成为当下众所周知的 RSA 加密算法，像数字签名，数字证书，SSH、HTTPS的加密连接，全部都是它的典型应用。

在实际使用中，由于公钥加密的计算量比较大，速度慢，通常会和对称加密算法一同使用，公钥加密算法常被用作最初连接的建立，而真正数据传输的过程，会交由对称加密算法来处理，完结！