大家耳熟能详的一个词叫 数字签名什么是数字签名Youtube视频

大家耳熟能详的一个词叫 数字签名什么是数字签名Youtube视频

各位同学大家好 我是李永乐老师

今天 我们想通过Youtube视频给大家介绍一下

大家耳熟能详的一个词叫 数字签名

什么是数字签名呢 为了理解这个问题

我们首先 要研究这样一个数学问题

假如一个班里面有50名同学

那么请问至少有两个人生日在同一天的概率有多大

也许有人会想 一年有365天

生日分布在这365天里

所以这个概率不会太大

实际上真的如此吗

我们来看一下生日问题

我们知道一年有365天

每个人的生日都是随机的

分布在这365天之中

我们定义 P:表示所有人的生日都是不在同一天的概率

那么自然而然

1-P 就是至少有两个人生日在同一天的概率 对吧

我们来思考一下

如果有一个人 他的生日不在同一天的概率有多大

那这个很简单了 一个人的话这个概率就是100%

365/365

什么意思

就是一年有365天

他随便找一天 他都不会有人跟他相同

因为一共就一个人 对吧

那么如果有两个人又如何

如果有两个人的话

就变成了第一个人 他可以在365天中随便选一天

而第二个人呢 第二个人为了跟他不相同

只能在什么 剩下那364天里选一个

所以再乘以364/365

这就是如果有两个人生日不在同一天

那要是三个人 显而易见就是

365/365×364/365×363/365 对吧

如此这般

那么如果我们有n个人

我想问 生日不在同一天的概率有多大

这大家是不是也就会了

这个数应该是什么

底下是365的n次幂 对吧

上面是什么

上面是 365×364×…×(365-n+1)

这样一个事 好吧

那么上面一共有多少项 上面一共也是n项

底下呢也是n项 这么一除就可以了

我们可以代入数据进行计算

看看这个结果是怎样的

如果这个班级里有10个人的话

那么这个概率就是88.3%

也就是说如果班里只有10个人的话

那么所有人生日都不同的概率是88.3%

那你知道有相同生日的概率是多少吗

1-P就行了吧 对不对

11.7%

也就是说大概1/10的概率 是有人的生日是相同的

那么如果是20个人

20个人 这个概率就等于58.8%

也就是说有58.8%的概率 所有人生日都不一样

而有人生日相同的概率就是41.2%

大家看

20个人就已经有接近50%的可能会出现生日相同了

那假如说 是50个人

就是所有人生日都不同的概率是2.9%

而有人生日相同的概率是97.1%

也就是说一个班级里有50个人的话

那么基本上都会有生日相同的 概率非常非常高

而且我们会发现 只要20多个人

就有50%以上的概率可以出现生日相同了

这种情况下我们就称之为生日碰撞

这和我们的想法可能很不一样

我们觉得一年有365天

你要是20多个人分布的365天里面

基本上不会有生日相同

但实际上不是这样

有50%以上的概率会存在生日相同的

那么这么一个数学问题 它有什么应用呢

其实在数字签名这里就非常有用了

下面我们就来讨论一下什么是数字签名

为了说数字签名

我们首先要说一个函数 名字叫哈希函数

这个名字听起来挺奇怪的

不过它并不难理解 哈希函数是这样一个特点

就是你给我一个字符串

我可以把这个字符串变成一个有限长度的新的字符串

而且是单向的

比如说有个字符串叫123

那么我们可以把它变成一个abc

这就是做了一个哈希函数

如果有个字符串叫4adb5 这么长 跟刚才不一样长

经过哈希运算 它也变成三位

比如说它可能变成了efg

你再给我一个其他的更长的字符串 我也能变成三位

这个就叫哈希函数

哈希函数具有什么特点呢

第一个特点是单向的

就是说 你从左往右是可以算的 而且很容易

但是你从右往左这个算不出来

你给我abc问我原来函数是什么 这个就不知道了

这是第一个特点

第二个特点 就是通过哈希函数算出来这个结果

它的位数是有限的

位数是固定的

不管你原来是几位

我最后算完了之后结果都是一样长的

可能是三位 可能是四位

这看你函数的情况不一样

这样就会出现一个什么问题

就是两个不同的原函数

两个不同的原项有可能经过哈希函数运算之后变成什么

变成是一个同样的值 这种情况下就称之为什么

称之为生日碰撞

那么出现了生日碰撞 是不好的

因为出现了生日碰撞就达不到数字签名的要求了

所以我们要尽量降低生日碰撞

那么人们经过计算发现 如果你的哈希值有n个的话

那么你出现生日碰撞大于50%的概率

只需要1.2倍√n就行了

比如我们的哈希值一共有一百种可能

那么我们原项只需要12个

就有可能会出现相同的哈希值 50%以上概率

如果我们的这个哈希值有1万个

我们只需要试多少次 只需要试120次

那我们就可以算出相同的哈希值来

就有可能出现这种情况

那么这个称之为生日碰撞

