计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (5): 322-329.doi: 10.11896/jsjkx.240700006

• 信息安全 • 上一篇    下一篇

大样本条件下随机性检测的误差分析及参数建议

孙月玥1, 范丽敏2   

  1. 1 北京理工大学数学与统计学院 北京 100081
    2 中国科学院软件研究所可信计算与信息保障实验室 北京 100190
  • 收稿日期:2024-07-01 修回日期:2024-10-01 出版日期:2025-05-15 发布日期:2025-05-12
  • 通讯作者: 范丽敏(fanlimin@iscas.ac.cn)
  • 作者简介:(yysunnya@163.com)
  • 基金资助:
    国家密码科学基金(2025NCSF02057)

Error Analysis and Parameter Recommendations for Randomness Test Under Large Sample Conditions

SUN Yueyue1, FAN Limin2   

  1. 1 School of Mathematics and Statistics,Beijing Institute of Technology,Beijing 100081,China
    2 Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China
  • Received:2024-07-01 Revised:2024-10-01 Online:2025-05-15 Published:2025-05-12
  • About author:SUN Yueyue,born in 1999,postgra-duate.Her main research interests include statistical test of randomness and so on.
    FAN Limin,born in 1978,Ph.D,senior engineer.Her main research interests include side channel analysis and protection,and password detection.
  • Supported by:
    National Cryptography Science Foundation of China(2025NCSF02057).

PDF (PC)

39

摘要： 在信息安全领域,随机性检测在确保密码系统的安全性中起着至关重要的作用。这些测试的稳定性和可靠性直接影响密码系统的整体安全性。检测过程中的误差问题一直是学术界和工业界关注的焦点,特别是在处理大规模样本时,误差的累积更容易导致随机性检测的可靠性降低。因此,研究如何提高随机性检测的准确性和可靠性具有重要意义。GM/T 0005-2021标准中包含了9个具有可变参数的检测项目。针对大样本二元数据的随机性检测问题,根据其特点进行分类,并进行误差量化分析。当待检二元序列比特长度为1×108时,GM/T 0005-2021标准中的检测参数建议基本合理。对于Maurer通用统计检测,子序列长度取6时p值误差上界为0.001 492 8,相较于GM/T 0005-2021中建议的参数表现出更高的准确性。对于线性复杂度检测,更小的子序列长度同样会导致更小的误差。随着样本长度的增加,扩展研究了1×109时的参数选择,分析了不同样本长度和参数下的误差,并给出了样本长度为1×109时的检测参数建议。

关键词: 随机性检测, 大样本, 误差分析, 检测参数, GM/T 0005-2021

Abstract: In the field of information security,randomness tests play a crucial role in ensuring the security of cryptographic systems.The stability and reliability of these tests directly impact the overall security of cryptographic systems,making error issues during the testing process a focal point for both academia and industry.Particularly when handling large-scale samples,the accumulation of errors can more readily lead to reliability issues in randomness testing.Consequently,studying methods to enhance the accuracy and reliability of randomness testing is of significant importance.The GM/T 0005-2021 standard outlines 9 tests with variable parameters designed for randomness testing of large binary data samples.This study categorizes these tests according to their characteristics and conducts a quantitative error analysis.Specifically,when the bit length of the binary sequence under test is 1×108,the parameters recommended by the GM/T 0005-2021 standard are generally reasonable.For the Maurer universal statistical test,a subsequence length of 6 results in upper bound p-value error of 0.001 492 8,demonstrating higher accuracy compared to the parameters suggested in the GM/T 0005-2021 standard.Similarly,for the linear complexity test,using smaller subsequence lengths results in smaller errors. With the increase in sample length,this study extends the analysis to parameter selection for a sample length of 1×109.It systematically examines the errors associated with different sample lengths and parameter configurations,providing refined parameter recommendations for randomness testing when the sample length reaches 1×109.

Key words: Randomness test, Large sample, Error analysis, Test parameters, GM/T 0005-2021

中图分类号: 

  • TN918.1
