改进的伪随机序列生成:基于随机序列统计特性与SemiHam算法

4 下载量 116 浏览量 更新于2024-08-28 收藏 727KB PDF 举报
"该文提出了一种新的伪随机序列生成方法,主要针对现有方法中伪随机序列均衡性和游程特性不足的问题。通过结合随机序列的统计特性与骑士巡游问题的SemiHam算法,该方法能生成满足随机序列统计特性的高质量伪随机序列。在实验中,生成的序列通过了NIST SP 800-22随机性测试,显示出较好的随机性。" 在信息安全和密码学领域,伪随机序列生成器(PRNGs)扮演着至关重要的角色。这些生成器用于创建看似随机但实际上可预测的数据流,广泛应用于加密、安全协议、模拟和测试等领域。本文关注的是如何改进伪随机序列的生成,尤其是增强其均衡性和游程特性。 均衡性是指伪随机序列中0和1出现的频率接近于理想随机序列,而游程特性则涉及连续相同数字(如0或1)的最长序列长度。这两者是衡量伪随机序列质量的关键指标,因为不理想的均衡性和游程特性可能暴露出序列的模式,从而降低其安全性。 基于随机序列统计特性的伪随机序列生成方法,首先在棋盘上为每个格子分配不同长度的0和1游程值。然后,利用SemiHam算法解决骑士巡游问题,这是一种寻找汉密尔顿圈(即遍历棋盘每个格子一次并仅一次的路径)的方法。SemiHam算法生成的路径被用来扫描设定好游程值的棋盘,通过这个过程,可以提取出具有所需游程特性的0和1序列,最终形成伪随机序列。 SemiHam算法的选择是因为它的路径特性能够为生成的序列引入更多的不可预测性,这有助于提高随机性。实验结果显示,使用这种方法生成的伪随机序列在统计特性上接近真正的随机序列,且通过了NIST SP 800-22随机性测试套件,这是国际公认的评估随机性的一系列严格测试。 NIST SP 800-22测试包括多种统计测试,如频率测试、游程测试、最长运行测试、偏斜度测试等,用于检查序列是否表现出足够的随机性。通过这些测试,可以确保生成的序列在实际应用中难以被破解,增强了系统的安全性。 总结而言,该研究提供了一种创新的伪随机序列生成技术,它利用随机序列的统计特性和骑士巡游问题的解决方案,生成的序列在均衡性、游程特性和随机性方面表现优秀,对于需要高安全性的应用具有重要意义。这种方法不仅提升了现有PRNGs的质量,也为未来伪随机序列生成技术的研究开辟了新途径。