第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加密、数字签名方案中大素数的生第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６００２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３０．０１２．ｈｔｍｌ 随机序列的扑克检测优化研究 杨先伟１ ，康红娟２ ，廖祖华３，４ （１． 无锡职业技术学院 基础部，江苏 无锡 ２１４１２１； ２． 四川长虹电器股份有限公司，四川 成都 ６１００４１； ３． 江南大学， 江苏 无锡 ２１４１２２； ４．江南大学 智能系统与网络计算研究所，江苏 无锡 ２１４１２２） 摘 要：现代计算机系统的安全性依赖于二元随机序列，随机性检测利用概率统计方法对二元序列的随机性进行分 析测试。 我国国家密码管理局发布了随机性检测规范，扑克检测为其中一个检测项。 本文通过充分分析扑克检测 效率不高的原因有针对性地提出一种新的快速实现算法，优化算法充分利用 ＣＰＵ 字长一次处理多个比特，将 ｍ 为 ４ 和 ８ 的情况整合在一起，减少不必要的处理流程。 同时精简并优化统计量的计算和判断过程，避免余不完全伽马函 数的计算。 分析和实验的结果表明该优化算法可以使得扑克检测的速度提升 ９．５ 倍左右。 关键词：二元序列；随机序列；随机数发生器；随机性检测；扑克检测；密码算法；效率分析；余不完全伽玛函数 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０５１３－０６ 中文引用格式：杨先伟，康红娟，廖祖华． 随机序列的扑克检测优化研究［Ｊ］． 智能系统学报， ２０１６， １１（４）： ５１３－５１８． 英文引用格式：ＹＡＮＧ Ｘｉａｎｗｅｉ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ， ＬＩＡＯ Ｚｕｈｕａ． Ｓｔｕｄｙ ｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｐｏｋｅｒ ｔｅｓｔ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ５１３－５１８． Ｓｔｕｄｙ ｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｐｏｋｅｒ ｔｅｓｔ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅｓ ＹＡＮＧ Ｘｉａｎｗｅｉ １ ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ ２ ， ＬＩＡＯ Ｚｕｈｕａ ３，４ （１． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｆｕｎｄａｍｅｎｔａｌ Ｃｏｕｒｓｅｓ， Ｗｕｘｉ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｘｉ ２１４１２１， Ｃｈｉｎａ； ２． Ｓｉｃｈｕａｎ Ｃｈａｎｇｈｏｎｇ Ｅｌｅｃｔｒｉｃ Ｃｏ．， Ｌｔｄ．， Ｃｈｅｎｇｄｕ ６１００４１， Ｃｈｉｎａ； ３． Ｓｃｈｏｏｌ ｏｆ Ｓｃｉｅｎｃｅ， Ｊａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ； ４．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｙｓｔｅｍ ＆Ｎｅｔｗｏｒｋ Ｃｏｍｐｕｔｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｓｅｃｕｒｉｔｙ ｏｆ ｍｏｄｅｒｎ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ ｄｅｐｅｎｄｓ ｏｎ ｂｉｎａｒｙ ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅｓ， ｓｕｃｈ ａｓ ｃｉｐｈｅｒ ａｌｇｏ⁃ ｒｉｔｈｍｓ ｋｅｙｓ， ＲＳＡ ａｌｇｏｒｉｔｈｍ ｐｒｉｍｅ ｎｕｍｂｅｒｓ， ｔｈｅ ｄｉｇｉｔａｌ ｓｉｇｎａｔｕｒｅ ｓｙｓｔｅｍ， ｔｈｅ ｉｄｅｎｔｉｔｙ ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｓｙｓｔｅｍ， ｅｔｃ． Ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔｓ ａｎａｌｙｚｅ ａｎｄ ｔｅｓｔ ｔｈｅ ｒａｎｄｏｍｎｅｓｓ ｏｆ ｓｅｑｕｅｎｃｅｓ， ｕｓｉｎｇ ｐｒｏｂａｂｉｌｉｔｙ ａｎｄ ｓｔａｔｉｓｔｉｃｓ． Ｔｈｅ Ｃｈｉｎｅｓｅ Ｎａ⁃ ｔｉｏｎａｌ Ｃｒｙｐｔｏｇｒａｐｈｙ Ａｄｍｉｎｉｓｔｒａｔｉｏｎ ｈａｓ ｒｅｌｅａｓｅｄ ｎａｔｉｏｎａｌ ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔ ｓｐｅｃｉｆｉｃａｔｉｏｎｓ ａｎｄ ｔｈｅ Ｐｏｋｅｒ ｔｅｓｔ ｉｓ ｏｎｅ ｏｆ ｔｈｅｓｅ． Ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｄ ｔｈｅ ｒｅａｓｏｎｓ ｆｏｒ ｔｈｅ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ Ｐｏｋｅｒ ｔｅｓｔ， ｔｈｅｎ ｐｒｏｐｏｓｅｓ ａ ｆａｓｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｌｇｏｒｉｔｈｍ． Ｔｈｉｓ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｄｅａｌｓ ｗｉｔｈ ｂｙｔｅｓ ｂｙ ｍａｋｉｎｇ ｆｕｌｌ ｕｓｅ ｏｆ ＣＰＵ ｗｏｒｄ ｌｅｎｇｔｈ， ｉｎｔｅｇｒａｔｅｓ ｔｈｅ ｄｅｔｅｃｔｉｏｎ ｐｒｏｃｅｓｓ， ａｎｄ ｒｅｄｕｃｅｓ ｓｏｍｅ ｕｎｎｅｃｅｓｓａｒｙ ｏｐｅｒａｔｉｏｎｓ ｕｎｄｅｒ ｔｈｅ ｃｏｎｄｉｔｉｏｎｓ ｗｈｅｎ ｍ ｅｑｕａｌｓ ４ ａｎｄ ８． Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ， ｔｈｅ ｍｅｔｈｏｄ ｒｅｄｕｃｅｓ ａｎｄ ｏｐｔｉｍｉｚｅｓ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ ａｓｓｅｓｓｍｅｎｔ ｏｆ ｓｔａｔｉｓｔｉｃａｌ ｑｕａｎｔｉｔｙ， ａｖｏｉｄｉｎｇ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｇａｍｍａ ｆｕｎｃｔｉｏｎｓ． Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｎｃｒｅａｓｅｓ ９．５ ｆｏｌｄ． Ｋｅｙｗｏｒｄｓ： ｂｉｎａｒｙ ｓｅｑｕｅｎｃｅ； ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ； ｐｓｅｕｄｏｒａｎｄｏｍ ｂｉｔ ｇｅｎｅｒａｔｏｒ； ｒａｎｄｏｍｎｅｓｓ ｔｅｓｔ； ｐｏｋｅｒ ｔｅｓｔ； ｅｎｃｒｙｐ⁃ ｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ； ｅｆｆｉｃｉｅｎｃｙ ａｎａｌｙｓｉｓ； ｉｎｃｏｍｐｌｅｔｅ ｇａｍｍａ ｆｕｎｃｔｉｏｎｓ． 收稿日期：２０１６－０６－０１． 网络出版日期：２０１６－０８－０８． 基金项目：国家自然科学基金项目（ ６１１７０１２１，１１４０１２５９）；江苏省自然 科学基金项目（ＢＫ２０１５１１１７）． 通信作者：廖祖华． Ｅ⁃ｍａｉｌ：ｌｉａｏｚｕｈｕａ５７＠ １６３．ｃｏｍ． 二元随机序列在密码应用中占有举足轻重的地 位。 现在大量的计算机系统的安全性需要依赖于二 元随机序列，比如各种密码算法中使用的密钥、非对 称密码算法 ＲＳＡ 加密、数字签名方案中大素数的生