更新时间: 2018-08-17 17:15:51       分类: 算法


介绍

非对称加密技术是当前互联网界采用较多的一种数据加密方式。

通过网络传输机密信息的问题是,传输的渠道是公开、透明的,某种程度上来讲,这就好比要使用明信片来传递秘密一样。

因此我们需要构建的数据加密方式必须能够做到,只有接受和发送消息的人才能够得到明信片上所真正表示的内容。

什么是秘钥?

首先,毋庸置疑的是,我们需要对公开传送的内容进行修改,使其成为加密的密文。

一个最简单的方法,就是“移位密码”。以英文为例,我们可以简单的让每个字母向后移动几个距离来实现内容的加密,比如下面这样:

Mark =每个字符向后移动3个距离=> Pdun

这是一个简单的方法,更进一步的,使用凯撒密码等方式,可以实现进一步的加密。

切换到计算机层面上,即是说可以对传输的二进制包整体做移位处理,从而实现加密(当然实际的算法要比这复杂的多)。

可以看到,无论是采用什么样的加密方式,消息的发送者和接受者都需要提前共享一样东西,来实现加密和解密:在移位密码的例子中,这个东西是字母向后移动的距离,在凯撒密码中,则是一串字母或是也该单词。

我们将这个需要双方提前共享的东西称为秘钥,这是一个很形象的比喻,我们对信息加密,就像是要对信息加上一把老式的旋转锁,而无论是上锁还是解锁,都需要一把同样的钥匙。

所以在共享秘钥的加密方式里,传输加密消息的关键在于如何通过公开的信道共享同一把秘钥

使用混合颜料

现在让我们想象一个场景:

在同一个房间里有A,B,C三个人,A要向B传输一段私密消息(比如说他的银行卡密码),而C是一名窃听者。

在不使用小纸条、悄悄话等方式的前提下,A和B要如何传输消息,才能避免C的窃听呢?

另外需要注意的一点是,A和B是陌生关系,这也就意味着他们没法使用诸如“天王盖地虎,宝塔镇河妖”之类的暗号进行交流。

乍看之下似乎是一个很无解的问题,但却有一个很巧妙的方法能够解决 —— 我们需要的只是几桶不同颜色的颜料罢了。

前提

现在我们假设A,B,C三个人,分别位于房间的三个角落里,而每个角落里都有很多很多不同颜色的颜料,每种颜色的颜料也是无限多的。

注意,我们规定,每个人在自己的角落里所做的事情,是其他任何人都无法看到的,如果两个人需要对话或是交换信息,就必须走到房间中央的公共区域去,在这里做的事情,是公开透明的。

第一步:A和B选择各自的私有颜色

A和B在各自的角落里选定一种颜色,我们将这个称为A和B的私有颜色,这意味着只有A和B自己知道它是什么颜色,其他人都无法知晓。

第二步:A和B选择各自的公开颜色

现在A和B需要再各自选定一种颜色,与之前不同的是,这次选定的颜色是公开的,这意味着A和B需要将这种颜色放到房间中央的公共区域去:任何人都可以取到他们的公开颜色。

第三步:A和B构建自己的混合颜色

现在A和B需要在各自的角落里做一些“调色”工作,这非常简单:

A将自己的私有颜色和自己的公开颜色进行混合,得到一种新的颜色,我们称其为A的“公开-私有混合颜色”。

同样的,B将自己的私有颜色,与A的公开颜色进行混合,得到B的“公开-私有混合颜色”。

注意,他们各自的混合颜色并不相同。

接下来A和B将会把各自的混合颜色公开,放置到房间中央的公共区域去。

第四步:A和B在彼此的混合颜色中,加入自己的私有颜色

现在我们假设,A获得了B的“公开-私有混合颜色”,并将它搬回了自己的角落;同样的,B也将A的“公开-私有颜色”搬回了自己的角落。

那么,神奇的地方来了,现在A和B分别向彼此的混合颜色中,加入自己的私有颜色,最终他们将得到相同的颜色,因为他们使用了同样的成分(A的公开颜色+A的私有颜色+B的私有颜色)来构建最终的颜色。

