Video在线视频

大家好

这一节我们介绍

难解的非对称加密技术

互联网时代的到来

密码学又产生了新的问题

比如

人们怎么通过一台计算机向

远方的另一台计算机传递机密的信息

就像大家熟知的网购

你在下单的时候

需要通过自己的计算机

发送银行卡号和密码

如何确保你这么重要的信息

不在“中途”被窃取

加密是可以解决被“偷看”的问题

但前提是你知道信息发给谁

对方也知道怎么解密

否则加密就失去了意义

就像你在明信片上使用密码

邮局工作人员显然不知道你在说什么

但收件人必须知道是怎么回事

现在真正的问题是

你要给不认识的人发送信息

如果你使用密码

对方就没有办法知道你在说什么

比如

你第一次用信用卡在亚马逊上购物时

你的计算机必须将你的信用卡卡号

传输给亚马逊的服务器

如果你把加密方法一同

传送给亚马逊的服务器

那互联网上信息传输所经过的

所有的路由器都可以“看到”

无异于“大白于天下”

加密也就失去了意义

那么

我们如何解决这样的问题呢

面对这样的难题

非对称加密技术应运而生

为更好地理解该技术的思想精髓

我们不妨从简单的实例说起

假定你、张三、李四同处一个房间

而你要以大声说话的方式告诉张三

一个秘密数字比如“7”

但又不能让李四知道

你该怎么做呢

你当然可以利用一些只有

你和张三熟知而李四不知道的事情

比如你可以对张三说

记得我们常去吃饭的

那家饭店的门牌号吗

如果你用门牌号

加上我现在想告诉你的这个数

结果是329

不难理解

这种方法的前提是

你和张三很熟悉

并且都记得那家饭店的门牌号

为什么这么简单的方法能奏效呢

因为你和张三有一样东西

也就是计算机科学家们

所谓的共享密钥

在这就是322

而你们俩都知道这个数字

但李四却不知道

你可以使用这个共享密钥

秘密地传输任何数字

只要和共享密钥相加

说出总数

让另一方减去共享密钥也就可以了

而听到总数对李四没有什么意义

因为她不知道要减去哪个数字

如果理解了这个简单的思想

你就理解了互联网上绝大多数

加密真正的原理

不过我们必须注意的是

一、共享密钥要足够长

像这样3位数的街道门牌号

只有999种可能

对计算机来说

几乎不费吹灰之力

就能试遍999个数

从而找出这个密钥

二 上述加密思想还要克服一个困难

那就是人们可以通过分析大量的

你加密过的消息来得到密钥

为此一种被称为“分块密码”

如高级加密标准AES

这样的现代加密技术诞生了

有兴趣的同学不妨更多地了解一下

对于双方比较熟悉的通信

共享密钥加密技术

似乎没有什么问题了

但是

如果你和张三并不认识

又要告诉张三一个秘密数字

那怎么办

是不是感觉简直不太可能

别失望还是有个精妙的办法

能解决这个问题

这就是计算机科学家们

称之为迪菲赫尔曼密钥交换的解决方案

要理解这一精妙绝伦的思想和方法

还是先让我们做一个

看起来很滑稽的假设

那就是假定李四知道如何做加法和乘法

但不知道如何做除法

先不管这样的假设是否现实

既然是假设

先认定这样的假设再说

有了这样的假定

就会有下面这样有趣的事情

比如给定两个数5和7

李四知道它们的乘积是35

但是给定乘数是5乘积是35

李四是无法知道另一个被乘数是7的

因为李四不知道怎么做除法

现在看看你和张三之间

如何传递信息而又不让李四知道

第一步

你和张三各选一个只有自己知道的数

比如你选择了4张三选择了6

注意这是你们心中的“秘密”

别人是无法知道的

第二步

你另选一个数并公开让大家都知道

假设你选择了7作为这个公开的数

也就是说

张三和李四都知道这个数是7

第三步

把你所选的私密数 也就是4

和公之于众的数7相乘

得到乘积28

然后公布这个结果

张三也将自己所选的私密数6

和公之于众的数7相乘得到结果42

并且也公开这个结果

第四步

你把张三公布的结果42

乘以你选的私密数4

结果是168

同样

张三用你公布的乘积28

乘以他自己选定的私密数6

也令人惊讶地得到了相同的结果

也就是168

通过这种办法

你相当于告诉了张三一个绝密的数168

而李四却无法知道

原因是李四不知道如何做除法运算

尽管她听到您说28张三说42

知道另一个公开的数是7

可要命的是

李四不可能傻到不懂除法运算

