不为有趣之事,何遣有涯之生
不失其所者久,死而不亡者寿

程序猿DE密码学(1) 随机数漫谈(上篇)

随机数漫谈(上)

阅读前希望你具备一定的密码学基础,理解了一些最基本的密码学名词

故事前言

从前有个锁匠,他制锁的手艺非常之高超,他自豪的和村子里的人说:"我制作的锁头十分坚固,小偷绝对打不开。"因此,村子里的人都为自己的房子装上了锁匠打的锁。锁匠的锁,真的非常坚固,没有人能够不用钥匙打开,但是大家发现了一个问题,锁匠做的每把锁的钥匙居然都是相同的!因此小偷只要得到任意一把钥匙就可以打开所有的房子上的锁了!这个粗心的锁匠~

此处输入图片的描述

锁和随机数

从上个故事里我们看到粗心的锁匠做的锁虽然坚固,但是却都用了相同的钥匙,导致一把钥匙可以打开所有的锁了。那么和我今天要讲的随机数有什么关系呢?我们知道在密码学里和安全最机密关系的就是对称密钥或私钥。那么要生成绝对安全性的对称密钥或者私钥,其实都是要用到随机数的,可以说随机数的生成方式就决定了密钥或私钥的安全性。如果我们用了相同的随机数或者不安全的随机数,那么生成的密钥或私钥就如同锁匠打造的锁,其实都用了相同的钥匙,你说随机数重要不重要?

随机数用来做什么?

在密码学里,其实很多地方都用到了随机数,但是我们平时都不太关注它,不知道默默无闻的随机数,在密码学领域时刻在默默无闻的发挥着重要的作用。例如如下场景中,我们就会使用到随机数:

  • 生成密钥

用于对称密码或者消息认证码

  • 生成密钥对

用于公钥密钥(非对称加密)和数字签名,公钥和私钥

  • 生成初始化向量(IV)

用于分组密码的CBC,CFB,OFB模式等

  • 生成nonce

用于防御重放攻击以及分组密码的CTR模式等

  • 生成盐

用于基于口令的密码(PBE)等

这些场景中,随机数扮演的角色都很重要,当然最重要的还是我们之前谈到的这里的头两项:生成密钥和生成密钥对。即使我们的密码算法强度再高,只要攻击者知道了密钥,你加密算法就会立刻形同虚设。而随机数就是让攻击者无法看穿密钥的关键所在。

随机数有哪些性质?

我们今天的随机概念只讲随机数和密码学之间的关系,不会涉及到哲学领域。
我们一般将随机数的性质分为以下三类:
- 随机性:不存在统计学偏差,是完全杂乱的数列(弱伪随机数)
- 不可预测性:不能从过去的数列推测出下一个出现的数(强伪随机数)
- 不可重现性:除非将数列本身保存下来,否则不能重现相同的数列(真伪随机数)

这三个性质的严格程度,是从上到下递增的。下面的性质包含了上面的性质,比如说:具备了不可重现性,就一定具备了不可预测性和随机性。
在密码学领域,至少具备了不可预测性性质的随机数,才可以被用于密码技术。
但是其实,密码学中的随机数也都只是做到了具备不可预测性而已,不会使用到不可重现性性质的随机数。为什么呢?我们接下来简单介绍下每个性质,你就一目了然了。

此处输入图片的描述

随机性

简单的说随机性就是杂乱无章的概念。不可以存在统计学上的偏差(所有值出现的频率相近),比如我们掷骰子,每个点数的出现都是随机的,进行统计的话,1-6的出现概率都是接近1/6的。我们平时玩个游戏,抽个奖,使用的随机数只要具备随机性就可以了。

但是密码学里不可行,因为只是具备随机性的话,不代表不会被看穿,就拿刚才掷骰子的例子,一个筛子只有1-6个点,只要攻击者知道你的随机数使用掷骰子的方式生成的(或者观察了一定次数后),那么就会知道下一次的点数肯定是1-6中的某一个数字,来6个攻击者,每个人猜一个数字,肯定有一个能猜中是吧。

所以,只具备随机性的随机数,我们称之为:弱伪随机数

不可预测性

密码学中的随机数,必须不能被看穿,所以要具备不可预测的性质才行。简单的说不可预测性就是事先不可能说中。复杂点说就是指攻击者在知道过去生成的伪随机数的前提下,依然无法预测出下一个生成出来的伪随机数。

其实伪随机数生成器的算法和密码学中加密算法一样,都是公开的。但是伪随机数生成器的种子(你可以理解成生成随机数需要的密钥)是保密的。所以即使攻击这知道了之前所有的伪随机数以及生成算法,他也无法预测出下一个生成出来的伪随机数,这就是不可预测性。

那么如何编写出不可预测性的伪随机数生成器呢?这是个很有趣的问题,我们的不可预测性其实是通过其他密码技术来实现的。例如:可以通过单向散列函数的单向性和密码的机密性来保证伪随机数生成器的不可预测性。后面会有详细的代码示例。

我们把具备不可预测性的随机数称之为:强伪随机数

不可重现性

不可重现性就是指无法重现和某一种随机数列完全相同的数列的性质。如果除了将随机数列本身保存下来以外,没有其他方法重现该数列。

告诉大家一个不幸的消息:使用软件是无法生成出具备不可重复性的随机数列的。软件只能生成伪随机数列,所以软件实现的随机数生成器,我们就称作伪随机数生成器。那这是什么原因呢?那是因为运行软件的计算机本身仅具备有限的状态集,在内部状态相同的情况下,软件必然会生成相同的数,所以通过软件生成的随机数,一定会重复。重复的长度我们称之为周期。周期可以很短,也可以很长,但终归还是有限的。

要生成具备不可重复性的随机数列,需要从不可重现的物理现象中获取信息。比如周围的温度和声音变化,鼠标的移动位置信息,键盘输入的时间间隔,放射线测量仪输出值等。根据硬件中获取到的信息生成的数列,一般可以认为是具备不可重复性的随机数列。

目前,已经出现了用传感器感知热度变化,并根据这一变化的信息来生成具备不可重复性的随机数列的硬件设备。但是要让这样的设备成为计算机的标配,那还需要比较长的一段时间。

我们把具备不可重复性的随机数称之为:真随机数

本文的漫谈就先到这里,下篇中我会给大家介绍伪随机数生成器的设计方法以及简单代码示例,还有一些常见的攻击方式。
最后问大家一个问题:我们反复掷骰子所生成的数列,是否具备不可重复性呢?答案见《随机数漫谈(下)》末尾

未经允许不得转载:菡萏如佳人 » 程序猿DE密码学(1)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

欢迎加入紫牛小筑

进入小筑关于作者