单比特频数检测和块内频数检测的快速实现研究*

2015-03-25张文科尹一桦徐远泽

通信技术 2015年9期

关键词：随机性频数字节

罗影，张文科，尹一桦，徐远泽

(卫士通信息产业股份有限公司，四川成都 610041)

单比特频数检测和块内频数检测的快速实现研究*

罗影，张文科，尹一桦，徐远泽

(卫士通信息产业股份有限公司，四川成都 610041)

随机序列在密码技术中占有非常重要的地位，随机性检测利用概率统计的方法对随机序列的随机性进行分析测试。美国国家标准与技术研究院(NIST)和我国国家密码管理局都发布了各自的随机性检测规范，二者都将单比特频数检测和块内频数检测作为其检测项。研究了单比特频数检测和块内频数检测的快速实现，提出了三种新的快速实现算法。这三种算法可以使单比特频数检测、块内频数检测和两种检测综合实现的速度分别提升29.2倍、15.5倍和32.8倍。

随机序列；单比特频数检测；块内频数检测

0 引言

随机序列在密码应用技术中占有非常重要的地位，香农的完善保密系统以及现代密码系统都将随机序列视为安全算法的根本。现在的计算机安全系统大量使用随机序列，如密钥的产生、数字签名、身份认证等，这充分体现了随机数的应用价值。

在应用密码学中，随机性检测的目的是采用概率统计方法分析测试随机数发生器等生成的序列的随机性，判断待检序列在统计上是否难以和真随机数区分开。不同的检测算法从不同的角度刻画待检序列与真随机序列之间的差距。经过多年的研究和发展后，随机性检测已经取得了丰硕的成果，目前已有大量的随机性检测算法，并且新的检测算法还在不断涌现。

美国国家标准与技术研究院(National Institute of Standards and Technology，NIST)发布的SP 800-22标准[1]建议了16种用于随机性测试的统计检验方法，以此为基础，德国发布了BSI AIS 30规范[2]。2009年，我国国家密码管理局发布了随机性检测规范[3]。

在实际应用中，随机性检测方法可用于评测按照特定标准生成的伪随机数据流，也可以对密码算法生成的数据流进行评测，如分组算法与特定工作模式相结合生成的数据流[4]。此举可为算法分析提供帮助，既减少了工作量，又可检测出其它方法无法发现的安全隐患。AES竞赛的候选算法均进行了随机性检测评估。目前已有大量的文章讨论随机性检测规范的快速现实以及相关检测项，比如Abdel-Rehim等[5]研究扑克检测的快速实现以及性能表现，Kaminsky[6]研究统计测试算法的GPU并行实现并建立并行实现的统计测试框架，Alcover等[7]研究一种新的统计测试方法以作为测试规范的补充。

单比特频数检测和块内频数检测是NIST的随机性检测规范和我国的随机性检测规范都有的检测项，研究这两种检测的快速实现是本文的主要工作。本文组织如下：首先，简单介绍两种检测算法；然后，分析测试并发现现有检测算法的效率问题；第三节分析算法效率较低的原因，并利用优化比特统计、复用比特统计、预先判断、消减除法等技术和方法，提出三种新的快速实现算法；第四节测试三种新算法的检测效率，这三种算法可以使得单比特频数检测、块内频数检测和两种检测组合实现的速度分别提升29.2倍、15.5倍和32.8倍；最后总结全文。

1 两种检测算法简介

我国的随机性检测规范有15项检测，NIST的随机性检测规范有16项检测，其中单比特频数检测和块内频数检测是二者共有的检测项。单比特频数检测的目的是保证0、1比特的个数大致相同。块内频数检测是检测待检序列的分组长度为m的子序列中1所占的比例，如果1的比例接近于一半则可以认为序列随机。当m取1时，块内频数检测退化为单比特频数检测。频数测试是随机性测试的基础，应首先进行。下面以我国的随机性检测规范为例讨论单比特频数检测和块内频数检测。

单比特频数检测的检测方法如下[3]:

1) 将待检序列εi中的比特0和1分别转化为-1和1，Xi=2εi-1,(1≤i≤n)。

2) 对其累加求和得到:

(1)

3) 根据中心极限定理:

(2)

计算统计值:

(3)

该统计值应服从标准正态分布。

4) 计算对应的P值：

(4)

其中erfc是余差函数。

(5)

5) 如果P-value≥α，则认为待检序列通过检测。

步骤5中的α为显著水平，我国的随机性检测规范规定α=0.01。

块内频数检测检测的检测方法如下[3]。

1) 将待检序列ε按长度m划分为N个非重叠的子序列，多余比特舍弃,其中:

N=⎣n/m」。

(6)

2) 计算各子序列中1所占的比例:

(7)

3) 所有子序列中1所占的比例的累加和作为统计量:

(8)

应服从自由度为N的χ2分布。

4) 计算P值:

(9)

其中igamc是余不完全伽马函数。

5) 如果P-value≥α，则认为待检序列通过检测。

