（微电子学与固体电子学专业论文）真随机数发生器设计.pdf

中文摘要 随着科学技术的日新月异，随机数发生器( r n g ) 在许多方面有着广泛的应 用，如通信安全、娱乐、音乐、图像多媒体、模拟和测试、数学、电子商务电子 政务等等。目前在密码学的应用更为广泛，本项目正是应用于密码系统的随机数 发生器的一种实现。 由于硬件真随机数发生器( t r n g ) 在随机性上有着软件伪随机数发生器( p r n g ) 不可逾越的优势，本设计采用振荡采样法来产生所需要的随机数。即通过一个高 电平触发的d 触发器把两个独立的方波进行数字混合，用低速波来采样高速波， 并且用“异或链来使输出平稳。 由于离散小波变换在信号处理中的广泛应用，我们将小波分析的分解和重构 思想应用于随机数发生器的设计中，以提高真随机序列的品质。 设计分模拟和数字两部分进行，前者主要是振荡器的设计，我们采用了环形 振荡器电路。后者包含小波滤波器设计、异或链设计。本文给出了电路框图及主 要模块功能描述。最后，基于一定的测试指标和原理，对本设计得到的随机数进 行了测试和分析。 关键词：随机数发生器环形振荡器振荡采样小波变换滤波器分解重 构 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h es c i e n c ea n dt e c h n o l o g y , t h er a n d o m n u m b e r g e n e r a t o r ( r n g ) h a sg o tm o r ea n dm o r ea p p l i c a t i o ni nm a n ya r e a ss u c ha ss e c u r i t yo f c o m m u n i c a t i o n ，e n t e r t a i n m e n t ，m u s i c ，m u l t i m e d i a s i m u l a t i o na n dt e s t ，m a t h e m a t i c ， e t c t h i sp r o j e c ti so n cr e a l i z a t i o no fr n gi nc r y p t o g r a p h y s i n c et h et r n gh a sg r e a ta d v a n t a g eo v e rt h ep r n go nr a n d o m n e s s ，t h e o s c i l l a t o rs a m p l i n gt e c h n i q u ei sa d o p t e dt og e tn e e d e dt h er a n d o mn u m b e r sa f t e r w e v ec o m p a r e dd i f f e r e n tm e t h o d so f t r n g w eu s ead i g i t a lm i x e rr e a l i z e dw i t ha d n i p f l o pf l i p p e db yah i g hp o t e n t i a lt om i xt w oi n d e p e n d e n tc l o c k sa n ds a m p l et h e h i g h 行e q u e n c yd a t ai n p u tw i t ht h el o wf r e q u e n c yc l o c ki n p u t t os t a b i l i z et h eo u t p u t a “x o rc h a i n ”i sd e s i g n e d t h ed i s c r e t ew a v e l e tt r a n s f o r m ( d w l ) h a sb e e na p p l i e dt os i g n a lp r o c e s s i n g s y s t c i r s , w ca p p l yt h ed e c o m p o s i t i o na n dr e c o n s t r u c t i o no f w a v e l c ta n a l y s i st or a n d o m n u m b e rg e n e r a t o rt or a i s et h eq u a l i t yo ft r u er a n d o mn u m b e r t h ep r o j e c ti sd i v i d e di n t ot w op a r t s ：a n a l o ga n dd i g i t a lt h ef o r m e ri st od e s i g n t h eo s c i l l a t o ra n dh e r ew eu s er i n go s c i l l a t o r t h el a t t e ri n c l u d e sw a v e l e t ef i l t e r d e s i g na n d x o rc h a i n ”d e s i g n t h es i m u l a t i o n 、p a r a m e t e ra d j u s t i n g 、l a y o u t i n t e r c o n n e c t i n ga r ea l s op r e s e n t e dh e r e i nt h ee n dt h eq u a l i t yo ft h er n g i st e s t e db y s e v e r a lm e t h o d s k e y w o r d s ：r a n d o mn u m b e rg e n e r a t o r ( r n g ) r i n go s c i l l a t o r o s c i l l a t o rs a m p l i n g t e c h n i q u e w a v e l e tt r a n s f o r m f i l t e r d e c o m p o s i t i o n r e c o n s t r u c t i o n i i 附：学位论文原创性声明和关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究曾做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律责任由本人承担。 论文作者签名：盘纽 日 期：2 q q z 生垒旦 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权贵州大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：l 色红一导师签名：望堑日期：2 q qz 生旦 1 1 课题背景及意义 第一章前言 随着科学技术的日新月异，随机数发生器( r n g ) 在许多方面有着广泛的应 用，如通信安全，模拟和测试、数学，神经网络的计算，随机性能的仿真，数字 系统的内建自检测，游戏以及电子政务和电子商务系统等等。目前在密码学领域 中随机数发生器的应用更加广泛 随机数在密码技术中是非常重要的，比如密钥管理、众多的密码学协议、数 字签名和身份认证等都要用到随机数。比如：在计算机安全方面最权威的著作应 用密码学中，共有6 1 个密码学协议。用到随机数的协议就有4 0 多个【3 1 对于密码系统的安全性来说，每个组件都是很重要的。一个组件设计的失败 可能使其他所有的组件崩溃。而密码随机数常常被用作密钥，补充信息，辅助信 息和初始化向量。对每一个组件来说，使用个好的随机数发生器( r n g ) 是必 要的 在密码学领域中，无论是非对称算法中的私钥，还是对称算法中的密钥，其 原始钥匙都是由r 产生的。在密码学应用的许多场合，往往希望产生的随机数 是完全不可预测和真正随机的，人们将这种情况下的随机数发生器称作真随机数 发生器( t r n 6 ) ，它有别于伪随机数发生器( p r n 6 ) ，因为后者往往是基于计算 机算法而产生，这两者的相关知识，我们将在后面章节介绍。 因此，由上述观点我们可以看出，真随机数发生器设计这个课题的研究具有 以下重要意义： 首先，真随机数发生器的研究是信息传输保护的需要。随着计算机技术、互 联网以及其他数字技术的发展，信息系统建设也得到了很大发展，同时在信息安 全方面给人们提出了挑战这些就导致了对信息传输保护的巨大需求。而这种保 护通常采用信息加密来实现。随机数发生器则是信息加密设备的一个重要组成部 分，它产生不可预知、不可再现的密钥数字串对信息加密有着重要的作用。 其次，真随机数发生器的研究也是人们对高质量随机数和高安全性要求的需 要。随着信息化水平的不断提高，对高质量的随机数的要求也与日俱增。伪随 机序列虽然在一些统计特性方面接近随机序列，但是它有规律性和重复性，如果 攻击者有足够的计算能力，则随机序列是可预测的，安全性较差，设计者只能够 尽量提高算法的复杂度来防止对其的攻击，这显然不能适应目前计算能力迅速提 高的形势，也不能满足人们对安全性越来越高的要求。我们希望，即使攻击者有 无限的计算能力，并且已知所有的产生序列，也不能预测系统下一个要产生的随 机数，即真随机序列，因此，如何方便、快速的产生统计性能良好的真随机数已 成为一个重要的研究课题，从而真随机数发生器的研究也就显得尤为重要。 1 2 国际国内研究状况和进展 关于真随机数发生器，在国内外已有很多这方面的研究其中有不少是利用 噪声来实现的真随机数发生器 l i n u x 操作系统中产生真随机数随机位： l i n u x 操作系统是一种源码开放的操作系统，利用源码，可以进行许多实用 操作系统的开发。它有一套自己的硬件随机序列生成和使用方法。l i n u x 的随机 数源的获取有如下4 种方式： 键盘随机性：相邻两次击键的时间间隔及本次键盘的扫描码。 鼠标随机性；相邻两次鼠标移动的时间间隔以及由计算机硬件报告的鼠标实 际位置。 中断随机性：选取那些合适的中断，取两次中断请求的时间间隔。 块设备随机性：取块设备完成块操作的时问。 不同的获取方式每次会获得适当的随机位，为提取这些随机源的随机性，将 得到的随机位被存放在一个被称为。熵池”( e n t r o p yp 0 0 1 ) 缓存区中。当用户 需要用到随机序列时，先从“熵池”中读取随机数源，再计算所取数据的单向 散列值，然后将单向函数值反馈进“熵池”以保证下次取得的不是同样的值。 利用计算机磁盘驱动器的随机数发生器 3 4 】： 磁盘的偏差主要是空气震荡的噪声引起的，测量读取磁盘扇区的时问，利用 时间差作为随机数源。采样和去偏方法是把快速傅立叶变换用于该随机序列发 生器中。 i n t e l 的真随机序列发生器； i n t e l 公司研制了一种新的硬件随机序列发生器，它主要利用半导体内部的 热噪声和闪烁噪声等为随机源，对混合输出的信号进行采样，来产生密码技术需 要的真随机序列。它有基本噪声采样部分、数字处理部分、接口部分组成 3 2 硬件随机序列发生器属于密码产品，i n t e 的真随机序列发生器即使将来集成在 芯片中，在我国的一些重要部门也不能采用。 a t & t 公司的随机数发生器： a t & t 公司的随机数发生器是基于自激震荡器中噪声，引起频率的不稳定，对 这种不稳定的频率信号进行采样，以此作为随机序列 3 0 。 利用通讯线路和网络线路的噪声产生随机数 4 0 ： 这种随机序列的产生受线路质量的影响比较大，当通信线路质量很好时。产 一2 一 生的随机数较少并且这种随机序列发生器离实用化还有一定的距离。 最后是我们中国科学院信息安全国家重点实验室利用模拟和数字电路的各 种噪声成功研制了数字物理噪声源芯片 2 0 ，产生信息安全需要的真随机序列 1 3 论文各部分的主要内容 本论文主要内容分四章，第二章介绍密码学与随机序列理论的知识，包含密 码的用途、密码技术对随机序列的要求以及随机序列理论；第三章主要介绍了与 真随机数相对应的伪随机数以及伪随机数发生器的一些知识；第四章介绍了真随 机数的概念随机源以及产生方法，检验方法等；第五章是本论文的核心部分，包 含了主要的设计过程、结果、对设计电路的系统级仿真以及输出序列的一些检验 和主要结论。 一3 一 第二章密码学概述 密码学是一门古老而又年轻的科学早在公元前一世纪，凯撒大帝就曾用过 一种代换式密码。而直到1 9 4 9 年，信息论之父ce s h a n n o n 发表了密码系统的 通信理论 ，密码学才走上科学和理性之路 现代信息社会迫切需要现代密码学目前，各种通信网络极大地改变了人们 的生活与工作方式。随着信息化社会的不断发展，信息在社会中的地位越来越重 要，每个人的生活都与信息的产生、存储、处理和传递密切相关，信息的安全与 保密问题成了人人都关心的事情。商业和金融领域也由于i n t e n e t ，特别是电子商 务的发展而更加关注信息安全问题。当然，密码学在传统应用领域一军事上仍 起着重要而且是日益关键的作用。电子对抗，从1 9 9 1 年的海湾战争到阿富汗反恐 战争，已经发展成为空前的大规模信息战由此可见，信息战是信息化社会发展 的必然产物。在信息战场上能否控制和取胜，是赢很政治、外交、军事和经济斗 争胜刹的先决条件。因此，信息系统的安全保密问题己成为影响社会稳定、国家 安危的战略性问题。 现代密码学涉及数学( 如数论、近世代数、复杂性理论、组合算法、概率算 法及代数几何等) 、物理学( 如量子力学、现代光学、混沌动力学等) 、信息论、 计算机科学等学科，内容十分丰富。 真随机数发生器在现代密码学领域有非常重要的应用。它是密码系统硬件实 现中的重要组成部分，它为加密算法提供密钥。密钥的安全性决定了密码系统的 安全性，所以随机数发生器设计的好坏决定了密码系统的安全性。 本文主要讨论真随机数发生器的电路设计和实现。为便于理解设计真随机数 发生器对于密码系统的意义，本章将首先介绍密码学理论基础知识，包括密码系 统的数学模型，密码算法、密码协议，熵的概念，完善密码系统存在的条件，以 及随机序列的描述及其在密码技术中的应用。关于随机数发生器，将在后续两章 中进行讨论。 2 1 密码系统数学模型 密码学是以研究秘密通信为目的，即对所要传送的信息采取一种秘密保护， 以防止第三者对信息的窃取。密码系统设计的目的就是使窃听者即使在完全准确 地接收到信号地情况下也无法恢复出原始消息。 任何一种密码体制包括5 个要素：需要采用某种方法来掩盖其要传送的信息 或字符串称为明文；采用某种方法将明文变为另一种不能被非授权者所理解的信 息或字符串的过程称为加密变换；经加密过程将明文变成的信息或字符串称为密 文；用于具体加密编码的参数称为密钥，将密文还原为明文的过程称为解密变换。 密码通信的过程可用下图来表示： 一4 一 图2 - 1 密码系统模型 信源是产生消息的源，在离散情况下可以是字母或符号可以用简单的概率 空间描述离散无记忆信源。设信源字母表为弘 a ，i = o ，1 ，2 ，n - l ，字母a t 出 现的概率为p ( a t ) t 0 ，且罗p ) 一1 。信源产生的任一长为l 的消息序列 儡 m - o ，m 2 ，。仉) ，m t e m ，l ，墨工研究所有长为l 的信源输出，则称 p - 肘- m - 。，肼：，朋。) i 啊e m ，1 f s 为消息空间或明文空间，它盒有时 个元素若信源有记忆时，需要考虑p 中各元素的概率分布。当信源为无记忆时， 有弓( ，力- p ( m , ，。肼上) 一丌p ( 码) 信源的统计特性对密码的设计和分析有着 7 - r 重要的影响。 密钥源是产生密钥序列的源。密钥k 通常是离散的。设密钥字母表为 b - 也，i - 0 , 1 , 2 ，$ 一1 字母岛的概率为p ) o 且p ( 6 f ) - 1 一般设计中使密 钥源为无记忆均匀分布源，所以各密钥符号为独立等概率长为r 的密钥序列 k - 毛屯。t ，七岛。 e b 的全体称为密钥空间k ，且k - f 一般，消息空间与 密钥空问彼此独立。合法接收者知道k 和密钥空间k 。窃听者不知道k ，也不知道 或不确知k 。 加密变换是将明文空间中的元素m 在密钥的控制下变为密文c ，即 c 一( c l ，c 2 ，吒) 一( 魄，m ：，埘工) ，称c 的全体为密文空间。以c y f 表示，其中y 表示密文字母表。通常密文字母集和明文字母集相同。有l 一。 密文空间的统计特性由明文和密钥的统计特性决定。假定明文埘p 发生的 概率为只( m ) ，密钥被选择的概率为最 ) ，密钥是在发送者发送消息之前选定 的，因而可假定消息空间和密钥空间是独立的对于一个密钥七k ，令， g 一 b ) i m p ) ，对每一个c c ，有 见( c ) 。磊既 妇，( d i ( c ) ) ( 2 1 1 )罐邑 (- 1 ) p 。( c l m ) - p i ) 枷：瓦 由贝叶斯公式可得 p ，( m ) 罗p k ) 乃( m i c ) - 酉蒜 ( 2 1 2 ) 一5 一 由( 2 卜1 ) 和( 2 1 - 2 ) 知，只要知道明文空间和密钥空间的概率分步，任何人 都能确定出密文空间的概率分步和明文空间关于密文空间的条件概率分步可 见，密文空间的统计特性由明文空间和密钥空间的统计特性完全决定。 在密码系统研究中，假设信道是无干扰的，因而对于合法的接收者，由于知 道解密变换和密钥，而易于从密文得到原来得消息m ，即历一d k ( c ) o k ( e a r n ) ) 假定密码分析者可以得到密文c ，而且一般假定密码分析者知道明文的统计特 性、加密体制、密钥空问及其统计特性，但不知道加密截获的密文c 所用的特定 密钥那么，基于以上假设，密码的安全性完全寓于秘密密钥之中。所以密钥的 设计对于密码系统的安全性具有非常重要的作用关于密钥的概念，要涉及到密 码算法以及密码协议的知识，下面将一一介绍。 2 2 密码算法 密码算法是信息系统安全的根本，一个劣质的密码算法会使整个系统变得毫 无安全可言。 在2 1 节已经介绍过，一般来说我们称待加密的消息为明文，用p 表示：加密 后的消息为密文，用c 表示；将明文变换到密文的过程称为加密，用e 表示；加密 的逆过程，即由密文恢复到明文的过程称为解密，用d 表示；称对明文进行加密 时所采用的变换方法为加密算法，称对密文进行解密时所采用的变换方法为解密 算法；一般来说，加解密都是在组密钥( k e y ) 的控制下进行的，密钥用k 表示， 我们称加密时采用的密钥为加密密钥，解密时采用的密钥为解密密钥。那么我们 有： e k 。( p ) - c 砬：一p ( 2 2 1 ) 并且e 和d 必须满足 皿2 【瓦，( 尸) ) - 尸 ( 2 2 - 2 ) 根据密钥的特点，可以将密码算法分为两类：对称密码算法和非对称密码算法： 2 2 ：1 对称密码算法( s y m m e t r i c al g o r i t h m ) 有时又称单钥( 0 n e ke y ) 密码算法或私钥( p r i v a t e ke y ) 密码算法或传统 ( c l a s s i c a l ) 密码算法，一般来说，私钥密码算法的加密密钥和解密密钥相同或 者两者之间可以通过简单的变换互相确定。 对成密码算法是指加密密钥和解密密钥为同一密钥的密码算法。因此，信息 的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码( 称 为对称密码) 。在对称密钥密码算法中，加密运算与解密运算使用同样的密钥。 通常，使用的加密算法比较简便高效，密钥简短，破译极其困难；由于系统的保密性 主要取决于密钥的安全性，所以，在公开的计算机网络上安全地传送和保管密钥 是一个严峻的问题。 对称算法可分为两类。一次只对明文中的单个位( 有时对字节) 运算的算法 称为序列算法或序列密码。另一类算法是对明文的一组位进行运算，这些位组称 一6 一 为分组，相应的算法称为分组算法或分组密码现代计算机密码算法的典型分组 长度为6 4 位这个长度大到足以防止分析破译，但又小到足以方便作用 对称密码术的优点在于效率高( 加解密速度能达到数十兆秒或更多) ， 算法简单，系统开销小，适合加密大量数据但它也存在着明显的缺陷； 第一，迸行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情 况下是可行的，但在某些情况下会非常困难，甚至无法实现。 第二，规模复杂。举例来说，a 与b 两人之间的密钥必须不同于a j 阳c n 人之 间的密钥，否则给b 的消息的安全性就会受到威胁。在有1 0 0 0 个用户的团体中， a 需要保持至少9 9 9 密钥。推而广之，n 个用户的团体需要抑个不同的密钥。 最典型的对称密码算法是d e s 算法，d e s ( d a t ae n c r y p t i o ns t a n d a r d ，数据 加密标准) 算法，它是一个分组加密算法，它以6 4b i t 位( 8b y t e ) 为分组对数 据加密，其中有8b i t 奇偶校验，有效密钥长度为5 6b i t 。6 4 位一组的明文从算 法的一端输入，6 4 位的密文从另一端输出。d e s 是一个对称算法。加密和解密用 的是同一算法。其安全性依赖于所用的密钥 2 2 2 非对称密码算法( a s y m m e t r i c i g o r i t h m ) 也称双钥( h o ke y ) 密码算法或公钥( p u b l i c ke y ) 密码算法，其思想是由 w d i f f i e 和h e l l m a n 在1 9 7 6 年提出的不同于以往的加密技术，非对称密码术是 建立在数学函数基础上的，而不是建立在位方式的操作上的更重要的是，与只 使用单一密钥的传统加密技术相比，它在加解密时，分别使用了两个不同的密 钥：一个可对外界公开，称为“公钥” 一个只有所有者知道，称为“私钥”公钥 和私钥之间具有紧密联系，用公钥加密的信息只能用相应的私钥解密，反之亦然 同时，要想由一个密钥推知另一个密钥，在计算上是不可能的。 从以上的介绍中可以看出，与对称密码技术相比较，利用非对称密码技术进 行安全通信，有以下优点： 首先，通信双方事先不需要通过保密信道交换密钥。 其次，密钥持有量太太减少。在n 个用户的团体中进行通信，每一用户只需 要持有自己的私钥，而公钥可放置在公共数据库上，供其它用户取用。这样，整 个团体仅需拥有n 对密钥，就可以满足相互之间进行安全通信的需求。( 实际中， 因安全方面的考虑，每一用户可能持有多个密钥，分别用于数字签名、加密等用 途。此种情况下，整个团体拥有的密钥对数为n 的倍数。但即使如此，与使用对 称密码技术时需要n 沈个不同的密钥相比，需要管理的密钥数量仍显著减少。) 第三，非对称密码技术还提供了对称密码技术无法或很难提供的服务：如与 哈希函数联合运用可组成数字签名，可证明的安全伪随机数发生器的构造，零知 识证明等。 使用非对称密码技术的主要缺点是：加解密速度慢、耗用资源大。一般来 说，实用的加解密方案都综合运用了对称密码技术和非对称密码技术。 2 3 密码协议 一7 一 上一节我们介绍了密码算法，本小节内容主要包含密码协议的定义及其结构 模块。 所谓协议是指双方或多方使用密码技术来完成某种任务的一系列步骤，密码 协议在密码体制中是非常重要的。虽然算法是安全的，如果协议使用不正确，同 样会给入侵者以可乘之机。 下面简单介绍一下协议结构模块。 ， 2 3 1 使用对称密码术的通信 在介绍密码系统数学模型的时候我们讲过，通信双方通过对通信加密解密过 程实现保密通信，加密解密的过程就涉及到密码协议。 使用对称密码术的通信过程如下： 通信双方协商用同一密码系统。 通信双方协商同一密钥。 发信方用加密算法和选取的密钥加密明文信息，得到了密文信息。 发送密文信息给接收方。 接收方用同样的算法和密钥解密密文 对称密码算法存在的问题； 密钥必须秘密地分配，它们比任何加密的信息更有价值，因为知道了密钥意 味着知道了所有信息。 如果密钥被损害了( 被偷窃，猜出来，被逼迫交出来，受贿等等) ，那么攻 击者就能用该密钥去解密所有传送的信息，也能够假装是几方中的一方，产生 虚假信息去愚弄另一方。 假设网络中每对用户使用不同的密钥，那么密钥总数随着用户数的增加迅速 增多n 个用户的网络需要n ( n - 1 ) 2 个密钥。 2 3 2 单向函数 单向函数的概念是公开密钥密码的中心。尽管它本身并不是一个协议，但对 大多数协议来说却是一个基本结构模块。单向函数的概念是计算起来相对容易， 但求逆却非常困难。也就是说，已知x ，我们很容易计算f ( x ) 但己知f ( ) ， 却难于计算出x 。在这里，“难”定义成：即使世界上所有的计算机都用来计算， , a f ( x ) 计算出也要花费数百万年的时间 单向h a s h 函数就是一种单项函数，有时候也称为压缩函数，缩短函数、消 息摘要、指纹、信息完整性检验( d i c ) 、操作检验码( h d c ) 。不管你怎么 叫，它是现代密码学的中心。单向h a s h 函数是许多协议的另一个结构模块。 h a s h 函数长期以来一直在计算机科学中使用，无论从数学上或别的角度看， h a s h 函数就是把可变输入长度串( 叫做预映射，p r e - i m a g e ) 转换成固定长度 ( 经常更短) 输出串( 叫做h a s h 值) 的一种函数。简单的h a s h 函数就是对预映 射的处理，并且返回由所有输入字节异或组成的一字节。 h a s h 函数是公开的，对处理过程不用保密。单向h a s h 函数的安全性是它的 一8 一 单向性无论怎么看，输出不依赖于输入预映射的值的单个比特的改变，平均 而言，将引起h a s h 值中一半的比特改变已知一个h a s h 值，要找到预映射的值， 使它的h a s h 值等于已知的h a s h 值在计算上是不可行的 一般情况下，你应使用不带密钥的单向h a s h 函数，以便任何人都能验证 h a s h 值。如果你只想接收者才能验证h a s h 值，那么可以采用带有秘密密钥的单 n h a s h 函数来实现。 消息鉴别码( m a c ) 也叫数据鉴别码( d a c ) ，它就是一种带有秘密密钥 的单向h a s h 函数。h a s h 值是预映射的值和密钥的函数。这在理论上与h a s h 函 数一样，除非只有拥有密钥的某些人才能验证h a s h 值。你可以用h a s h 函数或分 组加密算法产生m a c ；也有专用于h a c 的算法。 目前h a s h 函数已有不少成熟的算法，比如：s h a ，m d 5 ，m d 4 等 2 3 3 使用公开密钥密码术的通信 对称算法可看成保险柜，密钥就是保险柜的号码组合。知道号码组合的人能 够打开保险柜，放入文件，再关闭它。持有号码组合的其他人可以打开保险柜， 取出文件来，而不知道保险柜号码组合的人就必须去摸索打开保险柜的方法 1 9 7 6 年，w h i f f i e l dd i f f i e 和m a r t i nh e l l m a n 永远改变了密码学的范例。 他们提出了公开密钥密码学。他们使用两个不同的密钥：一个是公开的，另一个 是秘密的。持有公钥的任何人都可加密信息，但却不能解密。只有持有私钥的人 才能解密。就好像有人把密码保险柜变成一个信箱，把邮件投进邮箱相当于用公 开密钥加密，任何入都可以做，只要打开窗口，把它投进去。取出邮件相当于用 私钥解密。一般情况下，打开它是很难的，你需要焊接机和火把。然而，如果你 拥有私钥( 开信箱的钥匙) ，就很容易从邮箱中取出邮件。 数学上，这个过程是基于单向陷门函数。加密是容易的，加密指令就是公开 密钥，任何人都能加密信息。解密是困难的，它做得非常困难，以致于不知道这 个秘密，即使用c r a y 计算机和几百万年的时间都不能解开这个信息。这个秘密 或陷门就是私钥。持有这个秘密，解密就和加密一样容易： 在实际的世界中，公开密钥算法不会代替对称算法。公开密钥算法不用来加 密消息，而用来加密密钥。这样做有两个理由： 首先，公钥算法比对称算法慢，对称算法一般比公钥算法快一千倍。是的， 计算机变得越来越快，在1 s 年后计算机运行公开密钥密码算法的速度比得上现 在计算机运行对称密码的速度。但是，带宽需求也在增加，总有比公开密钥密码 处理更快的加密数据要求。 其次，公开密钥密码系统对选择明文攻击是脆弱的。如果c = e ( p ) ，当p 是n 个可能明文集中的一个明文，那么密码分析者只需要加密所有n 个可能的明 文，并能与c 比较结果( 记住，加密密钥是公开的) 。用这种方法，他不可能恢 复解密密钥，但他能够确定p 。 如果持有少量几个可能加了密的明文消息，那么采用选择明文攻击可能特别 有效。对称密码系统不易受这种攻击，因为密码分析家不可能用未知的密钥来完 9 - 威加密的尝试。 在大多数实际的实现中，公开密钥密码用来保安全和分发会话密钥。这些会 话密钥用在对称算法中，对通信消息进行保密。有时称这种系统为混合密码系统 2 3 4 数字签名 在数字签名技术出现之前，曾经出现过一种。数字化签名”技术，简单地说 就是在手写板上签名，然后将图像传输到电子文档中，这种“数字化签名”可以 被剪切，然后粘贴到任意文档上，这样非法复制变得非常容易，所以这种签名的 方式是不安全的。 数字签名技术与数字化签名技术是两种截然不同的安全技术，数字签名与用 户的姓名和手写签名形式毫无关系，它实际使用了信息发送者的私有密钥变换所 需传输的信息。对于不同的文档信息，发送者的数字签名并不相同。没有私有密 钥，任何人都无法完成非法复制。从这个意义上来说，“数字签名”是通过一个 单向函数对要传送的报文进行处理得到的，用以认证报文来源并核实报文是否发 生变化的一个字母数字串 该技术在具体工作时，首先发送方对信息施以数学变换，所得的信息与原信 息惟一对应；在接收方进行逆变换，得到原始信息只要数学变换方法优良，变 换后的信息在传输中就具有很强的安全性，很难被破译、篡改。这一个过程称为 加密，对应的反变换过程称为解密。 现在有两类不同的加密技术，一类是对称加密，双方具有共享的密钥，只有 在双方都知道密钥的情况下才能使用，通常应用于孤立的环境之中，比如在使用 自动取款机( a t m ) 时，用户需要输入用户识别号码( p i n ) ，银行确认这个号 码后，双方在获得密码的基础上进行交易，如果用户数目过多，超过了可以管理 的范围时，这种机制并不可靠。 另一类是非对称加密，也称为公开密钥加密，密钥是由公开密钥和私有密钥 组成的密钥对，用私有密钥进行加密，利用公开密钥可以进行解密，但是由于公 开密钥无法推算出私有密钥，所以公开的密钥并不会损害私有密钥的安全，公开 密钥无须保密，可以公开传播，而私有密钥必须保密，丢失时需要报告鉴定中心 及数据库 2 3 5 随机和伪随机序列的产生 为什么在大多数介绍密码学的书中都不厌其烦地谈论随机数产生呢? 随机 数产生器己嵌入在大多数编译器中了，产生随机数仅仅是函数调用而己为什么 不用编译器的那种呢? 不幸的是，那些随机数产生器对密码来说几乎肯定是不安 全的，甚至可能不是很随机的。它们中的大多数都是非常差的随机数。 随机序列产生器并不是随机的，因为它们不必要是完全随机的。像计算机游 戏，大多数简单应用中只需几个随机数，几乎无人注意到它们，然而密码学对随 机数产生器的性质是极其敏感的。用粗劣的随机数产生器，你会得到十分奇妙的 相关和奇怪的结果。如果安全性依赖于你的随机数发生器，那么你得到的最后的 东西就是这种奇妙的相关和结果 一1 0 。 随机数产生器不能产生随机序列，它甚至可能产生不了乍看起来像随机序列 的数。当然，在计算机上不可能产生真正的随机数d o n a l dk n u t h 弓l 用j o h n v o nn e u m a n n 的原话：“任何人考虑用数学的方法产生随机数肯定是不合情理 的”计算机确是怪兽；数据从一端进入，在内部经过完全可预测的操作，从另 一端出来的却是不同的数据；把同一数据在不相干情况下输入进去，两次出来的 数据是相同的；把同样的数据送入相同的两个计算机，它们的运算结果是相同的 计算机只能是一个有限的状态数( 一个大数，但无论如何是有限的) ，并且输出 状态总是过去的输入和计算机当前状态的确定的函数。这就是说计算机中的随机 序列产生器( 至少，在有限状态机中) 是周期性的，周期性的任何东西都是可预 测的如果是可预测的，那么它就不可能是随机的。真正的随机序列产生器需要 随机输入，计算机不可能提供这种随机输入。 2 3 5 1 伪随机序列 最好的计算机能产生的是伪随机序列产生器，什么意思呢? 许多人试图形式 化地定义它，但我不赞成，随机数序列是看起来是随机的序列，序列的周期应足 够长，使得实际应用中相当长的有限序列都不是周期性的。就是说如果你需要十 亿个随机比特，就不要选择仅在万六千比特后就重复的序列产生器。这些相对 短的非周期性的子序列应尽可能和随机序列没有多少区别。例如：它们应该有大 约相同数目的0 和1 。长度为1 的游程大约占一半( 同一比特序列) ，长度为2 的 游程占1 4 ，长度为3 的游程占1 8 等等。它们应该是不可压缩的，0 和1 游程的 分布应该是相同的 6 4 3 ，8 6 3 ，9 9 ，1 3 5 7 。这些性质是根据实验测得的，然 后用c h l - s q u a r e 检验与统计期望值比较。 我们的意思是，如果一序列产生器是伪随机的，它应有下面的性质： 首先，看起来是随机的，这表明它通过了我们所能找到的所有随机性统计检验。 人们在计算机上已经做了许多努力来产生好的伪随机序列，学术文献中有很多讨 论伪随机序列产生器和各种随机性检验的。但所有这些产生器是周期的( 都不可 能例外) 。然而周期大于2 2 5 6 比特的随机数序列，能够大量得到应用。 密码学意义上安全的伪随机序列：密码的应用比其他大多数应用对伪随机序 列的要求更严格。密码学的随机性并不仅仅意味着统计的随机性，虽然它也是其 中的一部分。密码学意义上安全的伪随机数，还必须具有下面的性质： 其次，它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特 流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。像任何密码 算法一样，密码学意义上安全的伪随机序列产生器也会受到攻击，就好像加密算 法有可能被破译一样，破译密码学意义上安全的伪随机序列产生器也是可能的。 密码学讲的都是关于如何使产生器抵抗攻击。 2 3 5 2 真正的随机序列 现在我们走进哲学家的领域，真有随机数这样的东西吗? 随机序列是什么? 你怎么知道序列是随机的? “1 0 1 1 1 0 1 0 0 ”比“1 0 1 0 1 0 1 0 1 ”更随机吗? 量 子力学告诉我们，在现实世界中有真正的随机性。但是在计算机芯片和有限状态 机的确定世界中，这种随机性还能保持吗? 暂且不说哲学从我们的观点来说， 如果一个随机序列产生器具有下面的第三条性质，它就是真正随机的： 第三，它不能可靠地重复产生如果你用完全同样的输入对序列产生器操作 两次( 至少与人所能做到的最精确的一样) ，你将得到两个不相关的随机序列 满足这三条性质的产生器的输出对于一次一密乱码本、密钥的产生和任何其它需 要真正随机数序列产生器的密码应用来说都是足够好的。难点在于确定真正的随 机数。如果我用一个给定的密钥，用d e s 算法重复地对一个字符串加密我将得到 一个好的，看起来随机的输出。但你仍不可能知道它是否真的随机数，除非你租 用美国国家安全局的d e s 破译专家。 2 4 密钥 我们前面介绍了密码算法以及密码协议，密码协议安全直接影响到密码系统 的安全性，而密码算法的安全性也是衡量一个密码系统安全性的重要因素，而评 价密码算法的安全性时，首先得有如下一个假设： k e r c h h o f f s 假设：假设秘密必须完全寓于密钥中，攻击者知道所有关于密码算 法设计与实现的全部知识。 也就是说，算法可以公开，也可以被分析，可以大量生产使用算法的产品， 即使偷听者知道你的算法也没有关系。只要他不知道你使用的具体密钥，他就不 可能阅读你的信息。而那种基于对密码算法保密的信息系统是很不安全的。 由此可见，密钥的安全性对一个信息系统来说是非常重要的。我们前面介 绍了密码学的两种算法，其中对称密码用于加密和解密的密钥是完全相同的， 而非对称密码中公开的那把钥匙称为公钥，自己保管的那把钥匙称为私钥用 公钥把锁锁上的过程称为公钥加密，用私钥把锁打开的过程称为私钥解密。 密钥算法用来对敏感数据、摘要、签名等信息进行加密，常用的密钥算法 包括：d e s ( d a t ae n c r y p t i o ns t a n d a r d ) ；数据加密标准，速度较快，适 用于加密大量数据的场合； 3 d e s ( t r i p l ed e s ) ：是基于d e s ，对一块数据 用三个不同的密钥进行三次加密，强度更高；r c 2 和r c 4 - 用变长密钥对大量 数据进行加密，比d e s 快； i d e a ( i n t e r n a t i o n a ld a t ae n c r y p t i o n a l g o r i t h m ) 国际数据加密算法，使用1 2 8 位密钥提供非常强的安全性； r s a ：由r s a 公司发明，是一个支持变长密钥的公共密钥算法，需要加密的 文件快的长度也是可变的；d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m ) ：数字签 一1 2 名算法，是一种标准的d s s ( 数字签名标准) ；a e s ( a d v a n c e de n c r y p t i o n s t a n d a r d ) ，高级加密标准，是下一代的加密算法标准，速度快，安全级别高， 目前a e s 标准的一个实现是r i j n d a e l 算法；b l o w f i s h ，它使用变长的密 钥，长度可达4 4 8 位，运行速度很快；其它算法，如e i g a m a l 、d e f f i e - h e l l m a n 、 新型椭圆曲线算法e c c 等 对密钥安全性的影响因素很多，其中密钥序列的随机性是很重要的一个方 面。而无论是非对称算法中的私钥，还是对称算法中的密钥，其原始钥匙都是 由r n g 产生的因此，随机数发生器质量的好坏，将直接影响密钥的安全性 2 5 完善保密性 前面我们介绍了密码系统的基础知识，那么，怎样来衡量一个密码系统的好 坏呢? 衡量一个密码系统的安全性有两种基本方法，一种是计算安全性，另一种 是无条件安全性，又称完善保密性。计算上安全，指利用最好的算法破译该系统 需要至少n 次运算，n 是一个确定的很大的数无条件安全，指具有无限计算资源 的密码分析者也无法破译该系统。 密码系统的安全性是针对于某种攻击而言的，我们针对唯密文攻击来研究密 码系统的完善保密性，即无条件安全性它不能保证在已知明文或选择明文的攻 击下也是完善保密的。 利用熵的概念，可以计算图2 - 1 中密码系统各部分的熵。 2 5 1 熵的概念 某事件而，发生时的信息量，“) ，发生概率盹) 。信息量定义为： j ) - - l 0 9 2 p ) ( b i t ) ( 2 5 - 1 ) 由( 2 3 ) 式可以看到，事件发生的概率越低所含有的信息量越多设 石- 饥i i l l , 2 , ， ，葺出现的概率为p “) 0 ，且眠) 一1 集x 的熵( a p j l z 筒 - 均信息量) 定义为；( x ) 一一善e ( x , ) l 0 9 2 p ( x , x b i o ( 2 5 2 ) 式( 2 5 - 2 ) 表明进行排列的所有事件的平均信息量，在事件发生概率相等时 为最大其中h ( x ) 表示集x 中事件出现的平均不确定性，或者为确定集x 中出现一 个事件平均所需要的信息量( 观测之前) ，或集x 每出现一个事件平均给出的信息 量( 观测之后) 。 集x 相对于事件y 。y 的条件熵为： h ( x i y ) 一一p “1 ) ，) l 0 9 2 p l y j ) ( 2 5 3 ) 面 集x 相对于集y 的条件熵定义为： 一1 3 u ( x i y ，) - 一善p ( y ，) h ( x l y ，) 一荟z p ( y ，) p “i y j ) 1 0 9 2 p ( x , l y ，) ( 2 5 - 4 ) 式( 2 5 - 4 ) 表示观测到集y 后集x 还保留的不确定性。如果将x 视为一个系统的 输入空间，则y 视为系统的输出空间。在通信中，通常将条件熵h ( x i y ) 称为含糊 度( e q u i v a c a t i o n ) 2 5 2 完善密码系统 令明文空间的熵为h ( p ) - - h 叫) ，密钥空间的摘为h ( k ) - h ( b ) ，密文空间的熵 为h ( c ) = h ( y v ) ，在已知密文条件下明文的含糊度为h 耐1 1 f l ) ，在已知密文条件下 密钥的含糊度为h ( k i 矿) 。从唯密文攻击来看，密码分析者的任务是从截获的密 文中提取有关明