RSA加密算法

加密算法

  谈到加密算法，我们不得不谈一下密码学中加密算法的两个分支：对称加密和非对称加密。

对称加密算法（以单表替代密码为例）

  我们假设Felix要向你们之间的某位读者发送一段信息$m$m，为方便起见，我们假设这段信息是"THANKYOUFORFOLLOWINGME"。现在，为了使这段信息不被外人所知，需要对其加密。我们假设加密方式为：所有用后一位字母替代，那么上述的这段信息就被加密为：“UIBOLZPVGPSGPMMPXJOHNF”，这是不可读的。当读者接收到这段信息时，只需要将加密后的信息往前倒退一位，便可以得到原始信息。我们把原始信息称为明文，加密后的信息称为密文，加密方式（在上例中体现为字母的替代）称为加密算法，解密方式（在上例中体现为字母的替代）称为解密算法，加密时移动的位数1称为加密密钥，解密时移动的位数1称为解密密钥。

  上面这种加密方式一般被称为单表替代密码，上述的例子又是其中十分特殊的一种，称为凯撒密码。我们观察可以知道，加密密钥和解密密钥是相同的，我们把具有这种性质的加密算法称为对称加密算法。

  对称加密算法是有好处的：其计算量小，加密简单，用于加密和解密的密钥相同，算法只需要选取可逆映射即可。但对称加密也存在一些问题：双方在通信前需要互相商定密钥，并且在通信过程中，任何一方的密钥泄露都将使得所有通信被破解；其次，任何两者之间的通信都需要选取不同的密钥，这在通信网复杂的情况下，每个通信节点都需要储存数量庞大的密钥，给用户带来负担。

  当然，密钥泄露的问题不是不可解决的。我们可以在每一次通信都使用不同的密钥，这样，密文在理论上是牢不可破的。但是这又会带来问题，我们如何获得这么庞大数量的密钥呢？我们又如何储存呢？密钥的分发在这种情况下变成了棘手的问题。所以，一次一密的加密方式在实际应用中是不广泛的。

非对称加密

  随即而来进入我们脑海的一种加密方式就是非对称加密，即加密密钥和解密密钥不相同的加密方式。我们一般称前者为公钥，后者为私钥，因为前者是公开给所有人的，后者是密文接收方自己保存的。我们知道，由于加密和解密是逆运算，我们是有可能通过暴力破解求出加密方式的逆运算的。所以，为了保证安全性，非对称加密的算法一般都十分复杂，运算量相比于对称加密算法繁琐得多，因此，非对称加密牺牲了加密效率，换来了更高的安全性。下面我们来讨论一下非对称加密中的典型加密方式，即RSA加密。

RSA加密算法

基于的数学运算原理——模运算

  首先我们来思考一个问题，有什么方式使得攻击者知道加密方式的情况下很难求算出其逆运算？有一种运算符合类似的性质：其正向运算十分简单，但逆运算极其复杂，它是模运算（Mod）。模运算就是我们一般说的求余。其正向运算是很简单的，例如

$3^3\text{ mod }7=6,$33 mod 7=6,

完成这个运算只需要一个简单的除法即可，但是设想，如果给出的形式是方程，即

$3^x\text{ mod }7=6,$3x mod 7=6,

求解满足上述方程的x的值，其运算是比较复杂的，因为我们不知道其商的值，也就不能快速利用乘法求算$x$x，一般我们会使用枚举法求算其解。但是如果方程是

$3^x\text{ mod }7156464845153468615315646=6,$3x mod 7156464845153468615315646=6,

这时候，枚举法也变得十分困难了，这个方程已经是计算上不可解的了。因此，模运算也被称为单向运算。RSA就是利用了模运算的这点性质。

加密算法和解密算法确定

  知道了我们要使用模运算作为加密和解密算法，那么我们不妨假设明文信息是$m$m（message），密文信息是$c$c（cipher），公钥为$e$e，私钥为$d$d，于是我们可以得到