我国的随机性检测规范规定块内频数检测的参数m取100。如前所述，频率检测在随机性检测中具有非常重要的作用，是其它检测的基础，因此这两种检测需具有极高的检测效率，以便快速剔除那些明显不满足随机性特征的待检样本。

2 两种检测算法的效率

在通常的实现方式中会先将待检数据转化为单比特表示，以便两种算法进行比特个数统计。单比特频数检测算法最关键也最耗时的步骤为步骤1和2的比特统计，计算统计量需要执行的操作数如表1，这里Xi利用查表得出(t[0]=-1,t[1]=1)。

表1 单比特频数检测算法的操作数量

块内频数检测算法中最关键也是最耗时的步骤为步骤1—3，计算统计量需要执行的操作数如表2。

表2 块内频数检测算法的操作数量

我国的随机性检测规范规定一组样本长1 000 000比特。下面统计了按普通方式实现这两个算法时检测一组样本所需的时间。测试平台为Intel Core i3 @3 400 MHz处理器、4 GB DDR3 1 600 MHz内存、WinXP SP3操作系统、VC6.0。测试结果见表3。

表3 两个检测项的性能(时间单位为微秒)

这里的两种检测综合实现是指这两种检测算法都实现。由上表可知，这两个检测算法的效率并不高。在实际检测中，需要更加快速高效的实现方式，以大大提高这两个算法的效率，增强其所起的筛选作用。

3 快速实现算法

3.1 效率分析与改进

单比特频数检测和块内频数检测的效率并不高的主要原因是比特数量统计采用了单比特统计方式，使得每次只能处理一个比特，CPU的字长没有得到充分利用。如果能一次处理多个比特，那么处理速度将会有明显的提升。并且，两个算法的统计量计算和判断过程还可以进行精简和优化。

改进算法的主要想法为：首先，利用查表法直接得出w个比特中比特1的个数；其次，因为两个算法都要用比特统计，所以比特统计的结果可以在两个算法之间共享；第三，优化统计检测公式，去除不必要的计算，降低计算复杂度。

查表的比特宽度记为w，则表中元素个数为2w。综合考虑连续w比特的获取难易度以及表的规模后发现w取8较合适。首先，8比特是一个字节，无需做字节间的拼接或拆分；其次，可以消除将待检数据拆分为单比特的步骤；第三，此时表的规模适中，为256字节，绝大部分处理器都能接受。

3.2 单比特频数检测优化

记B=B1‖…‖BL为连续多个字节形成的数组，其中Bi,1≤i≤L为一个字节。

记g(B,t)表示计算B1‖…‖Bt这t个字节中比特1的总个数。如果t取1，则g(B,1)表示计算字节B1中比特1的个数。g(B,1)可通过查表实现，g(B,t)可通过多次查表实现。

(10)

单比特频数检测算法优化如下。

算法1 优化实现的单比特频数检测算法

输入：n/8字节的数据Ei,1≤i≤n/8

输出：检测结果

1)初始化：Sn=0，i=1。

2)当i≤n/8时，执行

Sn=Sn+g(Ei,1)

i=i+1。

3)如果|Sn|s，通过检测；否则不通过。

优化实现算法中计算累加和Sn需要执行的操作数如表4。

表4 优化实现的单比特频数检测算法的操作数量

由表4可知，计算量降低为原来的1/8。此外消除余差函数也将大大减少计算量。

3.3 块内频数检测优化

块内频数检测的优化思想如前所述，另外还可以进一步提升效率。算法在计算统计量时使用了N次除法，但处理器执行除法运算的代价非常高，大约是乘法运算执行时间的10-20倍。优化统计量的计算过程可以减少除法次数。记Ni为第i个子序列中比特1的个数。统计量的计算可做如下简化:

(11)

利用上式计算统计量可将除法次数从N次降低为1次。

与单比特频数检测一样，可以根据余不完全伽马函数的性质求出V的界，以减少不完全伽马函数的计算。当α=0.01，N=10000时，若V

P-value=igamc(N/2,V/2)≥α。

(12)

另外，块内频数检测的参数m=100使得子序列没有按字节对齐。一个简单的解决办法是每次处理连续两个子序列共25字节。块内频数检测算法优化如下。

算法2 优化实现的块内频数检测算法

输入：n/8字节的数据Εi,1≤i≤n/8

输出：检测结果

1)N=⎣n/m」,S=0,i=1,a=m/2。

2)当i≤N时，执行

Ni=g(E25i+1,12)+g(E25i+13>>4,1)

Ni+1=g(E25i+14,12)+g(E25i+13∧0xF,1)

S=S+(Ni-a)2+(Ni+1-a)2

i=i+2。

3)统计量V=4S/m。

4)如果V

优化实现算法中，算出统计量V需要执行的操作量如表5。由表5可知，除法次数降低至1次，同时加减法次数也大大减少。

表5 优化实现的块内频数检测算法的操作数量

3.4 两种检测算法的合并优化

