Video在线视频

到目前为止我们已经看到了

这个共享密钥加密怎么样工作的

下面呢在这个网络安全里面

它的编码解码学还有一大类非常重要的算法

就是公共密钥的加密和解密算法

那么公共密钥呢它和这个共享密钥

有一个很大的不同

我们可以看的到在这一页slide上面呢

这个左边我列出来 共享密钥

它的加密算法呢这个最重要的一点是

要求这个发出和接收双方他们共享同一个钥匙

接收方和发出方这个钥匙呢

实际上是它们共同的一个秘密

可是一个非常重要的问题在这里呢

就是说这个发出方和接收方

互相从来没有见过面的前提下

他们怎么能够商量出来一个共同的秘密呢

这个实际上是

共享密钥加密算法的一个小的难点

那么区别与共享密钥我们现在来看一下

公共密钥加密算法

公共密钥加密呢就是英文叫 a public key infrastructure

就是在这个公共密钥加密算法里面呢

有一个跟共享密钥很大的区别是在于

公共密钥这个加密算法是

需要一对儿密钥的而不是一个

就是它对于每一对对话

每一个发出方和接收方

每一对儿这个Bob和Alice

它们之间一定要有一对儿钥匙

是两个不同的钥匙

一个呢叫做public key

就是公共密钥

另外一个呢叫做private key

叫做私有密钥

那这一对钥匙它不是随便的

任何一对就是都能够被放在一起

它要经过一个比较复杂的算法

那么公共密钥加密啊

就是public key的这个encryption

它的一个最重要的算法叫RSA

一会我们就会看一下

在我们讲述这个RSA具体算法之前呢

我们来先看一下

公共密钥加密这个空间里面

它的一些比较重要的terminology

就是这些名字都叫什么

我们有一个原文m

那么呢对原文进行加密

有这个encryption algorithm

就是加密算法

那在这一页幻灯片上我们可以看到

一般对原文进行加密的时候

如果是Alice想要给Bob发一段密文

那么Alice要用Bob的public key

对这一段原文进行加密

生成一个密文

我再说一遍我们可以看到

这个上面是实际上是用的

Bob的公共密钥或者说Bob的public key

对这个原文Alice想要给Bob发的原文m进行加密

那这样得到密文呢实际上

是用Bob的public key加密的密文

这个密文被Bob收到以后

那Bob用什么东西来进行解密呢

首先呢我们肯定是有一个解密算法这是毋庸置疑的

那这个解密算法里面呢我们会读到

就是读入这个密文

那Bob要用的这个key

这个密钥实际上是他的private key

就是他的私有密钥

这个时候就是Bob的私有密钥只有Bob自己知道

而他的公共密钥呢

可以被其他很多的这个network entities

就是其他的很多的网络设备所知道

这个是要大家非常清楚的一个概念

在这个public key encryption 这个算法里面

那么这样的话那我们看到就是说

Bob用自己的私有密钥

通过一个解密算法应用到就是Alice

用她的公共密钥加密的密文上

就可以得到原文m

这个就是这个Slide 44 就是44页

给大家描述了这样一个公共密钥加密的这样一个过程

这个过程非常重要

希望大家能够理解它 记住它

并且呢 最重要的一点可以看的到

它跟共享密钥加密的一个巨大的不同

共享密钥还是说它呢在共享密钥这空间里面

Alice和Bob是有共同的一个一模一样的钥匙

他们两个人呢 这是他们的shared secret

是他们共享的一个秘密

而在公共密钥加密的这空间里面呢

Alice只知道Bob的公共密钥

但是Alice并不知道Bob的私有密钥

而他的私有密钥只有Bob自己知道

那在公共密钥加密这个算法过程中

再说一遍我们需要一对儿钥匙才能让它工作

那因为有这样一个结构啊

大家就可以看的到

实际上呢因为如此因为它是一对不同的钥匙

所以呢Alice和Bob在没有见面的情况下

他们也用不着非要去互相相商量好

一个公共的一个秘密

用不着一个shared secret

这个是公共密钥加密算法的