那么我们现在说一说哈希函数怎么用在数字签名中

它这个签名的过程是什么

说签名干嘛使

签名的目的就是为了确认这个信息是你发出来的

比如说我想告诉你一段信息我可以进行加密

但是别人也可以加密告诉你

你怎么能区分这个加密信息是来源于我

还是来源于一个邪恶的人 对吧

这个问题就比较麻烦了

那么就需要数字签名进行发挥功力了

那首先

比如说我们先来说一下 非对称加密的这个基本算法

A想和B进行通信 对吧

B想把一段信息传给A

B想把什么信息传给A

他想把123这段信息传给A

那么非对称加密的过程是以前我们讲过

就是我们A先制作一套密码 制作一套密钥

这套密钥里面的加密方式是公开的

相当于一个盒子 这个盒子是打开的

任何人都可以往里装东西

这个邪恶者也可以装 B可以装

B拿到这个盒子之后把123装进去 然后把盒子扣上

这个时候谁也打不开了

只能加密不能解密 谁也打不开了

谁也打不开了之后怎么样 他就把这个盒子传给A

这个盒子只有A能打的开

于是A就用自己的钥匙把这个盒子打开

就得到了原来的数据123 就是这么一个过程

但问题是假如在这过程中有一个邪恶的窃听者

这个邪恶的窃听者他是可以实现加密的

因为他有这个盒子 对吧

于是邪恶的窃听者把一组数据 比如说4adb5

把这一组数据 他也装盒子里

然后传给A的话 A也可以解得开

解开之后发现这个数据是4adb5

那么他就不知道 说这个数据到底是B给的

还是一个邪恶者给的

所以这个事就很麻烦 那怎么办呢

我们可以实现数字签名

数字签名的过程是这样的

首先B要传输一组数据123

把它进行哈希计算

计算了之后得到它的哈希函数值叫abc

然后他把这个abc进行加密并且传给A

但是这个加密过程跟刚才刚好相反

是任何人都可以解密

但是只有B能加密

就好像说你把这个数据装在一个塑封袋里面

这个塑封袋 所有人一撕就把它撕开了

都可以看到里边的数据

但问题是 这个数据 只有B能装进去

你把塑封袋撕开了你再也装不回去了 是这么个过程

他把这个塑封袋传给A之后

A把它一撕开 得到了一个数据abc

然后A就去计算哈希值

看一看自己拿到的这个数据123

它的哈希值是不是abc

如果是abc那就没问题了 对吧

这个数据应该就是对的

如果不是abc的话 就说明这个数据可能是伪造的

你说这个邪恶的窃听者怎么办

邪恶的窃听者他有一组数据4adb5 他可以传给A

但问题是他可以计算的哈希值 我们刚才算出来了

哈希值应该是efg 对吧

这个efg它没有办法装到塑封袋里

也就是说他不能实现加密

这个数据传给A之后A一看 这个数据不对劲

没有经过加密 那就A就知道了

说你这个肯定是有问题 是有窃听者的 对吧

所以A就识别了这个窃听者和他想要的这个人的身份

那么在这个过程中

这个传输123的这个过程

我们就称之为密码传输

我们把它变到一个密码 然后再传过去

那么底下这个转成哈希函数把它传过去

这个过程我们就称之为数字签名

我可以确认这个信息是不是来源于我想要的那个人

有同学可能觉得很奇怪

说这个 你既然数字签名是谁都可以解密的

那么如果窃听者知道了这个信息的数字签名abc

它会不会知道原文123

这个不会的

因为哈希函数是一个什么函数

是个单向的 你从123推出abc很容易

但是你反对推 推不出来

就好像你知道一个人他的生日很容易

但是你倒过来说知道一个生日 问这个人是谁

那这个就推不出来了

这是第一个问题

第二个问题是说生日碰撞 在这个问题中有什么问题

就是因为吧

哈希函数是有限位数的 就像生日一样

所以两个不同的这个字符串可能对应同一个哈希函数

那么假如说这个窃听者把你这个信息改了

你本来想传输123 结果他改成了4adb5了 对不对

传给你了 传给你了之后

本来你通过验证它的哈希函数

你是可以知道这个信息不是你想要的

但问题是万一这两个它们的哈希函数是一样的

这就发生了碰撞

假如4adb5的哈希函数和123的哈希函数是一样的

那么这样就发生了碰撞

发生碰撞之后你就没有办法验证

说这个信息到底是不是来源于你想要的那个人了

因此生日碰撞对于这个数字签名来讲是一个威胁

我们以前说过这样一句话

说这个世界上大部分的物理学家都是数学家

但是并不是所有都是这样

有一些实验物理学家他数学能力可能没有那么强

但是 世界上所有的计算机科学家都是数学家

100% 为什么

因为计算机科学本质上其实就是一个用电脑实现的数学问题

大家如果喜欢我的视频

可以在西瓜视频和Youtube帐号李永乐老师里关注我。