$\{\begin{array}{c}{m}^e\text{ mod }N=c,\\ c^d\text{ mod }N=m.\end{array}${me mod N=c,cd mod N=m.​

消去密文$c$c，上式可化为

$(m^e\text{ mod }N{)}^d\text{ mod }N=m,$(me mod N)d mod N=m,

可以证明上式等价于

$m^{ed}\text{ mod }N=m.$med mod N=m.

这个结论先放在这里，我们后续会使用到它。

欧拉函数和欧拉定理

  为了充分理解RSA密码的数学原理，我们需要先提到欧拉函数和欧拉定理。

欧拉函数

  首先介绍一下欧拉函数：假设给定一个正整数$n$n，欧拉函数$\phi \left(n\right)$φ(n)的值是不超过$n$n的与其互质的正整数的数目，例如不超过6的与6互质的正整数有1和5，那么我们就说，$\phi \left(6\right)=2$φ(6)=2。一般求解欧拉函数的值时，我们经常采用素因数分解的方式，让我们来看一个例子：求解$\phi \left(100\right)$φ(100)的值。我们对其质因数分解，得到

$100=2^2\cdot 5^2\text{。}$100=22⋅52。

那么其与其互质的整数数量为

$\phi \left(100\right)=100\times (1-\frac{1}{2})\times (1-\frac{1}{5})=40.$φ(100)=100×(1−21​)×(1−51​)=40.

对于任意正整数$x$x，假设其各个质因数为$p_i$pi​，那么其欧拉函数的值为

$\phi \left(x\right)=x\prod _{i=1}^n(1-\frac{1}{p_i}).$φ(x)=xi=1∏n​(1−pi​1​).

显然，这样计算一个正整数的欧拉函数是很复杂的。但如果上式中的$x$x是质数呢？问题就变得非常简单，因为这时$P_i=\left\{x\right\}$Pi​={x}。于是我们可以知道，质数$p$p的欧拉函数为

$\phi \left(p\right)=p-1.$φ(p)=p−1.

同样的，如果对于两个互质的正整数$p,q$p,q，其乘积的欧拉函数就等于欧拉函数的乘积，即

$\phi (p\times q)=\phi \left(p\right)\times \phi \left(q\right).$φ(p×q)=φ(p)×φ(q).

这为我们求解欧拉函数提供了一个很好的解决方式。

欧拉定理

  欧拉定理是数论中的重要定理，我们这里只做介绍，不作证明。欧拉定理说的是，对于互质的两正整数$m$m和$n$n，满足以下关系恒成立：

$m^{\phi \left(n\right)}\equiv 1\left(\text{mod }n\right),$mφ(n)≡1 (mod n),

我们对上式两边同时取$k$k次幂，得到

$m^{k\phi \left(n\right)}\equiv 1\left(\text{mod }n\right),$mkφ(n)≡1 (mod n),

两边同时乘上$m$m，有

$m^{k\phi \left(n\right)+1}\equiv m\left(\text{mod }n\right),$mkφ(n)+1≡m (mod n),

改写得到

$m^{k\phi \left(n\right)+1}\text{ mod }n=m.$mkφ(n)+1 mod n=m.

这是我们需要的欧拉定理的形式。

密钥的生成

  读者是否还记得我们在确定算法的时候找到了公钥和私钥的关系式？即

$m^{ed}\text{ mod }N=m.$med mod N=m.

与我们得到的欧拉定理的形式

$m^{k\phi \left(n\right)+1}\text{ mod }n=m.$mkφ(n)+1 mod n=m.

相比，我们发现，这时我们只需要使得

$ed=k\phi \left(N\right)+1\text{，}$ed=kφ(N)+1，

即对于任何一个公钥$e$e，我们私钥$d$d的生成方式为计算$d$d使得

$ed\text{ mod }\phi \left(N\right)=1.$ed mod φ(N)=1.

这时我们可以利用到一条数学定理：如果两正整数互质（这里表现为$d$d与$\phi \left(N\right)$φ(N)互质），那么一定存在$d$d满足上述关系，即$ed-1$ed−1被$\phi \left(N\right)$φ(N)整除，我们称这样的$d$d为模反元素。

  所以，我们只要保证公钥$e$e和求得的$\phi \left(N\right)$φ(N)互质，那么私钥$d$d的存在性是不言而喻的。那么现在问题的关键就是：如何确定$\phi \left(N\right)$φ(N)和$e$e的值。

  我们任意选取足够大的两个质数$p$p和$q$q，这是我们产生$\phi \left(N\right)$φ(N)的来源。我们令$N=p\cdot q$N=p⋅q，这样的$N$N通常是非常大的，理论上计算$\phi \left(N\right)$φ(N)需要对其进行质因数分解，然而对不知道$p$p和$q$q的人来说，这几乎是不可能的事情，因为$N$N的质因数分解被证明是计算上不可行的了。但作为密钥的分发方，我们却很容易解出，因为我们选取的是两个质数，利用欧拉函数的性质，我们很容易知道

$\phi \left(N\right)=\phi (p\cdot q)=\phi \left(p\right)\cdot \phi \left(q\right)=(p-1)(q-1).$φ(N)=φ(p⋅q)=φ(p)⋅φ(q)=(p−1)(q−1).

有了这个解，我们只需要任意取一个和$\phi \left(N\right)$φ(N)互质的数就行了。由此，我们将$(e,N)$(e,N)作为公钥发送出去，待我们计算出$d$d后，保留$(d,N)$(d,N)作为私钥即可。销毁$p$p和$q$q，这样这组公钥私钥几乎是无法被破解的了。

加密流程总结

  至此，我们已经知道了加密基于的数学原理和方法，这里我们来一些总结。

  这就是RSA加密算法的原理和流程。

关于关键的$p$p和$q$q

  我们知道，如果两个数很接近，那么它们的差值一定很小。如果我们选取的$p$p和$q$q相差不大，那么RSA在这种情况下是很容易被攻破的。我们可以假设$p>q$p>q并且

$p=a+b,q=a-b,$p=a+b,q=a−b,

那么大数$N$N就可以被表示为

$N=p\times q=(a+b)(a-b)=a^2-b^2.$N=p×q=(a+b)(a−b)=a2−b2.

由于$b$b很小，所以$a$a和$\sqrt{N}$N​的值非常接近，于是我们可以轻易倒推出用于产生密钥的$p$p和$q$q的值。这种情况下，RSA的安全性很低。但好在幸运的是，应用中不会产生这样的错误，所以RSA依然是很可靠的加密方式。

后记

  从对于RSA彻底的分析来看，密码学在本质上是数学的实际应用。笔者在理解RSA密码加密的学习过程中，其实更多的时候都在了解其基于的数学原理，而并非大多数人所认为的加密过程。站在一个高度看RSA密码，其实其可靠性是由于人类对质因数分解掌握的不完全所保证的，因为知道公钥$(e,N)$(e,N)，从理论上是可以破解私钥的，只是实际不可行罢了。当然，我们也不能因此质疑RSA密码的可靠性，因为密码学对密码是否可用的标准一直只有两条：破解密码耗费的资源大于信息本身，或者破解密码需要的时间远大于信息的时效性，而并没有将牢不可破作为其中的标准。

  RSA密码在历史上首次是被政府发现的，然后其就一直作为机密被尘封起来。直到1977年，三位麻省理工的数学家独立发掘出这种公钥私钥计算方法，然后才成为了如今广泛使用的RSA加密算法。这个算法也由他们的名字命名：Ron Rivest,Adi Shamir,Leonard Adleman。

公开RSA的三位数学家

  回过来看这个优美的表达式

$d=\frac{k\phi \left(N\right)+1}{e},$d=ekφ(N)+1​,

一对看似无关的数字却连接着探索真相的答案，一个看似简单的算法却暗藏着千年未解的数学难题，这或许就是密码最终的魅力。

本文链接：https://my.lmcjl.com/post/16013.html