一个非常重要的一个特性

也是一个非常有用的特性

我们将要在后面的很多应用中

看得到它是怎么样被运用的

公共密钥加密算法的一些细节啊

我们在这里列一下

首先呢 要让公共密钥加密算法工作

我们这对钥匙它必须要满足下面这样一个特性

就是说我用一个entity

我们就拿Bob来做例子啊

Bob可以是any body

可以是任何一个网络设备

那我们Bob的这个公共密钥

去解密Bob的私有密钥加密的一个密文会得到原文

其实反之是亦然的

就是说我用Bob的私有密钥

去解密用Bob的公共密钥加密的一个密文

也可以得到原来的那个最初始的原文

这个呢用数学表达大家可以看的到

在这个第45页上 数学表达式是这个样子的

就是K(B)minus我们用K(B)minus

去代表Bob的这个private key

上面这K(B)是代表Bob这个人

那它可以是A如果是K(A)minus

就代表是Alice的这个private key

就是以此类推

那我们用K(B)minus去解密K(B)plus

加密的这个m这个原文

最终还能够得到m本身

反过来也这样的

如果我把K(B)plus 提出来提到括号外面来

我用K(B)plus 就是Bob的公共密钥

去解密K(B)minus

就是Bob的私有密钥加密的那个原文

就得到这个密文

我最终还能得到这个m同样的道理

那么在这个公共密钥加密算法

这样一个空间里面

还有说每一个网络设备

它的这个私有密钥只有它自己知道

那除了Bob本人不论谁

获得Bob的公共钥匙

都不应该能够计算的出来

Bob的这个私有密钥

这一点也是很重要的

只有Bob自己可以算的出来

他的私有密钥是什么

而实际的操作中也是这样

就是说Bob自己来运算一下

他自己生成一对钥匙

一个是公共密钥一个是私有密钥

在这对钥匙生成之后

Bob对外可以宣称一下

这里是我的公共钥匙你们可以拿走

不管是谁拿到我的公共钥匙

你都可以用我的公共钥匙来对一段

任何你想加密的这样一个文件去进行加密没有关系

那只有我Bob本人才能对

你用我的公共钥匙加密的这段原文

进行解密这个是它这个public key encryption

最美的地方可以说是

因为就是说它就像一个magic一样

在这样一个情况下能够工作

是很好玩的一点事情

那么RSA这个算法的名字呢

它实际上是三个科学家的名字缩写

这三个科学家的名字呢

是Rivest Shamir和Adelson

那我们大家要记住RSA这个算法

实际上是非常重要的一个public key encryption algorithm

被最广泛的应用的

这个公共密钥的这样一个加密算法

那么我想跟大家一起就是

看一遍这个RSA这个算法它是怎么样工作的

那么要了解RSA的一定的这个理论基础

那我们要先小小的复习一下

余数定理是怎么回事

我相信很多同学应该都对余数定理不陌生了

那余数定理呢就是几条

我们用得上的这个公式呢

我已经列在这里

在那个46页上

余数定理讲的是这样子的啊

就是什么是余数呢这个大家都知道

如果是x mod n 这个是它的数学表达

x mod n 就是x对n求余数

它的意思是指x除n它余几对吧

比如说这个6除2 6 mod 2 six mod two

它的余数是几呢 是0

因为没有东西余下来对吧

但如果是six mod five 它的余数呢就是1

因为6除5余1

那我们再说一遍这个x mod n等于x除n的余数

那由上面这个

简单的这样的余数的这个公式

我们可以有下面的一些定理

可以复习一下啊

下面定理是这样讲的

a mod n 加上 b mod n

就这两个余数相加

它们一起再对n求余 就是再mod n

得到的是a和b先相加

这个和对n求余这是一样的

那第二条那是说a mod n减去 b mod n

就是a对n求余这个余数

减去b对n求余的余数

整个的这个差对n求余数

等于a先减b这个差对n直接求余数

这个两边呢也是一样的

最后一条呢是[(a mod n) - (b mod n)] mod n =(a*b) mod n

这个就是一样的道理啊

