伪随机二值序列的局部弱随机现象的快速检测方法

技术领域

本发明属于二值序列随机性检测领域，具体涉及一种伪随机二值序列的局部弱随机现象的快速检测方法。

背景技术

在密码学中，序列密码也被称为流密码，此类密码算法具有加密速度快、软硬件易于实现等优点。而对于序列密码来说，伪随机序列发生器是其核心部件，序列密码加密强度的优劣主要取决于伪随机序列发生器产生的二值序列(也即密钥流)的复杂性和随机性。目前对伪随机二值序列随机性测试的分析方法主要有频率测试、游程测试、自相关和重叠子序列测试等。除此之外，国际上还制定了几种常用的二值序列随机性测试套件，如TestU01、NIST SP800-22统计测试套件以及GM/T 0005-2012随机性检测规范等。近些年来，相关学者发现某些伪随机二值序列的局部范围内会出现部分可度量的短序列，一些整体上看似随机的二值序列其局部范围内会出现弱随机现象，这个现象将对序列密码的安全性造成严重威胁。目前国际常用的二值序列随机性检测标准很难对二值序列局部包含的随机性弱化现象进行精准检测，而对于序列密码来讲，伪随机序列发生器生成的密钥流(也即伪随机序列)是序列密码安全性的决定因素，因此，对伪随机序列性能的评估至关重要。

发明内容

基于以上不足之处，本发明提供一种伪随机二值序列的局部弱随机现象的快速检测方法，解决了现有技术无法对二值序列局部包含的随机性弱化现象进行精准检测的问题。本方法可快速且精确的检测某一伪随机二值序列中包含的所有局部弱随机现象，以此来检测二值序列的局部弱随机性和安全性。

本发明所采用的技术方案如下：一种伪随机二值序列的局部弱随机现象的快速检测方法，采用CUDA计算平台，其方法如下：根据待测伪随机二值序列构建初始化矩阵A，根据初始化矩阵A构建r-1行k列的弱随机检测矩阵B；基于r-1行k列的弱随机检测矩阵B，采用并行运算方式按顺序依次构建四个r-1行k列的方向矩阵D

本发明还具有如下具体技术特征：如上所述的一种伪随机二值序列的局部弱随机现象的快速检测方法，具体步骤如下：

S1：设某一伪随机二值序列ε(t)的长度为n，t代表某元素在二值序列ε(t)中的对应位置，以k为周期对此二值序列ε(t)进行折叠形成不同尺寸的初始化矩阵A，初始化矩阵A被定义为

r为矩阵的行数，k为列数，其中当伪随机二值序列ε(t)的长度n为偶数时k∈{2,3,…,n/2}，当n为奇数时k∈{2,3,…,(n-1)/2}，此外变量r表示为

式中

S2：根据初始化矩阵A构建r-1行k列的弱随机检测矩阵B，矩阵B被定义为

S3：基于r-1行k列的弱随机检测矩阵B，按顺序依次构建四个r-1行k列的方向矩阵D

四个方向矩阵D

其中，L

S4：生成完四个方向矩阵之后，二值序列ε(t)的局部弱随机现象便是利用这四个方向矩阵D

判断一个元素是否为临界值，其遵循的原则是：如果D

下一步，当确定一个临界值的位置(i,j)后，便执行矩阵扫描算法去搜索此临界值附近是否有局部弱随机现象，首先定义两个临时变量rStart和rEnd，并将D

下一步，判断公式1*(rEnd-rStart+2)≥n*thres是否成立，这里变量n和thres分别表示二值序列ε(t)的序列长度和局部弱随机现象的决策阈值(thres推荐设置为0.03)。如此式成立则输出一组变量(rStart,j,rEnd,j)，基于此组变量便可定位出二值序列ε(t)中的局部弱随机的具体位置，其具体位置表示为：

ε((rStart-1)*k+j)＝ε(l*k+j)，l∈[rStart,rEnd] (9)

如式1*(rEnd-rStart+2)≥n*thres不成立，则无需输出变量组(rStart,j,rEnd,j)，继续搜索并定义变量m，将j赋值给变量m，这里变量m代表局部弱随机现象的结束列。之后执行以下步骤：

步骤1：将m+1赋值给变量m，判断等式m＞D