接下来,A和B只需要使用这种相同的颜色对要传输的信息进行加密/解密操作,就可以实现消息的秘密传输了(参照移位密码)。

整体的过程可以参考下图:

我们可以看到,对于窃听者C,无论如何拼凑信息,都无法得到真正的共享秘钥。

颜料混合的要点

之所以能够使用混合颜料来达到上述的神奇效果,关键在于:

实际网络中的公钥加密算法

我们以混合颜料的例子说明了如何实现共享秘钥的构建,现在是时候思考如何在二进制的网路世界里达到同样的效果了。

首先我们需要一种特殊的数字运算方式,能够和颜料的混合一样实现不可逆运算,同时还能够保证相同的数字按照不同的顺序进行运算后,能够得到同样的结果(即满足交换律)。

现在来介绍能够满足上述要求的一种计算方式,也是网络早期共享秘钥Diffie Hellman算法所采用的计算方式:模运算+幂运算

模运算(mod)

这对于熟识计算机常识的人并不是一个陌生的数学知识,我们假定一个模数A,那么任何一个数字BA取模的结果就是B / A的余数。

以模数A = 11为例子:

13 mod 11 = 2
(3 + 6) mod 11 = 9
(2^4) mod 11 = 5 

有了模运算的概念后,我们就可以开始着手构建可用的共享秘钥算法了,下面依旧基于A,B,C三个人的场景进行说明。

第一步:A和B各自选择一个私人数字

为了方便阅读,我们假设A和B选择的都是一个非常小的数字:比如A选择8,B选择9。注意在实际的应用中,这个数字要大得多。

第二步:A和B选择两个公开的数字

和颜色混合不同,现在每个人的公开部分需要包含两个数字,其中一个是模数,另一个是基数

假设A的公开数字分别是11(模数)和2(基数)。

第三步:A和B构建自己的公开-私人数字(PPN)

这是关键的一步,我们要解释一个等同于颜料混合的算数过程,这个过程构建出的结果将会是不可逆的。

现在,A和B都将使用A的两个公开数字,和自己的私有数字,利用下面的公式计算自己的公开-私有数字(我们称其为PPN):

PPN = 基数^私人数字 mod 模数

于是:

A的PPN = 2^8 mod 11 = 3
B的PPN = 2^9 mod 11 = 6

可以看到这个计算PPN的过程是不可逆的,这主要归功于取模操作。

第四步:A和B向彼此的PPN中混合自己的私人数字

混合的计算方式和上面类似,只是公开基数被替换成了对方的PPN:

A计算共享秘钥 = B的PPN^8 mod 11 = 6^8 mod 11 = 4
B计算共享秘钥 = A的PPN^9 mod 11 = 3^9 mod 11 = 4

之所以能够得到同样的结果,是因为幂运算满足交换律,即:

(a^b)^c = (a^c)^b =  a^(bc)

很好,A和B成功混合得到了同样的共享秘钥!现在他们只需要使用这个共享秘钥进行数字的加密/解密就可以实现私密通信了。

而窃听者C无论拿到谁的PPN,都会因为无法混入另一个人的私钥而不能得到最终的共享秘钥。

我们可以把上面的过程总结为下图:

真实的Deffie-Hellman算法

上面的例子中,为了方便理解,我们都采用了非常小的数字,比如模数11,对应的结果空间只有0-10一共11个数字,那么窃听者完全可以通过暴力尝试的方式遍历整个结果空间,最终破译得到密码。

所以,Deffie-Hellman对公开数字有以下几个要求:

有关本原根,我们可以参考上面使用到的数字,对于模数11而言,2和6都是本原根,而3则不是:

3的幂循环对11取模后得到的值只有3,9,5,4,1,而无法得到2,6,7,8,10

更多

共享秘钥加密,是不对称加密的一个典型使用范例,除了Deffie-Hellman算法之外,大名鼎鼎的RSA也属于同样的思路。

后续的文章中将会更新更多有关不对称加密的内容。

本文参考:《改变未来的九大算法》第四章


评论

还没有评论