就是a对n求余数乘上b对n求余数

这个两个余数的积对n求余数

就等于a和b的积一起就是直接对n求余数

有了这些性质 有了这些定理呢

我们就可以推出下面就是在这个红色的这一行

写出来的这样一个等式

这个等式是什么呢

就是a对n求余数的d次方再对n求余数

就相当于a的d次方

这个幂对n求余数

这个等式两边是相同的结果

那有了红字列出来的这一行的性质呢

我们就可以来看一个例子

下面这个例子讲的是说

如果我有一个整数x=14

还有一个n是10 那d这个指数呢是2

如果对这样一个数字组合

我们来做如下运算

我们能得到什么呢

就是x mod n的d次方 mod n

实际上就相当于是14 mod n

对吧就14 mod 10 就14对10求余数

那这个结果是4 对吗

4的2次方 d是2

4的2次方再对10求余数就是6

因为4的2次方是16

16对10求余数是6

那我们再往下看就是

x的d次方呢是14的2次方

在这个例子里面 14的次2方等于196

那么x的d次方对这个10求余数呢

就是196对10求余数也是6

所以我们通过这个简单例子

基本上呢就算是复习了一下这个余数定理

然后余数定理呢对我们后面

讲述RSA这个算法

它从它的推演到最后它的应用

是很有用的一步

那么下面我们就来看一下

这个RSA的基本的一些认知啊

在RSA这个算法的这个空间里面呢

我们把每一条信息

我们实际上都把它当做一个数字

其实这个也是非常合理的

因为我们在这个计算机的这个领域里面呢

我们在这个讲述数字的时候一般都是二维码的数字

那一串字符也实际上是一个二维码

这个二维码本身它是可以翻译成一个整数的

那比如说我们在这个47页上面这个例子

m=10010001

这个binary number这个二维码它实际上你算一下

转换成十进制的这个整数它就是145

这个二维码就是二进制到十进制转化

对于我想在这个屏幕前的同学们而言

应该都是一个小case对吧

应该都很简单的一件事情

那么RSA呢就是它要想操作的话

首先我们make一个sumption

就是我们假设的呢就是说

每条信息实际上它都是一个字符串

而这个字符串呢它其实就是一个整数

这样的话呢我们对一个原文m加密的过程

实际上就是对这个m代表的这个整数

做运算的一个过程

那再回来到这个47页上面这个例子

我们可以说m等于10010001

它实际上是145这个整数

那我想对m进行加密

实际上就是对145这个十进制的数进行加密

那好那我们下面就来具体看一下这个RSA

它是怎么样就神奇地去创造出来

这个公共密钥和私有密钥这一对是怎么做的

很有意思的一个过程

不一定记住但如果你能够

真正是强行记住它

也是一个很好的事情

但是呢最重要的是理解

理解这个算法它是怎么样工作的

首先第一步呢

我们选两个比较大的质数p和q

记住是质数

没有任何约束的啊

p和q比如每一个都有可能有1024比特长

就是一个很长的很大的质数

那么呢第二步就是我们对这个p和q

这两个大质数我们算它的乘积p*q

这个p*q的乘积呢我们用n来代表

就是n=p*q

那同时呢我们再算一个数叫z

z就相当于是p minus one

就是(p-1)*(q-1)就得到z

所以说n是p*q

z是(p-1)*(q-1)

那到第三步我们还是选一个整数e

这个e呢我们一定要小于n

就是小于这个p和q的乘积

同时呢还有个规定就是e和z之间

是没有公约数的

z是怎么来的是(p-1)*(q-1)

那e和z之间我们就选一个e

这个e可以有多个可能啊

但我们选一个e e比n小

同时呢e和z是没有公约数的

就是说e和z是互质的关系

那有了这个e以后我们再来就是看第四步

第四步呢就是选一个d

d呢他可以满足一个什么性质呢

就是说以至于第三步中的e乘上这个d

它们两的乘积减去1可以被z整除

我再说一遍这个第四步

我们选一个数d

以至于第三步算出来这个e和d相乘减去1

这个差就是ed-1可以被z整除

