（模式识别与智能系统专业论文）基于混沌映射的随机数产生器.pdf

华中科技大学硕士学位论文 = ；= = = = = = ；= = ；= = = 自；= = = l 自；= 4 = = = _ 一 摘要 信息技术的发展对信息安全提出了新的要求，由于随机数产生器在众多信息 t 安全方法中的广泛应用，使得研究高性能的随机数产生器日益迫切。通过分析常 用的设计随机数器的三种方法，本文提出了一种兼具这些实现方法的优点，而又 、 避免了需要外接器件缺点的新的随机数产生器的实现方法。，a 一，- ， 本文从离散动力学和符号动力学的角度，严格证明了分段线性映射能得到随 机序列，并且从直观上解释了数据精度的有限性是这种确定映射函数能得到随机 序列的原因。在随机种子的产生上，本文创造性地采用数模结合的方法，将系统 中噪声随机源和d a 变换所得到的离散随机幅值结合起来，形成真正具有随机性 的种子。这种方法实现简单，克服了从随机过程或随机现象得到随机性的复杂性。 常用的离散系统可以采用开关电容和开关电流方式实现，通过分析比较，文中采 用开关电流方式实现，既保证了与数字工艺的很好兼容性又提高了速度。采用 c m o s 电路实现了系统中的初始值处理单元、函数模块、偏置模块等，并进行了 仿真。通过研究众多的随机性测试方法，选用较为通用的具有客观性的f i p s 一1 4 0 l 标准对所得序列进行了测试，结果证明本文中的方法是有效的。 本文的研究成果可应用于信息安全中各种需要加密的场合。， 关键词：随机数产生器 望鎏墅羞皇沉f i p s 一- 1 4 0 - 1 华中科技大学硕士学位论文 = = = = = = = ；= = = = = = _ _ = ；i j | ；_ = ；a 自目 a b s t r a c t t h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g yh a sp u tf o r w a r dt h en e wd e m a n dt o i n f o r m a t i o n s e c u r i t y , a n dh i g hp e r f o r m a n c er n g ( r a n d o mn u m b e rg e n e r a t o r ) b e c o m e sar e s e a r c hh o tp o i n tb e c a u s eo f t h ew i d e l ya p p l i c a t i o ni ni n f o r m a t i o n s e c u r i t y i nt h i st h e s i s ，am e t h o di s p r e s e n t e dw h i c hi n t e g r a t et h ea d v a n t a g e sa n da v o i dt h e s h o r t c o m i n g o f t h em o s tt h r e e p o p u l a rd e s i g n m e t h o d so f r n g i nt h i st h e s i s p i e c e w i s e - l i n e a rm a p c 眦s e tr a n d o m s e r i a lw i l lb ep r o v e ds t r i c t l y b yt h ev i e wo f d i s c r e t ed y n a m i c sa n ds y m b o ld y n a m i c s ，a n de x p l a i nt h er e r s o nt h a t m a p p i n g f u n c t i o nc a ng e tr a n d o ms e r i a li st h ef m i t yo fd a t a a c c u r a c y t h es y s t e mn o i s e s o u r c ea n dd i s c m mm a g n i t u d en 删t e db yd ac o n v e r s i o na r ec o m b i n e dt og e n e r a t e r a n d o ms e e db yt h ei n n o v a t i v em i x e d - c i r c u i tm e t h o dt h i sm e t h o di s v e r ys i m p l e b e c a u s ei to v e r c o m e st h ec o m p l e x i t yo f g e t t i n gr a n d o m s e r i a lf r o mr a n d o m p r o c e s so r p h e n o m e n a c o m m o n d i s c r e t es y s t e mc a nb ei m p l e m e n t e db ys w i t c h e dc a p a c i t a n c eo r s w i t c hc u r r e n t , a n di nt h i st h e m s ，s y s t e mi s i m p l e m e n t e db ys w i t c h e dc u r r e n t i t s c o m p a t i b i l i t yw i t hd i 酏a lp r o c e s sa n dh i g hs p e e d t h e i n i t i a l i z a t i o nu n i t ，f u n c t i o n m o d u l e ，b i a sm o d u l ei si m p l e m e n t e db yc m o sc i 咄a n d t h es y s t e mi ss i m u l a t e d t h i st h e s i ss e l e c tf i p s - 1 4 0 1a st e s ts t a n d a r dt ot e s tt h er a n d o m s e r i a la f t e rt h ec o m p a r e b e t w e e nd i f f e r e n tt e s ts t a n d a r d s ，t h et e s tm s u i ts h o w t h i sm e t h o di se f f e c t i v e t h er e s e a r c ha c h i e v e m e n to ft h i st h e w sc a nb ea p p l i e di ns o m ea r e s si nt h ed o m a i n o fi n f o r m a t i o ns e c u r i t y k e y w o r d s ：r a n d o m n u m b e rg e n e r a t o r ，c h a o s ，s w i t c h e dc u r r e n t ，f i p s - 1 4 0 1 i i 华中科技大学硕士学位论文 = = = = = = = = = ；= 。= = l i _ 自= ；_ t ；目_ _ = = j j _ z = = = = 一_ 1 1 课题目的与意义 1绪论 随着通信技术和计算机技术的迅速发展，信息资源越来越多，信息资源日益 成为越来越重要的资源。无论是国家或个人，信息资源占有的多寡与自身的利益 密切相关。但是由于信息资源的社会性和开放性，使得信息资源存在很多不安全 因素。如何保护自身的信息资源不被他人窃取及破坏成为越来越重要的问题。为 了有效地保护自身的信息资源，人们采取了众多的措施，其中加密是采用得最多 也是最为有效的保护方式。为此，人们发明了众多的加密算法。在密码学中，随 机数是极为重要的，在密钥产生和管理，众多的密码学协议，数字签名和身份认 证中都要用到随机数。在计算机安全方面最权威的著作应用密码学中所讲到 的六十多个协议中，有四十多个用到了随机数【l l 。因而获得高质量的随机数在加密 算法中是极为重要的，从某种程度上讲，随机数的随机性决定了整个加密算法的 性能。 随机数不仅用于信息安全中，在通信系统中也有广泛的应用。例如在扩频通 信中，对用于扩频的序列要求有尖锐的自相关函数和低的互相关函数。序列的平 衡性好，即序列中“l ”和“0 ”出现的概率基本相等 2 1 。这正好与二进制随机序 列的特性相符合，因而随机数在扩频通信中有广泛的应用。特别是随着通信速度 的提高，要求硬件实现随机数的要求更迫切，因而研究集成化的随机数产生器在 通信中也是极有意义的。 随机数还在科学研究有着极为重要的应用。蒙特卡罗是研究随机事件的一种 极为重要的方法，在进行蒙特卡罗分析的过程中就要用到随机数。同时在一些测 试分析过程中，测试模式的生成也要用到随机数，可见随机数在科学研究中也有 重要的应用。 随机数的广泛应用引发了对产生随机数的广泛研究。基于不同的应用目的， 华中科技大学硕士学位论文 人们得到了不同性质的随机数。为了便于后文的论述，有必要对随机数进行分类。 不同的文献对随机数的分类都不一样，这里采用得最多的一种分类方法。这 种分类方法把随机数产生器分为三类：一是基于随机物霆过程或现象的随机数产 生器，这类随机数产生器一般也被称为真随机数产生器【“。第二种是基于随机种子 的随机数产生器，这类产生器在给定了随机种子后所得到的序列是完全随机的。 但是这种随机数产生器的研究重点不在随机种子的产生上，其一般假设已存在可 用的随机种子。第三种为伪随机数产生器，其一般是通过数学函数的迭代得到的， 所得到的序列存在周期。这三种随机数产生器所产生的序列应用对象是不完全一 样的。一般伪随机数产生器在通信，科学研究和测试中用得比较多，而基于物理 过程或现象的随机数产生器和基于随机种子的随机数产生器在信息安全中的应用 比较多。 本论文所设计的随机数产生器是介于第一类和第二类之间的，其采用第一类 方法来得到随机种子，再采用第二类方法得到随机序列，也是用于信息安全中。 但是第一类实现方法和第二类实现方法一般需要外接器件，因而不适合i c 卡上应 用，因而，与其它随机数产生器设计相比，本论文具有更明确的应用目标，那就 是设计适合在i c 卡上集成的随机数产生器。 i c 卡在我们的日常生活中随处可见，如i c 电话卡，手机卡，还有在购物，社 会保险等中广泛使用的各种i c 卡。因而i c 卡有着很大的社会需求。同时由于信 息安全产品国产化是极为必要的，因而我们应该研究开发有着自主核心技术的i c 卡。随机数产生器作为i c 卡中的一个重要模块，在整个i c 卡的性能中起着至关 重要的作用。因而设计适合片上集成的随机数产生器是很必要的。 1 0 2 国内外的研究概况 上面所提到的三种随机数由于应用目标的不同，受社会需求的推动也不同， 因而各自的发展进程和研究现状也是不一样的。下面将就各自的发展进程和现状 作简单介绍。由于伪随机数产生器和本文所论及的随机数产生器关系不是很紧密， 故只做简略介绍，主要介绍基于随机物理过程和现象的随机数产生器和基于随机 华中科技大学硕士学位论文 = = = = = = = = = = = = ；自；= ；i ；自自= = = 种子的随机数产生器的发展进程和研究现状。 伪随机数产生器的实现方法很多，常用的有如下实现方法 4 1 ：v o nn e u m a n 在 1 9 4 0 年提出的平方取中法，其原理是将一个给定的2 n 比特的数平方后高位补0 得 到4 n 比特的数，再截取中间的2 n 比特进行下一次迭代得到随即序列。这种方法 实现简单，但是其周期受初始值影响，最大周期不超过2 “。f i b o n a e e i 方法也是一 种常用的方法，其实现需要两个初始值和一个模数m ，所得序列的周期为三m ， 2 实现也很简单。但是在所得序列中会有很多相同游程的子序列。1 9 5 1 年l e h m e r 提出的线性同余法是用得较多的伪随机数产生方法。其迭代通式为： z + l = ( 口墨+ c ) m o d m u + i = 墨“m u + 。为归一化表示，如果m 很大，那么u + ，在x e n 0 ，l 】上分布很密集且有近似的的 均匀分布，而且受初始值影响不大。在很多仿真过程中都用到这种随机数产生器。 硬件实现最多的一种伪随机数产生器是基于线性反馈移位寄存( l i n e a rf e e d b a c k s h i f tr e g i s t e r ) 器的唑其主要是根据下面所示的迭代方程： x = a 1 x 一10 口2 x 卜20 o 口。z 。一_ 其中珥 o ，1 )i = l ，2 ，3 埘，0 表示“异或”操作。m 表示电路中所用到的寄存器 数。将r a 个寄存器中所存储的数据通过“异或”网络后形成新的数据流。合适选取“异 或”网络中的系数口，能得到最长周期2 ”一1 ，当需要的寄存器很多，即m 很大时， 我们也可采用s r a m 来代替寄存器，这样所得序列的周期将更长，而且芯片面积 也不会很大。这种随机数产生器结构很适合f p g a 实现，但是遗憾的是，这种方 法虽然能得到较为均衡的序列，但是所得到的序列仍然存在明显的相关性。 基予随机物理过程和现象的随机数产生器是一种最直观的能获得真正随机信 号的随机数产生器。其研究最多，实现方式也最多。其中最主要的一种是基于随 机噪声的【6 1 f 7 1 ，其基本原理是将性能良好的噪声信号进行放大，采样，量化而得到随 华中科技大学硕士学位论文 = = = = = = = = = = 自= = = = = 目t = = 目z = ；= = ；= 机序列。其基本原理框图如图i - l 所示： 图l - l 基于噪声随机数产生器框图 噪声源可以是雪崩p - n 结噪声，s h o t 噪声和热噪声，但是由于p - n 的雪崩需 要一个较高的电压，而这个电压在芯片内很难提供，因而外接较多。同时由于雪 崩p - n 结的噪声谱不是很平坦，因而噪声性能不是很好。热噪声用得最多，一般 是采用电阻的热噪声。这种实现方式既有它的优势也有它的不利之处。优势是由 于这种结构一般是采用连续系统的方式实现，相对于离散采样系统的实现方式有 较高的带宽。因而能得到较高速率的随机序列，一般可以达到数兆比特秒的速率。 不利之处也很多。首先由于电路中除了采用的噪声源外，还存在另外的噪声源， 这些噪声源相互干扰，会影响所采用噪声源的性能【7 1 。比如采用电阻的热噪声源作 为信源，由于在芯片中缺乏有效的对电阻隔离的方法，使得电阻的热噪声受到另 外的噪声源如衬底噪声，电源波动噪声和l f 噪声等的影响，而这些噪声的强度要 远远强于热噪声，而且他们的分布与我们所期望的类白噪声分布相差甚远，因而 这种干扰对电阻热噪声源来讲是本质性的，最终所取得的信号很有可能是这些干 扰源所合成的，而所期望的电阻热噪声所起的作用可能很小。这些干扰源的频谱 与电阻热噪声的频谱有着严重的交叠成分，这使得即使通过滤波也很难将其分离 出来。由于这些噪声所合成的信号随环境不同分布可能有很大差异，因而很难形 成有效的模型来分析它，这使得也不可能通过对原始序列进行数字校正来改善它 的性能，因为缺乏有效的校正依据。其次，由于噪声信号幅度微小，一般的放大 器很难敏感这么微小的信号，因而为了能有效的放大微小的噪声信号，放大器的 4 华中科技大学硕士学位论文 敏感度应相当高，设计很高敏感度的放大器是一项很艰难的工程。放大器还应有 低噪功能，若放大器自身的噪声淹没了噪声源所输入的噪声，那么放大就失去了 意义，当然最后所得到的序列也不是我们所期望的。设计噪声性能如此良好的放 大器也是一件很困难的事。基于以上原因，采用这种方式设计的随机数产生器其 可控性差，不能确保所的到的随机序列能满足随机性要求，因而基于这种方式的 随机数产生器所占的比重原来越小。基于频率不稳定的振荡器的实现方式也是一 种较为常见的方法f 删。r c f a i r f i e l d 在1 9 8 4 年就提出了这种方法，这种方法的 原理图如图l - 2 所示： 几几几几n 广 门厂 f a s t - juuuulluil o s c i l l a t o r dq 数据流 厂 厂 厂 ) c k 一一l i c i o c k 图i - 2 基于频率不稳定振荡器随机数产生器框图 这种实现方式利用两个振荡频率不同的振荡器和一个寄存器来实现的。低频 振荡器的输出作为触发器的输入时钟，高频振荡器的输出作为振荡器的数据输入， 适当选取两振荡器的振荡频率和占空比，可以得到随机比特流输出。随机性的本 质来自于相位噪声所引起的高频振荡器的抖动。相位噪声由电路中的众多噪声源 共同作用而形成的。因而与基于噪声的随机数产生器不一样，不具有类白噪声分 布，同样由于模型不清晰，即使采用校正，也不会收到很理想的效果。基于a 巾 变换的误差具有随机性来实现随机数产生器也是一种有效的方法【1 0 l 。其基本原理 是将输入信号与经过a d 和d a 变换后的信号作比较，判断量化误差为正还是为 负从而进行量化得到二进制信号，并将量化误差放大后再进行量化，依此反复迭 代便得到二进制序列。本质上将量化所得的误差具有混沌性。基于混沌的实现方 式将在后面部分来讨论。 基于随机种子方式实现随机数产生器是当前研究随机数产生器的趋势。对一 切基于混沌影射的随机数产生器基本上都是属于这一类的【1 1 1 2 1 1 3 】【1 4 1 。对于这种实 现方式，若给定了随机种子，那么所得到的序列应该是非周期的，且具有尖锐的 自相关函数，而且对于不同的初始值应该得到不同的随机序列。混沌的定义决定 其是唯一符合此要求的映射【1 5 】，考虑到电路实现上的可行性，一般采用较为简单 的混沌映射，如l o g i s t i c 映射或分段线性映射，而且这类映射已经足够满足随机性 要求【“j 。但是在这些研究中，由于受各自需要的限制，很少考虑了随机种子的产 生问题，虽然在文献 1 1 】中考虑了初始值问题，但那种产生种子的方式存在严重的 局限性 1 6 】。这种实现方式。如果能很好解决随机种子的产生问题，那么其性能比 基于噪声方式的随机数产生器更优，而且在实现上要简单得多。 除了上面所论及的随机数产生器外，还有基于椭圆曲线来产生随机数的【1 7 1 和 基于遗传算法的等 1 a 】。 1 3 本论文研究内容 本论文在总结前人成果的基础上，研制出适合i c 卡上应用的随机数产生器， 为了达到这一目的，有下面这些内容需要在本文中研究： 一研究真正随机种子的产生方法。 基于随机种子的随机数产生器的研究已经很多，但是有很少的研究注重在怎样产 生随机种子上，有一些研究中也谈到种子的产生问题，但是产生方法都约束了种 子的选取区间，限制了其随机性。本文从数，模混合实现的角度构建一种新的随机 种子产生方法，在实现过程中引入噪声源来增强种子的随机性。 二基于新的随机种子产生方法，设计出随机数产生器。 采用开关电流技术设计出种子产生模块和映射量化模块等。充分考虑各种非理想 因素来优化电路参数的选取和设计。使电路在不锁定的前提下获得最佳随机性能。 三选取合理的测试标准，对所得随机序列进行随机性分析。 熟悉各种随机数测试方法和标准，并比较各自优缺点。选取广泛接受的测试方法 来测试随机序列，并分析测试结果，正确判断所得序列的随机性。 一 6 华中科技大学硕士学位论文 目日_ _ _ _ _ i _ l _ - _ _ _ _ 目= l 目目_ t _ i 目= # = 2 论文涉及的概念及基本原理 2 1 随机数产生器 随机数产生器本质上是离散的无记忆的各态历经的信号源，信源中各符号出 现的概率相等，且各符号间的转移概率也相同。所谓无记忆性是指当前符号的产 生与过去所产生的符号无关，不能通过过去所产生的符号来预测当前将要产生的 符号，亦即具有不可预见性。现实中所构造的随机数产生器各符号所出现的概率 是不可能完全相等的，转移橛率也不可能完全相同。一般采用冗余度来标识这种 理想信源与实际信源之间的差别程度，可表示为： p = l 一巩4 , 其中：h 。、h ，分别为实际与理想信源的熵( 1 9 】。 所谓熵，是信号源信息量的一种量度，从信号源的熵的大小可以直观地看出 信号源中各符号相关与否及相关程度。对于个符号的信号源s ，s 。( 滓l ，2 ，3 n ) 表示每个符号，p ( s 。) 表示符号s 。出现的概率，则信号源的熵可表示为： e ( s ) = 一p ( s ，) + l o g ( s 。) l ，i 对于随机数产生器所产生的随即序列，还可以利用序列的相关性来标识序列的随 机性能。 2 2 混沌 混沌是一个较为难懂的数学概念，在引入混沌的概念之前必需要介绍一些与 混沌概念相关的知识，以便于对混沌概念的介绍和理解。混沌本质上是离散动力 系统，因而先介绍一些离散动力系统的知识。为了正确理解混沌的随机性，必须 要从符号动力学的角度来认识混沌，因而也应了解一些与混沌相关的符号动力学 的知识乜町。1 儿船1 。 对于一个离散的动力系统：以+ = ，( 以) ，：埘b 膨其r 1 次迭代所得到的序 列记为x ，( x ) ，广( x ) ，尸( x ) ，其正向轨道定义为 0 + ( ) = z ，( x ) ，广( z ) ，广( z ) 。如果对某个z 。膨有尸( z 。) = 彳。 且不存在k n ，使得有广( x 。) = x 。，那么x 。，即为，的一个n _ 周期点。而 o ，( xo ) ，尸( z o ) ，尸( xo ) ) 即为，的n 一周期轨道。对于不同离散动力系统， 其周期点的性态是不一样的，有的周期点对周围的点有吸引作用，有的有排斥作 用。一般采用周期轨道的稳定与否来标识这一性态。稳定周期轨道定义为： 设是函数，( x 。) 的n 周期点，若f 广( x 。) f 1 ，则称x o 为，( 以) 的排斥周期点( 源) 。相应称 “ z 。，( x o ) ，2 ( ) ，f ( x 0 ) ) 为稳定周期轨道。这种稳定与否的讨论是针对周期 点的邻域内的点丽言的。在离散动力系统，中，如果存在集合x 使得，( x ) = x ， 那么z 成为，的不变集，特殊情况当x 退化为( 托 ，那么x 0 就称为，的不动点。 在混沌的描述中有一个很关键的术语吸引子。吸引子可以定义为：设x 是映射 ，：肜一的非空不变集。如果点x 满足广( x ) 一x ( r l - - - ) o o ) ，那么称点为不变 集x 的吸引点。不变集z 的吸引点全体称之为z 的吸引域，记为a ( z ) 。如果 存在开集u 使得a ( z ) ) u 3 x ，那么称不变集x 为，的一个吸引子。 为了便于理解，将从离散动力系统引出符号动力系统的一些概念a 对于给定 的离散动力系统以+ = ，( 以) ，：m m ，对区间m 进行划分等到p = c t ，c 2 ，c ，c n ) ， 因为是划分，故有c ，n c ，n c ，q = m ，c ，u c 。u c 。c 。= m ，定义符号集p 上的映射 兀( c 。) = c 。，厶：p - 啼p ，i ，j = l ，2 n 。设s 为f ( n 。一) 次迭代所得到的序列， 即s = s 。岛5 ：，j ，p ，i = l ，2 ，3 设由s 构成的空间为。，定义n 上的移位映射 一一 r 华中科技大学硕士学位论文 = = = = 目= = i ；= j = = = ；= ；= ： 6 ( s ) 2 6 ( s o 置s 2 ) = s i s 2 ，6 ：。斗。，下面来分析离散动力系统映射，和 一 符号动力系统映射6 的关系。 为了理解两种映射之间的关系，有必要先理解一个概念，即拓扑共轭“”。拓 扑共轭定义为：设a 和b 是两个拓扑空间，：4 斗一，g ：b _ b 分别是4 与丑 上的自映射，如果存在4 到b 的同胚 ：4 _ b ，使得| i l 。= g 。 ，那么称，和g 是拓扑共轭的。同胚可以近似理解为一一映射。拓扑共轭的映射具有下面的关系： 1 自反性：，与，是拓扑共轭的。 2 对称性：若，与g 拓扑共轭，则g 与，也拓扑共轭。 3 传递性：如，与g 拓扑共轭，g 与t 拓扑共轭，则，与t 也拓扑共轭。 因而拓扑共轭的映射间是等价关系。具有等价关系的映射间具有相同的动力学性 态。由于离散动力系统中的映射，与符号动力系统中的映射6 是拓扑共轭的，因 而可以通过研究简单的映射6 来了解复杂的映射， 下面以l o g i s t i c 映射为例，通过参数变化，来观察映射由非混沌向混沌的演 化过程，形象地理解混沌，为后面理解混沌的数学定义奠定基础。 l o g i s t i c 映射的表达式为：l ( x 。) = x ( 卜x ) ，这里只讨论o 4 ，x 0 ，1 的情况。 c a s e ：o l 与1 3 当0 1 时，令f x 。( 卜x ) = x 得 0 ，1 上唯一得不动点x 。= 0 ，o + = 1 ，0 ，0 ， ， 而当x o ( 0 ，1 ) 时，设0 + ( x o ) = ( x 0 ，x ，x 2 i ” ，则x i = x o ( 卜x o ) o ， 故x 。有极限，很容易得到此极限为0 ，这说明了：当o l 时，由，( x 。) = x 。( 卜 x 。) 所决定得离散动力系统很简单，除了不动点x 。= 0 ，没有其他的周期点，而x 。2 0 是其吸引不动点。当1 l ，为排 9 斥不动点，而，( 卜三) = 2 一卢，则f ，( 卜上) f l ，故为吸引不动点，可以证明对 p耻 于任意】【o ( 0 ，1 ) 都存在： 坳厂( x 。) = 1 一上，由上分析可知当l 1 ，吸引点失去稳定性，变成排斥点，形成一个新 的源。为了看清当- - - - - 3 时到底发生什么情况，我们利用计算机作数字分析，将其 近似的图形化出来。在区间( o ，1 ) 中任意的选取一个数作为迭代的初始值x 。让 计算机将其迭代，为了便于在窗口中绘制，丢弃前迭代1 0 0 次的数据，对应于每 一个2 ，迭代4 0 0 次，便能在窗口中得到较为清晰的图形，按一定步长扫描的 值，便能得到如图2 - i 所示的分支图。 一一一 l o 图2 - 1 混沌分支圈 由图可见卢= 3 时，单线开始一分为二，这表明出现了2 一周期点。在l 1 ，此时y = f 2 ( x 。) 与y = x 产生两个新的交 m 点，这样f ( x 。) - - = x 。除了0 ，卜二两个根外，由出现两个根p 、g ，这两个根不是 不动点，而是f ( x 。) 的2 一周期点。由于在 3 时，l 周期点失去稳定，2 一周期点 便产生了。我们称= 3 为倍周期分枝点。这个2 周期点可以求出来，由f ( x 。) = x 。可得：2x 。( 1 x j 1 一x n ( 1 一x j 2 k 消去x n ( x - - 1 + 丢) 因予，等价消去不动 点，可得： x z x n ( x 。+ 上) + l 掣：0 i x 故得2 一周期点为： x i ：= 去 ( 1 + i x ) 4 ( i x + 1 ) ( i x - 3 ) ( i x 3 ) 由于兰尸( 工? ) = l 一板万叹万面，从而当从3 变到1 + 否时，孚尸( 0 ) 由l c “ 靠 变到一1 ，i 1 1 13 i x l ，这样y = ，( x 。) 与y = x 除了0 ，卜二，i ，芏：四个交 甜 t 。 点外，又将产生四个交点，即厂( x t i ) 要产生四个新根，这就是4 一周期点。在p = 肫 处，产生第二次倍周期分支，t 周期点失稳，同时产生一条稳定得4 - 周期轨道。 4 一周期窗口比2 一周期窗口要窄，它只存在至胁= 3 5 4 4 0 9 0 3 5 9 ，在鸬处产生第三次 倍周期分支。由于所取得点数有限，使得我们不能看清太窄的分支，但数学 计算计算表明这些分支是确实存在的，而且周期窗口绘越来越窄，周期的分裂是 没有限制的。但u 的取值却有极限 。= 3 5 6 9 9 4 5 6 7 2 由于每次倍周期分支得到的周期解是稳定的，对( 0 ，1 ) 内的几乎所有初始值，它 的轨道将徘徊在这个唯一的稳定周期解附近，但当一风时，由于周期无穷长， 实质上便是非周期，这样o + ( x 。) 便没有什么规律可循，呈现出混沌特性。 当心 。( 。为映射产生混沌行为的临界值， 约为3 5 7 ) 时，映射有混沌行为。由于本文选择分段线性的混沌映射来产生随机数， 因而在分析混沌产生随机数原理时，也采用分段线性混沌映射来分析。双线性区 分段线性映射的表达式如下： 眠，= 麓：箍；：删 z ， 协， 由文献【3 可知区间上的离散分段线性映射在召 i ，2 】时具有混沌特性，利用此混 沌映射来分析其所产生序列的随机性。为了便于讨论，做如下假定：b = 2 ，映射 区间为对称区间卜4 ，a 】( 如图2 - 3 所示) 。 ，( x n ) 。j ， 吸 。 一l i ， o 1x n 。 ，。z ：! ， ，一1 图2 - 3 分段线性映射 以下面的推论即证明过程为基础，来分析混沌映射产生随机数原理。根据混 一 1 4 沌的拓扑传递性则可得： 推论：区间卜a ，a 1 上的任意点在任意初始点通过映射迭代所得的值序列中出 现且仅出现一次。 证明：对区间上的任意初始值妊和任意值k ，令u = 仁。 ，v = 慨 ，则根据 拓扑传递性，则必存在整数七 0 ，使得，( u ) n v 中，即厂( k ) = 匕，即区间 中的任意点都会出现在任意初始点通过迭代所构成的值序列中。若存在点p 在值 序列中出现两次，则必存在整数h 0 ，使得f ( x 。) = p ，f ( 五+ 。) = p ，令 u = 置，置。，置+ 。 ，矿= ，一u ( ，= - a ，刎) ，则不存在整数k 0 使得 f 。( u ) n v m ，与拓扑传递性相矛盾，故不存在点在值序列中出现多次。( 证毕) 根据推论，可得迭代变量工的概率密度函数为 贴) = 嵌髦卅a 棚 ( 2 - 2 ) 将区间 - a ，棚划分为 - a ，0 1 ， 0 ，a 】，分别用符号“0 ”，“1 ”来标识，在粗粒空间分析 符号0 和1 的统计特性。由式( 2 2 ) 可得p ( o ) = p o ) = 1 2 ，则两符号是等概率的。 根据2 - 3 ，可得转移概率p o l0 ) = p ( o io ) = 1 2 ，p ( o 1 ) = p ( 1 1 1 ) = 1 2 ，因而混沌映 射所构成的信源是等概率且符号间转移概率也相同。 上面虽然证明了混沌能够产生等概无记忆序列，但是此序列是否存在周期， 其随机性又由什么原因导，我们还是不清楚。下面将根据前面的论述来解释这个 问题。数的表示是存在精度问题的，即使给定一个数的精度很高，如能精确到1 0 “”，这个数仍然是不确定的，其实只是给定了一个以：1 0 - 1 ”为半径的一个邻域( 这 里只考虑一维空间的邻域) ，如果以映射作用于这个数就相当于以映射作用于这个 邻域，根据映射性质不同，将会出现不同的结果。对于不具有混沌特性的映射兄， 邻域内的点经过其作用后将收敛于一些周期点集上，而对于混沌映射c 作用后， 一 轨迹将分离开去，不收敛。示意如图2 4 ( 不同映射作用于同一邻域6 的情形) 盘毖 兄作用只作用 图2 - 4 不同映射作用相同领域 对于一个给定的可度量的初始值，设其精度为，o ，那么在以为中心，r o 为半径的领域内是不确定的。对于，虽然我们在可度量的范围内认为是确定的， 但是其真实值是我们所不可知的，而混沌迭代过程则是对这个真实初始值提供附 加信息的过程，每一个迭代数字的出现都是对真实初始值所在领域的范围的进一 步细分，由上分析可知混沌对任意小的初始值差别都敏感，因而只能通过无限次 迭代才能完整地提供真实初始值在领域中确切位置的信息。以对于数据精度有限 的混沌映射迭代过程，可以以数据精度的一半为半径，将映射作用区间进行划分， 假设映射作用区间为s ，依精度对区间进行了划分m - - - - - c j ，c 2 ，c 3 c 。) ，那么可及 从符号动力学的角度来讨论这个问题。定义一个m 上的映射吒：m m 使得如 果置c ，疋( z ) c ，那么( e ) = c ，f ，= l 二3 n 。那么如果存在映射只 和适当的划分m 使得在基于其上的映射的作用下，在吒迭代所得到的序列中各 符号的出现概率相同，各符号间的转移概率相同，且不存在周期，则r 映射就可 以用来产生随机数。推论中正好证明了试( 2 3 1 ) 在划分m = 【a ，o 】，【0 州) 及b = 2 的 情况下序列是等概的，而上面有证明了序列不存在周期，因而能作为随机数产生 器。混沌映射的迭代过程实际上是个逼近初始值的过程。每一次迭代都使得初 始值的不确定邻域的半径在减小，无限次迭代所得的序列与一个理论上完全确定 一 1 6 华中科技大学硕士学位论文 的初始值相对应，可见混沌映射所体现出的随机性实质上是由初始值的精度有限 性即不完全确定性所提供的。 至此，我们不但在理论上证明了混沌映射能产生随机数，而且直观地解释了 确定地混沌映射能产生随机行为的原因，下一章将根据此原理来设计随机数产生 器。 3 1 映射参数确定 3 系统结构及电路实现 在现实中存在很多映射，它们在一定的条件下具有混沌特性，它们的映射函 数有的简单有的复杂，在这些混沌映射中应选择一种合适的用来作为产生随机数 的信源。由于是采用集成电路的方式实现，因而所选择的映射函数应该形式简单， 这样不但电路设计简单，而且能节省芯片面积。其次所选择的映射函数在可实现 的情况下能得到很好的随机性。应用最多的混沌有l o g i s t i c 映射和分段线性映射， 但由于l o g i s t i c 映射中存在平方项，在电路中不好实现，而且实现平方项需要用到 模拟乘法器，受模拟乘法器带宽的限制，电路不可能操作在很高的频率，产生随 机比特的速率不能很高。而对于两区域的分段线性映射而言，其柯尔莫哥夫熵为1 ， 对于产生二进制的随机数来说已经足够了。同时由于两区域的分段线性映射参数 比较少，便于分析映射性能对参数的依赖关系，有利于参数的优化选择。因而本 论文采用如式2 3 1 表示的分段线性映射，选取a 的值为l ，则映射区间为 1 ，1 j 。 b 的可取值区间为【云，2 】b 值的选取是一个很关键的问题。如果选取b 为2 ，那 么映射可以表示为图3 1 所示 ，( x r o ， ， 穷 一t ， ， o 1x n 谣i 童 ， ，一1 ，。， ， ， 图3 - 1 分段线性映射 由于映射只在区间( 1 ，1 ) 之间是混沌的，当点越出此区间时，f ( x 。) 将向一 一 1 8 和- 一方向发展，当f ( 以) 达到一定值时，将使电路中的m o s 管进入饱和状态，使 一 ，( 以) 值趋于稳定，电路进入寄生吸引子，不能正常工作，使得映射关系变成如 图3 2 所示： 摹0 b i ) 。i i 。斧 一l ； 0 1h 一 够：；：逊。 o ， 图3 - 2 有寄生吸引子的分段线性映射 由于制造误差和系统中的噪声。如果选取b 为2 ，则使得越出区间( 1 ，1 ) 是 不可避免的，因而b 不能选取为2 ，必须存在一定的富余。b 也不能选取过小，选 取过小就会影响所产生序列的随机性。考虑到所采用的o 3 5 u r n 工艺的制造误差和 系统的噪声水平，因而要保正大约6 哆扣9 的冗余，因而b 在区间 1 8 2 ，1 8 9 之间 选取较为合理，在本论文中选取b 为1 8 6 。为了确保电路不进入寄生吸引子，则 应保证电路在进入寄生吸引子之前已进入饱和状态，为了实现这一点，必须合理 选择电路中某些关键m o s 管的尺寸和偏置电压。最终电路中所得到混沌映射的传 输曲线应如图3 - 3 所示： 1 1 ( 】【n ) ( 1 ，1 ) ，7 - ，：矛 一1 ， 0 1翻 r “ 图3 - 3 存在富余的分段线性映射 1 9 f ( 以+ 。) 2 3 2 实现方式选择 ( 3 一1 ) 由于所采用的映射是离散时间函数，而对于离散时间函数的实现较为常用的 有两种方式；开关电容( s w i t c h e dc a p a c i t o r ) 方式和开关电流( s w i t c h e dc u r r e n t ) 方式【2 6 l 唧【2 卅【2 9 】。至于这两种实现方式的优缺点可以参考文献 3 0 】。但是开关电流 方式有一些很显著的特点。首先在开关电流电路中只有m o s 管，因而能很好和 c m o s 数字工艺兼容，同时由于其不会用到运算放大放和比较器，因而与开关电 容电路相比，其所用到的管子数将大大减少，节省了面积，这对于面积因素很关 键的应用环境i c 卡系统来说是至关重要的。由于本文所设计的随机数产生器是面 向与i c 卡应用的，因而采用开关电流的实现方式。 在设计具体电路之前有必要先分析分段线性映射中所设计到的运算，观察式 ( 3 1 ) 可知所涉及到的算子有延时算子d ，求和算子和固定系数放大算子a 。”。下 面将介绍这些算子在开关电流电路中是如何实现的。 电流延时算子d 在开关电流系统中，延时是通过电流存储器( c u r r e n t m e m o r y ) 的串接来实现的。电流存储器的实现方法很多。”3 ，其中以下面这种实 现方式较为常用。 广j l ! ! 厂厂 厂 n ill i o 厂一 图3 - 4 开关电流存储单元 其中开关s 0 和s 1 分别由不重叠得两相时钟t o 和t l 控制，当t o 为高电平 时，t i 为低电平，则开关s 0 打开，而开关s l 关闭，i i n 通过s o 充电m o s 管m i 的栅极寄生电容c m i g ，将电荷储存在m i 的栅极上。当下半个时钟周期到来时， t 0 变为低而t l 变为高，s o 关断而s 1 开启，储存在m 1 栅极的电荷通过s 1 转移 到m 2 的栅极寄生电容c m g 上，由于m 1 和m 2 的尺寸相同，则l o u t 形负的电 流，其大小为i i n ，即l o u t = 一i i n ，延时为半个时钟周期即t 2 。那么若将两个电 流存储单元串接起来则能得到延时一个周期t 得延时器。其基本结构如图3 5 ： 图3 - 5 延时单元 其时序关系依然如图3 - 4 中所示，s o 开关和s 2 开关熟t 0 控制，s 1 受t 1 控 制。由于经过两次反相，所以输出l o u t 与i i n 是同相的，即l o u t = f i n 。延时时间为 一个周期t 。 电流求和算子。在开关电容电路中，求和电路是通过利用运算放大器和多 输入比例电路一起形成的。在开关电流电路中，求和运算则极为简单。根据基尔 霍夫电流定律，流入某个节点的电流之和等与流出此结点的电流之和。由此定律 一 2 1 ：竺中科技大学硕士学位论文 三 ： = ： 可知，开关电流电路中的电流求和可以通过连接结点简单的实现，可表示为图3 - 6 所示： 图3 , - 6 求和运算示意图 则有i i l + i i 2 + + l i n = i o l + 1 0 2 + + i o t a 。 固定系数放大运算a 。在开关电容电路中，电压量的放大是通过运放所构成 的比例放大电路来实现的。在开关电流电路中的电流放大器是通过种类似于电 流镜的结构来实现的。其基本结构如下： 图3 7 电流放大器示意图 由于v 擎m 产