（通信与信息系统专业论文）基于一维元胞自动机的伪随机数发生器的研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 元胞自动机伪随机数发生器是利用其具有的时间空间、状态的离散性生成伪随机 数的一种确定方法，它不同于传统的同余和线形反馈移位寄存器，有其组成单元简单 ，单元之间作用的局部性和信息处理的高度并行性，并表现出复杂的全局特性等特点。 自1 9 8 5 年w o l e a m 首次提出基于一维元胞自动机随机序列的概念以后，在序列密码， 随机数发生器，私钥密码等有广泛的研究。由于元胞自动机有组成单元的简单性，使 得它在密码学领域有着独特的优势。 本文对基于一维扩展元胞自动机伪随机数发生器的深入研究，首先在最基本的元 胞自动机伪随机数发生器上从三变量，四变量和五变量实现并输出伪随机数研究，其 元胞自动机采用统一的元胞规则和循环边界，随机选择一个元胞输出其状态( 0 或1 ) ， 用n i s t 测试包进行测试，获得很好随机性的元胞自动机规则。 其次、在一维扩展元胞自动机伪随机数发生器的输出模式上，本文采用五种并行 的输出模式，并对输出用n i s t 测试包进行测试，从而提高产生随机数的效率。 最后、本文引进了遗传算法( g e n e t i c a l g o r i t h m ，g a ) ，以元胞状态序列的修正熵作 为遗传演化的适应度，从而获得在待定初始条件下的较优的伪随机数发生器，并对其 输出用n i s t 测试包进行测试，印证其较优的随机性。 关键词：一维元胞自动机；演化规则；伪随机数发生器；遗传算法；输出模式 a b s tr a c t p s e u d o r a n d o mn u m b e r sg e n e r a t o rb a s e do nc e l l u l a ra u t o m a t ai sam e t h o d t od e t e r m i n e p s e l l d o r a n d o mn u m b e r st h a tu s eo f t h e i rt i m eo fs p a c ea n dd i s c r e t es t a t e ，i ti sd i f f e r e n tf r o m t r a d i t i o n a lc o n g r u e n c ea n dl i n e a rf e e d b a c ks h i f tr e g i s t e rw h i c hh a sc o m p o s i t i o no fs i m p l e u n i t ，t h er o l eo fp a r t i a lb e t w e e nu n i t sa n dh i l l yp a r a l l e li n f o r m a t i o np r o c e s s i n g a tt h es a m e t i m e ，i ts h o w sc o m p l e xf e a t u r e so fg l o b a lp r o p e r t i e s s i n c e19 8 5w o l f r a m f i r s tt i m ep r o p o s e d t h ec o n c e p to fr a n o ms e q u e n c e sb a s e do no n e d i m e n s i o n a lc e l l u l a ra u t o m a t a , i t w a sw i d e l y u t i l i z e di nc i p h e r ，r a n d o mn u m b e r sg e n e r a t o ra n dp r i v a t ek e yp a s s w o r d s i n c et h es i m p l i c i t y o fc o m p o n e n tu n i ti nc e l l u l a ra u t o m a t a , i th a sau n i q u ea d v a n t a g ei nt h ep a s s w o r df i e l d t h i sp a p e rb a s e do i lt h ei n d e p t hs t u d yo fp s e u d o - r a n d o mn u m b e r sg e n e r a t o rb a s e do n o n e d i m e n s i o h a le x t e n d e dc e l l u l a ra u t o m a t a f i r s to fa l l ，f r o m t h et h r e ev a r i a b l e s ，f o u r v a r i a b l e sa n df i v ev a r i a b l e s ，i ta c h i e v e do u t p u tp s e u d o r a n d o mn u m b e r sr e s e a r c hi nt h em o s t b a s i cp s e u d o r a n d o mn u m b e r sg e n e r a t o rb a s e do nc e l l u l a ra u t o m a t a , i t sc e l l u l a ra u t o m a t a u s eu n i f i e dc e l l u l a rr u l e sa n dc y c l eb o u n d a r y ，r a n d o m l ys e l e c t sac e l l u l a ro u t p u t si t ss t a t e ( 0 0 1 1 ) ，u s e sn i s tt e s t i n gp a c k a g et e s t sa n dg e t sr a n d o mc e l l u l a ra u t o m a t a r u l e s s e c o n d l y , i nt h e o u t p u tm o d eo fp s e u d o - r a n d o mn u m b e r sg e n e r a t o r b a s e do n o n e d i m e n s i o n a le x t e n d e dc e l l u l a ra u t o m a t a , t h i sp a p e ru s e sf i v ep a r a l l e lo u t p u tm o d ea n d n i s tt e s tp a c k a g et e s t si tw i t he x p o r t ，t oi m p r o v et h ee f f i c i e n c yo fg e n e r a t i n gr a n d o m n u m b e r s f i n a l l y ，t h i sp a p e ri n t r o d u c e st h eg e n e t i ca l g o r i t h m ( g a ) ，t o t h ea m e n d m e n te n t r o p y o fc e l l u l a rs t a t es e q u e n c e sa st h ef i t n e s so fg e n e t i ce v o l u t i o n ，t h e no b t a i n e dt h eo p t i m u m p s e u d o - r a n d o mn u m b e r sg e n e r a t o ri nt h ei n i t i a lc o n d i t i o n s ，a n d u s e sn i s tt e s tp a c k a g et e s t s i t se x p o r t ，c o n f i r m si t st h eo p t i m u mr a n d o m k e yw o r d s ：o n e d i m e n t i o nc e l l u l a ra n t o m a t a ；r u l e o fc e l l u l a ra n t o m a t a ；p s e u d o r a n d o m n u m b e r sg e n e r a t i o n ；g e n e t i ca l g o r i t h m ；m o d eo fo u t p u t 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关 部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可 以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印 手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密酣使用本授权书。 ( 请在以上方框内打“v ”) 学位论文作者签名：忽钮玄 日期： 伽年只弓日 指导棚签名：犬百 日期：w 略7 目弓日 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。 本人完全了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名：度劣侈丢 日期：硼f 。耳1 ，目多目 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 随机数在现代网络安全中有重要而广泛的应用，通常并不能获得真正的随机数， 而是采用一些方法来生成伪随机数，目前常用的伪随机数发生方法主要有线性同余发 生方法，另外一种方法是线性反馈移位寄存器( l f s r ) 发生器，本文采用的基于元胞 自动机的生成方法则是这个领域的最新进展。 1 1 元胞自动机伪随机数发生器 元胞自动机伪随机数发生器是依据元胞自动机的局部作用原理，非常适合硬件实 现，又可以快速并行地产生伪随机数，具有非常优越的特点。 1 元胞自动机 元胞自动机是与连续c a n t o r 映射动力系统相对应的离散动力系统，具有时间、空 间、状态的离散性【l 】以及复杂的动力特征。1 9 5 1 年，v n e u m a n n 正式提出元胞自动机 的概念，随后元胞自动机理论在地理、数学、生物、经济和工程等领域得到了深入的 研究和广泛的应用。 w o l f r a m 最早将元胞自动机理论引入密码学，他提出了一种基于元胞自动机的序列 密码【2 j ，随后涌现了许多基于元胞自动机理论的随机数发生器、私钥密码、公钥密码和 h a s h 函数文献 3 - 6 。 2 元胞自动机伪随机数发生器 元胞自动机伪随机数发生器是利用元胞自动机的状态的离散性和并行迭代的特 征，将元胞自动机的元胞在某时刻t 的状态看作为伪随机数序列的一部分s ( t ) ，并通过 定时对这些元胞的状态进行采样来构成一个最终的随机数输出序列 ( s ( o ) ，s ( 1 ) ，s ( 2 ) s ( t ) ) ，如选择某个元胞的状态( 状态集为数集) 迭代的状态作为伪随 机数的位输出，或者一次选择多个元胞的作态( 状态集为数集) 的状态作为伪随机数 的一部分迭代输出。 w o l f r a m 在1 9 8 6 年利用一维元胞自动机设计出伪随机数发生器，产生了比反馈移 位寄存器更好的随机性，在一些关键的应用中，可以通过对序列中某点的定时采样， 可以得到质量更好的伪随机数。 1 2 基于一维扩展元胞自动机伪随机数发生器现状与研究意义 1 基于一维扩展元胞自动机伪随机数发生器的现状 在国外，已经w o l f r a m 、h o r t e n s i u s 、t s a l i d e s 、n a n d i 等人对c a 在随机数生成进行 了详细的论述，1 9 8 5 年w o l f r a m 首次提出了基于一维数元胞自动机的伪随机数序列2 1 ， 并将它应用于序列密码。文献 2 证明了该随机序列发生器优于其他广泛使用的随机序 西南交通大学硕士研究生学位论文第2 页 列发生器如基于同余和线性反馈移位寄存器的伪随机序列发生器。随后s i p p e r 和 t o m a s s i n i 引入算法来发现元胞自动机的规则，研究了基本元胞自动机中生成高质量伪 随机数的一维和二维元胞自动机规则，s e r e d y n s k i 等人对这种方法大大减少了寻找c a 规则的工作，能够找到满足条件的最优c a 规则。同时，g u t o w i t z 提出利用元胞自动 机的触发特性可以快速构造先导状态，只要把数据编码成初始状态，把元胞自动机动 力系统作为密钥，反向演化实现加密，正向演化实现解密的过程，实现了对称密码算 法。o l i v e i t a 等人对g u t o w i t z 方法进行了改进，提出了采用双向的元胞自动机产生随机 数用于加密，解决了误差单向传播的问题。但是，由于双触发元胞自动机规则的数量 要比单触发的规则要少得多，导致密钥空间太小，难以满足安全性的要求，因而必须 增加规则半径来增加密钥空间，而这又带来了计算量的大大增加【37 i 。近一些年来，主 要集中研究了二维元胞自动机伪随机数发生器，在不失去实现简单，统计性好的优点 的情况下，让元胞自动机的机构多样化，以提高它生成随机数的质量。 在国内，赵学龙、王庆梅、许满武和刘凤玉对一维扩展的伪随机数发生器进行了 研究，也获得了比较好的随机数发生器；朱保平、马骞和刘风玉将元胞自动机扩展到 二维，建立了二维梯形元胞自动机伪随机数发生器模型；夏学文、李元香和戴志锋又 提出了双层交叉元胞自动机的随机数发生方法；赵建林、方勇、扬玲和鲍丙芳又提出 了基于2 一b y n 细胞( 元胞) 自动机的伪随机数发生方法；随后，扬勇、方勇、夏天和 欧阳聪提出了一种基于2 - b y n 元胞自动机的高质量的伪随机数发生器。 2 基于一维扩展元胞自动机伪随机数发生器的研究意义 本文通过编程实现基于一维扩展元胞自动机的伪随机数发生器，通过对一维( 半 径为一并且无扩展三四五变量) 元胞自动机，一维扩展元胞自动机( 半径为一采用五 模式输出的三四五变量) 和一维扩展自动机( 三四五变量并且采用遗传算法) 实现并 得到较优的元胞自动机演化规则。为网络安全及信息安全提供一种比较适合硬件实现 的，简单快速的伪随机数发生器。 1 3 全文章节安排 论文主要目的是研制我国d t m b 标准的单频网适配器。全文详细讲述了d t m b 单 频网适配器的工作原理、硬件设计、软件编程以及样机测试等一整套设计过程，对实 现单频网组网具有非常重要的意义。全文共分为七章，具体安排如下： 第一章绪论提出了课题背景、意义和目标，以及全文章节的安排。 第二章介绍元胞自动机伪随机数发生器原理与结构。 第三章介绍n i s t 测试包。 第四章介绍遗传算法。 第五章介绍基本三、四和五变量自动机伪随机数发生器。 第六章介绍引入输出模式的一维扩展元胞自动机伪随机数发生器。 第七章介绍用遗传算法演化选择较好的伪随机数发生器规则。 最后，本文对研制过程进行总结，指出己取得的研究成果和需要改进的环节。 西南交通大学硕士研究生学位论文第3 页 第2 章元胞自动机伪随机数发生器的原理与结构 2 1 元胞自动机伪随机数发生器原理 2 1 1 元胞自动机简述 元胞自动机是与连续c a n t o r 映射动力系统相对应的离散动力系统，具有时间、空 间、状态的离散性要以及复杂的动力学特征。以一维元胞自动机为例，各个元胞按 线性( 非循环边界) 或圆环( 循环边界) 排列，每个元胞的状态形成一个状态集，元 胞的下一状态除了受自己现在状态的影响外，还受到左右邻居的影响，三变量的元胞 自动机就是影响半径为l 的情况。对于半径不同，其影响情况不同。对于二维和更高 的情况更加复杂。 元胞自动机理论涉及到多个领域，其应用也很广泛，本论文只是元胞自动机理论 在信息安全领域中的一个小的应用，其目的是为了得到随机性更好的随机数。 2 1 2 元胞自动机的数学定义与组成 1 元胞自动机的数学定义 3 6 】 元胞自动机是一个数学模型，其定义如下： 定义1 元胞自动机c a 是一个四元组，c a - - ( d ，s ，n ，f ) ，其中： d ：空间维数； s ：有限状态集； n ：邻域向量，是由z d 中个不同的位置向量组成，记为n = ( x l ，x 2 ，x m ) ； f ：局部转换函数，又称规则，是s m 到s 的映射； 根据定义，一维元胞自动机的邻域向量可以表示为n = ( ， ， ， ， ) ；其演化过程的一般表达式为： s i ( t + 1 ) - - f ( s i r ( t ) ，s i ( t ) ，s i “t ) ) ， i z ( 2 1 ) 其中，r 表示规则半径，s i ( t ) 为第i 个元胞在t 时刻的状态。本论文中空间维数d 为1 ，有限状态集s = 0 ，1 ) ，半径r 为l 。不同的是三变量的是半径r 为1 的基本元胞自 动机，而四变量五变量为半径为1 的扩展元胞自动机。 2 元胞自动机的组成 元胞自动机最基本的部分是由元胞、元胞空间、邻居及演化规则。简单讲，元胞 自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。 西南交通大学硕士研究生学位论文第4 页 图2 1 元胞自动机的组成 图2 1 是一维的元胞自动机的组成图，其维数d 为1 ，元胞空间为元胞状态集。 以下分别对元胞、元胞空间、邻居及演化规则简单介绍。 一、元胞 元胞又可称为单元，或基元，是元胞自动机的最基本的组成部分。元胞分布在离 散的一维、二维或多维欧几里德空间的晶格点上。 二、状态 状态可以是 o ，1 的二进制形式，或是 s 0 ，$ 2 ，s i s k ) 整数形式的离散集。严格 意义上，元胞自动机的元胞只能有一个状态变量，但在实际应用中，往往将其进行了 扩展，例如每个元胞可以拥有多个状态变量，本论文为了简化，依然采用0 和1 两种 状态。 三、元胞空间( l a t t i c e ) 元胞所分布在的空间网点集合就是这里的元胞空间。理论上，它可以是任意维数 的欧几里德空间规则划分，目前研究多集中在一维和二维元胞自动机上。对于一维元 胞自动机，元胞空间的划分只有一种，而高维的元胞自动机，元胞空间的划分为三角、 四方或六边形三种网格。元胞空间通常是在各维向上是无限延展的，这有利于在理论 上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件， 因此，我们需要定义不同的边界条件，一般分为循环边界和非循环边界，本论文采用 一维扩展元胞和循环边界。 四、邻居( n e i g h b o r ) 在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的 状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定 的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径， 来确定邻居，距离一个元胞内的所有元胞均被认为是该元胞的邻居。本论文基本元胞 自动机采用半径r 为1 ，即左和右两个元胞为邻居，扩展只是在此基础上引入其本元胞 或邻居元胞先前状态作为变量而已。 西南交通大学硕士研究生学位论文第5 页 2 1 3 元胞自动机伪随机数发生器发展概况与演化规则 1 元胞自动机伪随机数发生器发展概况 元胞自动机伪随机数发生器是将元胞自动机概念引入密码学的成果，最早将元胞 自动机引入密码学的是w o l f r a m ，他提出了一种基于元胞自动机的序列密码，随后涌现 了许多基于元胞自动机理论的随机数发生器、私钥密码、公钥密码和h a s h 函数文献。 w o l f r a m 、h o r t e n s i u s 、t s a l i d e s 、n a n d i 等人对c a 在伪随机数生成进行了详细的论述。 随后s i p p e r 和t o m a s s i n i 引入算法来发现元胞自动机的规则，研究了基本元胞自动机 中生成高质量伪随机数的一维和二维元胞自动机规则，s e r e d y n s k i 等人对这种方法大 大减少了寻找c a 规则的工作，能够自动地找出满足条件的最优c a 规则。 国内很多学者也对元胞自动机伪随机数发生器作了大量的研究，赵学龙、王庆梅、 许满武和刘玉凤在基本元胞自动机基础上提出一维扩展元胞自动机维随机数发生器； 朱保平、马骞和刘风玉将元胞扩展到二维上，建立了二维梯形元胞自动机模型；夏学 文、李元香和戴志锋提出了双层交叉元胞自动机的随机数发生方法；扬勇、方勇、扬 玲和鲍丙芳提出了基于2 - b y n 细胞自动机的伪随机数发生方法：随后，扬勇、方勇、 夏天和欧晓聪提出了一种基于2 - b y - n 元胞自动机高质量的伪随机数发生器。总体来看， 国内研究元胞自动机伪随机数发生器研究起步较晚，真正高质量又能应用于实际产品 的方法还没有出现，元胞自动机伪随机数发生器的研究有待继续努力。 2 元胞自动机伪随机数发生器的演化规则 元胞自动机是与连续c a n t o r 映射动力系统相对应的离散动力系统，具有时间、空 间、状态的离散性要以及复杂的动力学特征。以一维元胞自动机为例，各个元胞按 线性( 非循环边界) 或圆环( 循环边界) 排列，每个元胞的状态形成一个状态集，元 胞的下一状态除了受自己现在状态的影响外，还受到左右邻居的影响，三变量的元胞 自动机就是影响半径为1 的情况。对于半径不同，其影响情况不同。对于二维和更高 的情况更加复杂。 元胞自动机理论涉及到多个领域，其应用也很广泛，本论文只是元胞自动机理论 在信息安全领域中的一个小的应用，其目的是为了得到随机性更好的随机数。 2 2 三、四和五变量一维元胞自动机伪随机数发生器基本原理 下面分别介绍本论文研究的三、四和五变量一维( 包括扩展) 元胞自动机伪随机 数发生器的基本原理。 2 2 1 三变量一维元胞自动机伪随机数发生器基本原理 三变量的元胞自动机伪随机数发生器是最基本的元胞自动机伪随机数发生器，也 是论文中要多次提到的概念，每个元胞的下一个状态是由前后元胞和自己当前的状态 决定，其决定方式就是演化规则。仅为了介绍其原理，我们采用循环边界的一维元胞 自动机，即首尾元胞称为邻居，形成环状结构。其演化规则为： s i ( t + 1 ) = f ( s i 1 ( t ) ，s i ( t ) ，s i + l ( t ) )( 2 - 2 ) 西南交通大学硕士研究生学位论文第6 页 式2 2 为元胞迭代的演化函数，其演化函数结构如图2 1 所示： ia s i - k t ) s i ( t ) s i - q ( t ) a f ( s 1 1 ( t ) ，s i ( t ) ，s i + l ( t ) ) 1r i i a ” s i 1 ( t + 1 )s i ( t + 1 )s i + k t + 1 ) a 图2 - 1 三变量一维元胞自动机伪随机数发生器演化函数示意图 可以看出元胞演化函数是元胞自动机最核心的部分，它的质量好坏关系到整个元 胞自动机伪随机数发生器生成伪随机数的质量。 2 2 2 四变量一维扩展元胞自动机伪随机数发生器基本原理 四变量元胞自动机伪随机伪随机数发生器与三变量非常相似，不同之处就是演化 函数的不同，在三变量的情况之上引入了一个变量而已，而这个变量就是该元胞当前 状态的前一状态。其演化函数为： s i ( t + 1 ) = f i s i ( t - 1 ) ，s i 1 ( t ) ，s i ( t ) ，s i + t ( t ) ) ( 2 - 3 ) 式2 3 就是本论文四变量一维扩展元胞自动机伪随机数发生器的演化函数，其演 化函数的结构如图2 2 。 图2 2 可以看出四变量一维扩展元胞自动机伪随机数发生器的演化函数是比三变 量更复杂的结构，将自己的前一轮状态作为演化函数的一变量来影响下一态，扩展后 的四变量其演化规则有更多的可能性，这在后面的五、六、七章将会涉及到，而演化 规则是元胞自动机演化函数的实现，它的演化函数的具体实例化，也是该论文研究的 重点。 i a s i 1 ( t 1 ) s i ( t 一1 1s i + i ( t 一1 ) a | ￥；( t ) s i + l ( t ) aa s i 1 ( t ) 边 坟s i ( t - 1 ) ，s i i ( t ) ，s i ( t ) ，s i + l ( t ) ) 1 r ia s i 1 ( t + 1 ) s i ( t + 1 ) s i + l ( t + 1 )a 图2 2 四变量一维扩展元胞自动机伪随机数发生器演化函数示意图 西南交通大学硕士研究生学位论文第7 页 2 2 3 五变量一维扩展元胞自动机伪随机数发生器基本原理 五变量一维扩展元胞自动机伪随机数发生器是五变量一维扩展元胞自动机在随机 数生成上的应用，它与四变量一维扩展元胞自动机伪随机数发生器类似，不同的是在 四变量演化函数第一变量前引入了左边元胞的向前推第二代元胞状态作为第一变量。 同样，其演化函数为： s i ( t + 1 ) = f 【s i 1 ( t - 2 ) ，s i ( t - 1 ) ，s i x ( t ) ，s i ( t ) ，s i + l ( t ) ) ( 2 - 4 ) 式2 4 就是本论文五变量一维扩展元胞自动机伪随机数发生器的演化函数，其演化 函数的结构如图2 3 。 图2 3 可以看出五变量一维扩展元胞自动机演化函数同四变量结构很相似，比四变 量更加复杂，在初始化元胞自动机每个元胞的初始状态要初始化三轮，演化规则比四 变量的可能性更多了，这给了更多的选择较优演化规则的机会，同时也增加了搜素较 优演化规则的难度。作为演化函数实例化的演化规则，对于具体实现过程在后面的五、 六、七章将会涉及到。 | a s “t - 2 )s i ( t 一2 )s j + l ( t - 2 )a i i a s i 沁1 )s i ( t - 1 )s i + l ( t - l 、a i | a 。 s i - l ( t ) n s- ( t ) s h ( t ) a 卜 n f ( s i l ( t - 2 ) ，s j ( t 一1 ) ，s i 1 ( t ) ，s i ( t ) ，s i + l ( t ) ) 1r i a s i 1 ( t + 1 )s i ( t + 1 )s i + l ( t + 1 ) a 图2 3 五变量一维扩展元胞自动机伪随机数发生器演化函数示意图 西南交通大学硕士研究生学位论文第8 页 3 1n i s t 测试包介绍 第3 章n i s t 测试包 3 1 1n i s t 测试包通用序列随机性测试内容 n i s t 开发了通用的序列随机性测试软件。我们采用n i s t 测试包来测试元胞自动 机伪随机数发生器生成的随机数随机性的质量。n i s t 通过假设检验来检测序列的随机 性，包括了1 6 项测试：频率( 单比特) 测试，块内频率测试，游程测试，块内游程测 试，二进制矩阵秩测试，离散傅立叶变换( 频谱) 测试，非重叠模板匹配测试，重叠 模板测试，m a u r e r 通用统计测试，l e m p e l z i v 压缩测试，线性复杂度测试，序列测试， 近似熵测试，累积和( 累加和) 测试，随机偏移测试和随机偏移变量测试，下面对测 试内容进一步介绍。 n i s t 是最为全面和通用的随机数测试标准。通常我们采用n i s t 测试包来测试得 到的密钥材料( 随机数) 的质量。n i s t 设置的上述1 6 项测试的具体含义与要求如下【4 7 j ： ( 1 ) 频率( 单比特) 测试( f r e q u e n c y ) ：测试序列中“0 ”和“1 ”的比例。该测试要求序列 长度n = 1 0 0 比特。 ( 2 ) 块内频率测试( b l o c k f r e q u e n c y ) ：检测m 比特大小的块中的“1 ”的个数是否接近m 2 。 当m = i 时该测试退化为频率测试。该测试要求序列长度n = 1 0 0 比特，块长度m = 2 0 ， 并且m n 1 0 0 。 ( 3 ) 游程测试( r u n s ) ：测试序列中所有游程的数目，检测序列中各个长度的“0 ”和“l ” 的游程的数目是否随机。该测试要求序列长度n = 1 0 0 比特。 ( 4 ) 块内游程测试( 1 0 n g e s t r u n s ) ：测试序列中m 比特的块内的最大游程，检测被测序列 中“1 ”的最大游程是否与随机序列得到的结果相同。该测试中序列长度与块长度的 对应关系为：n = 1 2 8 时m = 8 ，n = 6 2 7 2 时m = 1 2 8 ，n = 7 5 0 0 0 0 时m = 1 0 0 0 0 。 ( 5 ) 二进制矩阵秩测试( r a n k ) ：测试序列中不相交的子矩阵的秩，检测整个序列中特定长 度字串的线性相关性。该测试默认的行m = 3 2 ，列n = 3 2 ，序列长度n = 3 8 m n 。 ( 6 ) 离散傅里叶变换( 频谱) 测试( m ) ：测试序列的离散傅里叶变换的峰值高度以测试 序列的周期特性，检测9 5 的峰值门限与5 f - j 限值是否有显著差别。该测试要求序 列长度n = 1 0 0 0 比特。 ( 7 ) 非重叠模版匹配测试( n o n p e r i o d i c t e m p l a t e s ) ：测试序列中预先指定的目标串的个数， 西南交通大学硕士研究生学位论文第9 页 检测产生器是否产生了太多的特定的j e 周期串。测试包序列长度n = 1 0 6 ，块长度 m = 1 3 1 0 7 2 ，如果使用其他长度，要求m 0 o l n 。 ( 8 ) 重叠模版测试( o v e r l a p p i n g t e m p l a t e s ) ：测试序列中预先指定的m 比特模式串的个数， 检测产生器是否产生了太多的指定的非周期串。与非重叠模版测试的区别是，匹配 成功时，重叠模版测试向后移动一个比特，而非重叠模版匹配移动m 个比特。该测 试要求序列长度n = 1 0 0 。 ( 9 ) 通用统计测试( u n i v e r s a l ) ：测试序列中模式串的数目，检测序列是否能显著压缩而不 损失信息。序列以l 比特的块被分为两大段( 6 三l 耋1 6 ) ，第一个段包含q 个初始块 ( q = 1 0 * 2 l ) 。第二段包含k 个测试块( r1 0 0 0 2 l ) 。 q o ) 压缩测试( 1 e m p e l z i v ) ：测试序列中累计相异模式的数目，检测序列可以被压缩的程 度。测试要求序列长度n = 1 0 6 。 o d 线性复杂度测试( 1 i n e a r - c o m p l e x i t y ) ：测试序列的线性复杂度，检测序列是否具有足 够的复杂度。测试要求序列长度n = 1 0 6 ，块大小5 0 0 耋m 三5 0 0 0 ，块数目n = 2 0 0 。 序列测试( s e r i a l ) ：测试序列中所有可能的重叠式m 比特模式的频率，当m = l 时该测 试等同于频率( 单比特) 测试。使用两个统计量v ：( d 加) 和v 2 ( o b s ) ，结果数据有两 组。要测试m c e l l u l a r n u m b e r = l ； r - g e n e r a t i o n 2 0 ： f o r ( i = 2 ；i d a t a = i v 【i 】； r - n e x t = l ； l - p r i r o r = r ； l - g e n e r a t i o n = o ： l - c e l l u l a r n u m b e r = i ； r = l ； ) r - n e x t = h e a d ； h e a d - p r i r o r = r ； 元胞的演化规则是采用了一个查表的的函数i n ts e a r c h t a b l e ( i n t * l e f t ，i n t * m i d d l e ，i n t r i g h t ) 来获取元胞的下一个状态，而元胞左右邻居的当时刻的状态就通过但个元胞中 结构体中的p r i r o r ，n e x t 两指针来完成，从而实现元胞的演化。以三变量的元胞自动机 伪随机数发生器的演化函数为例，查表函数i n ts e a r c h t a b l e ( i n t * l e f t ，h a t * m i d d l e ，i n t ，c r i g h t ) 是演化规则的实现主体，也是元胞自动机实现的基础。 3 基本维元胞自动机的输出方式 实验采用4 0 0 。个元胞，随机的选择一个元胞的状态作为输出，实验输出轮数采用1 西南交通大学硕士研究生学位论文第2 3 页 x1 0 8 作为代表，输出在一个文本文件中以便于用n i s t 柳0 试包测试其随机性。 4 基本一维元胞自动机随机数发生器输出的测试 对上面输出的文本文件，用n i s t 测试包测试。图5 1 、图5 2 和5 3 为其使用n i s t 测试包时的测试界面。在圈52 中，n u m b e ro fb i ts t r e a m s 输入为1 1 0 。，l e n g t ho f b i t 输入为1 0 0 - t t 一 “w m ru l r r r n r _ m i _ r0 - 】 - 4 a 一 - 1 阿_ ! 一 li i i x ：i j 图5 - ln i s t 测试包目0 试0 、i 数据流随机性界面1 在图b - 2 中，采用默认的测试参数，即b l o c kf r e q u e n c y 的b l o c k ：1 2 8 ： o v e r l a p p i n gt e m p l a t e s 的t e m p l a t e ：9 ；n o no v e r l a p p i n gt e m p l a t e s 的t e m p l a t e ：9 ： s e r i a l 的b l o c k1 6 ：a p p r o x i m a t eg n t o p y 的b l o c k ：1 0 ：l i n e a rc o m p l e x i t y 的 b l o c k ：5 0 0 ：u n i v e s a l 的n u m b e ro f ：7 、b l o c k ：1 2 8 0 。 要里塞塑奎耋鎏圭兰圣兰兰堡笙主里翌垂 翻5 - 2n i s t 铡试包测试0 、1 数据流随机性界面2 图5 - 3n i s t 测试包测试0 、1 数据流随机性界面3 西南交通大学硕士研究生学位论文第2 5 页 5 1 3 基本三变量元胞自动机伪随机数发生器演化规则研究 所谓基本一维元胞自动机三变量的伪随机数发生器，如5 1 1 介绍的一样，其演化 函数如式5 1 ，而其输出的随机性与演化规则密切相关，这也是本论文研究的地方。本 论文采用4 0 0 个元胞循环边界，随机选择了一个元胞输出1x1 0 8 个0 或1 ，以此来找 到比较好的基本的一维元胞自动机随机数发生器三变量的演化规则。三变量规则如表 5 - 1 ： 表5 - 2 基本三变量元胞自动机伪随机数发生器演化规则 十进制表示演化规则的二进制表示演化规则的二进制表示十进制表示 1 50 00 011 1 1 1 1 11 o00 o2 4 0 2 3o0010l1l111010002 3 2 2 7o0o1101111010002 1 6 2 9 o 0ol110110l1 l o0018 4 3 00o0111lo0111lo001 2 0 3 70ol0011lll10 o1002 2 8 4 3 0 010l01111o10l002 1 2 4 5o01o1l011o11o10o18 0 4 6 o010111o o l ll 01 0 o1 1 6 5 l00l1001111001l002 0 4 5 300llo10110101o017 2 5 4 0 0110l1o0ll0l0o1 0 8 5 7001110ollo011l001 5 6 5 800l1l010010111o09 2 6 0 00 1 1 1100 7 1o1o0o111l110 0o1o2 2 6 7 5010010l111oloo102 1 0 7 70l0011o11o110o1017 8 7 8o1o0l110o111001011 4 8 301o10o11l1001olo2 0 2 8 5 01o101011olol01017 0 8 9010110011oollolo1 5 4 9 0010l1010 9 9 o11o 001 l11 0oo 11o1 9 8 1 0 1o1l001011010011o1 6 6 l0 20110o110 1 0 5 01101 0o 110 01 o11 0 15 0 1 0 6011o1010ol0101108 6 1 1 301110 0ol10001101 4 2 1 3 5 1 o0 0 0111l110o0o12 2 5 1 3 9100010l1110l0oo12 0 9 1 4 1l00011ol1011000117 7 1 4 7 1 0o 1 001 1 1100100 1 2 0 l 1 4 91oo1o10l1o101oo11 6 9 1 5 31o0lloo1 1 6 3l01o001l110o o10l1 9 7 1 6 510lo0l01 1 9 511000011 由于规则中1 和0 出现等概率，故八位二进制中0 和1 各占四位( 如表5 2 ) ，相 当于八中取四的组合共有7 0 种。对每种演化规则进行运行，并对生成的随机数用n i s t 测试包测试，测试通过n i s t 测试包的如表5 3 。 以规则9 0 ( 即r u l e 9 0 ，简称r 9 0 ) 为例，对r 9 0 基本三变量元胞自动机伪随机数 发生器的输出测试，其过程如5 1 2 所介绍那样，通过测试结果线性回归图如图5 3 ( 为 了方便书写，“r 9 0 基本三变量元胞自动机伪随机数发生器输出”写成“第一代r 9 0 ”。) ： 西南交通大学硕士研究生学位论文第2 6 页 表5 - 3 通过n i s ta 试包的基本三变量元胞自动机伪随机数发生器演化规则 十进制表示演化规则的二进制袁示十进制表示 演化规则的二进制表示 6 0 00 1llloo 9 0o10ll010 1 0 2 1 9 5 n d t “。f - 圈5 0 第一代r 9 0 频率( 单比特) 检验测试线性回归图 要重至堡查主要主至圣兰耋簦笙兰要：要 7 - _ d - 。m h ! u ! 生_ j 图5 4 第一代r 9 0 块内频率检验测试线性回归图 n r d t _ 。h ，r qj 一川帅t 吐1w no 畸”l h f l i1 ，lh i 出ch o = d ，u 二 躅5 - 5 第一代r 9 0 累积和检验测试线性回归图 d 脚l 轴 亘要三鎏奎兰堡圭至圣兰兰堡丝塞矍：! 要 n u _ i 。h 。 吣io 一- mh “h i1 吐 耶i 唧r f j 瓤ri - j “i i ：_ - “i z ，i o 二u ! 一! l _ | 圈s - 6 第一代r 9 0 游程检验测试线性回归图 图5 - 7 第一代p - 9 0 长游程检验测试线性回归幽 西南交通大学硕士研究生学位论文第2 9 页 1 图5