z相当于是(p-1)*(q-1)

也就是说呢就是如果我们把

刚刚第四项里面列出来这一条换一个说法

实际上就是说ed mod z

就是ed的乘积对z求余

这个余数得1

好了 那我们基本上1 2 3 4 四步

这个魔法棒已经挥了四下对吧

然后挥到这里呢

基本上我们已经得到了我们想要的

就是我们真正需要的就是这个e和d

第三步生成这个e

和第四步选出来的这个d

那我们怎么样通过原来的这个n

和这个e还有d来设这个公共密钥的这一对钥匙呢

就是我们可以做第五步的这样一个设置

就是把(n,e) 设成Bob的公共密钥

(n,d) 设成相应的一个私有密钥很重要

因为你前面这1 2 3 4算出来的

这个e d 还有那个n

它们之间都是有相互的

数学关系和逻辑关系的

我们只有这样设置才能够使

后续的这个公共密钥的这种算法

才能让它工作

所以呢这里再给大家再次重复一遍

公共密钥是什么

是我们经过上述的这几步算出来的

(n,e)这一对那个数字

那私有密钥呢是(n,d)这一对数字

而(n,e)这个公钥对应的私钥

只能是这个(n,d) 反之亦然

好 我们现在呢看了这个RSA算法

它是怎么样来生成一对密钥对儿的

这个过程呢很好玩

如果大家有兴趣呢

去看一下整个这个过程的证明

那么那个大家可以就是在线下

自己做一下文献上的搜索

然后来学习一下是很有趣的一个数学过程

那么我们现在呢有了RSA这个算法

给我们提供的这样一对密钥

一个公钥一个私钥

我们此时此刻如何

用这一对得到的公钥和密钥

来对一个原文进行加密

以及之后怎么样对一段密文进行解密

这就是我们下面想要来了解的

就下一页slide是49页

那我们如何用RSA这个算法进行加密和解密

前提是说我们已经有了刚刚用RSA算法

得出的(n,e)和(n,d)这一对密钥

那我们有了(n,e)的话我们用(n,e)

对原始信息m进行加密

这个运算过程就是我列在了

这个第一行的这个红字里面

是说这个c ciphertext

这个密文就等于原文对e求幂

就是原文m的e次方

之后这个幂对n求余

就是c equals to m to the power of e mod n

就是c呢这个ciphertext

它是相当于原文对e求幂

原文的e次方之后再mod n

就是再对n求余数

这样得到的一段那个字符码

就是ciphertext 就是密文

那这个第一步在这个49页上1这个部分里面

我们得到的是这个密文 ciphertext

拿到密文以后

我怎么样用私钥应用到这个密文上

再把原文还原呢

这个就是下一行那个红字写的这个算式

就是这个原本m

实际上是相当于一模一样的这个算法的这个步骤

就是说只输入不一样了

这个时候呢这个函数的输入

实际上是c是ciphertext

然后呢它的这个用的钥匙是d

而不是e了对吧

这个d是什么来的

是我们私钥的一部分

所以就是说我们把这个ciphertext

就是密文的d次方私钥的一部分

求一个幂 得到这个幂对n求余

最终得到的结果就是我们的原文

用数学来表达

m等于c的d次方对n求余数

这个是我们怎么样通过这个ciphertext c

就这个密文c我们怎么样还原原文m

是这样一个过程

如果要是我们想要去

来确认一下它真的是能够工作的话

那么因为我们刚才已经复习了余数定理

我们简单的来看一个小小的证明

就这一行的证明

这个magic是怎么happen的

那我在这个最下面这个方框里面

这段算式是可以给大家简单的证明一下

m是怎么样能够被还原的

通过刚刚的这两步

加密和解密的方法

我们其实可以看的到

实际上m就相当于是c对吧

c to the power of d mod n

那c是什么

c就是算式1中的m to the power of e mod n

所以呢就是我们把它加在一起

实际上就是m的e次方mod n

之后这个余数的d次方再mod n

这个数字实际上最后的结果是m

根据刚才我们复习过的余数定理的一些步骤