步骤2:将max(rStart,D

步骤3：判断m＜D

步骤4：判断等式(m-j+1)*(rEnd-rStart+2)≥n*thres是否成立，如成立输出一组变量(rStart,j,rEnd,m)，基于此组变量便能定位出二值序列ε(t)中的局部弱随机的具体位置，其具体位置由下式表述：

ε((rStart-1)*k+j)…ε((rStart-1)*k+m)＝ε(l*k+j)…ε(l*k+m)，l∈[rStart,rEnd]

如不成立则跳转到步骤1。

本发明的优点及有益效果：

本发明实现了伪随机二值序列的局部弱随机现象的快速检测与定位，其可对任意伪随机二值序列的局部弱随机现象进行100％精确定位。本发明还可在一定程度上去评估序列密码的加密强度，其具有重要意义。本发明的算法采用了大量的自定义矩阵运算，为CUDA平台大规模并行计算的实现提供的方便，这样通过基于GPU芯片的CUDA平台便可大幅增加算法的执行速度。

附图说明

图1为本发明的方法流程图；

图2为核函数中grid的层次结构图；

图3为logistic伪随机二值序列的弱随机检测结果图。

具体实施方式

下面根据附图举例对本发明做进一步的说明：

实施例1

如图1所示，一种伪随机二值序列的局部弱随机现象的快速检测方法，采用CUDA计算平台，具体步骤如下：

S1：设某一伪随机二值序列ε(t)的长度为n，t代表某元素在二值序列ε(t)中的对应位置，例如二值序列ε(t)＝101101，长度n＝6，ε(3)＝1即为第三个元素。之后以k为周期对此二值序列ε(t)进行折叠形成初始化矩阵A，初始化矩阵A被定义为

r为矩阵的行数，k为列数，其中当伪随机二值序列ε(t)的长度n为偶数时k∈{2,3,…,n/2}，当n为奇数时k∈{2,3,…,(n-1)/2}，此外变量r可表示为

式中

S2：根据初始化矩阵A构建r-1行k列的弱随机检测矩阵B，矩阵B被定义为

S3：基于r-1行k列的弱随机检测矩阵B，进一步按顺序依次构建四个r-1行k列的方向矩阵D

四个方向矩阵D

其中，L

这里举例说明，设弱随机检测矩阵B为下式

由上式可知B

这里

S4：生成完四个方向矩阵之后，二值序列ε(t)的局部弱随机现象便是利用这四个方向矩阵D

判断一个元素是否为临界值，其遵循的原则是：如果D

下一步，当确定一个临界值的位置(i,j)后，便执行矩阵扫描算法去搜索此临界值附近是否有局部弱随机现象，首先定义两个临时变量rStart和rEnd，并将D

下一步，判断公式1*(rEnd-rStart+2)≥n*thres是否成立，这里变量n和thres分别表示二值序列ε(t)的序列长度和局部弱随机现象的决策阈值(thres推荐设置为0.03)。如此式成立则输出一组变量(rStart,j,rEnd,j)，基于此组变量便可定位出二值序列ε(t)中的局部弱随机的具体位置，其具体位置表示为：

ε((rStart-1)*k+j)＝ε(l*k+j)，l∈[rStart,rEnd] (10)

如式1*(rEnd-rStart+2)≥n*thres不成立，则无需输出变量组(rStart,j,rEnd,j)，继续搜索并定义变量m，将j赋值给变量m，这里变量m代表局部弱随机现象的结束列。之后执行以下步骤：

步骤1：将m+1赋值给变量m，判断等式m＞D

步骤2:将max(rStart,D

步骤3：判断m＜D

步骤4：判断等式(m-j+1)*(rEnd-rStart+2)≥n*thres是否成立，如成立输出一组变量(rStart,j,rEnd,m)，基于此组变量便能定位出二值序列ε(t)中的局部弱随机的具体位置，其具体位置由下式表述：

ε((rStart-1)*k+j)…ε((rStart-1)*k+m)＝ε(l*k+j)…ε(l*k+m)，l∈[rStart,rEnd] (11)

如不成立则跳转到步骤1。

实施例2

采用logistic混沌映射去产生伪随机二值序列，logistic映射的迭代公式如下

x

μ是控制参数，一般取值为4，x

式中Δx＝x