加密算法

  谈到加密算法,我们不得不谈一下密码学中加密算法的两个分支:对称加密非对称加密

对称加密算法(以单表替代密码为例)

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

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

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

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

非对称加密

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

RSA加密算法

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

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

33 mod 7=6,3^3\ \textrm{mod}\ 7=6,

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

3x mod 7=6,3^x\ \textrm{mod}\ 7=6,

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

3x mod 7156464845153468615315646=6,3^x\ \textrm{mod}\ 7156464845153468615315646=6,

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

加密算法和解密算法确定

  知道了我们要使用模运算作为加密和解密算法,那么我们不妨假设明文信息是mm(message),密文信息是cc(cipher),公钥为ee,私钥为dd,于是我们可以得到

{me mod N=c,cd mod N=m.\begin{cases} m^e\ \textrm{mod}\ N=c,\\ c^d\ \textrm{mod}\ N=m. \end{cases}

消去密文cc,上式可化为

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

可以证明上式等价于

med mod N=m.m^{ed}\ \textrm{mod}\ N=m.

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

欧拉函数和欧拉定理

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

欧拉函数

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

100=2252100=2^2\cdot 5^2。

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

φ(100)=100×(112)×(115)=40.\varphi(100)=100\times(1-\dfrac{1}{2})\times(1-\dfrac{1}{5})=40.

对于任意正整数xx,假设其各个质因数为pip_i,那么其欧拉函数的值为

φ(x)=xi=1n(11pi).\varphi(x)=x\prod^n_{i=1}(1-\dfrac{1}{p_i}).

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

φ(p)=p1.\varphi(p)=p-1.

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

φ(p×q)=φ(p)×φ(q).\varphi(p\times q)=\varphi(p)\times \varphi(q).

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

欧拉定理

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

mφ(n)1 (mod n),m^{\varphi(n)}\equiv1\ (\textrm{mod}\ n),

我们对上式两边同时取kk次幂,得到

mkφ(n)1 (mod n),m^{k\varphi(n)}\equiv1\ (\textrm{mod}\ n),

两边同时乘上mm,有

mkφ(n)+1m (mod n),m^{k\varphi(n)+1}\equiv m\ (\textrm{mod}\ n),

改写得到

mkφ(n)+1 mod n=m.m^{k\varphi(n)+1}\ \textrm{mod}\ n= m.

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

密钥的生成

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

med mod N=m.m^{ed}\ \textrm{mod}\ N=m.

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

mkφ(n)+1 mod n=m.m^{k\varphi(n)+1}\ \textrm{mod}\ n=m.

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

ed=kφ(N)+1ed=k\varphi(N)+1,

即对于任何一个公钥ee,我们私钥dd的生成方式为计算dd使得

ed mod φ(N)=1.ed\ \textrm{mod}\ \varphi(N)=1.

这时我们可以利用到一条数学定理:如果两正整数互质(这里表现为ddφ(N)\varphi(N)互质),那么一定存在dd满足上述关系,即ed1ed-1φ(N)\varphi(N)整除,我们称这样的dd模反元素

  所以,我们只要保证公钥ee和求得的φ(N)\varphi(N)互质,那么私钥dd的存在性是不言而喻的。那么现在问题的关键就是:如何确定φ(N)\varphi(N)ee的值。

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

φ(N)=φ(pq)=φ(p)φ(q)=(p1)(q1).\varphi(N)=\varphi(p\cdot q)=\varphi(p)\cdot\varphi(q)=(p-1)(q-1).

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

加密流程总结

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


步骤 内容 生成
1 选取两个不相等的足够大的质数 ppqq
2 计算它们的乘积N=p×qN=p\times q NN
3 利用NN的因数计算其欧拉函数φ(N)=(p1)×(q1)\varphi(N)=(p-1)\times(q-1) φ(N)\varphi(N)
4 选取任一与φ(N)\varphi(N)互质的整数ee 公钥成员ee
5 计算模反元素dded mod φ(N)=1ed\ \textrm{mod}\ \varphi(N)=1 私钥成员dd
6 公布公钥(e,N)(e,N) 公钥(e,N)(e,N)
7 保存私钥(d,N)(d,N) 私钥(d,N)(d,N)
8 销毁ppqq

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

关于关键的ppqq

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

p=a+b,q=ab,p=a+b,\quad q=a-b,

那么大数NN就可以被表示为

N=p×q=(a+b)(ab)=a2b2.N=p\times q=(a+b)(a-b)=a^2-b^2.

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

后记

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

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

公开RSA的三位数学家
公开RSA的三位数学家

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

d=kφ(N)+1e,d=\dfrac{k\varphi(N)+1}{e},

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

- -