大家其实想要证明这个结果是并不难的

所以说这个整个算法其实本身是很简单的

而就是根据经过几位数学家

经过几位科学家的这个努力

能够让这样一个数学公式

被大家发现并且利用

真正运用到实际的这个编码解码学中

这是一个非常有意义的事情

到目前为止我们已经看到了

RSA基本上理论上它是怎么样工作的

然后呢我们怎么样生成这个

公钥和密钥的这一对儿钥匙对儿

然后我们有了这对儿钥匙以后

我们要怎么样对原文进行加密

怎么样对密文进行解密

这个我们都已经看过了

那现在我们来看一个实例

第50页我们会看到呢

这个有一个很简单的一个例子

给大家一起我们运算一下

这时候呢我们假设Bob他选择了一个p

不管Bob是谁啊

任何一个这个网络设备都可以是Bob

Bob他自己来运行这个RSA这个算法

自己来生成一对儿钥匙对儿

这个是Bob要做的事情

那Bob呢他第一步就是选两个大的质数

我们为了这个例子上

给大家有一个比较简单的一个演示啊

所以这个p和q在我们这个实例里面

实际上是比较小的

但是呢其实我们真正的应用中

这个p和q是很大的值

那在我们这个实例里面呢

p是5 q是7这个很简单

那n就很简单就是5*7=35

z呢就是4*6=24

因为z=（5-1）*（7-1）对吧（p-1）*（q-1）

所以n和z我们都知道了

这个时候我们挑一个e e可以是不同的

那这个时候我们选择e=5

因为5和z互质并且5比n小

我们e的条件是说

我们需要选一个e它比n小

并且呢还要和z互质

那这个数字5是满足这个条件的

之后呢我们再选个数字

就是这个d

d呢这个时候我们选29

因为这个数字呢必须要满足e*d-1

可以被z整除

29这个数字是满足这个性质的

就是29乘5减去1可以整除24

所以呢d我们设它为29

那这样子的话呢

到此为止这个Bob那它就成功的

升成了一对密钥的这个密钥对儿

它呢就可以把它的公共密钥就是public key

设成这个（5，n） 就是5和35

public key就是（e，n）

就是（5，35）这一对数字是它的公共密钥

那（29，35）这一对数字呢

是它的这个私有密钥

那我们有了这一对钥匙对儿以后

我们假设对以下的这一段

8个比特的这个字符串进行加密

整个过程是什么样呢

我们可以看一下啊

那假设我们有这样一个字符串是0000 四个0

然后1000 8个比特长的这样一个数字

这个数字非常好算

它就是实际上的十进制中的12

这个对12这个原文我们进行加密

就相当于是说我首先对12求e次方

就是12的5次方得到的数字是24832

这是这个m的e次方

那之后呢ciphertext等于什么来的呢

是等于m的e次方mod n

n在这里是35

所以就是24832这个数对35求余

余数是得17

那17这个数字是什么呀

就是我们想要拿到的那个加过密以后的密文

我们用的什么加密呢

用的是Bob的public key

这个public key是什么来的 是（n，e）

那在这个情景里面n是35 e是5

同学们应该到此为止呢

就是应该在逻辑上已经有这样一个概念了

那好我现在原文有了 原文是12

密文也有了是17

Bob收到密文17

Bob怎么样从新算出来这个原文呢

那我们就是这个解密的过程

Bob用来解密的这个密钥是他的私钥

他的私钥是什么来着

是那个d和那个n的组合

d我们说过了d是29 n是35

所以呢那我有了密文17

我有了这个自己Bob的密钥29和35这一对儿数字

我下面呢进行解密

解密的过程是这样子

我把c输入到这个解密算法中 c是17

17to the power of d

就是17的d次方 17的29次方

就下面这个密密麻麻很长的一个很大的数字

我就不再一个一个念了非常长

我们拿这个17的29次方得出来以后

我们在对这个17的29次方对35对n求余数

那这个时候确确实实很magic很神奇

这个余数它正好是个12

12是什么 就是我们当初加密过的那个原文00001000