如前所述，比特统计的结果可在两个算法之间共享：两个子序列的比特1的个数相加，然后该和值累加便可得到整个序列中比特1的总数S1，最后累加和为|Sn|=|n-2S1|。

算法3 优化实现的合并检测算法

输入：n/8字节的数据Ei,1≤i≤n/8

输出：检测结果

1)N=⎣n/m」,S1=S2=0,i=1,a=m/2。

2)当i≤N时，执行

Ni=g(E25i+1,12)+g(E25i+13>>4,1)

Ni+1=g(E25i+14,12)+g(E25i+13∧0xF,1)

S2=S2+(Ni-a)2+(Ni+1-a)2

S1=S1+Ni+Ni+1

i=i+2。

3)分别计算两个统计量：

Sn=n-2S1,V2=4S2/m。

4)如果|Sn|≤s，则通过单比特频数检测；否则不通过。

5)如果V2

优化实现算法3中，需要执行的操作量如表6。由表6可知，算法3和算法2相比，仅仅是多了2N次加法即可计算出累加和。

表6 优化实现的合并检测算法的操作数量

4 实验结果

为了更准确地说明新算法的效率，利用前面的测试平台对算法1-3进行测试并统计各自的检测时间。测试结果见表7。

表7 算法性能对比(时间单位为微秒)T1和T2分别表示优化前和优化后的耗时

优化后的单比特频数检测速度提升29.2倍，这归功于累加和界的利用和比特统计方式的优化。优化后的块内频数检测速度提升15.5倍，这归功于除法数量的减少和比特统计方式的优化。优化后的两个检测速度提升32.8倍，这归功于比特统计的优化复用、累加和界的利用和除法数量的减少。

5 结语

本文对我国随机性检测规范和NIST随机性检测规范都采用的单比特频数检测和块内频数检测进行优化实现。通过组合利用比特统计的优化复用、累加和界和统计量优化等方法使得单比特频数检测、块内频数检测和两个检测组合实现时的速度分别提升了29.2倍、15.5倍和32.8倍。

本文提出的三个快速实现算法加快了单比特频数检测和块内频数检测的软件实现，有利于我国随机性检测规范和NIST随机性检测规范的推广和应用。在实际使用中，如果只需进行单比特频数检测，建议使用算法1；如果只需进行块内频数检测，建议使用算法2；如果两种检测都要使用，建议使用算法3。

[1] NIST SP800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications [S]. Revision 1a. Washington DC, USA: Information Technology Laboratory of National Institute of Standards and Technology, 2010.

[2] BSI AIS-20, AIS-30. Application Notes and Interpretation of the Scheme Functionality Classes and Evaluation Methodology for Deterministic and Physical Random Number Generators [S]. Berlin, Germany: German Federal Office for Information Security, 2008.

[3] 随机性检测规范[S]. 北京: 国家密码管理局, 2009. Randomness Test Specification [S]. Beijing: National Cryptography Administration, 2009.

[4] 罗影, 刘冬梅, 康红娟. NIST新分组密码工作模式及快速实现研究[J]. 通信技术, 2014, 47 (9):1066-1070. 1066-1070. LUO Ying, LIU Dong-mei, KANG Hong-juan. NIST New Block Cipher Modes of Operation and Their Fast Implementation[J]. Communications Technology, 2014, 47(9):1066-1070.

[5] Wael M. F. Abdel-Rehim, Ismail A. et al. Testing Randomness: Implementing Poker Approaches with Hands of Four Numbers [J]. IJCSI International Journal of Computer Science Issues, 2012, 9(3): 59-64.

[6] Kaminsky, A. GPU Parallel Statistical and Cube Test Analysis of the SHA-3 Finalist Candidate Hash Functions [EB/OL]. http://www.cs.rit.edu/～ark/parallelcrypto/sha3test01/, 2011.

[7] Edro María Alcover, Antonio Gullamon, María del Carmen Ruiz. A New Randomness Test for Bit Sequences [J]. Informatica, 2013, 24(3): 339-356.

Fast Implementation of Monobit Frequency Test and Frequency Test Within a Block

LUO Ying, ZHANG Wen-ke, YIN Yi-hua, XU Yuan-ze

(Westone Information Industry, Ltd., Chengdu Sichuan 610041,China)

Random sequence plays a very important role in the crypto technology. Randomness test, by using the method of probability statistics, analyzes and tests randomness of the sequence. US National Institute of Standards and Technology and China National Cryptography Administration respectively released their randomness test specifications. These two specifications both take monobit frequency test and frequency test within a block as the test items. This paper discusses the fast implementation of monobit frequency test and frequency test within a block, analyzes the hotspots, and proposes three fast implementation algorithms. These new algorithms can greatly improve the speed of monobit frequency test，frequency test within a block and their combined implementation.

random sequence;monobit frequency test;frequency test within a block

2015-04-03；

2015-07-14 Received date:2015-04-03；Revised date：2015-07-14

TP309

1002-0802(2015)09-1073-05