如果这个前提不成立

推出的任何结论都没有意义

那么说了老半天

这种方法没有意义了吗

不

数学家们又给我们想出了

非常有效的办法

那就是既便李四知道如何做除法运算

也让他无能为力或者得不偿失

比如说

李四要用50年或者100年才能

算出她想要的结果

那样的话

既便她能算出结果来

也已经没有什么实际意义了

为了更好地理解数学家们的工作

我们先学习两个基本的概念

一个是素数

另一个叫模运算

所谓素数也称质数

它除了1和它本身之外

不能被其它自然数所整除

比如11就是一个素数

与之相关的一个概念叫互素或者叫互质

如果两个或多个整数的最大公因数为1

我们则称它们为互素

比如 7 10 13的最大公因数是1

因此它们互素

所谓模运算也就是取余运算

即一个自然数除以

另外一个自然数所得的余数

注意在这里我们只关心自然数

例如7和4取余结果为3

这两个概念很容易理解

有了这些概念的铺垫

我们就可以了解

科学家们是怎么解决问题的了

数学家们已经证实

用两个巨大的素数相乘

并获取其乘积不是一件很难的事

但是要想从该乘积反推出

这两个巨大的素数

却没有任何有效的办法

这种不可逆的单向数学关系

是国际数学界公认的质因数分解难题

这一点类似于把两种不同颜色的染料

混合在一起很容易

再想把它们分开就太难了

李维斯特 沙米尔和阿德尔曼

三人巧妙利用这一数学上的难题

设计出了著名的RSA公钥加密算法

它的基本思想是这样的

第一步

用计算机随机产生

两个很大的素数p和q

然后计算它们乘积N

N就等于p乘以q

这里所说的“很大”是个什么概念呢

通常达到百位甚至几百位

这里的单位是bit

就是二进制位

第二步

利用p和q有条件地生成加密密钥e

在这里e可任意取值

但是e与p-1乘以q-1必须互素

并且e小于等于p-1乘以q-1

满足这个条件的e不止一个两个

可任选一个

为什么这里是p-1乘以q-1呢

因为根据欧拉定理

不大于N且与N互质的整数个数

为p-1乘以q-1

这些您大概了解一下就可以了

第三步

通过计算得到与N互为素数的解密密钥d

这个计算公式是

d乘e和p-1乘q-1取余等于1

在p q e都已知的情况下

求d的值应该就不难了

第四步

将N和e共同作为公钥对外发布

将私钥d秘密保存起来

不能泄露

初始素数p和q的使命就完成了

可以销毁

感觉很复杂吗

不复杂

让我们看个简单的例子

例如

设素数p为7

q等于11

则N就是77

p-1乘以q-1结果就是六十

我们不妨取e等于7

根据计算公式d乘e

和p-1乘以q-1取余等于一

我们可以算出d等于43

当你需要向张三传输

不想让别人知道的信息

或者称为明文时

就用加密密钥e

按某种特定的方式

对这个明文进行加密

这个过程也叫密码化

然后将加密后的信息也成为密文

同公钥N和e一起对外发布

张三接收到密文以及公钥N和e后

计算出解密密钥d

按特定的方式就可以把密文解密了

国际数学届和密码学界已证明

企图利用公钥和密文推断出明文

或者企图利用公钥推断出私钥的难度

等同于分解两个巨大素数的乘积

事实上

公开密钥方法保证产生的密文是

统计独立而且分布均匀的

什么意思呢也就是说

不论给出多少份明文和对应的密文

也无法根据已知的明文和密文的对应

来破译下一份密文

大家也许看过电视连续剧《暗算》

应该注意到传统的密码破译员老陈

破译了一份密电

但却无法用相同的方法破解第二份

第三份密电

而年轻的黄依依第一次找的结果

经过一系列计算发现无法“归零”

也就是说除不尽

她应该是在试图将一个大数N做分解

没有成功

第二次计算的结果“归零”了

说明她找到了N的分解办法

当然

这样复杂的计算是不可能用算盘完成的

这就是电视剧的“夸张”手法

当然

世界上没有永远破不了的密码

关键是它能有多长时间的有效期

一种加密方法只要保证50年内

计算机破不了也就可以满意了

事实上

1999年

RSA-155（512 bits）被成功破解

2002年

RSA-158也被成功破解

到2009年12月12日

RSA-768（768 bits）也被成功分解

被分解的两个素数是这样的

仔细想想

上面讲的非对称加密技术

其实是数学思维与工程思维

互补与融合的经典案例

不是吗

好 这节就讲到这

谢谢大家