这个就是原文的还原过程

我不知道同学们是怎么感觉的

总之呢这个RSA这个算法呢

实际上它是一个这个确确实实非常有趣

是很神奇的一个算法

我希望同学们在学习的过程中

能够去理解它的意思能够去体会它的美

这个东西还是很好玩的

不错的一个发明吧算是

那么我们怎么样能够就是判断RSA算法

它实际上是安全可用的呢

这个也是有相当多的证明了

就说证明这个RSA它是很难被破译的

原因是说就是如果一个人

他知道了Bob的公共密钥

还是说因为Bob的公共密钥

实际上是大众可以获得的

虽然说不是所有人都是这个

随便去download的不是这个意思

但是如果Bob想的话

可以把它变成所有人都可以download的

这样一段字符是可能的

但是呢就是说即使是

某一个人拿到了Bob的这个公共密钥

他想通过Bob的公共密钥

去算出来Bob的私有密钥

这个过程在数学上讲是非常难的

基本上这就意味着

我们需要在不知道p和q的情况下

找到n的约束而想找全一个很大的一个数的约数

这是一个非常难的一个数学过程

所以说呢就是想要生成这个RSA的

这个一对钥匙对

必须要找到大的质数p和q

这个质数比较大呢那你这个算法就

更加的secure就更加的安全

就更难被破译了

那如何去找呢我们一般都先作猜想然后再去找

这个呢实际上我们可以去看一下这个kaufman

他有一些证明和一些方法

到此呢我们基本上

就是讲了这个RSA这个算法

它是怎样被运用的

然后怎么样生成这个

public key和private key这一对钥匙

然后呢这一对钥匙呢又是怎么样

在这个实际的一些算法中被利用起来的

我们看了这个RSA这个算法之后呢

也基本上了解了这个公共密钥的这样一类算法

它是就是对原文是怎么样加密

对密文是怎么样解密的

那么这个公共密钥的这个算法

虽然它很好玩

但是呢它有一个很麻烦的地方

是在于它的运算的复杂性其实是非常高的

也就是说它算起来还是蛮耗时间的

它真正在这个加密的这个过程中

DES算法实际上要比RSA快很多倍

假如说这个对一个文件也好

或者对一段对话也好

我想要进行加密的话

如果我就是对每一个这个字节

都是用RSA来进行加密

那真的是可能会花很久很久时间

所以那RSA它一般就公共密钥的这种算法呢

它是怎么样被应用的呢

它实际上是跟这个shared key的

这种共享密钥的算法相结合

来被实际用在安全协议中的

那一般而言呢

就是我们用公共密钥的加密方法来进行交换

交换什么呢 交换一段很重要的信息

信息的本身实际上就是那个shared key

这个共享密钥是为了这个用共享密钥算法

进行加密解密的

这个shared key它自己

是由公共密钥的算法来进行交换了

在Alice和Bob 之间进行交换

比如说这个Alice呢它生成了一个shared key

或者我们也叫session key

那这个Alice会想要告诉Bob这个session key是什么

这个时候Alice怎么做呢

它就直接用Bob的public key去encrypt

去吧这个session key给做encryption进行加密

然后呢把这个加密过的session key发给Bob

这个时候呢Bob之前并不知道

有这个shared key或者这个session key

它并不知道这个东西是什么

但是Bob收到了一段Alice发来的

用Bob的这个公共密钥加密的一段信息

那Bob呢就用自己的私有密钥来进行解密

得到内容是什么呢

就是这个shared secret 这个session key

那到此为止如果就是Bob可以成功解密的话

之后Alice和Bob两个人之间

其实就有了一个共同的共享密钥

就是那个session key

从此之后Bob和Alice之间

如果它们想要再发任何私密的信息

它们就可以用这一段shared key

来对原文进行加密和解密

这个过程就会快很多了

也就是说只要它们拿到了这个shared secret以后

他们就可以开始用DES算法

而不用永远或者一直

用这个RSA这样的算法来进行复杂运算

这个就是RSA这种这个public key

这样的算法呢它最大的贡献