《密码学》09 随机数的产生与检验

密码学第九章随机数的产生与检验随机数的描述1随机数和伪随机数产生方法2随机数的检验方法3第九章随机数的产生与检验一、随机数的描述

随机数在密码学中扮演着非常重要的角色。如密码算法中使用随机数作为密钥可以使破译者通过猜测得到密钥的成功概率达到最小；相互鉴别方案中使用随机数充当现时可以挫败攻击者确定或猜到现时的努力等。下面我们对随机性进行简要描述。

若不特别说明，本节中的随机变量均为离散型随机变量。一、随机数的描述

若随机变量取每一种可能值的概率均相等，则称服从均匀分布。一、随机数的描述设1,2,,r是r个随机变量，1,2,,r的可能值的集合分别为X1,X2,,Xr，若对任意xiXi(i=1,2,,r)，均有p(1=x1,2=x2,,r=xr)=p(1=x1)p(2=x2)p(r=xr)则称1,2,,r相互独立。

设1,2,是随机变量序列，若对任意r2

，均有1,2,,r相互独立，则称1,2,相互独立。一、随机数的描述定义

由服从均匀分布且相互独立的随机变量

j(j=1,2,)构成的序列1,2,称为随机数序列。特别地，{0,1}上的随机数序列被称为二元随机数序列。备注：(1)

随机数序列是满足下面两个条件：（a）序列的元素服从均匀分布；（b）序列的任一截段相互独立。的随机变量序列。

(2)

随机数序列并非具体的序列，具体的序列只是它们的样本序列。一、随机数的描述在不引起混淆的情况下，由随机数序列产生的样本输出序列也往往被人们简称为随机数序列，而人们通常所说的随机数序列指的就是这类数值序列。

一、随机数的描述一个随机数序列应具有如下性质：(1)能通过已知的所有随机性统计检验（即随机性测试）。(2)不可预测。即使知道产生前面序列位的全部内容，也不可能预测出下一个随机位是什么。(3)无法重复产生。如果用完全同样的输入对序列发生器操作两次，将得到两个不相关的随机数序列。一、随机数的描述值得注意的是，由于利用计算机或数学的方法产生的输出状态总是过去的输入和当前状态确定的函数，因此是可预测的，从而决定了利用计算机或数学的方法不可能产生真正的随机数序列，它们最好只能产生出能够通过随机性测试但本质上并不是随机数序列的伪随机数序列，只有通过超数学的方法如用物理噪声等产生出来的序列才有可能是真正的随机数序列。

二、随机数和伪随机数产生方法

自然界中客观存在的随机现象是随机数的可能来源。随机数产生方法有人工产生和随机数发生器产生两种方式。

（一）随机数产生方法

1、人工方式采用抛硬币、掷骰子等人工方式产生随机数。二、随机数和伪随机数产生方法

2、随机数发生器采用物理噪声、放射性衰减等客观世界中存在的随机现象作为信号源产生随机数。由于这种产生随机数的方法在客观上是随机的，因此理论上可能产生出真正的随机数。

二、随机数和伪随机数产生方法

伪随机数发生器使用数学方法或算法技术产生随机数。（二）伪随机数产生方法由于数学方法或算法是确定性的，因此不可能产生出真正的随机数，最好只能产生出能通过随机性测试但本质上并不是随机数的伪随机数。三、随机数的检验方法由于人们无法从数学上证明一个序列发生器产生的数值序列的确是随机序列，因此在实际应用中人们常常借助于统计检验来判断一个数值序列随机性的好坏，考察序列发生器是否具有特定类型的弱点。这里仅介绍随机数的五项常规统计检验。五项常规统计检验

取s

s0s1s2…sn1是一个n长的二元序列。本部分介绍五种用来判别一条序列是否具有真正随机序列所具有的某些特殊性质的统计检验。如果序列没有通过某种检验，我们判断该序列不是随机序列，但值得注意的是，即使一条序列能够通过这五种检验，也不能保证它就是随机的，只是概率性地“证明”该序列是具有随机特性的序列。三、随机数的检验方法

1、频数检验（单比特检验）三、随机数的检验方法

频数检验的目的是考察序列中0,1的个数是否近似相等，即考察序列的0,1平衡性。

用n0,n1分别表示序列s中0的个数和1的个数。当n较大时，统计量

近似服从自由度为1的2分布。