[1]BASSHAM L E,RUKHIN A L,SOTO J,et al.A Statistical Test Suite for Randomand Pseudorandom Number Generators for Cryptographic Applications:Technical Report [EB/OL].https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=906762.
[2]ILLMANN W,SCHINDLER W.A Proposal for:Functionality Classes for Random Number Generators[EB/OL].https://www.bsi.bund.de/EN/Home/home_node.htm.
[3]MARSAGLIA G.The Marsaglia Random Number Cdrom Including the Diehard Battery of Tests of Randomness[EB/OL].https://ani.stat.fsu.edu/diehard/.
[4]L′ECUYER P,SIMARD R.Testu01:Ac Library for Empirical Testing of Random Number Generators[J].ACM Transactions on Mathematical Software(TOMS),2007,33(4):1-40.
[5]随机性检测规范:GM/T 0005-2021 [S].北京:国家密码管理局,2021.
[6]MAO C,SONG Y,CHEN J.A Lightweight Adaptive Random Testing Method for Deep Learning Systems[J].Software:Practice and Experience,2023,53(11):2271-2295.
[7]DEMIRHAN H,BITIRIM N.Statistical Testing of Crypto-graphic Randomness[J].İstatistikçiler Dergisi:İstatistik ve Aktüerya,2016,9(1):1-11.
[8]ZHU S,MA Y,LIN J,et al.More Powerful and Reliable Se-cond-Level Statistical Randomness Tests for NIST SP 800-22[C]//Advances in Cryptology-ASIACRYPT 2016:22nd International Conference on the Theory and Application of Cryptology and Information Security,Hanoi,Vietnam,December 4-8,2016,Proceedings,Part I 22.Berlin Heidelberg:Springer,2016:307-329.
[9]CHEN D,CHEN H,FAN L,et al.Error Analysis of NIST SP 800-22 Test Suite[J].IEEE Transactions on Information Forensics and Security,2023,18:3745-3759.
[10]PARESCHI F,ROVATTI R,SETTI G.OnStatistical Tests for Randomness Included in the NIST SP 800-22 Test Suite and Based on the Binomial Distribution[J].IEEE Transactions on Information Forensics and Security,2012,7(2):491-505.
[11]CHEN L H Y,GOLDSTEIN L,SHAO Q M.Normal Approximation by Stein's Method[M].Berlin Heidelberg:Springer,2010.
[12]LUENGO E A,OLIVARES B A,VILLALBA L J G,et al.Further Analysis of the Statistical Independence of the NIST SP 800-22 Randomness Tests[J].Applied Mathematics and Computation,2023,459:128222.
[13]RUKHIN A L.Approximate Entropyfor Testing Randomness[J].Journal of Applied Probability,2000,37(1):88-100.
[14]IWASAKI A,UMENO K.Randomness Test to Solve Discrete Fourier Transform Test Problems[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2018,101(8):1204-1214.
[15]IWASAKI A.Deriving the Variance of the Discrete FourierTransform Test Using Parseval's Theorem[J].IEEE Transactions on Information Theory,2019,66(2):1164-1170.
[16]HARAMOTO H.Study on Upper Limit of Sample Size for a Two-Level Test in NIST SP800-22[J].Japan Journal of Industrial and Applied Mathematics,2021,38(1):193-209.
[17]AKCENGIZ Z.A New Lightweight Statistical Randomness Test Suite and Its Evaluationby Comparison with Other Test Suites[D].Ankara:Middle East Technical University,2021.
[18]AKCENGIZ Z,ASLAN M,DOǦANAKSOY A,et al.LS-14Test Suite for Long Sequences[J].Hacettepe Journal of Mathematics and Statistics,2024,53(1):230-250.
[19]CHEN M,CHEN H,FAN L,et al.A New Discrete FourierTransform Randomness Test[J].Science China Information Sciences,2019,62:1-16.
[20]HIKIMA Y,IWASAKI A,UMENO K.The Reference Distributions of Maurer's Universal Statistical Test and Its Improved Tests[J].IEEE Transactions on Information Theory,2021,68(4):2674-2683.
[21]MENG C,CAI M,YANG Y,et al.Generation of True Quantum Random Numbers with on-Demand Probability Distributions via Single-Photon Quantum Walks[J].Optics Express,2024,32(11):20207-20217.
[22]IL′YA S T.Refinement of the Upper Bounds of the Constants in Lyapunov's Theorem[J].Russian Mathematical Surveys,2010,65(3):586.
[23]PEARSON K X.On the Criterion That a Given System of Deviations from the Probable in the Case of a Correlated System of Variables is Such That it Can Be Reasonably Supposed to Have Arisen from Random Sampling[J].The London,Edinburgh,and Dublin Philosophical Magazine and Journal of Science,1900,50(302):157-175.
[24]CORON J S,NACCACHE D.An Accurate Evaluation of Mau-rer's Universal Test[C]//International Workshop on Selected Areas in Cryptography.Berlin,Heidelberg:Springer Berlin Heidelberg,1998:57-71.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发