（通信与信息系统专业论文）密码算法性能测试及平台搭建.pdf

摘要 摘要 当今信息社会，信息的流动无处不在，因此信息的安全保密性显得越来越重 要。信息的保密与安全传输，一定程度上依赖于对信息的处理，而这种处理往往 是通过加密的方式来实现。一个实际的问题是：密码算法众多，如何评价密码算 法安全性的高低，这决定着对敏感信息保护的有效性。 本文从分组密码和流密码入手，着重进行分组密码和流密码的安全性分析， 给出有参考价值的评判标准，以便在实际应用中采用更合适的密码算法来实现信 息的保密及安全传输。文中提出了一种多密码算法的安全测试平台的设计方案， 并且通过编程手段完成了测试平台的搭建。通过对密码算法特点的分析，针对不 同的密码算法，采用不同的测试方案，在这些方案中尽量使平台的使用者对其实 现测试的细节弱化，只要求使用者提供必要的测试参数就能够完成安全性测试； 同时，也需要给平台的使用者留出扩展的接口，可以让使用者对未知的密码算法 也能进行我们提供的测试；为了使安全性测试更为实用，对测试算法的代码进行 了优化，并且统一了接口。 关键词：流密码分组密码随机性安全性分析测试平台 a b s t r a c t n o w a d a y s ，t h ei n f o r m a t i o ne x i s t si ne v e r y w h e r e ，s ot h es e c u r i t ya n d t h ep r o t e c t i o n o fi n f o n n a t i o nb e c o m em o r ea n dm o r ei m p o r t a n t t h ep r o t e c t i o n a n ds e c u r i t y1 1 3 t r a n s m i t t i n go fi n f o r m a t i o n ，s o m e w h a td e p e n do n t h et r a n s f o r m i n gw i t ht h ei n f o r m a t i o n ， w h i l et h i sp r o c e s s i n gs o m e t i m eu s i n ge n c r y p t i o nt or e a l i z e ap r a c t i c a lp r o b l e mi sh o w t oe v a l u a t ea ne n c r y p t i o na l g o r i t h m t h i sq u e s t i o ni si m p o r t a n tt o t h ev a l i d i t yi n p r o t e c t i n gi n f o r m a t i o n 1 1 1 i sa m d es t a r t sf r o mt h ei n t r o d u c t i o no fb l o c kc i p h e ra n ds t r e a mc i p h e r , f o c u s e s o nt h eb l o c kc i p h e ra n ds t r e a mc i p h e rs e c u r i t ya n a l y s i s ，a n dg i v e s t h er e f e r e n c e dr e s u l t s i no r d e rt oa c h i e v et h ei n f o r m a t i o nc o n f i d e n t i a la n ds e c u r et r a n s m i s s i o nw i t ha m o r e a p p r o p r i a t ee n c r y p t i o na l g o r i t h m id e s i g n e das e c u r i t yt e s tp l a t f o r mf o rm u l t i c i p h e r a l g o r i t h m ，a i l da c c o m p l i s h e di t sc o n s t r u c t i n gb yp r o g r a m m i n g t h r o u g ha n a l y s i st h e c 】 l a r a c t e r i s t i co fd i f f e r e n te n c r y p t i o na l g o r i t h m ，w eu s et h ec o r r e s p o n d i n gt e s tp l a n i n o u rd e s i g n ，w eh o p et h eu s e ro n l ys u p p o r t i n gt h en e e d e da r g u m e n t so f t h et e s tw i t h o u t k n o w i n gt h ed e t a i lp r o c e s s i n go f t h et e s t a tt h es a m et i m e ，w en e e dt or e s e ea n e x p a n d i n gi n t e r f a c eo ft h ep l a t f o r mf o rt h eu s e r s ，w h i c hl e tt h e u s e r se n a b l et ot e s tt h e u n k n o w nc i p h e ra l g o r i t h mt h a tw ep r o v i d e d f o rt h ep r a c t i c a b i l i t yo f t h e s es e c u r i t yt e s t s ， w ed i ds o m eo p t i m i z a t i o no nt h et e s ta l g o r i t h ma n du n i f i e dt h ei n t e r f a c ew h i c h u s e do n t h ep l a t f o r m k e y w o r d s ：s t r e a mc i p h e r t e s tp l a t f o r m b l o c kc i p h e rr a n d o m n e s ss e c u r i t ya n a l y s i s 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：二瞳 本人承担一切的法律责任。 日期 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本人签名： 导师签名： 复丛 日期半 日期丞啤：fi 第一章绪论 第一章绪论 随着计算机技术及网络技术的广泛应用，信息的传递越来越频繁，越来越多 样，与此共生的一个问题就出现了如何提高信息的安全性，如何保证敏感信 息的传输过程中不被窃取、篡改。 现代密码学的大力发展，使得对信息的保密及安全传输提供了强有力的支持， 然而究竟什么样的密码算法才是好的密码算法，如何评价其安全性，对不同密级 水平的信息采用与其密级水平相适应的加密算法，就成为一个比较实际的问题。 1 1 密码的发展历史 古典密码学【l 】：古典密码学的最经典的两个加密技巧是：置换和替代。置换： 将字母顺序重新排列；替代：有系统地将一组字母替换成其他的字母或符号。 由经典加密法产生的密文很容易泄漏关于明文的统计信息，因此，在现代密 码学看来，这种加密方法其实是很容易破解的。 现代密码掣2 】：现代密码学大致可被区分为数个领域。对称钥匙密码学指的是 传送方与接收方都拥有相同的钥匙。直到1 9 7 6 年这还是唯一的公开加密方法。现 代的对称密码学研究主要是分组密码( b l o c kc i p h e r ) 与流密码( s t r e a mc i p h e r ) 及其应用。 流密码：构造一段任意长的钥匙原料，与明文依位元或字符结合，有点类似 一次一密。输出的串流根据加密时的内部状态而定。在一些流密码中由钥匙控制 状态的变化。r c 4 3 j 是相当有名的流密码算法。 分组密码：取用明文的一个区块和钥匙，输出相同大小的密文区块。由于信 息通常比单一区块还长，因此有了各种方式将连续的区块编织在一起。d e s 和a e s 是美国联邦政府核定的分组密码标准( a e s 4 悯将取代d e s 4 】【6 】) 。尽管将d e s 从 标准上废除，d e s 依然很流行( t r i p l e d e s 变形仍然相当安全) ，被使用在非常多 的领域上，从自动交易机、电子邮件到远端存取。 密码杂凑函数( 有时称作消息摘要函数，散列函数或哈希函数) 不一定使用 到钥匙，但和许多重要的密码算法相关。它将输入资料( 通常是一整份文件) 输 出成较短的固定长度杂凑值，这个过程是单向的，逆向操作难以完成，而且碰撞 ( 两个不同的输入产生相同的杂凑值) 发生的机率非常小。 消息认证码【4 胴( m e s s a g ea u t h e n t i c a t i o nc o d e s ，m a c ) 很类似密码杂凑函数， 除了接收方额外使用私钥来认证杂凑值。 密码分析：密码分析又被称为破密技术。 密码分析的目的是发现密码机制的 弱点，分析者可能是意图颠覆系统的恶意攻击者或评估系统弱点的设计人。在现 2 密码算法性能测试及平台搭建 代，密码算法与协议必须被仔细检查和测试，确定其保证的安全性。 普遍误解认为所有加密法都可以被破解，但是后经证明，只要钥匙是完全随 机，不重覆使用，对外绝对保密，与信息等长或比信息更长的一次一密的加密方 式是不可能破解的。除了一次一密以外的多数加密法都可以通过暴力攻击法破解， 但是破解所需的努力可能随钥匙的长度指数成长。 密码分析的方式有很多，有数个分类。一个常见的分类法是根据攻击者知晓 信息的多少来进行分类。在唯密文攻击中，密码分析者只能存取密文，好的现代 密码系统对这种情况通常是免疫的。在已知明文攻击中，密码分析者可以存取多 个明文、密文对，通过明文密文对，对密码进行统计分析。在选择明文攻击中， 密码分析者可以自选任意明文，并被赋予相对应的密文。选择密文攻击中，密码 分析者可以自选任意密文，并被赋予相对应的明文。 对称钥匙加密的密码分析通常旨在寻找比己知最佳破解法更有效率的破解方 法。例如，以最简单的暴力8 】【9 】【1 0 1 法破解d e s 需要一个已知明文与2 s s 解密运算， 尝试近半数可能的钥匙。线性分析攻击法【l l 】对d e s 需要2 4 3 已知明文与2 t ，d e s 运 算，显然比暴力法有效。 通用的密码算法检测分析技术是公开的，但是各国专用的密码算法测评的核 心技术是不可能公开的，借鉴公开的密码算法的测评思想，研究专用的密码算法 的测评方法和测评技术是非常重要的，这是各个国家大力推进测评方法和测评技 术研究的主要目的。密码算法检测分析方法，借鉴国际上已提出的评价方法来实 现安全性的测评。 本文主要参考围际上提出的测试方法，对于各种测评算法在充分理解的基础 上，用编程实现测试算法，对相应的密码算法实现安全性分析，给出该种密码算 法的安全性分析结果，得出相对较为全面客观的评价。在此基础上实现测试平台 的搭建，最终使之成为一个具有实际应用价值的软件，以期在实际应用密码算法 是选择合适的算法来实现信息的保密及安全传输。 1 2 密码性能概述 密码算法的性能主要分为两个方面： 1 密码算法的运算性能：密码算法的运算性能是指密码算法在通过软件或硬 件实现的时候，算法在运算方面所体现出的性能。具体地说，就是算法的 实现速度及其稳定性方面的性能。一个密码算法再好，如果实现起来有一 定的网难，或者简单地说，运算速度很慢，或者不稳定，那么它在实用场 合，也不会有太大的用处。因此密码算法的运算性能是密码性能的一个重 要侧面。 第一章绪论 3 2 密码算法的安全性能：密码安全性能是指密码算法抵抗密码分析的能力。 使用密码算法就是为了信息的安全，如果被加密的信息的安全性不能保 证，那么密码算法也就没有什么实际意义了。因此密码算法的安全性能， 是密码性能的重要方面。 本文中所涉及的密码算法性能检测平台是针对密码算法安全性能分析的平 台，进行的是密码算法的安全性检测。 1 3 密码安全的级别 密码系统的安全性是评价个密码系统优劣的最高准则，但是密码系统的安 全性很难从理论上给出证明。衡量一个密码系统的安全性【2 】【1 2 有两种方式，其一是 无条件安全性，又称理论安全性；其二是实际安全性。 理论安全性是假定密码分析者的计算资源不受任何条件限制，但是对密码系 统的任何攻击，都不优于( 对明文) 完全盲目地猜测，这样的密码系统就称为无 条件安全的( 或完善保密的) 。一次一密的加密方式容易实现无条件安全性。因为 密钥时时更新，所以以往得到的任何明文密文对，对于破译新的密文没有任何帮 助，只能做完全盲目地猜测。 实际安全性是假定密码分析者的计算资源是有限的，即根据破译密码系统所 需计算量来评价其安全性。估计一个密码系统的实际保密性，需要考虑的主要因 素是密码分析者的计算能力和他所采用的破译算法的有效性。实际安全性又分为 计算安全性和可证明安全性两类。如果破译一个系统在原理上是可能的，但利用 所有已知算法和现有计算工具不可能完成所要求的计算量，则称其为计算上安全。 如果能够证明破译某系统的困难性等价于解决某个数学难题，则称其为可证明安 全。这两种安全性都是从计算量角度来考虑的，不同的是，计算安全要算出或估 计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低 于求解某个已知难题的计算量。如果利用已有的最好方法破译该系统所需的努力 超过了敌手的破译能力( 如时间、空间和资金等资源) ，或破译该系统的难度等价于 解决数学上的某个已知难题，如破译r s a 的难度等价于大数分解问题、破译 e 1 g a m a l 的难度等价于离散对数问题等，我们就称某个密码系统是实际安全的。 计算安全【2 】：计算安全是一个模糊的概念。 1 对密码系统的任何攻击，虽然可能优于完全盲目地猜测，但超出了攻击者 的计算能力。这是最高级别的计算安全。 2 对密码系统的任何攻击，虽然可能没有超出攻击者的计算能力，但所付出 的代价远远大于破译成功所得到的利益。这是第二级别的计算安全。 3 对密码系统的任何攻击，虽然可能没有超出攻击者的计算能力，但破译成 4 密码算法性能测试及平台搭建 功所需要的时间远远大于明文本身的有效期限。这也是第二级别的计算安 全。 1 4 密码系统安全组件 密码系统的安全性是评估密码系统的重要因素，再好的密码系统，若其安全 性不够则毫无实用价值，然而，密码系统的安全性很难从理论上进行充分论证， 主要依赖于经验性评估和实验检验。 流密码( 序列密码) 的安全性取决于随机数牛成器产生的密钥流是否足够的 “乱”，以及产生的密钥流的周期是否够“长”，因而随机数生成器是流密码的核 心安全组件。 公钥密钥体制的安全性都是建立在一个n p 问题基础上的，其中陷门单向函数 【l3 j 为公钥密码系统的核心安全组件。 分组密码体制可视为由一系列密码组件复合而成，分组密码的安全性则更多 地依赖于其核心安全组件，依据分组密码设计准则，其核心组件必须满足平衡性、 严格雪崩、高非线性度、高代数次数、多项数、输出比特相关性小及碰撞概率小 等系列密码学性能。目前分组密码中常用的扩散混合组件有s 盒、整数环上的m o d n 加法和整数或多项式环上的m o dn 乘法、矩阵与矢量乘法等。 大多数分组密码都选用s 盒作为系统的安全密码组件，以提供密码系统所需 的扩散和混合效果，s 盒作为大多数分组密码的唯一线性部件，其密码强度决定了 整个分组密码的安全强度，因此s 盒的设计与分析是分组密码设计中的一个重要 环节，其好坏直接影响分组密码体制的安全性。由于构造和实现大规格s 盒十分 困难，所以现在密码系统选取的s 盒都较小，1 5 个a e s 候选算法所采用的s 盒规 格有6 种，分别为4 x 4 ，6 x 4 ，8 x 8 ，8 x 3 2 ，1 l x 8 及1 3 x 8 ，虽然仔细地选择s 盒作为分 组密码的扩散混合组件，可以有较好的安全性，但由于s 盒规格小，相应的密码 算法需要采用多轮迭代才能达到较好的扩散混合效果，另外由于s 盒规格小，攻 击者对s 盒的性能容易进行统计分析，如d e s 采用6 x 4 小规格s 盒使得差分分析 者对其输入输出差分进行统计分析成为可能，因而差分攻击法对d e s 构造了较大 威胁。 1 5 密码算法的安全性定义 概括地说，安全性就是从任何角度难以攻破。其中两个最重要的角度是： 1 对于一个正在使用的加密算法，即使攻击者获得“许多”精心选择的明文密 文对，他仍无法“接近”密钥； 2 即使攻击者获得“许多”精心选择的明文密文对，他仍无法“接近”任一个新 第一章绪论 密文所对应的明文。 影响安全性的因素很多，诸如分组长度和密钥长度等。但有关实用密码的两 个一般的设计原则是s h a n n o n 提出的混乱【1 4 1 原则和扩散原则。 混乱原则：人们所设计的密码应使得密钥和明文以及密文之间的依赖关系相 当复杂以至于这种依赖性对密码分析者来说是无法利用的。 扩散原则：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数 字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数 字以便隐蔽明文数字的统计特性。 1 6 本论文的主要章节及安排 第一章绪论部分简要介绍密码学的发展，以及密码算法安全性分析的意义； 第二章介绍密码体制分类，以及各种密码体制的安全性的介绍；第三章详细介绍 密码算法安全性能评估方法；第四章介绍整个测试平台搭建的方案，以及具体采 用的安全性测试算法。 第二章密码体制简介 7 第二章密码体制简介 2 1 密码体制的分类 密码体制2 】【1 5 】分为对称密码体制( 单钥密码体制) 和非对称密码体制( 双钥密 码体制) 。对称密码体制( 单钥密码体制) 的加密密钥z 和解密密钥k 能够简单地 相互推导出来( 通常情况下z - k ) ，通信双方的地位是对称的，可以双向地发送和 接收保密信息。这样通信的双方采用相同的密钥来处理明密文，对明文实现加密， 对密文实现解密，如流密码、分组密码等；非对称密码体制( 双钥密码体制) 中 要从加密密钥z 推导出解密密钥k 是很困难的( 即使加密密钥z 唯一地确定了解密 密钥k ) 。公钥密码体制除了具有信息保密的功能以外，还具有了种信息认证功 能。通信双方共享公钥、加密算法，采用自己的私钥对信息加密、解密，典型算 法是r s a 3 】【1 6 】。 2 2 1 流密码的定义 2 2 流密码 流密码又称序列密码，设： 1 明文是比特流m ，称为明文流； 2 加密密钥和解密密钥相同，是比特流k ，称为密钥流； 3 密文是比特流c ，称为密文流； 4 加密算法和解密算法相同。加密：c = mok ；解密：m = c ok 。 2 2 2 流密码安全性分析 由流密码的定义容易看出，其安全性【1 1 7 】在于密钥流随机性的好坏。假设密钥 流k 是一个完全随机的序列，即：任意两个不相重叠的密文段，它们所对应的密 钥段都是相互独立的。换句话说，每一次加密都使用与以前的密钥段完全无关的 新的密钥段。再换句话说，此时的加密方式是一次一密的。因此，此时达到了最 高的安全性标准：无条件安全( 完善保密) 。实际应用中，由于密钥流k 必须由确 定的算法自动生成，因此是无法做到真正的随机的。不过这样的序列在攻击者看 来很像真正的随机序列，称这样的密钥流k 为伪随机序列。这样，实际中采用的 加密算法就无法做到真正意义上的一次一密，即不重叠的密文段，采用的密钥段 并不是相互独立的，这样就无法做到无条件安全。 密码算法性能测试及平台搭建 因此流密码的安全隐患就在密钥流k 的非随机性上，这也就成为了分析流密 码安全性的入手处。密钥流k 的随机性越好，即密钥流各个比特间的相关性越小， 则加密出的密文就越安全。 2 3 1 分组密码的定义 2 3 分组密码 分组密码取用明文的一个区块和密钥，输出相同大小的密文区块。由于信息 通常比单一区块还长，因此有了各种方式将连续的区块编织在一起，每个区块采 用相同的加密算法和相同的密钥。设： 1 明文和密文是固定长度为n 的比特串；m = m l m 2 m 3 m 。；c = c c 2 c 3 巳； 2 加密密钥和解密密钥相等，是固定长度为j 的比特串；z = z i z ：z ，z ，； 3 加密算法为c = e ( m ，z ) ； 4 解密算法为m = d ( c ，z ) = d ( e ( m ，z ) ，z ) ； 则称这样的加解密算法为分组密码。 2 3 2 分组密码的安全性 分组密码由一系列密码组件复合而成。因此对于分组密码来说其安全性可以 从算法的整体结构来考虑，也就是说通过检测明文与密文的相关性、密钥与密文 的相关性、初始向量与密文的相关性等统计信息来评判分组密码的安全性能。另 一个侧重点在于大多数分组密码所采用的s 盒组件。例如对d e s 的分析可知，其 安全性在于采用的s 盒【2 】【3 】对输入的混淆能力上。因此，对于具有s 盒密码组件的 密码算法，对s 盒的安全性检测也是我们必须考虑的内容。 2 3 3 分组密码的特点 2 3 4 5 分组密码的加解密算法( e ，d ) 简洁快速，所占用的计算资源小，易于软件 和硬件实现。一般来说，用硬件实现时，流密码比分组密码更简单快速；用软 件实现时，分组密码比流密码更简单快速。 加解密算法( e ，d ) 参数固定，比流密码更容易实现标准化。 由于明文流被分段加密，因此容易实现同步，而且传输错误不会向后扩散。 分组密码的安全性很难被证明，至多证明局部安全性。 分组密码所面对的丰要威胁是已知明文攻击。分组密码的密钥z 被重复使用， 即多次一密。因此最主要的威胁就是已知明文攻击。 为了抵抗已知明文攻击( 甚至选择明文攻击) ，分组密码应该满足的性质： 第二章密码体制简介 9 混淆性：所设计的密码应使得明文、密文、密钥之间的依赖关系相当复杂， 以至于这种依赖关系对密码分析者来说是无法利用的。密码分析者利用这种依赖 关系的方法非常多，因此混淆性也是一个极为繁杂的概念。 扩散性【l8 j ：所设计的密码应使得 1 密钥的每一个比特影响密文的每一个比特，以防止对密钥进行逐段破译； 2 明文的每一个比特影响密文的每一个比特，以便最充分地隐蔽明文。 非线性度：这一项属于混淆性。基本数学原理： 如果明文与密文的关系是1 1 维线性关系，系数是密钥，则n 个明文密文对( 而 不是2 n 个) 就可破解密钥； 如果明文与密文的关系是1 1 维r 次函数关系，且系数是密钥，则n r 个明文密 文对就可破解密钥； 如果次数r 较大，但明文与密文的关系“非常逼近”一个n 维线性关系，则n 个 明文密文对就可“基本上”破解密钥。 上述就是线性密码分析的思想。抵抗线性密码分析的强度就是非线性度。 2 4 杂凑函数 给定一个任意长度的消息m ，通过这样一个函数日( m ) ，使得函数的返回值 为个固定长度的散列值h ，其中h 的长度为m 。即，h = h ( m ) 。 单向散列函数3 1 应具备的特性： 1 给定m ，很容易计算出i z ； 2 给定h ，根据h = 日( m ) 计算m 很难； 3 给定m ，要找到另一个消息m 并满足日( m ) = h ( m i ) 很难； 杂凑函数是一类特殊的单向函数。 设数据文件是任意长度的比特串x 。在密码应用中，希望有这样的函数 y = 日( 功，满足 1 将x 压缩成为固定长度的比特串y 。 2 不同的z 一定要生成不同的y 。 3 由y 的值无法倒算x 的值。 我们把这样的单向函数称为杂凑函数。 对h a s h 函数的主要攻击方式是碰撞攻击。 碰撞攻击：找到两个消息m 和膨使得h ( 必) = h ( m ； 杂凑函数实际性质： 其性质来源于杂凑函数的定义：因此杂凑函数y = 日( x ) 满足 1 压缩性：将任意长度的比特串工压缩成为固定长度的比特串y 。 1 0 密码算法性能测试及平台搭建 2 单向性：己知x ，计算y = 日( x ) 很容易：已知y ，找一个x 满足y = 1 - i ( x ) 却 很困难。 3 无碰撞性：找( 五，x 2 ) ，五x 2 ，日( 五) = h ( x 2 ) ，很困难。 杂凑函数的构造标准： 1 不应具有可加性：设y = h ( x ) 对任意的x i ，x 2 ，h ( x 1 ) + 日( 恐) = h ( x l + x 2 ) 。 这样的函数不能作为杂凑函数。 2 不应具有线性：设函数y = 日( x ) 对任意的x ，a ，a h ( x ) = h ( a x ) 。这样的 函数不能作为杂凑函数。 3 不应具有局部置换性：设函数y = h ( x ) ，无论石为何值，x 的第一个比特 总等于y 的第三个比特。这样的函数不能作为杂凑函数。 4 不应具有某种连续性：设函数y = h ( x ) ，当y 。与“距离很近”时，存在 与恐“距离很近”，且y l = 日( ) ，y 2 = i - 1 ( x ：) 。这样的函数不能作为杂凑 函数。 5 设函数y = h ( x ) ，y 的固定长度太小。这样的函数不能作为杂凑函数，因 为可以用穷举的方法进行碰撞攻击。因此，杂凑函数y = i - l ( x ) 中，x 的任意一 个比特影响y 的每一个比特，达到充分的混淆和扩散。此外，y 的长度不能太 短，一般在1 2 8 以上，以防止用穷举的方法进行碰撞攻击。 杂凑函数的安全性： 从上述杂凑函数的构造标准可以看出，要想达到消息的充分混淆和扩散，使 得杂凑函数的安全性提高，就不能使选择的单向函数具有可加性、线性、局部置 换性、连续性等性质，而且杂凑出的杂凑值，应该保证具备一定的长度，以抵抗 碰撞攻击。 2 5 消息认证码 利用密钥对要认证的消息产生新的数据块并对数据块加密生成的。它对于要 保护的信息来说是一一对应的。因此可以有效地保护消息的完整性，以及实现发 送方消息的不可抵赖和不能伪造。 消息认证码的作用： 用来验证所收到的消息确实是来自真正的发送方且未被修改的消息，也可以 验证消息的顺序和及时性数字签名。 消息认证码的生成方式： 消息认证码生成有多种方式，主要方式还是采用广泛使用的单项散列函数， 来生成相应的消息认证信息，但这样的散列函数又不同于简单的杂凑函数，他是 有密钥参与的杂凑函数。 第二章密码体制简介 消息认证码的安全性【l9 】： 消息认证码的安全性取决于两点： 1 采用的加密算法，所谓数字签名。即利用公钥加密算法( 不对称密钥) 对 块加密，以保证消息的不可抵赖和完整性。 2 待加密数据块的牛成方法，消息认证不支持可逆性，是多对一的函数，其 定义域由任意长的消息组成，而值域则是由远小于消息长度的比特值构成，从 理论上说，一定存在不同的消息产生相同的冗余数据块。因此必须要找到一种 足够单向和强碰撞自由性的方法对消息认证才是安全的。 首先，利用校验码加密的方式构造认证码，它可以实现数据完整性，它对消 息不可抵赖不可伪造性的认证性能取决于加密的函数。因此这种方法的安全性取 决于校验码的长度和加密的方法。但是由于它是针对局部变量的校验，比如针对 一行或者一列，它的抗碰撞性能不是很好，即有可能产生消息被改动，认证码仍 然没有变动的情况。 其次，对于用单项散列函数构造认证码的方式来说，安全性是基于该函数的 抗强碰撞性的，即攻击主要目标是找到一对或更多对碰撞消息，该消息生成摘要 是相同的。在目前已有的攻击方案中，一些是一般的方法，是基于穷举的，可攻 击任何类型的h a s h 方案，例如生日攻击方法，另一些是特殊的方法，只能用于攻 击某些特殊类型的h a s h 方案，例如适用于攻击具有分组链结构的h a s h 方案的中 间相遇攻击，适用于攻击基于模算术的h a s h 函数的修正分组攻击。因此摘要的长 度是关键的一个因素。 2 6 公钥密码简介 双钥密码体制( 公钥密码体制) ： 于1 9 7 6 年由w d i f f i e 和m h e l l m a n 1 9 7 6 提出，同时r m e r k l e 1 9 7 8 也独立 提出了这一体制。可用于保密通信，也可用于数字签名。这一体制的出现在密码 学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术 基础。 公钥体制的基本原理是陷门单向函数。 一个函数f a b ，若它满足： 1 对所有x a ，易于计算f ( x ) 。 2 对“几乎所有x a ”，由f ( x ) 求x “极为网难”，以至于实际上不可能做到。 则称f 为一单向( o n e w a y ) 函数。 定义中的“极为困难”是对现有的计算资源和算法而言。 公钥密码就是基于数学难题构造这样的单向函数，主要的数学难题有求解离 1 2 密码算法性能测试及平台搭建 散对数问题，大数分解问题，背包问题，格向量最小等。 陷门单向函数( t r a p d o o ro n e w a yf u n c t i o n ) ，是这样的单向函数： 1 在不知陷门信息下，由f ( x ) 求x “极为困难”， 2 当知道陷门信息后，由f ( x ) 求x 是易于实现的。 公钥密码的一般要求： 1 加密解密算法相同，但使用不同的密钥； 2 发送方拥有加密或解密密钥，而接收方拥有另一个密钥； 安全性要求： 1 两个密钥之一必须保密； 2 无解密密钥，解密不可行； 3 知道算法和其中一个密钥以及若干密文不能确定另一个密钥。 第三章密码安全性能评估原理及方法 第三章密码安全性能评估原理及方法 3 1 流密码的测评原理 流密码是通过不断产牛的密钥流对信息逐比特进行加密，正是因为这样的加 密方式使得信息的加密近似为为一次一密的方式。如果密钥流是一个真正随机的 比特流，即，密钥流每个比特都与密钥流中其他的比特相互独立，这样加密出的 结果就能保证足够的安全性。对攻击者来说，收集再多的明密文对，也是徒劳的， 因为密钥流中比特之间的独立性，使得对明密文的统计信息在以后的攻击中毫无 用处。因此对流密码安全性能的评估就集中落在密钥流的随机性分析上。 3 2 流密码的测评方法 频率测试【2 0 】【2 1 】【2 2 】( f r e q u e n c yt e s t ) ： 频率测试主要测试的是一个待测序列中，0 和1 所占的比例。目的在 于确定一个二进制序列中o 和l 所占的比例是不是近似相等。由于真正的 随机序列，其0 和1 所占的比例是近似相等的，因此，我们从这一点来评 判这个测试序列是一个随机的序列。 分块频率测试( f r e q u e n c y t e s tw i t hab l o c k ) ： 分块频率测试主要测试的是l 在一个m 比特长的分块中所占的比例。测试 的目的在于确定一个长为m 比特的比特串，其中1 的个数是不是近似的等于 m 2 。如果测试的结果是1 的个数近似的等于m 2 ，我们就可以认为它是一个 随机的串流。当分块儿的长度m = i 时，这个测试就蜕变为频率测试。 游程测试( r u nt e s t ) ： 游程测试测试的是一个序列中的游程的总数，一个游程表示的是某一个字符 连续出现的串流。一个长为k 的游程，是由k 个某字符构成的，并且在其前后都 有一个相反的字符作为其确定的边界。测试的目的在于求解一个由o 1 构 成的不同长度的游程序列是不是满足一个随机序列的游程特性。尤其是，通过这 个测试来判断0 和1 之间的震荡是不是太快或者太慢。 l 最大游程测试( l o n g e s tr u no f o n e si nab l o c k ) ： 1 最大游程测试针对一个长为m 比特的区块中最长的1 游程。测试目 的在于是确定最长的1 游程的长度是否是连续的，如果是则可以认为测试序列 是随机序列。由于最长1 游程的无规则性同时也意味着0 游程的无规则性， 因此，仅仅测试l 游程就已经完全足够了。 二元矩阵秩测试( b i n a r ym a t r i xr a n kt e s t ) ： 1 4 密码算法性能测试及平台搭建 二元矩阵秩测试是统计整个测试序列中不相连的子矩阵的秩。测试的目的在 于测试来自于测试序列中固定长度子串间的线性独立性。这项测试来源于 d i e h a r db a t t e r y 测试中的第七项测试。 频谱测试( d i s c r e t ef o u r i e rt r a n s f o r n lt e s t ) ： 频谱测试是检测测试序列的离散傅里叶变换的峰高。测试的目的在于找出测 试序列的周期性，通过统计超过门限值9 5 的峰值数，来找出测试序列与真正的 随机序列相背离的情况。 非重叠匹配测试( n o n o v e r l a p p i n gt e m p l a t em a t c h i n gt e s t ) 非重叠匹配测试统计的是测试序列出现预先指定的目标串流的次数。测试的 目的在于统计测试序列中是否出现太多的非周期串流。一个m 比特的窗口用来匹 配特定的m 比特串流。如果没有匹配上，那么窗口向后滑动一个比特；如果匹配 上了特定的串流，就将窗口的起始位置重新设置到匹配上的位置，并且继续计数。 重叠匹配测试( o v e r l a p p i n gt e m p l a t e m a t c h i n gt e s t ) 重叠匹配测试也是统计随机序列中预先规定串流的出现次数。这个测试与非 重叠匹配测试同样采用m 比特的滑窗进行统计。统计的方法：如果没有匹配上串 流，向后滑动一个比特；如果匹配上串流，也是将滑窗向后滑动一个比特，然后 计数。 m a u r e r 通用统计测试 2 3 1 ( m a u r e r su n i v e r s a ls t a t i s t i c a lt e s t ) ： m a u r e r 通用统计测试统计的是两个匹配模式的比特数( 一种与被压缩的序列 相关的测试) 。目的在于测试一个序列是否可以被明显的压缩而不丢失所含有的 信息。如果一个序列可以被显著地压缩，而没有丢失信息，那么我们就可以认为 这个序列是个非随机的序列。 l z 压缩测试【2 4 】( l e m p e l z i vc o m p r e s s i o nt e s t ) ： l z 压缩测试在于统计一个待测序列中渐增的完全不同的模式( “字”) 的数 目。测试的目的在于确定待测序列究竟能多大程度地被压缩。如果待测序列可以 被明显地压缩，那么就可以认为他是非随机的序列。一个真正的随机序列的不同 模式的数目在统计意义上是个特定的数值。 线性复杂度测试( l i n e a rc o m p l e x i t yt e s t ) ： 线性复杂度测试的关键在于将待测序列看作是线性反馈移位寄存器( l f s r ) 产生的。测试的目标是检测待测序列，看其是否是足够的复杂，让我们可以认为 它是一个随机的序列。随机序列具有更长的l f s r 的阶数，如果一个l f s r 太短， 则我们可以认为它是一个非随机的序列。 连续性测试( s e r i a lt e s t ) ： 连续性测试关注的是一个序列中所有m 比特长的相互交叠的串流( 共2 m 种模 式) 出现的频率。测试的目的在于检测待测序列中长为m 比特的交叠的串流出现 第三章密码安哞= 性能评估原理及方法 的次数是否近似的等于真正的随机序列中相同模式出现的次数。真正随机的序列 中出现的次数是无规则的，也就是说，任何一个长为m 比特的模式与其他长为m 比特的串流出现的几率是相同的。值得注意的是：当m = l 时，连续性测试等效于 频率测试。 近似熵测试( a p p r o x i m a t et e s t ) 近似熵测试关注的与连续性测试一样，也是一个序列中所有m 比特长的相互 交叠的串流( 共2 m 种模式) 出现的频率。测试的目标是比较待测序列中两个连续 的长为m 和m + l 的交叠块出现频率与真正随机的序列的不同。 累积和测试( c u m u l a t i v es u m st e s t ) ： 累积和测试的重点在于将0 1 比特串转换成一l + 1 串流，计算最 大的随机游走。测试目标为求出待测序列中出现子