三、随机数的检验方法检验方法：选定显著性水平，计算统计量X1的值，查表求自由度为1时，显著性水平下的2值x，比较x与X1的大小，若X1

x，则判断序列s通过频数检验；若X1

x，则判断序列s通不过频数检验。

2、序偶检验（双比特检验）三、随机数的检验方法

序偶检验的目的是考察相邻位转移概率是否合理，即考察序列中00，01，10和11的个数是否近似相等。

用n0,n1分别表示序列s中0的个数和1的个数，用n00,n01,n10,n11分别表示序列s中00，01，10，11的个数。

当n较大时，统计量

近似服从自由度为2的2分布。

三、随机数的检验方法检验方法：选定显著性水平，计算统计量X2的值，查表求自由度为2时，显著性水平下的2值x，比较x与X2的大小，若X2

x，则判断序列s通过序偶检验；若X2

x，则判断序列s通不过序偶检验。

3、扑克检验三、随机数的检验方法

扑克检验的目的是考察将序列以m比特为单位分组后（若最后一个分组不足m比特，则将其舍去），将每组m比特看作0~2m1的数时，序列中这些数的出现频次是否合理。即考察将序列以m比特为单位分组后，组序列中0,1,…,2m1的个数是否近似相等。可以取不同的m值进行扑克检验。由于m

1时扑克检验退化为频数检验，因此可将扑克检验看作频数检验的更一般形式。三、随机数的检验方法近似服从自由度为2m1的2分布。

选定一个整数m，令表示不大于的最大整数，则可将序列s分成k个不重叠的m比特长分组，将每组m比特看作0~2m1的数，用ni（0

i

2m1）表示s的k个分组中i出现的次数。当较大时，统计量三、随机数的检验方法检验方法：选定整数m和显著性水平，计算统计量X3的值，查表求自由度为2m1时，显著性水平下的2值x，比较x与X3的大小，若X3

x，则判断序列s通过扑克检验；若X3

x，则判断序列s通不过扑克检验。

4、自相关检验三、随机数的检验方法

自相关检验的目的是考察原序列和其经非循环移位变换后的序列之间的相关性，即考察序列是否具有可预测性。三、随机数的检验方法近似服从标准正态N(0,1)。因为A(d)太小或太大都不好，因此应使用双边检验。可以取不同的移位位数进行自相关检验。设移位位数为整数d，则d满足1

d

，序列s和它经d位移位变换后的序列对应位置上信号不同的个数，其中表示异或运算。当nd

较大时，统计量三、随机数的检验方法检验方法：选定整数d和显著性水平，计算统计量X4的值，查标准正态分布表求显著性水平下的双侧分位数x，比较x与X4的大小，若X4

x，则判断序列s通过自相关检验；若X4

x，则判断序列s通不过自相关检验。

5、游程检验三、随机数的检验方法

游程检验的目的是考察序列中0,1信号的游程分布是否合理，即考察序列中各个长度的0、1游程总数与随机序列中相应长度的0、1游程总数是否近似相等。三、随机数的检验方法

n长随机序列中长为i的0游程（或1游程）的个数的期望值为ei

(ni+3)/2i+2。令k为使ei5的最大整数i。Bi,Gi分别表示序列s中长为i的0游程和1游程的个数，1

i

k。统计量近似服从自由度为2k2的2分布。

三、随机数的检验方法检验方法：选定显著性水平，根据n计算ei和k的值，进而计算统计量X5的值，查表求自由度为2k2时，显著性水平下的2值x，比较x与X5的大小，若X5

x，则判断序列s通过游程检验；若X5

x，则判断序列s通不过游程检验。三、随机数的检验方法例：将下面的序列重复四次产生长为160比特的非随机序列

1110001100010001010011101111001001001001

检验在显著性水平

0.05下，该序列是否能通过频数检验、序偶检验、扑克检验（取m

3）、自相关检验（取d

8）和游程检验？三、随机数的检验方法解：(1)（频数检验）n084，n176，统计值X10.4；(2)（序偶检验）n0044，n0140，n1040，n1135，统计值X20.6252；

(3)（扑克检验）取m3，则k53，在s的53个分组中，000,001,010,011,100,101,110,111分别出现5,10,6,4,12,3,6,7次，统计值X39.6415；

(4)（自相关检验）取d8，计算得A(8)100，统计值X43.8933；三、随机数的检验方法(5)（游程检验）计算得e120.25，e210.06