第11卷第4期 智能系统学报 Vol.11 No.4 2016年8月 CAAI Transactions on Intelligent Systems Aug.2016 D0I:10.11992/is.201606002 网络出版地址：http://www.cnki.net/kcms/detail,/23.1538.TP.20160808.0830.012.html 随机序列的扑克检测优化研究 杨先伟，康红娟2，廖祖华34 (1.无锡职业技术学院基础部，江苏无锡214121：2.四川长虹电器股份有限公司，四川成都610041；3.江南大学， 江苏无锡214122；4.江南大学智能系统与网络计算研究所，江苏无锡214122) 摘要：现代计算机系统的安全性依赖于二元随机序列，随机性检测利用概率统计方法对二元序列的随机性进行分 析测试。我国国家密码管理局发布了随机性检测规范，扑克检测为其中一个检测项。本文通过充分分析扑克检测 效率不高的原因有针对性地提出一种新的快速实现算法，优化算法充分利用CPU字长一次处理多个比特，将m为4 和8的情况整合在一起，减少不必要的处理流程。同时精简并优化统计量的计算和判断过程，避免余不完全伽马函 数的计算。分析和实验的结果表明该优化算法可以使得扑克检测的速度提升9.5倍左右。 关键词：二元序列：随机序列：随机数发生器：随机性检测：扑克检测：密码算法：效率分析：余不完全伽玛函数 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)04-0513-06 中文引用格式：杨先伟，康红娟，廖祖华.随机序列的扑克检测优化研究[J].智能系统学报，2016,11(4)：513-518. 英文引用格式：YANG Xianwei,KANG Hongjuan,LIAO Zuhua..Study on optimization of poker test random sequences[J].CAAl Transactions on Intelligent Systems,2016,11(4):513-518. Study on optimization of poker test random sequences YANG Xianwei',KANG Hongjuan2,LIAO Zuhua4 (1.Department of Fundamental Courses,Wuxi Institute of Technology,Wuxi 214121,China;2.Sichuan Changhong Electric Co., Ltd.,Chengdu 610041,China;3.School of Science,Jangnan University,Wuxi 214122,China;4.Institute of Intelligence System &Network Computing,Jiangnan University,Wuxi 214122,China) Abstract:The security of modern computer systems depends on binary random sequences,such as cipher algo- rithms keys,RSA algorithm prime numbers,the digital signature system,the identity authentication system,etc. Randomness tests analyze and test the randomness of sequences,using probability and statistics.The Chinese Na- tional Cryptography Administration has released national randomness test specifications and the Poker test is one of these.This paper analyzed the reasons for the low efficiency of the Poker test,then proposes a fast implementation algorithm.This new algorithm deals with bytes by making full use of CPU word length,integrates the detection process,and reduces some unnecessary operations under the conditions when m equals 4 and 8.At the same time, the method reduces and optimizes the computation and assessment of statistical quantity,avoiding computation of incomplete gamma functions.The results show that the efficiency of the new algorithm increases 9.5 fold. Keywords:binary sequence;random sequence;pseudorandom bit generator;randomness test;poker test;encryp- tion algorithms;efficiency analysis;incomplete gamma functions. 二元随机序列在密码应用中占有举足轻重的地 收稿日期：2016-06-01.网络出版日期：2016-08-08. 位。现在大量的计算机系统的安全性需要依赖于二 基金项目：国家自然科学基金项目(61170121,11401259)：江苏省自然元随机序列，比如各种密码算法中使用的密钥、非对 科学基金项目(BK20151117). 通信作者：廖祖华.E-mail:liaozuhua57@163.com. 称密码算法RSA加密、数字签名方案中大素数的生
第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６００２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３０．０１２．ｈｔｍｌ 随机序列的扑克检测优化研究 杨先伟１ ，康红娟２ ，廖祖华３，４ （１． 无锡职业技术学院 基础部，江苏 无锡 ２１４１２１； ２． 四川长虹电器股份有限公司，四川 成都 ６１００４１； ３． 江南大学， 江苏 无锡 ２１４１２２； ４．江南大学 智能系统与网络计算研究所，江苏 无锡 ２１４１２２） 摘 要：现代计算机系统的安全性依赖于二元随机序列，随机性检测利用概率统计方法对二元序列的随机性进行分 析测试。 我国国家密码管理局发布了随机性检测规范，扑克检测为其中一个检测项。 本文通过充分分析扑克检测 效率不高的原因有针对性地提出一种新的快速实现算法，优化算法充分利用 ＣＰＵ 字长一次处理多个比特，将 ｍ 为 ４ 和 ８ 的情况整合在一起，减少不必要的处理流程。 同时精简并优化统计量的计算和判断过程，避免余不完全伽马函 数的计算。 分析和实验的结果表明该优化算法可以使得扑克检测的速度提升 ９．５ 倍左右。 关键词：二元序列；随机序列；随机数发生器；随机性检测；扑克检测；密码算法；效率分析；余不完全伽玛函数 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０５１３－０６ 中文引用格式：杨先伟，康红娟，廖祖华． 随机序列的扑克检测优化研究［Ｊ］． 智能系统学报， ２０１６， １１（４）： ５１３－５１８． 英文引用格式：ＹＡＮＧ Ｘｉａｎｗｅｉ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ， ＬＩＡＯ Ｚｕｈｕａ． Ｓｔｕｄｙ ｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｐｏｋｅｒ ｔｅｓｔ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ５１３－５１８． Ｓｔｕｄｙ ｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｐｏｋｅｒ ｔｅｓｔ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅｓ ＹＡＮＧ Ｘｉａｎｗｅｉ １ ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ ２ ， ＬＩＡＯ Ｚｕｈｕａ ３，４ （１． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｆｕｎｄａｍｅｎｔａｌ Ｃｏｕｒｓｅｓ， Ｗｕｘｉ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｘｉ ２１４１２１， Ｃｈｉｎａ； ２． Ｓｉｃｈｕａｎ Ｃｈａｎｇｈｏｎｇ Ｅｌｅｃｔｒｉｃ Ｃｏ．， Ｌｔｄ．， Ｃｈｅｎｇｄｕ ６１００４１， Ｃｈｉｎａ； ３． Ｓｃｈｏｏｌ ｏｆ Ｓｃｉｅｎｃｅ， Ｊａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ； ４．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｙｓｔｅｍ ＆Ｎｅｔｗｏｒｋ Ｃｏｍｐｕｔｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｓｅｃｕｒｉｔｙ ｏｆ ｍｏｄｅｒｎ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ ｄｅｐｅｎｄｓ ｏｎ ｂｉｎａｒｙ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅｓ， ｓｕｃｈ ａｓ ｃｉｐｈｅｒ ａｌｇｏ⁃ ｒｉｔｈｍｓ ｋｅｙｓ， ＲＳＡ ａｌｇｏｒｉｔｈｍ ｐｒｉｍｅ ｎｕｍｂｅｒｓ， ｔｈｅ ｄｉｇｉｔａｌ ｓｉｇｎａｔｕｒｅ ｓｙｓｔｅｍ， ｔｈｅ ｉｄｅｎｔｉｔｙ ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｓｙｓｔｅｍ， ｅｔｃ． Ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔｓ ａｎａｌｙｚｅ ａｎｄ ｔｅｓｔ ｔｈｅ ｒａｎｄｏｍｎｅｓｓ ｏｆ ｓｅｑｕｅｎｃｅｓ， ｕｓｉｎｇ ｐｒｏｂａｂｉｌｉｔｙ ａｎｄ ｓｔａｔｉｓｔｉｃｓ． Ｔｈｅ Ｃｈｉｎｅｓｅ Ｎａ⁃ ｔｉｏｎａｌ Ｃｒｙｐｔｏｇｒａｐｈｙ Ａｄｍｉｎｉｓｔｒａｔｉｏｎ ｈａｓ ｒｅｌｅａｓｅｄ ｎａｔｉｏｎａｌ ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔ ｓｐｅｃｉｆｉｃａｔｉｏｎｓ ａｎｄ ｔｈｅ Ｐｏｋｅｒ ｔｅｓｔ ｉｓ ｏｎｅ ｏｆ ｔｈｅｓｅ． Ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｄ ｔｈｅ ｒｅａｓｏｎｓ ｆｏｒ ｔｈｅ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ Ｐｏｋｅｒ ｔｅｓｔ， ｔｈｅｎ ｐｒｏｐｏｓｅｓ ａ ｆａｓｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｌｇｏｒｉｔｈｍ． Ｔｈｉｓ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｄｅａｌｓ ｗｉｔｈ ｂｙｔｅｓ ｂｙ ｍａｋｉｎｇ ｆｕｌｌ ｕｓｅ ｏｆ ＣＰＵ ｗｏｒｄ ｌｅｎｇｔｈ， ｉｎｔｅｇｒａｔｅｓ ｔｈｅ ｄｅｔｅｃｔｉｏｎ ｐｒｏｃｅｓｓ， ａｎｄ ｒｅｄｕｃｅｓ ｓｏｍｅ ｕｎｎｅｃｅｓｓａｒｙ ｏｐｅｒａｔｉｏｎｓ ｕｎｄｅｒ ｔｈｅ ｃｏｎｄｉｔｉｏｎｓ ｗｈｅｎ ｍ ｅｑｕａｌｓ ４ ａｎｄ ８． Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ， ｔｈｅ ｍｅｔｈｏｄ ｒｅｄｕｃｅｓ ａｎｄ ｏｐｔｉｍｉｚｅｓ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ ａｓｓｅｓｓｍｅｎｔ ｏｆ ｓｔａｔｉｓｔｉｃａｌ ｑｕａｎｔｉｔｙ， ａｖｏｉｄｉｎｇ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｇａｍｍａ ｆｕｎｃｔｉｏｎｓ． Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｎｃｒｅａｓｅｓ ９．５ ｆｏｌｄ． Ｋｅｙｗｏｒｄｓ： ｂｉｎａｒｙ ｓｅｑｕｅｎｃｅ； ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ； ｐｓｅｕｄｏｒａｎｄｏｍ ｂｉｔ ｇｅｎｅｒａｔｏｒ； ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔ； ｐｏｋｅｒ ｔｅｓｔ； ｅｎｃｒｙｐ⁃ ｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ； ｅｆｆｉｃｉｅｎｃｙ ａｎａｌｙｓｉｓ； ｉｎｃｏｍｐｌｅｔｅ ｇａｍｍａ ｆｕｎｃｔｉｏｎｓ． 收稿日期：２０１６－０６－０１． 网络出版日期：２０１６－０８－０８． 基金项目：国家自然科学基金项目（ ６１１７０１２１，１１４０１２５９）；江苏省自然 科学基金项目（ＢＫ２０１５１１１７）． 通信作者：廖祖华． Ｅ⁃ｍａｉｌ：ｌｉａｏｚｕｈｕａ５７＠ １６３．ｃｏｍ． 二元随机序列在密码应用中占有举足轻重的地 位。 现在大量的计算机系统的安全性需要依赖于二 元随机序列，比如各种密码算法中使用的密钥、非对 称密码算法 ＲＳＡ 加密、数字签名方案中大素数的生
.514 智能系统学报 第11卷 成以及挑战应答身份识别系统中的挑战数等，这些 测、二元推导检测、自相关检测。扑克检测不仅出现 都充分体现了二元随机序列的实际使用价值。在应 在我国的随机性检测规范中，也出现在很多别的基本 用密码学中，随机性检测采用概率统计的方法对随 随机性检测中，比如作为5项基本检测项中的一项出 机数发生器等生成的二元序列的随机性进行分析和 现，5项基本检测包括单比特频数检测、序偶检测、扑 检测，判断待检序列在统计上是否难以和真随机数 克检测、游程分布检测、自相关检测。 区分开来。不同的随机性检测算法从不同的侧面分 我国随机性检测规范对扑克检测的执行流程分 析刻画待检二元序列与真随机序列之间的差距。经 为4个步骤，描述如下)： 过多年的发展，随机性检测算法已取得丰硕成果，出 1)将长度为n的二元待检序列61s2…6n划分 现并颁布了大量的随机性检测算法和相关标准，与 为N=n/m个长度为m的非重叠子序列，将多余的 此同时，大量新的随机性检测算法还在源源不断地 比特舍弃。统计第i种子序列模式出现的频数，用 涌现。美国国家标准与技术研究院(National Insti- n:（1≤i≤2m)表示。我国随机性检测规范规定m tute of Standards and Technology,NIST)发布了SP 取4和8。 800-22标准)，其中建议了16种用于随机性测试 2)计算统计值： 的统计检侧方法。德国以此规范为基础发布了BSI (1) AIS30规范)。我国国家密码管理局于2009年颁 i=1 布了适用于我国的随机性检测规范)。随机性检 3)计算P值： 测在实际应用中有重要的实用价值，不仅可以用于 Palue igamc 2m-1V 22 (2) 测评按照密码算法或特定标准生成的伪随机数据的 性质，如分组算法与某些工作模式相结合生成的数 4)如果P≥a,则认为待检序列通过检测。 据流4)，还可以分析测试以杂凑算法为核心生成的 式(2)中使用的gamc是余不完全伽马函数，该 数据流，如我国SM3杂凑算法)生成的数据流。上 函数的定义为 述工作不仅可以帮助算法分析，减少分析的难度和 e-a-dt 复杂度，而且可以检测出其他检测方法难以检测出 igame(a,x)=1 T(a),a>0,x>0(3) 的某些安全性隐患。因此，国际上很多著名的密码 式中：T(x)为伽马函数，该函数的定义为 算法竞赛均进行了大量的随机性检测评估，比如 AES密码算法竞赛、欧洲的NISSIE竞赛、estream算 r(x)=erd山，x>0 (4) 法竞赛等，我国的祖冲之序列密码算法[6刀也进行 扑克检测在很多基本的随机性检测中都会出 了大量相关的随机性检测。此外，还有大量文章对 现，因此这是一种基础检测项，在随机性检测中具有 随机性检测算法和标准进行进一步的分析讨论，比 非常重要的作用。在实际应用中，该检测项需要具 如讨论随机性检测规范的各项检测项的快速实现， 有较高的检测速度，以便快速剔除那些明显不满足 例如研究单比特检测以及块内频数的快速实现]， 随机性特征的样本。 尝试新的统计测试方法以便作为现有测试规范的有 益补充9)，考虑统计测试算法的GPU并行化，搭建 2原算法的检测效率分析 可并行计算的统计测试实现框架。本文的研究 在实际应用中，送入的待检序列数据多为字节 重点是扑克检测的快速实现，因为扑克检测不仅是 序列，但传统的实现方式会根据算法描述先将待检 我国随机性检测规范的检测项，而且也是很多基本 数据转化为单比特表示，然后对m=4和m=8各执 的随机性检测的必检项目之一，所以此项检测的快 行一遍算法中的1)~4)的操作。扑克检测算法中 速实现研究具有非常重要的现实意义。 3)和4)在一次样本检测中执行两次，1)的执行次数 1扑克检测 则为O(n):2)的执行次数则为0(1)，所以其中最 关键也最耗时操作为准备工作的字节转比特操作以 我国的随机性检测规范有15项检测，包括：单比 及1)的统计各种频数。 特频数检测、块内频数检测、扑克检测、重叠子序列检 在分析算法的计算量时，本文采用如下缩略符 测、游程总数检测、块内最大1游程检测、矩阵秩检 号：XOR表示异或运算：SHIT表示左/右移位运 测、累积和检测、近似熵检测、线性复杂度检测、Mar- 算；ADD表示加法运算：AND表示与运算。 r通用统计检测、离散傅里叶变换检测、游程分布检 传统的扑克检测中最关键也最耗时的步骤是
成以及挑战应答身份识别系统中的挑战数等，这些 都充分体现了二元随机序列的实际使用价值。 在应 用密码学中，随机性检测采用概率统计的方法对随 机数发生器等生成的二元序列的随机性进行分析和 检测，判断待检序列在统计上是否难以和真随机数 区分开来。 不同的随机性检测算法从不同的侧面分 析刻画待检二元序列与真随机序列之间的差距。 经 过多年的发展，随机性检测算法已取得丰硕成果，出 现并颁布了大量的随机性检测算法和相关标准，与 此同时，大量新的随机性检测算法还在源源不断地 涌现。 美国国家标准与技术研究院（Ｎａｔｉｏｎａｌ Ｉｎｓｔｉ⁃ ｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ＮＩＳＴ） 发布了 ＳＰ ８００⁃２２ 标准［１］ ，其中建议了 １６ 种用于随机性测试 的统计检测方法。 德国以此规范为基础发布了 ＢＳＩ ＡＩＳ ３０ 规范［２］ 。 我国国家密码管理局于 ２００９ 年颁 布了适用于我国的随机性检测规范［３］ 。 随机性检 测在实际应用中有重要的实用价值，不仅可以用于 测评按照密码算法或特定标准生成的伪随机数据的 性质，如分组算法与某些工作模式相结合生成的数 据流［４］ ，还可以分析测试以杂凑算法为核心生成的 数据流，如我国 ＳＭ３ 杂凑算法［５］生成的数据流。 上 述工作不仅可以帮助算法分析，减少分析的难度和 复杂度，而且可以检测出其他检测方法难以检测出 的某些安全性隐患。 因此，国际上很多著名的密码 算法竞赛均进行了大量的随机性检测评估，比如 ＡＥＳ 密码算法竞赛、欧洲的 ＮＩＳＳＩＥ 竞赛、ｅｓｔｒｅａｍ 算 法竞赛等，我国的祖冲之序列密码算法［６－７］ 也进行 了大量相关的随机性检测。 此外，还有大量文章对 随机性检测算法和标准进行进一步的分析讨论，比 如讨论随机性检测规范的各项检测项的快速实现， 例如研究单比特检测以及块内频数的快速实现［８］ ， 尝试新的统计测试方法以便作为现有测试规范的有 益补充［９］ ，考虑统计测试算法的 ＧＰＵ 并行化，搭建 可并行计算的统计测试实现框架［１０］ Ｐ 。 本文的研究 重点是扑克检测的快速实现，因为扑克检测不仅是 我国随机性检测规范的检测项，而且也是很多基本 的随机性检测的必检项目之一，所以此项检测的快 速实现研究具有非常重要的现实意义。 １ 扑克检测 我国的随机性检测规范有 １５ 项检测，包括：单比 特频数检测、块内频数检测、扑克检测、重叠子序列检 测、游程总数检测、块内最大 １ 游程检测、矩阵秩检 测、累积和检测、近似熵检测、线性复杂度检测、Ｍａｕｒ⁃ ｅｒ 通用统计检测、离散傅里叶变换检测、游程分布检 测、二元推导检测、自相关检测。 扑克检测不仅出现 在我国的随机性检测规范中，也出现在很多别的基本 随机性检测中，比如作为 ５ 项基本检测项中的一项出 现，５ 项基本检测包括单比特频数检测、序偶检测、扑 克检测、游程分布检测、自相关检测。 我国随机性检测规范对扑克检测的执行流程分 为 ４ 个步骤，描述如下［３］ ： １） 将长度为 ｎ 的二元待检序列 ε１ε２…εｎ 划分 为 Ｎ ＝ ｎ ／ ｍ 个长度为 ｍ 的非重叠子序列，将多余的 比特舍弃。 统计第 ｉ 种子序列模式出现的频数，用 ｎｉ （ １ ≤ ｉ ≤２ ｍ ）表示。 我国随机性检测规范规定 ｍ 取 ４ 和 ８。 ２） 计算统计值： Ｖ ＝ ２ ｍ Ｎ ∑ ２ｍ ｉ ＝ １ ｎ ２ ( ｉ ) － Ｎ （１） ３） 计算 Ｐ 值： Ｐｖａｌｕｅ ＝ ｉｇａｍｃ ２ ｍ － １ ２ ， Ｖ ２ æ è ç ö ø ÷ （２） ４） 如果 Ｐｖａｌｕｅ ≥ α ，则认为待检序列通过检测。 式（２）中使用的 ｉｇａｍｃ 是余不完全伽马函数，该 函数的定义为 ｉｇａｍｃ（α，ｘ） ＝ １ － ∫ ¥ ｘ ｅ －ｔ ｔ α－１ ｄｔ Γ（α） ，α ＞ ０，ｘ ＞ ０（３） 式中： Γ（ｘ） 为伽马函数，该函数的定义为 Γ（ｘ） ＝ ∫ ¥ ０ ｅ －ｔ ｔ ｘ－１ ｄｔ，ｘ ＞ ０ （４） 扑克检测在很多基本的随机性检测中都会出 现，因此这是一种基础检测项，在随机性检测中具有 非常重要的作用。 在实际应用中，该检测项需要具 有较高的检测速度，以便快速剔除那些明显不满足 随机性特征的样本。 ２ 原算法的检测效率分析 在实际应用中，送入的待检序列数据多为字节 序列，但传统的实现方式会根据算法描述先将待检 数据转化为单比特表示，然后对 ｍ ＝ ４ 和 ｍ ＝ ８ 各执 行一遍算法中的 １） ～ ４）的操作。 扑克检测算法中 ３）和 ４）在一次样本检测中执行两次，１）的执行次数 则为 Ｏ（ｎ） ；２）的执行次数则为 Ｏ（１） ，所以其中最 关键也最耗时操作为准备工作的字节转比特操作以 及 １）的统计各种频数。 在分析算法的计算量时，本文采用如下缩略符 号：ＸＯＲ 表示异或运算； ＳＨＩＦＴ 表示左／ 右移位运 算；ＡＤＤ 表示加法运算；ＡＮＤ 表示与运算。 传统的扑克检测中最关键也最耗时的步骤是 ·５１４· 智 能 系 统 学 报 第 １１ 卷
第4期 杨先伟，等：随机序列的扑克检测优化研究 .515. 1),因此以下分析执行一组样本检测时1)所需的运 数据并更新频数，即 算量。在m=4和m=8时1)需分别执行n次 SHIFT、n次LOAD和2n次ADD,即合计总共需执行 C[E]=c[E]+1,0≤i≤g-1(5) 2n次SHIFT、2n次LOAD和4n次ADD。1)进行一 参数m=4时的频数统计方式为先加载字节数 组样本检测所需执行的操作数详情如表1。 据，接着获取高半字节和低半字节， 表1扑克检测算法的操作数量 Table 1 The calculation of poker test H=E≥4L=E,N0F,0≤i≤ -1(6) 步骤1 运算量 最后利用获取的高半字节和低半字节更新对应 m=4 nSHIFT nLOAD +2nADD 的频数，即 m=8 nSHIFT +nLOAD +2nADD C4[H]=C4[H]+1,C4[L]=C4[L]+1(7) 合计 2nSHIFT +2nLOAD +4nADD 参数m=4时和m=8时的统计过程分开实现 会使得待检数据序列重复加载，这也是扑克检测效 按我国随机性检测规范规定一组样本的大小n为 率不高的主要原因之一。如果能更进一步将参数在 10bit,因此由表1的统计结果可知，算法的运算量不 两种不同取值时的统计过程合并在一起，则可以减 小，执行效率不会太快。在实际检测中，需要加快扑克 少大量的数据重复加载。参数m取4和8合并实 检测的执行速度，以增强它的基础筛选作用。 现时的频数统计方式为先加载字节数据，然后获取 3 优化思想和优化算法 高半字节和低半字节，最后更新m=4的频数和m= 8的频数，合并式(5)~(7)，可得 根据上一节的分析可知，扑克检测的效率不高 的主要原因是计算统计量时出现了以下问题： H=E:≥4，L=E:∧0xF,0≤i≤n/8-1 1)采用了单比特统计方式，每次仅仅处理一个 C4[H]=C4[H]+1,C4[L]=C4[L]+1 比特，CPU的字长没有得到充分利用：如果一次处 Cs[E:]=Cs[E;]+1 (8) 理多个比特则处理速度将有明显的提升： 统计量的计算和判断过程还可以进行精简和优 2)对参数m=4和m=8,传统实现方式会各执 化：可根据余不完全伽马函数的性质预先求出 行一遍算法中的1)~4)的操作，存在相同数据反复 P.le≥a时统计量V的阈值，让统计值V直接和此 加载的情况： 阈值比较，如此可以减少余不完全伽马函数的计算 3)算法的统计量计算和判断过程没有精简和 次数。 优化，存在不必要的余不完全伽马函数的计算。 记m=4时的统计量为V,即 15 针对扑克检测原算法出现的效率不高问题，下 -642c,[)-4 (9) 面有针对性地提出几点优化想法。具体的优化想法 n 0 如下： 记m=8时的统计量为V,即 255 1)一次处理多个比特，比如一个字节或半个字 -2048 (10) 节，加快频数统计过程： n =0 2)对m=4和m=8整合在一起实现，减少不必 计算统计值所用的余不完全伽马函数满足性质 要的数据加载： igame(a,0)=1,igamc(a,o)=0。经简单计算可 3)精简并优化统计量的计算和判断过程，事先 知，当显著水平α=0.01，m=4时，统计量V,的阈值 计算P≥a时统计量V的阈值，让统计值直接和 为入4=30.577914：当显著水平a=0.01,m=8时， 此阈值比较，避免每个样本都计算两次余不完全伽 统计量V.的阈值为入g=310.457388。即如果V,< 马函数。 入，且'。<入g则认为待检序列通过检测。根据以上 记待检序列为n/8字节的字节数据E:,E:= 描述，优化实现的扑克检测算法如下。 E+:‖E数+2‖…‖eg:+8,0≤i≤n/8-1。为区分两 算法1优化实现的扑克检测算法 种不同参数取值时各种序列模式出现的频数，记 输入n/8字节的数据E:,0≤i≤n/8-1: C.[],0≤i≤15为m=4时各种序列模式出现的 输出检测结果。 频数，记Cg[i],0≤i≤255为m=8时各种序列模 1)初始化数据：i=0。 式出现的频数。 C4[j]=0,0≤j≤15， 参数m=8时的频数统计方式为直接加载字节 Cg[j]=0,0≤j≤255
１），因此以下分析执行一组样本检测时 １）所需的运 算量。 在 ｍ ＝ ４ 和 ｍ ＝ ８ 时 １） 需分别执行 ｎ 次 ＳＨＩＦＴ、ｎ 次 ＬＯＡＤ 和 ２ｎ 次 ＡＤＤ，即合计总共需执行 ２ｎ 次 ＳＨＩＦＴ、２ｎ 次 ＬＯＡＤ 和 ４ｎ 次 ＡＤＤ。 １）进行一 组样本检测所需执行的操作数详情如表 １。 表 １ 扑克检测算法的操作数量 Ｔａｂｌｅ １ Ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｐｏｋｅｒ ｔｅｓｔ 步骤 １ 运算量 ｍ ＝ ４ ｎＳＨＩＦＴ ＋ ｎＬＯＡＤ ＋２ｎＡＤＤ ｍ ＝ ８ ｎＳＨＩＦＴ ＋ｎＬＯＡＤ ＋２ｎＡＤＤ 合计 ２ｎＳＨＩＦＴ ＋２ｎＬＯＡＤ ＋４ｎＡＤＤ 按我国随机性检测规范规定一组样本的大小 ｎ 为 １０ ６ ｂｉｔ，因此由表 １ 的统计结果可知，算法的运算量不 小，执行效率不会太快。 在实际检测中，需要加快扑克 检测的执行速度，以增强它的基础筛选作用。 ３ 优化思想和优化算法 根据上一节的分析可知，扑克检测的效率不高 的主要原因是计算统计量时出现了以下问题： １）采用了单比特统计方式，每次仅仅处理一个 比特，ＣＰＵ 的字长没有得到充分利用；如果一次处 理多个比特则处理速度将有明显的提升； ２）对参数 ｍ ＝ ４ 和 ｍ ＝ ８，传统实现方式会各执 行一遍算法中的 １） ～４）的操作，存在相同数据反复 加载的情况； ３）算法的统计量计算和判断过程没有精简和 优化，存在不必要的余不完全伽马函数的计算。 针对扑克检测原算法出现的效率不高问题，下 面有针对性地提出几点优化想法。 具体的优化想法 如下： １）一次处理多个比特，比如一个字节或半个字 节，加快频数统计过程； ２）对 ｍ ＝ ４ 和 ｍ ＝ ８ 整合在一起实现，减少不必 要的数据加载； ３）精简并优化统计量的计算和判断过程，事先 计算 Ｐｖａｌｕｅ ≥ α 时统计量 Ｖ 的阈值，让统计值直接和 此阈值比较，避免每个样本都计算两次余不完全伽 马函数。 记待检序列为 ｎ ／ ８ 字节的字节数据 Εｉ ， Εｉ ＝ ε８ｉ＋１‖ε８ｉ＋２‖…‖ε８ｉ＋８ ， ０ ≤ ｉ ≤ ｎ ／ ８ － １。 为区分两 种不同参数取值时各种序列模式出现的频数，记 Ｃ４ ［ｉ］，０ ≤ ｉ ≤ １５ 为 ｍ ＝ ４ 时各种序列模式出现的 频数，记 Ｃ８ ［ｉ］，０ ≤ ｉ ≤ ２５５ 为 ｍ ＝ ８ 时各种序列模 式出现的频数。 参数 ｍ ＝ ８ 时的频数统计方式为直接加载字节 数据并更新频数，即 Ｃ８ ［Ｅｉ］ ＝ Ｃ８ ［Ｅｉ］ ＋ １，０ ≤ ｉ ≤ ｎ ８ － １ （５） 参数 ｍ ＝ ４ 时的频数统计方式为先加载字节数 据，接着获取高半字节和低半字节， Ｈ ＝ Ｅｉ ≫ ４，Ｌ ＝ Ｅｉ ∧ ０ｘＦ，０ ≤ ｉ ≤ ｎ ８ － １ （６） 最后利用获取的高半字节和低半字节更新对应 的频数，即 Ｃ４ ［Ｈ］ ＝ Ｃ４ ［Ｈ］ ＋ １，Ｃ４ ［Ｌ］ ＝ Ｃ４ ［Ｌ］ ＋ １ （７） 参数 ｍ ＝ ４ 时和 ｍ ＝ ８ 时的统计过程分开实现 会使得待检数据序列重复加载，这也是扑克检测效 率不高的主要原因之一。 如果能更进一步将参数在 两种不同取值时的统计过程合并在一起，则可以减 少大量的数据重复加载。 参数 ｍ 取 ４ 和 ８ 合并实 现时的频数统计方式为先加载字节数据，然后获取 高半字节和低半字节，最后更新 ｍ ＝ ４ 的频数和 ｍ ＝ ８ 的频数，合并式（５） ～ （７），可得 Ｈ ＝ Ｅｉ ≫ ４，Ｌ ＝ Ｅｉ ∧ ０ｘＦ，０ ≤ ｉ ≤ ｎ ／ ８ － １ Ｃ４ ［Ｈ］ ＝ Ｃ４ ［Ｈ］ ＋ １，Ｃ４ ［Ｌ］ ＝ Ｃ４ ［Ｌ］ ＋ １ Ｃ８ ［Ｅｉ］ ＝ Ｃ８ ［Ｅｉ］ ＋ １ （８） 统计量的计算和判断过程还可以进行精简和优 化：可根 据 余 不 完 全 伽 马 函 数 的 性 质 预 先 求 出 Ｐｖａｌｕｅ ≥α 时统计量 Ｖ 的阈值，让统计值 Ｖ 直接和此 阈值比较，如此可以减少余不完全伽马函数的计算 次数。 记 ｍ ＝ ４ 时的统计量为 Ｖ４ ，即 Ｖ４ ＝ ６４ ｎ ∑ １５ ｉ ＝ ０ Ｃ４ ［ｉ］ ２ ( ) － ｎ ４ （９） 记 ｍ ＝ ８ 时的统计量为 Ｖ８ ，即 Ｖ８ ＝ ２ ０４８ ｎ ∑ ２５５ ｉ ＝ ０ Ｃ８ ［ｉ］ ２ ( ) － ｎ ８ （１０） 计算统计值所用的余不完全伽马函数满足性质 ｉｇａｍｃ（α，０） ＝ １， ｉｇａｍｃ（α，¥） ＝ ０。 经简单计算可 知，当显著水平 α ＝ ０．０１， ｍ ＝ ４ 时，统计量 Ｖ４ 的阈值 为 λ４ ＝ ３０．５７７ ９１４；当显著水平 α ＝ ０．０１， ｍ ＝ ８ 时， 统计量 Ｖ８ 的阈值为 λ８ ＝ ３１０．４５７ ３８８。 即如果 Ｖ４ ＜ λ４ 且 Ｖ８ ＜ λ８ 则认为待检序列通过检测。 根据以上 描述，优化实现的扑克检测算法如下。 算法 １ 优化实现的扑克检测算法 输入 ｎ ／ ８ 字节的数据 Εｉ，０ ≤ ｉ ≤ ｎ ／ ８ － １； 输出 检测结果。 １）初始化数据： ｉ ＝ ０。 Ｃ４ ［ｊ］ ＝ ０， ０ ≤ ｊ ≤ １５， Ｃ８ ［ｊ］ ＝ ０， ０ ≤ ｊ ≤ ２５５。 第 ４ 期 杨先伟，等：随机序列的扑克检测优化研究 ·５１５·
.516 智能系统学报 第11卷 2)当i<n/8时执行如下步骤：否则转3)。 如整数的加、减、比较、比特运算及移位等仅需一个 ①X=E:,H=X≥4，L=E:A0xF 时钟周期(eycle)。但数据加载的执行时间则有很 ②C4[H]=C[H]+1, 多因素，无法以准确的值计量。这里仅做粗略估计， C4[L]=C4[L]+1, 因此加速数据加载也仅需要一个时钟周期。这样一 Cs[X]=C[x]+1, 来原算法对一个样本进行检测的粗略估计时间为 ③i=i+1。 64M个时钟周期，算法1对一个样本进行检测的粗 3)计算两个统计值V,和V。 略估计时间为6M个时钟周期，以此法粗略估计，算 .-4芝ca-子 法1的检测速度为原算法的10.7倍左右。当然，此 =0 处为不精确的粗略估计而已，具体的速度提升情况 2048/ n c,9)-号 以实验为准。 :=0 4)如果V,<入且Vg<入g,则认为待检序列通 5模拟实验测试 过检测。否则未通过。 为更准确地说明本文提出的算法的效率，本节 算法1的主要优化方式是直接对输入的待检序 测试优化前后算法的执行效率。 列按字节而不是比特进行处理，减少了大量不必要的 测试数据是利用我国的分组密码算法SM4算 数据拆分为单比特等操作；并且将两种参数下的频数 法生成的10°bit的伪随机数据，按样本大小10比 统计合并在一起，避免了大量的数据加载等操作。 特划分为1000个样本。 4优化前后计算量分析与对比 测试平台为Intel Core i3@3400MHz处理器、4 GB DDR316 00MHz内存、Windows XP SP3操作系 本节对优化前的算法和优化后的算法的计算量 统、Visual Studio2008编译器。处理器的缓存情况 进行定量评估与对比。 为：一级缓存为每个核心32KB,二级缓存为每个核 原算法的2)~4)的计算量都很小，因此本节在 心64KB,三级缓存为多核共享3MB。 进行计算量评估对比时，只比较最关键最耗时的步 模拟实验使用的代码情况如下。优化前的测试 骤统计频数所需要的运算量。为简化表示，将n比 代码来源是先从NIST的官方网站取得检测代码，然 特二元序列的字节长度记为M,M=n/8。而且通常 后按原算法以及NST代码思想对以比特表示的二 情况下输入的二元序列都是以字节表示，因此这里 元序列，按比特操作实现扑克检测，NIST代码完成 默认待检二元序列的比特长度n能被8整除。 字节序列转比特表示的二元序列的相关功能。优化 根据第2节的分析结果知，对一个n=10bit 后的代码（参见附录）是对以字节表示的序列按算 (M=125×103字节)的样本而言，原算法1)的计 法1的步骤以字节处理为主实现扑克检测。所有的 算量为16M次SHFT、16M次L0AD和32M次 算法都采用标准C实现。 ADD。扑克检测优化算法1的1)进行简单分析可 实验采用欧洲estream算法竞赛的速度测试模 知，对一个n=10bit的样本而言，算法1的2)的计 型的简化版本，该测试模型不仅在estream算法竞赛 算量为M次SHIFT、M次LOAD、M次AND和3M次 中采用，后续许多算法的性能评估也常采用该测试 ADD。原算法和优化算法（算法I)的运算量详情以 模型。具体来讲速度测试流程如下。1)在被测试 及对比情况见表2。 代码段的前后各设置一个时间计数器T,和T。;2) 表2两个算法的运算量对比 Table 2 The performance comparison of two algorithms 将两个计时器之差T=T。-T,作为这段代码的耗 时：3)重复1)和2)多次，为统计方便设定重复次数 运算 原算法 算法1 为奇数，记重复次数为C,得到一系列的耗时值 LOAD 16M M T[i],1≤i≤C:4)将统计得到的耗时值序列按从 SHIFT 16M M 大到小的顺序排列得到T[1]≥T[2]≥…≥ AND 0 M T[C],当然也可按从小到大的顺序排列：5)取新 ADD 32M 3M 序列的中值T'[(C+1)/2]作为本段代码的统计耗 由表2可知，优化后的扑克检测的计算量显著 时值。W为了保证测试结果的准确性，本测试模型 降低。 中1)的时间计数器使用CPU频率计时器，直接调 在现在的CPU中，常见的整数运算都比较快， 用汇编指令RDTSC,在Windows环境下也可调用_
２）当 ｉ ＜ ｎ ／ ８ 时执行如下步骤；否则转 ３）。 ① Ｘ ＝ Ｅｉ ， Ｈ ＝ Ｘ ≫ ４， Ｌ ＝ Ｅｉ ∧ ０ｘＦ ② Ｃ４ ［Ｈ］ ＝ Ｃ４ ［Ｈ］ ＋ １， Ｃ４ ［Ｌ］ ＝ Ｃ４ ［Ｌ］ ＋ １， Ｃ８ ［Ｘ］ ＝ Ｃ８ ［Ｘ］ ＋ １， ③ ｉ ＝ ｉ ＋ １。 ３）计算两个统计值 Ｖ４ 和 Ｖ８ 。 Ｖ４ ＝ ６４ ｎ ∑ １５ ｉ ＝ ０ Ｃ４ ［ｉ］ ２ ( ) － ｎ ４ Ｖ８ ＝ ２ ０４８ ｎ ∑ ２５５ ｉ ＝ ０ Ｃ８ ［ｉ］ ２ ( ) － ｎ ８ ４）如果 Ｖ４ ＜ λ４ 且 Ｖ８ ＜ λ８ ，则认为待检序列通 过检测。 否则未通过。 算法 １ 的主要优化方式是直接对输入的待检序 列按字节而不是比特进行处理，减少了大量不必要的 数据拆分为单比特等操作；并且将两种参数下的频数 统计合并在一起，避免了大量的数据加载等操作。 ４ 优化前后计算量分析与对比 本节对优化前的算法和优化后的算法的计算量 进行定量评估与对比。 原算法的 ２） ～４）的计算量都很小，因此本节在 进行计算量评估对比时，只比较最关键最耗时的步 骤统计频数所需要的运算量。 为简化表示，将 ｎ 比 特二元序列的字节长度记为 Ｍ， Ｍ ＝ ｎ ／ ８。 而且通常 情况下输入的二元序列都是以字节表示，因此这里 默认待检二元序列的比特长度 ｎ 能被 ８ 整除。 根据第 ２ 节的分析结果知，对一个 ｎ ＝ １０ ６ ｂｉｔ （ Ｍ ＝ １２５ × １０ ３ 字节）的样本而言，原算法 １）的计 算量 为 １６Ｍ 次 ＳＨＩＦＴ、 １６Ｍ 次 ＬＯＡＤ 和 ３２Ｍ 次 ＡＤＤ。 扑克检测优化算法 １ 的 １） 进行简单分析可 知，对一个 ｎ ＝ １０ ６ ｂｉｔ 的样本而言，算法 １ 的 ２）的计 算量为 Ｍ 次 ＳＨＩＦＴ、Ｍ 次 ＬＯＡＤ、Ｍ 次 ＡＮＤ 和 ３Ｍ 次 ＡＤＤ。 原算法和优化算法（算法 １）的运算量详情以 及对比情况见表 ２。 表 ２ 两个算法的运算量对比 Ｔａｂｌｅ ２ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ 运算 原算法 算法 １ ＬＯＡＤ １６Ｍ Ｍ ＳＨＩＦＴ １６Ｍ Ｍ ＡＮＤ ０ Ｍ ＡＤＤ ３２Ｍ ３Ｍ 由表 ２ 可知，优化后的扑克检测的计算量显著 降低。 在现在的 ＣＰＵ 中，常见的整数运算都比较快， 如整数的加、减、比较、比特运算及移位等仅需一个 时钟周期（ ｃｙｃｌｅ）。 但数据加载的执行时间则有很 多因素，无法以准确的值计量。 这里仅做粗略估计， 因此加速数据加载也仅需要一个时钟周期。 这样一 来原算法对一个样本进行检测的粗略估计时间为 ６４Ｍ 个时钟周期，算法 １ 对一个样本进行检测的粗 略估计时间为 ６Ｍ 个时钟周期，以此法粗略估计，算 法 １ 的检测速度为原算法的 １０．７ 倍左右。 当然，此 处为不精确的粗略估计而已，具体的速度提升情况 以实验为准。 ５ 模拟实验测试 为更准确地说明本文提出的算法的效率，本节 测试优化前后算法的执行效率。 测试数据是利用我国的分组密码算法 ＳＭ４ 算 法生成的 １０ ９ ｂｉｔ 的伪随机数据，按样本大小 １０ ６ 比 特划分为 １ ０００ 个样本。 测试平台为 Ｉｎｔｅｌ Ｃｏｒｅ ｉ３ ＠ ３４００ＭＨｚ 处理器、４ ＧＢ ＤＤＲ３ １６００ＭＨｚ 内存、Ｗｉｎｄｏｗｓ ＸＰ ＳＰ３ 操作系 统、Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２００８ 编译器。 处理器的缓存情况 为：一级缓存为每个核心 ３２ ＫＢ，二级缓存为每个核 心 ６４ ＫＢ，三级缓存为多核共享 ３ ＭＢ。 模拟实验使用的代码情况如下。 优化前的测试 代码来源是先从 ＮＩＳＴ 的官方网站取得检测代码，然 后按原算法以及 ＮＩＳＴ 代码思想对以比特表示的二 元序列，按比特操作实现扑克检测，ＮＩＳＴ 代码完成 字节序列转比特表示的二元序列的相关功能。 优化 后的代码（参见附录）是对以字节表示的序列按算 法 １ 的步骤以字节处理为主实现扑克检测。 所有的 算法都采用标准 Ｃ 实现。 实验采用欧洲 ｅｓｔｒｅａｍ 算法竞赛的速度测试模 型的简化版本，该测试模型不仅在 ｅｓｔｒｅａｍ 算法竞赛 中采用，后续许多算法的性能评估也常采用该测试 模型。 具体来讲速度测试流程如下。 １） 在被测试 代码段的前后各设置一个时间计数器 ＴＳ 和 ＴＦ ；２） 将两个计时器之差 Ｔ ＝ ＴＦ － Ｔｓ 作为这段代码的耗 时；３）重复 １）和 ２）多次，为统计方便设定重复次数 为奇数，记重复次数为 Ｃ， 得到一系列的耗时值 Ｔ［ｉ］ ， １ ≤ ｉ ≤ Ｃ ；４）将统计得到的耗时值序列按从 大到小的顺序排列得到 Ｔ′［１］ ≥ Ｔ′［２］ ≥ … ≥ Ｔ′［Ｃ］ ，当然也可按从小到大的顺序排列；５） 取新 序列的中值 Ｔ′［（Ｃ ＋ １） ／ ２］ 作为本段代码的统计耗 时值。 ｗ 为了保证测试结果的准确性，本测试模型 中 １）的时间计数器使用 ＣＰＵ 频率计时器，直接调 用汇编指令 ＲＤＴＳＣ，在 Ｗｉｎｄｏｗｓ 环境下也可调用＿＿ ·５１６· 智 能 系 统 学 报 第 １１ 卷
第4期 杨先伟，等：随机序列的扑克检测优化研究 .517, dtsc()函数，该指令或函数返回CPU时钟周期值， //扑克测试优化后代码 按现代CPU的时钟频率计算，此计数器可精确到纳 int poker_test(BYTE p_u8,int n 秒级。两次RDTSC指令返回的时钟周期之差再除 以CPU频率，即可得到以s为单位的耗时值。 double v; 原算法和优化算法（算法1）对1000个样本进 BYTE p_bound p_u8 n/8,d; 行检测的性能统计结果见表3。 u32c4[16]={0},c8[256]={0}; 表3算法性能对比 while(p_u8 p_bound Table 3 The performance comparison of two algorithms 性能对比 原算法 算法1 d=*P_u8++; 耗时/s 2.244 0.236 c8[d]+: 速度比 1:1 9.508:1 c4[d4]++; 理论评估时只估算了最重要也最耗时的步骤 c4[d&0xf]++: 1),略去了后面的步骤的耗时。虽然步骤2)的计算 过程和原算法一样，但优化算法对步骤3)也做了相 /m=8时计算统计量 应的优化。实验的结果表明，优化算法通过充分利 v=poker_get_statistics(8,n,c8); 用CPU字长一次处理多个比特，优化整合算法流程 if(v>=POKER_BOUND_M_8) 减少不必要的计算，精简统计量的计算和判断过程 的技术方式和方法，的确可以显著地提升扑克检测 return -8; 的检测性能，且检测速度可提升9.5倍左右。 / 此外，算法性能提升显著的另外一个重要原因 /m=4时计算统计量 是扑克检测中的参数m取值较为特殊，m=8恰好 v=poker_get_statistics(4,n,c4); 是一个字节，m=4恰好是将一个字节拆分为两个 if(v >POKER_BOUND_M_4) “半字节”。这使得优化算法基于字节的处理方式 得到了淋漓尽致的发挥。 return -4; 6 结论 return 1; 本文对我国随机性检测规范采用的扑克检测算 } 法进行优化实现。通过充分利用CPU字长一次处 //扑克检测计算统计量，n为序列比特长度 理多个比特，优化整合算法流程减少不必要的计算， /m为参数，P_ct为子序列频数 精简统计量的计算和判断过程的技术方式和方法， double poker_get_statistics(int m,int n,u32 可以显著地提升扑克检测的检测性能，实验结果表 p_ctr) 明检测速度可提升9.5倍左右。因此，建议在实际 检测中采用软件实现时使用本文提出的扑克检测快 int i,blk_sz,pow_m; 速实现方式以提高扑克检测的检测效率。NIST和 double blk_sz_inv,sum; 我国的随机性检测规范还有很多别的检测项，其中 sum=0.0: 还有很多检测项可以做必要的性能优化，这将是今 pow_m 1 <<m; 后工作的一个研究方向。另外，怎样利用并行化技 blk sz n m; 术（如多线程技术，SMD指令、GPU运算）快速实现 blk_sz_inv 1.0 blk_sz; 这些检测项，也是今后研究的另一个方向。 for(i 0;i<pow_m;i++) 附录优化算法的代码 sum +p_ctr[i]p_ctr[i]blk_sz_inv; 本节列出优化算法（算法1）的标准C代码。其 中poker_.test函数为扑克测试优化后的功能实现函 return sum pow_m )-blk_sz; 数，poker_.get_statistics函数为扑克检测中计算统计 量的函数
ｒｄｔｓｃ（）函数，该指令或函数返回 ＣＰＵ 时钟周期值， 按现代 ＣＰＵ 的时钟频率计算，此计数器可精确到纳 秒级。 两次 ＲＤＴＳＣ 指令返回的时钟周期之差再除 以 ＣＰＵ 频率，即可得到以 ｓ 为单位的耗时值。 原算法和优化算法（算法 １）对 １ ０００ 个样本进 行检测的性能统计结果见表 ３。 表 ３ 算法性能对比 Ｔａｂｌｅ ３ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ 性能对比 原算法 算法 １ 耗时／ ｓ ２．２４４ ０．２３６ 速度比 １：１ ９．５０８：１ 理论评估时只估算了最重要也最耗时的步骤 １），略去了后面的步骤的耗时。 虽然步骤 ２）的计算 过程和原算法一样，但优化算法对步骤 ３）也做了相 应的优化。 实验的结果表明，优化算法通过充分利 用 ＣＰＵ 字长一次处理多个比特，优化整合算法流程 减少不必要的计算，精简统计量的计算和判断过程 的技术方式和方法，的确可以显著地提升扑克检测 的检测性能，且检测速度可提升 ９．５ 倍左右。 此外，算法性能提升显著的另外一个重要原因 是扑克检测中的参数 ｍ 取值较为特殊，ｍ ＝ ８ 恰好 是一个字节，ｍ ＝ ４ 恰好是将一个字节拆分为两个 “半字节”。 这使得优化算法基于字节的处理方式 得到了淋漓尽致的发挥。 ６ 结论 本文对我国随机性检测规范采用的扑克检测算 法进行优化实现。 通过充分利用 ＣＰＵ 字长一次处 理多个比特，优化整合算法流程减少不必要的计算， 精简统计量的计算和判断过程的技术方式和方法， 可以显著地提升扑克检测的检测性能，实验结果表 明检测速度可提升 ９．５ 倍左右。 因此，建议在实际 检测中采用软件实现时使用本文提出的扑克检测快 速实现方式以提高扑克检测的检测效率。 ＮＩＳＴ 和 我国的随机性检测规范还有很多别的检测项，其中 还有很多检测项可以做必要的性能优化，这将是今 后工作的一个研究方向。 另外，怎样利用并行化技 术（如多线程技术、ＳＩＭＤ 指令、ＧＰＵ 运算）快速实现 这些检测项，也是今后研究的另一个方向。 附录 优化算法的代码 本节列出优化算法（算法 １）的标准 Ｃ 代码。 其 中 ｐｏｋｅｒ＿ｔｅｓｔ 函数为扑克测试优化后的功能实现函 数，ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ 函数为扑克检测中计算统计 量的函数。 ／ ／ 扑克测试优化后代码 ｉｎｔ ｐｏｋｅｒ＿ｔｅｓｔ（ＢＹＴＥ ∗ｐ＿ｕ８， ｉｎｔ ｎ ） ｛ ｄｏｕｂｌｅ ｖ； ＢＹＴＥ ∗ｐ＿ｂｏｕｎｄ ＝ ｐ＿ｕ８ ＋ ｎ ／ ８， ｄ； ｕ３２ ｃ４［１６］ ＝ ｛０｝， ｃ８［２５６］ ＝ ｛０｝； ｗｈｉｌｅ（ ｐ＿ｕ８ ＜ ｐ＿ｂｏｕｎｄ ） ｛ ｄ ＝ ∗ｐ＿ｕ８＋＋； ｃ８［ ｄ ］＋＋； ｃ４［ ｄ ≫ ４ ］＋＋； ｃ４［ ｄ ＆ ０ｘｆ ］＋＋； ｝ ／ ／ ｍ ＝ ８ 时计算统计量 ｖ ＝ ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ（８， ｎ， ｃ８）； ｉｆ（ｖ ＞ ＝ ＰＯＫＥＲ＿ＢＯＵＮＤ＿Ｍ＿８） ｛ ｒｅｔｕｒｎ －８； ｝ ／ ／ ｍ ＝ ４ 时计算统计量 ｖ ＝ ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ（４， ｎ， ｃ４）； ｉｆ（ｖ ＞ ＝ ＰＯＫＥＲ＿ＢＯＵＮＤ＿Ｍ＿４） ｛ ｒｅｔｕｒｎ －４； ｝ ｒｅｔｕｒｎ １； ｝ ／ ／ 扑克检测计算统计量，ｎ 为序列比特长度 ／ ／ ｍ 为参数，ｐ＿ｃｔｒ 为子序列频数 ｄｏｕｂｌｅ ｐｏｋｅｒ＿ｇｅｔ＿ｓｔａｔｉｓｔｉｃｓ（ｉｎｔ ｍ， ｉｎｔ ｎ， ｕ３２ ∗ ｐ＿ｃｔｒ） ｛ ｉｎｔ ｉ， ｂｌｋ＿ｓｚ， ｐｏｗ＿ｍ； ｄｏｕｂｌｅ ｂｌｋ＿ｓｚ＿ｉｎｖ， ｓｕｍ； ｓｕｍ ＝ ０．０； ｐｏｗ＿ｍ ＝ １ ＜＜ ｍ； ｂｌｋ＿ｓｚ ＝ ｎ ／ ｍ； ｂｌｋ＿ｓｚ＿ｉｎｖ ＝ １．０ ／ ｂｌｋ＿ｓｚ； ｆｏｒ（ ｉ ＝ ０； ｉ ＜ ｐｏｗ＿ｍ； ｉ＋＋ ） ｛ ｓｕｍ ＋ ＝ ｐ＿ｃｔｒ［ｉ］ ∗ ｐ＿ｃｔｒ［ｉ］ ∗ ｂｌｋ＿ｓｚ＿ｉｎｖ； ｝ ｒｅｔｕｒｎ （ ｓｕｍ ∗ ｐｏｗ＿ｍ ） － ｂｌｋ＿ｓｚ； ｝ 第 ４ 期 杨先伟，等：随机序列的扑克检测优化研究 ·５１７·
.518. 智能系统学报 第11卷 [8]罗影，张文科，尹一桦，等.单比特频数检测和块内频 参考文献： 数检测的快速实现研究[J].通信技术，2015,48(9)： [1]National Institute of Standards and Technology.NIST SP 800 1073-1077 -22,A statistical test suite for random and pseudorandom LUO Ying,ZHANG Wenke,YIN Yihua,et al.Fast Imple- number generators for cryptographic applications[S].Revi- mentation of monobit frequency test and frequency test with- sion 1a.Washington DC,USA:Information Technology La- in a block[J].Communications technology,.2015,48(9): boratory of National Institute of Standards and Technology, 1073-1077. 2010. [2]BSI AIS-20,AIS-30,.Application notes and interpretation [9]Edro M AALCOVER P M,GUILLAM6N A.RUIZ M D of the scheme functionality classes and evaluation methodol- CAntonio G,et al.A new randomness test for bit sequences ogy for deterministic and physical random number generators [J].Informatica,2013,24(3):339-356. [S].Berlin,Germany:German Federal Office for Informa- [10]KAMINSKY A.GPU parallel statistical and cube test anal- tion Security,2008. ysis of the SHA-3 finalist candidate hash functions[EB/ [3]随机性检测规范[S].中国北京：国家密码管理局， 0L].(2012-02-13)[2016-03-31].htp:/www.cs.rit 2009. edu/~ark/parallelcrypto/sha3test01/. Randomness test specification[S].Beijing:National Cryp- tography Administration,2009. 作者简介： [4]罗影，刘冬梅，康红娟.NST新分组密码工作模式及快 杨先伟，男，1980年生，讲师.主要 速实现研究[J].通信技术，2014,47(9)：1066-1070. 研究方向为密码学及通信与系统工程。 LUO Ying,LIU Dongmei,KANG Hongjuan.,NIST new block cipher modes of operation and their fast implementa- tionoperation modes and their fast implementations of nist new block cipher[J].Communications technology,2014, 47(9):1066-1070. [5]杨先伟，康红娟.SM3杂凑算法的软件快速实现研究 康红娟，女，1983年生，硕士，工程 [J].智能系统学报，2015,10(6)：9541-9597. 师，主要研究方向为保密通信。 YANG Xianwei,KANG Hongjuan.Fast software implemen- tation of SM3 hash algorithm[J.CAAI transactions on in- telligent systems,2015,10(6):9541-9597. [6]CCSA.Specification of the 3GPP confidentiality and integri- ty algorithms 128-EEA3 128-EIA3.Document 2:ZUC specification[S].Cedex,France:CCSA,2011. 廖祖华，男，957年生，教授，主要 [7]冯秀涛.3 GPP LTE国际加密标准ZUC算法[J].信息安 研究方向为人工智能、模糊与粗糙代 全与通信保密，2011,9(12)：45-46. 数、广义逆理论及应用。主持省自然科 FENG Xiutao.ZUC algorithm:3GPP LTE international en- 学基金项目1项。发表学术论文130 cryption standard[J].Information security and communica- 余篇，其中被SCI和EI检索30余篇。 tions privacy,20112,9(12):45-46
参考文献： ［ １］Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． ＮＩＳＴ ＳＰ ８００ －２２， Ａ ｓｔａｔｉｓｔｉｃａｌ ｔｅｓｔ ｓｕｉｔｅ ｆｏｒ ｒａｎｄｏｍ ａｎｄ ｐｓｅｕｄｏｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒｓ ｆｏｒ ｃｒｙｐｔｏｇｒａｐｈｉｃ ａｐｐｌｉｃａｔｉｏｎｓ［ Ｓ］． Ｒｅｖｉ⁃ ｓｉｏｎ １ａ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ， ＵＳＡ： Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ Ｌａ⁃ ｂｏｒａｔｏｒｙ ｏｆ Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２０１０． ［２］ＢＳＩ ＡＩＳ－２０， ＡＩＳ－３０，． Ａｐｐｌｉｃａｔｉｏｎ ｎｏｔｅｓ ａｎｄ ｉｎｔｅｒｐｒｅｔａｔｉｏｎ ｏｆ ｔｈｅ ｓｃｈｅｍｅ ｆｕｎｃｔｉｏｎａｌｉｔｙ ｃｌａｓｓｅｓ ａｎｄ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄｏｌ⁃ ｏｇｙ ｆｏｒ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ａｎｄ ｐｈｙｓｉｃａｌ ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒｓ ［Ｓ］． Ｂｅｒｌｉｎ， Ｇｅｒｍａｎｙ： Ｇｅｒｍａｎ Ｆｅｄｅｒａｌ Ｏｆｆｉｃｅ ｆｏｒ Ｉｎｆｏｒｍａ⁃ ｔｉｏｎ Ｓｅｃｕｒｉｔｙ， ２００８． ［３］ 随机性检测规范［ Ｓ］． 中国北京： 国家密码管理局， ２００９． Ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔ ｓｐｅｃｉｆｉｃａｔｉｏｎ［ Ｓ］． Ｂｅｉｊｉｎｇ： Ｎａｔｉｏｎａｌ Ｃｒｙｐ⁃ ｔｏｇｒａｐｈｙ Ａｄｍｉｎｉｓｔｒａｔｉｏｎ， ２００９． ［４］罗影， 刘冬梅， 康红娟． ＮＩＳＴ 新分组密码工作模式及快 速实现研究［Ｊ］． 通信技术， ２０１４， ４７（９）： １０６６－１０７０． ＬＵＯ Ｙｉｎｇ， ＬＩＵ Ｄｏｎｇｍｅｉ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ．， ＮＩＳＴ ｎｅｗ ｂｌｏｃｋ ｃｉｐｈｅｒ ｍｏｄｅｓ ｏｆ ｏｐｅｒａｔｉｏｎ ａｎｄ ｔｈｅｉｒ ｆａｓｔ ｉｍｐｌｅｍｅｎｔａ⁃ ｔｉｏｎｏｐｅｒａｔｉｏｎ ｍｏｄｅｓ ａｎｄ ｔｈｅｉｒ ｆａｓｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ ｏｆ ｎｉｓｔ ｎｅｗ ｂｌｏｃｋ ｃｉｐｈｅｒ ［ Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｔｅｃｈｎｏｌｏｇｙ， ２０１４， ４７（９）： １０６６－１０７０． ［５］杨先伟， 康红娟． ＳＭ３ 杂凑算法的软件快速实现研究 ［Ｊ］． 智能系统学报， ２０１５， １０（６）： ９５４１－９５９７． ＹＡＮＧ Ｘｉａｎｗｅｉ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ． Ｆａｓｔ ｓｏｆｔｗａｒｅ ｉｍｐｌｅｍｅｎ⁃ ｔａｔｉｏｎ ｏｆ ＳＭ３ ｈａｓｈ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎ⁃ ｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ９５４１－９５９７． ［６］ＣＣＳＡ． Ｓｐｅｃｉｆｉｃａｔｉｏｎ ｏｆ ｔｈｅ ３ＧＰＰ ｃｏｎｆｉｄｅｎｔｉａｌｉｔｙ ａｎｄ ｉｎｔｅｇｒｉ⁃ ｔｙ ａｌｇｏｒｉｔｈｍｓ １２８－ＥＥＡ３ ＆ １２８－ＥＩＡ３． Ｄｏｃｕｍｅｎｔ ２： ＺＵＣ ｓｐｅｃｉｆｉｃａｔｉｏｎ［Ｓ］． Ｃｅｄｅｘ， Ｆｒａｎｃｅ： ＣＣＳＡ， ２０１１． ［７］冯秀涛． ３ＧＰＰ ＬＴＥ 国际加密标准 ＺＵＣ 算法［ Ｊ］． 信息安 全与通信保密， ２０１１， ９（１２）： ４５－４６． ＦＥＮＧ Ｘｉｕｔａｏ． ＺＵＣ ａｌｇｏｒｉｔｈｍ： ３ＧＰＰ ＬＴＥ ｉｎｔｅｒｎａｔｉｏｎａｌ ｅｎ⁃ ｃｒｙｐｔｉｏｎ ｓｔａｎｄａｒｄ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｅｃｕｒｉｔｙ ａｎｄ ｃｏｍｍｕｎｉｃａ⁃ ｔｉｏｎｓ ｐｒｉｖａｃｙ， ２０１１２， ９（１２）： ４５－４６． ［８］罗影， 张文科， 尹一桦， 等． 单比特频数检测和块内频 数检测的快速实现研究［ Ｊ］． 通信技术， ２０１５， ４８（ ９）： １０７３－１０７７． ＬＵＯ Ｙｉｎｇ， ＺＨＡＮＧ Ｗｅｎｋｅ， ＹＩＮ Ｙｉｈｕａ， ｅｔ ａｌ． Ｆａｓｔ Ｉｍｐｌｅ⁃ ｍｅｎｔａｔｉｏｎ ｏｆ ｍｏｎｏｂｉｔ ｆｒｅｑｕｅｎｃｙ ｔｅｓｔ ａｎｄ ｆｒｅｑｕｅｎｃｙ ｔｅｓｔ ｗｉｔｈ⁃ ｉｎ ａ ｂｌｏｃｋ［Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｔｅｃｈｎｏｌｏｇｙ，． ２０１５， ４８（９）： １０７３－１０７７． ［９］ Ｅｄｒｏ Ｍ ＡＡＬＣＯＶＥＲ Ｐ Ｍ， ＧＵＩＬＬＡＭóＮ Ａ， ＲＵＩＺ Ｍ Ｄ ＣＡｎｔｏｎｉｏ Ｇ， ｅｔ ａｌ． Ａ ｎｅｗ ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔ ｆｏｒ ｂｉｔ ｓｅｑｕｅｎｃｅｓ ［Ｊ］． Ｉｎｆｏｒｍａｔｉｃａ， ２０１３， ２４（３）： ３３９－３５６． ［１０］ＫＡＭＩＮＳＫＹ Ａ． ＧＰＵ ｐａｒａｌｌｅｌ ｓｔａｔｉｓｔｉｃａｌ ａｎｄ ｃｕｂｅ ｔｅｓｔ ａｎａｌ⁃ ｙｓｉｓ ｏｆ ｔｈｅ ＳＨＡ⁃３ ｆｉｎａｌｉｓｔ ｃａｎｄｉｄａｔｅ ｈａｓｈ ｆｕｎｃｔｉｏｎｓ ［ ＥＢ／ ＯＬ］． （２０１２－０２－１３） ［２０１６－０３－３１］． ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｓ．ｒｉｔ． ｅｄｕ ／ ～ ａｒｋ ／ ｐａｒａｌｌｅｌｃｒｙｐｔｏ ／ ｓｈａ３ｔｅｓｔ０１ ／ ． 作者简介： 杨先伟，男，１９８０ 年生，讲师，主要 研究方向为密码学及通信与系统工程。 康红娟，女，１９８３ 年生，硕士，工程 师，主要研究方向为保密通信。 廖祖华，男，９５７ 年生，教授，主要 研究方向为人工智能、模糊与粗糙代 数、广义逆理论及应用。 主持省自然科 学基金项目 １ 项。 发表学术论文 １３０ 余篇，其中被 ＳＣＩ 和 ＥＩ 检索 ３０ 余篇。 ·５１８· 智 能 系 统 学 报 第 １１ 卷