硕士学位论文-密码算法性能测试及平台搭建.pdf

西安电子科技大学硕士学位论文密码算法性能测试及平台搭建申请学位级别：硕士专业：通信与信息系统20090101摘要摘要当今信息社会，信息的流动无处不在，因此信息的安全保密性显得越来越重要。信息的保密与安全传输，一定程度上依赖于对信息的处理，而这种处理往往是通过加密的方式来实现。一个实际的问题是：密码算法众多，如何评价密码算法安全性的高低，这决定着对敏感信息保护的有效性。本文从分组密码和流密码入手，着重进行分组密码和流密码的安全性分析，给出有参考价值的评判标准，以便在实际应用中采用更合适的密码算法来实现信息的保密及安全传输。文中提出了一种多密码算法的安全测试平台的设计方案，并且通过编程手段完成了测试平台的搭建。通过对密码算法特点的分析，针对不同的密码算法，采用不同的测试方案，在这些方案中尽量使平台的使用者对其实现测试的细节弱化，只要求使用者提供必要的测试参数就能够完成安全性测试；同时，也需要给平台的使用者留出扩展的接口，可以让使用者对未知的密码算法也能进行我们提供的测试；为了使安全性测试更为实用，对测试算法的代码进行了优化，并且统一了接口。关键词：流密码分组密码随机性安全性分析测试平台AbstractNowadays，theinationexistsineverywhere，SOthesecurityandtheprotectionofinfonnationbecomemoreandmoreimportantTheprotectionandsecurity113transmittingofination，somewhatdependonthetransingwiththeination，whilethisprocessingsometimeusingencryptiontorealizeApracticalproblemishowtouateanencryptionalgorithmThisquestionisimportanttothidityinprotectingination111isamdestartsfromtheintroductionofblockcipherandstreamcipherfocusesontheblockcipherandstreamciphersecurityanalysis，andgivesthereferencedresultsinordertoachievetheinationconfidentialandsecuretransmissionwithamoreappropriateencryptionalgorithmIdesignedasecuritytestplatulticipheralgorithm，aIldaccomplisheditsconstructingbyprogrammingThroughanalysisthec】laracteristicofdifferentencryptionalgorithm，weusethecorrespondingtestplanInourdesign，wehopetheuseronlysupportingtheneededargumentsofthetestwithoutknowingthedetailprocessingofthetestAtthesametime，weneedtoreseeanexpandinginterfaceoftheplatfortheusers，whichlettheusersenabletotesttheunknowncipheralgorithmthatweprovidedForthepracticabilityofthesesecuritytests，wedidsomeoptimizationonthetestalgorithmandunifiedtheinterfacewhichusedontheplatKeywords：streamciphertestplatblockcipherrandomnesssecurityanalysis西安电子科技大学学位论文独创性(或创新性)声明秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人签名：二瞳本人承担一切的法律责任。日期西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。(保密的论文在解密后遵守此规定)本人签名：导师签名：复丛日期半日期丞啤：fI第一章绪论第一章绪论随着计算机技术及网络技术的广泛应用，信息的传递越来越频繁，越来越多样，与此共生的一个问题就出现了如何提高信息的安全性，如何保证敏感信息的传输过程中不被窃取、篡改。现代密码学的大力发展，使得对信息的保密及安全传输提供了强有力的支持，然而究竟什么样的密码算法才是好的密码算法，如何评价其安全性，对不同密级水平的信息采用与其密级水平相适应的加密算法，就成为一个比较实际的问题。11密码的发展历史古典密码学【l】：古典密码学的最经典的两个加密技巧是：置换和替代。置换：将字母顺序重新排列；替代：有系统地将一组字母替换成其他的字母或符号。由经典加密法产生的密文很容易泄漏关于明文的统计信息，因此，在现代密码学看来，这种加密方法其实是很容易破解的。现代密码掣2】：现代密码学大致可被区分为数个领域。对称钥匙密码学指的是传送方与接收方都拥有相同的钥匙。直到1976年这还是唯一的公开加密方法。现代的对称密码学研究主要是分组密码(BlockCipher)与流密码(StreamCipher)及其应用。流密码：构造一段任意长的钥匙原料，与明文依位元或字符结合，有点类似一次一密。输出的串流根据加密时的内部状态而定。在一些流密码中由钥匙控制状态的变化。RC43J是相当有名的流密码算法。分组密码：取用明文的一个区块和钥匙，输出相同大小的密文区块。由于信息通常比单一区块还长，因此有了各种方式将连续的区块编织在一起。DES和AES是美国联邦政府核定的分组密码标准(AES4悯将取代DES4】【6】)。尽管将DES从标准上废除，DES依然很流行(tripleDES变形仍然相当安全)，被使用在非常多的领域上，从自动交易机、电子邮件到远端存取。密码杂凑函数(有时称作消息摘要函数，散列函数或哈希函数)不一定使用到钥匙，但和许多重要的密码算法相关。它将输入资料(通常是一整份文件)输出成较短的固定长度杂凑值，这个过程是单向的，逆向操作难以完成，而且碰撞(两个不同的输入产生相同的杂凑值)发生的机率非常小。消息认证码【4胴(Messageauthenticationcodes，MAC)很类似密码杂凑函数，除了接收方额外使用私钥来认证杂凑值。密码分析：密码分析又被称为破密技术。密码分析的目的是发现密码机制的弱点，分析者可能是意图颠覆系统的恶意攻击者或评估系统弱点的设计人。在现2密码算法性能测试及平台搭建代，密码算法与协议必须被仔细检查和测试，确定其保证的安全性。普遍误解认为所有加密法都可以被破解，但是后经证明，只要钥匙是完全随机，不重覆使用，对外绝对保密，与信息等长或比信息更长的一次一密的加密方式是不可能破解的。除了一次一密以外的多数加密法都可以通过暴力攻击法破解，但是破解所需的努力可能随钥匙的长度指数成长。密码分析的方式有很多，有数个分类。一个常见的分类法是根据攻击者知晓信息的多少来进行分类。在唯密文攻击中，密码分析者只能存取密文，好的现代密码系统对这种情况通常是免疫的。在已知明文攻击中，密码分析者可以存取多个明文、密文对，通过明文密文对，对密码进行统计分析。在选择明文攻击中，密码分析者可以自选任意明文，并被赋予相对应的密文。选择密文攻击中，密码分析者可以自选任意密文，并被赋予相对应的明文。对称钥匙加密的密码分析通常旨在寻找比己知最佳破解法更有效率的破解方法。例如，以最简单的暴力8】【9】【101法破解DES需要一个已知明文与2ss解密运算，尝试近半数可能的钥匙。线性分析攻击法【ll】对DES需要243已知明文与2t，DES运算，显然比暴力法有效。通用的密码算法检测分析技术是公开的，但是各国专用的密码算法测评的核心技术是不可能公开的，借鉴公开的密码算法的测评思想，研究专用的密码算法的测评方法和测评技术是非常重要的，这是各个国家大力推进测评方法和测评技术研究的主要目的。密码算法检测分析方法，借鉴国际上已提出的评价方法来实现安全性的测评。本文主要参考围际上提出的测试方法，对于各种测评算法在充分理解的基础上，用编程实现测试算法，对相应的密码算法实现安全性分析，给出该种密码算法的安全性分析结果，得出相对较为全面客观的评价。在此基础上实现测试平台的搭建，最终使之成为一个具有实际应用价值的软件，以期在实际应用密码算法是选择合适的算法来实现信息的保密及安全传输。12密码性能概述密码算法的性能主要分为两个方面：1密码算法的运算性能：密码算法的运算性能是指密码算法在通过软件或硬件实现的时候，算法在运算方面所体现出的性能。具体地说，就是算法的实现速度及其稳定性方面的性能。一个密码算法再好，如果实现起来有一定的网难，或者简单地说，运算速度很慢，或者不稳定，那么它在实用场合，也不会有太大的用处。因此密码算法的运算性能是密码性能的一个重要侧面。第一章绪论32密码算法的安全性能：密码安全性能是指密码算法抵抗密码分析的能力。使用密码算法就是为了信息的安全，如果被加密的信息的安全性不能保证，那么密码算法也就没有什么实际意义了。因此密码算法的安全性能，是密码性能的重要方面。本文中所涉及的密码算法性能检测平台是针对密码算法安全性能分析的平台，进行的是密码算法的安全性检测。13密码安全的级别密码系统的安全性是评价个密码系统优劣的最高准则，但是密码系统的安全性很难从理论上给出证明。衡量一个密码系统的安全性【2】【12有两种方式，其一是无条件安全性，又称理论安全性；其二是实际安全性。理论安全性是假定密码分析者的计算资源不受任何条件限制，但是对密码系统的任何攻击，都不优于(对明文)完全盲目地猜测，这样的密码系统就称为无条件安全的(或完善保密的)。一次一密的加密方式容易实现无条件安全性。因为密钥时时更新，所以以往得到的任何明文密文对，对于破译新的密文没有任何帮助，只能做完全盲目地猜测。实际安全性是假定密码分析者的计算资源是有限的，即根据破译密码系统所需计算量来评价其安全性。估计一个密码系统的实际保密性，需要考虑的主要因素是密码分析者的计算能力和他所采用的破译算法的有效性。实际安全性又分为计算安全性和可证明安全性两类。如果破译一个系统在原理上是可能的，但利用所有已知算法和现有计算工具不可能完成所要求的计算量，则称其为计算上安全。如果能够证明破译某系统的困难性等价于解决某个数学难题，则称其为可证明安全。这两种安全性都是从计算量角度来考虑的，不同的是，计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于求解某个已知难题的计算量。如果利用已有的最好方法破译该系统所需的努力超过了敌手的破译能力(如时间、空间和资金等资源)，或破译该系统的难度等价于解决数学上的某个已知难题，如破译RSA的难度等价于大数分解问题、破译E1Gamal的难度等价于离散对数问题等，我们就称某个密码系统是实际安全的。计算安全【2】：计算安全是一个模糊的概念。1对密码系统的任何攻击，虽然可能优于完全盲目地猜测，但超出了攻击者的计算能力。这是最高级别的计算安全。2对密码系统的任何攻击，虽然可能没有超出攻击者的计算能力，但所付出的代价远远大于破译成功所得到的利益。这是第二级别的计算安全。3对密码系统的任何攻击，虽然可能没有超出攻击者的计算能力，但破译成4密码算法性能测试及平台搭建功所需要的时间远远大于明文本身的有效期限。这也是第二级别的计算安全。14密码系统安全组件密码系统的安全性是评估密码系统的重要因素，再好的密码系统，若其安全性不够则毫无实用价值，然而，密码系统的安全性很难从理论上进行充分论证，主要依赖于经验性评估和实验检验。流密码(序列密码)的安全性取决于随机数牛成器产生的密钥流是否足够的“乱”，以及产生的密钥流的周期是否够“长”，因而随机数生成器是流密码的核心安全组件。公钥密钥体制的安全性都是建立在一个NP问题基础上的，其中陷门单向函数【l3J为公钥密码系统的核心安全组件。分组密码体制可视为由一系列密码组件复合而成，分组密码的安全性则更多地依赖于其核心安全组件，依据分组密码设计准则，其核心组件必须满足平衡性、严格雪崩、高非线性度、高代数次数、多项数、输出比特相关性小及碰撞概率小等系列密码学性能。目前分组密码中常用的扩散混合组件有S盒、整数环上的modN加法和整数或多项式环上的modN乘法、矩阵与矢量乘法等。大多数分组密码都选用S盒作为系统的安全密码组件，以提供密码系统所需的扩散和混合效果，S盒作为大多数分组密码的唯一线性部件，其密码强度决定了整个分组密码的安全强度，因此S盒的设计与分析是分组密码设计中的一个重要环节，其好坏直接影响分组密码体制的安全性。由于构造和实现大规格S盒十分困难，所以现在密码系统选取的S盒都较小，15个AES候选算法所采用的S盒规格有6种，分别为4x4，6x4，8x8，8x32，1lx8及13x8，虽然仔细地选择S盒作为分组密码的扩散混合组件，可以有较好的安全性，但由于S盒规格小，相应的密码算法需要采用多轮迭代才能达到较好的扩散混合效果，另外由于S盒规格小，攻击者对S盒的性能容易进行统计分析，如DES采用6x4小规格S盒使得差分分析者对其输入输出差分进行统计分析成为可能，因而差分攻击法对DES构造了较大威胁。15密码算法的安全性定义概括地说，安全性就是从任何角度难以攻破。其中两个最重要的角度是：1对于一个正在使用的加密算法，即使攻击者获得“许多”精心选择的明文密文对，他仍无法“接近”密钥；2即使攻击者获得“许多”精心选择的明文密文对，他仍无法“接近”任一个新第一章绪论密文所对应的明文。影响安全性的因素很多，诸如分组长度和密钥长度等。但有关实用密码的两个一般的设计原则是Shannon提出的混乱【141原则和扩散原则。混乱原则：人们所设计的密码应使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。扩散原则：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐蔽明文数字的统计特性。16本论文的主要章节及安排第一章绪论部分简要介绍密码学的发展，以及密码算法安全性分析的意义；第二章介绍密码体制分类，以及各种密码体制的安全性的介绍；第三章详细介绍密码算法安全性能评估方法；第四章介绍整个测试平台搭建的方案，以及具体采用的安全性测试算法。第二章密码体制简介7第二章密码体制简介21密码体制的分类密码体制2】【15】分为对称密码体制(单钥密码体制)和非对称密码体制(双钥密码体制)。对称密码体制(单钥密码体制)的加密密钥Z和解密密钥k能够简单地相互推导出来(通常情况下z-k)，通信双方的地位是对称的，可以双向地发送和接收保密信息。这样通信的双方采用相同的密钥来处理明密文，对明文实现加密，对密文实现解密，如流密码、分组密码等；非对称密码体制(双钥密码体制)中要从加密密钥Z推导出解密密钥k是很困难的(即使加密密钥Z唯一地确定了解密密钥k)。公钥密码体制除了具有信息保密的功能以外，还具有了种信息认证功能。通信双方共享公钥、加密算法，采用自己的私钥对信息加密、解密，典型算法是RSA3】【16】。221流密码的定义22流密码流密码又称序列密码，设：1明文是比特流m，称为明文流；2加密密钥和解密密钥相同，是比特流k，称为密钥流；3密文是比特流c，称为密文流；4加密算法和解密算法相同。加密：C=mok；解密：m=cok。222流密码安全性分析由流密码的定义容易看出，其安全性【117】在于密钥流随机性的好坏。假设密钥流k是一个完全随机的序列，即：任意两个不相重叠的密文段，它们所对应的密钥段都是相互独立的。换句话说，每一次加密都使用与以前的密钥段完全无关的新的密钥段。再换句话说，此时的加密方式是一次一密的。因此，此时达到了最高的安全性标准：无条件安全(完善保密)。实际应用中，由于密钥流k必须由确定的算法自动生成，因此是无法做到真正的随机的。不过这样的序列在攻击者看来很像真正的随机序列，称这样的密钥流k为伪随机序列。这样，实际中采用的加密算法就无法做到真正意义上的一次一密，即不重叠的密文段，采用的密钥段并不是相互独立的，这样就无法做到无条件安全。密码算法性能测试及平台搭建因此流密码的安全隐患就在密钥流k的非随机性上，这也就成为了分析流密码安全性的入手处。密钥流k的随机性越好，即密钥流各个比特间的相关性越小，则加密出的密文就越安全。231分组密码的定义23分组密码分组密码取用明文的一个区块和密钥，输出相同大小的密文区块。由于信息通常比单一区块还长，因此有了各种方式将连续的区块编织在一起，每个区块采用相同的加密算法和相同的密钥。设：1明文和密文是固定长度为n的比特串；m=mlm2m3m。；C=CC2c3巳；2加密密钥和解密密钥相等，是固定长度为J的比特串；Z=ZIZ：z，Z，；3加密算法为C=E(m，z)；4解密算法为m=D(c，z)=D(E(m，z)，z)；则称这样的加解密算法为分组密码。232分组密码的安全性分组密码由一系列密码组件复合而成。因此对于分组密码来说其安全性可以从算法的整体结构来考虑，也就是说通过检测明文与密文的相关性、密钥与密文的相关性、初始向量与密文的相关性等统计信息来评判分组密码的安全性能。另一个侧重点在于大多数分组密码所采用的S盒组件。例如对DES的分析可知，其安全性在于采用的S盒【2】【3】对输入的混淆能力上。因此，对于具有S盒密码组件的密码算法，对S盒的安全性检测也是我们必须考虑的内容。233分组密码的特点2345分组密码的加解密算法(E，D)简洁快速，所占用的计算资源小，易于软件和硬件实现。一般来说，用硬件实现时，流密码比分组密码更简单快速；用软件实现时，分组密码比流密码更简单快速。加解密算法(E，D)参数固定，比流密码更容易实现标准化。由于明文流被分段加密，因此容易实现同步，而且传输错误不会向后扩散。分组密码的安全性很难被证明，至多证明局部安全性。分组密码所面对的丰要威胁是已知明文攻击。分组密码的密钥Z被重复使用，即多次一密。因此最主要的威胁就是已知明文攻击。为了抵抗已知明文攻击(甚至选择明文攻击)，分组密码应该满足的性质：第二章密码体制简介9混淆性：所设计的密码应使得明文、密文、密钥之间的依赖关系相当复杂，以至于这种依赖关系对密码分析者来说是无法利用的。密码分析者利用这种依赖关系的方法非常多，因此混淆性也是一个极为繁杂的概念。扩散性【l8J：所设计的密码应使得1密钥的每一个比特影响密文的每一个比特，以防止对密钥进行逐段破译；2明文的每一个比特影响密文的每一个比特，以便最充分地隐蔽明文。非线性度：这一项属于混淆性。基本数学原理：如果明文与密文的关系是11维线性关系，系数是密钥，则n个明文密文对(而不是2n个)就可破解密钥；如果明文与密文的关系是11维r次函数关系，且系数是密钥，则nr个明文密文对就可破解密钥；如果次数r较大，但明文与密文的关系“非常逼近”一个n维线性关系，则n个明文密文对就可“基本上”破解密钥。上述就是线性密码分析的思想。抵抗线性密码分析的强度就是非线性度。24杂凑函数给定一个任意长度的消息M，通过这样一个函数日(M)，使得函数的返回值为个固定长度的散列值h，其中h的长度为m。即，h=H(M)。单向散列函数31应具备的特性：1给定M，很容易计算出Iz；2给定h，根据h=日(M)计算M很难；3给定M，要找到另一个消息M并满足日(M)=H(MI)很难；杂凑函数是一类特殊的单向函数。设数据文件是任意长度的比特串x。在密码应用中，希望有这样的函数Y=日(功，满足1将x压缩成为固定长度的比特串Y。2不同的z一定要生成不同的Y。3由Y的值无法倒算x的值。我们把这样的单向函数称为杂凑函数。对Hash函数的主要攻击方式是碰撞攻击。碰撞攻击：找到两个消息M和膨使得H(必)=H(M；杂凑函数实际性质：其性质来源于杂凑函数的定义：因此杂凑函数Y=日(x)满足1压缩性：将任意长度的比特串工压缩成为固定长度的比特串Y。10密码算法性能测试及平台搭建2单向性：己知X，计算Y=日(x)很容易：已知Y，找一个x满足Y=1-I(x)却很困难。3无碰撞性：找(五，X2)，五x2，日(五)=H(x2)，很困难。杂凑函数的构造标准：1不应具有可加性：设Y=H(x)对任意的XI，x2，H(x1)+日(恐)=H(Xl+X2)。这样的函数不能作为杂凑函数。2不应具有线性：设函数Y=日(x)对任意的X，a，aH(x)=H(ax)。这样的函数不能作为杂凑函数。3不应具有局部置换性：设函数Y=H(x)，无论石为何值，X的第一个比特总等于Y的第三个比特。这样的函数不能作为杂凑函数。4不应具有某种连续性：设函数Y=H(x)，当Y。与“距离很近”时，存在与恐“距离很近”，且Yl=日()，Y2=I-1(x：)。这样的函数不能作为杂凑函数。5设函数Y=H(x)，Y的固定长度太小。这样的函数不能作为杂凑函数，因为可以用穷举的方法进行碰撞攻击。因此，杂凑函数Y=I-l(x)中，X的任意一个比特影响Y的每一个比特，达到充分的混淆和扩散。此外，Y的长度不能太短，一般在128以上，以防止用穷举的方法进行碰撞攻击。杂凑函数的安全性：从上述杂凑函数的构造标准可以看出，要想达到消息的充分混淆和扩散，使得杂凑函数的安全性提高，就不能使选择的单向函数具有可加性、线性、局部置换性、连续性等性质，而且杂凑出的杂凑值，应该保证具备一定的长度，以抵抗碰撞攻击。25消息认证码利用密钥对要认证的消息产生新的数据块并对数据块加密生成的。它对于要保护的信息来说是一一对应的。因此可以有效地保护消息的完整性，以及实现发送方消息的不可抵赖和不能伪造。消息认证码的作用：用来验证所收到的消息确实是来自真正的发送方且未被修改的消息，也可以验证消息的顺序和及时性数字签名。消息认证码的生成方式：消息认证码生成有多种方式，主要方式还是采用广泛使用的单项散列函数，来生成相应的消息认证信息，但这样的散列函数又不同于简单的杂凑函数，他是有密钥参与的杂凑函数。第二章密码体制简介消息认证码的安全性【l9】：消息认证码的安全性取决于两点：1采用的加密算法，所谓数字签名。即利用公钥加密算法(不对称密钥)对块加密，以保证消息的不可抵赖和完整性。2待加密数据块的牛成方法，消息认证不支持可逆性，是多对一的函数，其定义域由任意长的消息组成，而值域则是由远小于消息长度的比特值构成，从理论上说，一定存在不同的消息产生相同的冗余数据块。因此必须要找到一种足够单向和强碰撞自由性的方法对消息认证才是安全的。首先，利用校验码加密的方式构造认证码，它可以实现数据完整性，它对消息不可抵赖不可伪造性的认证性能取决于加密的函数。因此这种方法的安全性取决于校验码的长度和加密的方法。但是由于它是针对局部变量的校验，比如针对一行或者一列，它的抗碰撞性能不是很好，即有可能产生消息被改动，认证码仍然没有变动的情况。其次，对于用单项散列函数构造认证码的方式来说，安全性是基于该函数的抗强碰撞性的，即攻击主要目标是找到一对或更多对碰撞消息，该消息生成摘要是相同的。在目前已有的攻击方案中，一些是一般的方法，是基于穷举的，可攻击任何类型的Hash方案，例如生日攻击方法，另一些是特殊的方法，只能用于攻击某些特殊类型的Hash方案，例如适用于攻击具有分组链结构的Hash方案的中间相遇攻击，适用于攻击基于模算术的Hash函数的修正分组攻击。因此摘要的长度是关键的一个因素。26公钥密码简介双钥密码体制(公钥密码体制)：于1976年由WDiffie和MHellman1976提出，同时RMerkle1978也独立提出了这一体制。可用于保密通信，也可用于数字签名。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。公钥体制的基本原理是陷门单向函数。一个函数fAB，若它满足：1对所有xA，易于计算f(x)。2对“几乎所有xA”，由f(x)求x“极为网难”，以至于实际上不可能做到。则称f为一单向(Oneway)函数。定义中的“极为困难”是对现有的计算资源和算法而言。公钥密码就是基于数学难题构造这样的单向函数，主要的数学难题有求解离12密码算法性能测试及平台搭建散对数问题，大数分解问题，背包问题，格向量最小等。陷门单向函数(Trapdooronewayfunction)，是这样的单向函数：1在不知陷门信息下，由f(x)求X“极为困难”，2当知道陷门信息后，由f(x)求X是易于实现的。公钥密码的一般要求：1加密解密算法相同，但使用不同的密钥；2发送方拥有加密或解密密钥，而接收方拥有另一个密钥；安全性要求：1两个密钥之一必须保密；2无解密密钥，解密不可行；3知道算法和其中一个密钥以及若干密文不能确定另一个密钥。第三章密码安全性能评估原理及方法第三章密码安全性能评估原理及方法31流密码的测评原理流密码是通过不断产牛的密钥流对信息逐比特进行加密，正是因为这样的加密方式使得信息的加密近似为为一次一密的方式。如果密钥流是一个真正随机的比特流，即，密钥流每个比特都与密钥流中其他的比特相互独立，这样加密出的结果就能保证足够的安全性。对攻击者来说，收集再多的明密文对，也是徒劳的，因为密钥流中比特之间的独立性，使得对明密文的统计信息在以后的攻击中毫无用处。因此对流密码安全性能的评估就集中落在密钥流的随机性分析上。32流密码的测评方法频率测试【20】【21】【22】(FrequencyTest)：频率测试主要测试的是一个待测序列中，0和1所占的比例。目的在于确定一个二进制序列中O和l所占的比例是不是近似相等。由于真正的随机序列，其0和1所占的比例是近似相等的，因此，我们从这一点来评判这个测试序列是一个随机的序列。分块频率测试(FrequencyTestwithaBlock)：分块频率测试主要测试的是l在一个M比特长的分块中所占的比例。测试的目的在于确定一个长为M比特的比特串，其中1的个数是不是近似的等于M2。如果测试的结果是1的个数近似的等于M2，我们就可以认为它是一个随机的串流。当分块儿的长度M=I时，这个测试就蜕变为频率测试。游程测试(RunTest)：游程测试测试的是一个序列中的游程的总数，一个游程表示的是某一个字符连续出现的串流。一个长为k的游程，是由k个某字符构成的，并且在其前后都有一个相反的字符作为其确定的边界。测试的目的在于求解一个由O1构成的不同长度的游程序列是不是满足一个随机序列的游程特性。尤其是，通过这个测试来判断0和1之间的震荡是不是太快或者太慢。l最大游程测试(LongestRunofOnesinaBlock)：1最大游程测试针对一个长为M比特的区块中最长的1游程。测试目的在于是确定最长的1游程的长度是否是连续的，如果是则可以认为测试序列是随机序列。由于最长1游程的无规则性同时也意味着0游程的无规则性，因此，仅仅测试l游程就已经完全足够了。二元矩阵秩测试(BinaryMatrixRankTest)：14密码算法性能测试及平台搭建二元矩阵秩测试是统计整个测试序列中不相连的子矩阵的秩。测试的目的在于测试来自于测试序列中固定长度子串间的线性独立性。这项测试来源于DIEHARDbattery测试中的第七项测试。频谱测试(DiscreteFourierTransfornlTest)：频谱测试是检测测试序列的离散傅里叶变换的峰高。测试的目的在于找出测试序列的周期性，通过统计超过门限值95的峰值数，来找出测试序列与真正的随机序列相背离的情况。非重叠匹配测试(NonoverlappingTemplateMatchingTest)非重叠匹配测试统计的是测试序列出现预先指定的目标串流的次数。测试的目的在于统计测试序列中是否出现太多的非周期串流。一个m比特的窗口用来匹配特定的m比特串流。如果没有匹配上，那么窗口向后滑动一个比特；如果匹配上了特定的串流，就将窗口的起始位置重新设置到匹配上的位置，并且继续计数。重叠匹配测试(OverlappingTemplateMatchingTest)重叠匹配测试也是统计随机序列中预先规定串流的出现次数。这个测试与非重叠匹配测试同样采用m比特的滑窗进行统计。统计的方法：如果没有匹配上串流，向后滑动一个比特；如果匹配上串流，也是将滑窗向后滑动一个比特，然后计数。Maurer通用统计测试231(MaurerSUniversalStatisticalTest)：Maurer通用统计测试统计的是两个匹配模式的比特数(一种与被压缩的序列相关的测试)。目的在于测试一个序列是否可以被明显的压缩而不丢失所含有的信息。如果一个序列可以被显著地压缩，而没有丢失信息，那么我们就可以认为这个序列是个非随机的序列。LZ压缩测试【24】(LempelZivCompressionTest)：Lz压缩测试在于统计一个待测序列中渐增的完全不同的模式(“字”)的数目。测试的目的在于确定待测序列究竟能多大程度地被压缩。如果待测序列可以被明显地压缩，那么就可以认为他是非随机的序列。一个真正的随机序列的不同模式的数目在统计意义上是个特定的数值。线性复杂度测试(LinearComplexityTest)：线性复杂度测试的关键在于将待测序列看作是线性反馈移位寄存器(LFSR)产生的。测试的目标是检测待测序列，看其是否是足够的复杂，让我们可以认为它是一个随机的序列。随机序列具有更长的LFSR的阶数，如果一个LFSR太短，则我们可以认为它是一个非随机的序列。连续性测试(SerialTest)：连续性测试关注的是一个序列中所有m比特长的相互交叠的串流(共2m种模式)出现的频率。测试的目的在于检测待测序列中长为m比特的交叠的串流出现第三章密码安哞=性能评估原理及方法的次数是否近似的等于真正的随机序列中相同模式出现的次数。真正随机的序列中出现的次数是无规则的，也就是说，任何一个长为m比特的模式与其他长为m比特的串流出现的几率是相同的。值得注意的是：当m=l时，连续性测试等效于频率测试。近似熵测试(ApproximateTest)近似熵测试关注的与连续性测试一样，也是一个序列中所有m比特长的相互交叠的串流(共2m种模式)出现的频率。测试的目标是比较待测序列中两个连续的长为m和m+l的交叠块出现频率与真正随机的序列的不同。累积和测试(CumulativeSumsTest)：累积和测试的重点在于将01比特串转换成一l+1串流，计算最大的随机游走。测试目标为求出待测序列中出现子串流的累积和是否是太大或者太小，将结果与真正随机的序列得到的标准进行比较。这样的累积和可以认为是一种随机游走。对于真正的随机序列，这样的游走是相当大的。随机散漫测试(RandomExcursionTest)：随机散漫测试重点在于在一个累积和的随机游走中出现K次的循环次数。通过将(0，1)序列转换成(1，+1)序列，计算出其累积和。一个随机游走循环由一个序列构成，该序列步长单位长度随机开始，然后返回初始位置。目的在于统计一个循环中出现特殊状态的次数是否与真正随机序列的次数相背离。随机散漫可变测试(RandomExcursionsVariantTest)：随机散漫可变测试的重点在于统计一个累积和随机游走中特殊状态出现的次数。目的在于检测随机游走中不同状态出现次数与期望值之间的偏离度。间隔测试【2刘(GapTest)：首先定义倪和的值，条件是0a”一O，1)，满DI)j(f)=0，则说它满足阶为-，的高阶严格雪崩性，记为DHOSAq(厂)=DD(f)。密码算法性能测试及平台搭建我们知道，最大取值为n，因此当J=n时，若函数f：0，1)”一0，1)，满足DD(f)=0，则说它满足最大阶严格雪崩性，记为MOSAC(f)=DDn(f)。7比特独立标准(BIC)对一个S盒，我们定义它满足高阶比特独立性如下：DHOBICi，(s)-。嚣瑟哆(胁)(39)l|C2IISlI|足I。若存在矩阵4，4，4使得：4互(P，s)=E(4p，4S)则称分组密码算法Z()具有线性因之4，4，4。由基本原理，我们容易看出下列事实：定理：密码算法鼻()存在线性因子的充要条件是：存在明文向量P，密钥向量墨和密文向量q使得对任意的明密文对P，s有：cFl(p，J)=cF(p+Pl，s+sI)34分组密码的测评方法通过对分组密码的介绍可知，分组密码应该满足混淆性、扩散性、高非线性度28】【29】等性质，以及使用的S盒应具有较高的混淆性。我们应从分组密码应该满足的特性来出发，分析其安全性，这样就要求我们对具体的密码算法整体结构给出相应的安全性分析。对于具有S盒部件的分组密码算法，我们还给出了独立测试S盒安全性能的测试功能。第叫章测试平台搭建方案及实现第四章测试平台搭建方案及实现我们所要构建的测试平台区别于其他测试平台的最大不同点在于，我们不是仅仅测试一两种密码算法，而是一个多种密码算法的安全性测试平台。由于密码测试算法较多，我们对测试算法进行了分类，并且对输入输出的方式，以及测试算法的运行维护方式进行了规定。对测试平台的构想中，我们力求做到以下几点：首先，对于同一类别的测试算法，采用相同或相似的输入、输出；其次，对具体的测试算法，尽量使其与测试平台的关联性降低，提高我们对此测试软件的维护的方便性，也便于日后对软件功能的扩展；最后，对于灵活性要求较高的部件，给测试软件的使用者留出标准接口，提高软件的实用性。41平台搭建方案平台搭建中应考虑的几个问题：1、对不同的密码算法进行分类，以便进行测试项目的分类；2、对同一类型的测试方法使用尽可能相同的测试参数，即接口近似或相同；3、对一些测试方法要求提供相对比较完整的密码算法进行测试时，应该给出公共的密码算法接口，以便对多种密码算法测试；4、对于测试的结果应该能够保存，给出一个比较直观的结果。对密码算法分类，我们对密码算法进行了深入的分析，分类的标准是以密码算法的构成组件，以及其加密的方式来进行分类的。因此在实现时，我们采用的具体分类是：流密码、分组密码、S盒等。为了让测试中采用的算法使用相同或相似的测试参数，我们对密码算法进行了比较深刻的抽象，将同一类密码算法中所必须的部分作为此类密码算法进行安全性测试的公共参数，结合不同测试中要求的一些附加参数，一起作为测试中使用的参数表，从而实现我们这方面的构想。进行密码算法整体结构性安全分析时，我们对密码算法的具体实现不应该限定，这样有利于提高我们的测试平台的通用性。因此我们只对密码算法实现的接口进行规范化，将密码算法的实现部分留给密码算法的开发者，这样我们就能够将一个对未知的密码算法的安全性测试，平滑地导入我们的测试平台，完成相应的测试项目。一些细节方面的考虑：从使用方便性的角度来说，我们采用windows向导模式。在用户使用时，给用户使用测试软件时一个引导，以便完成需要的测试项目。测试时，只要求用户提供相应的测试参数，而无需用户关注测试的具体实现过程，这样就降低了该软24密码算法性能测试及平台搭建件的使用门槛。从整个软件的适用性上，由于我们大量的采用了动态链接库，使整个软件的维护，升级都具备很大的方便性，尤其是我们对于某些测试给出的是密码算法的动态链接库，这样一旦要对新设计的密码算法进行测试，只需要把该动态链接库的源代码更改，而接口参数及函数名称不变，就可以完成该算法的测试。我们应该针对不同的测试，规定不同的测试对象：由前面分析可知，流密码算法的安全性在于其产牛的密钥流的随机性的好坏，因此我们将测试的对象确定为一个保存了密钥流信息的文件(文本文件和二进制文件两种形式)。考虑到用户有可能会要针对某一特定的序列生成算法所生成的序列进行随机性分析，因此，还在测试软件中留出相应的测试接口，专门用来检测序列牛成算法，供用户扩展使用。分组密码可以看成由一系列密码组件复合而成，而各个分组密码所采用的密码组件又不尽相同，因此对分组密码的安全性分析主要是针对整个算法的结构性的安全性分析上。由于是对整个密码算法进行分析，因此需要我们将整个密码算法作为用户的输入接口，以便提高用户使用软件时的灵活性。在这里，我们给用户留出了标准的接口，用户只需按照我们留出的接口，完成具体的分组密码实现代码，通过编译生成对应的动态链接库，就可以在我们的测试软件中正常运行，得到对分组密码安全性的分析结果。由于具有S盒组件的不仪仪有分组密码，还有一些其他的密码算法，因此我们将S盒抽取出来，作为一个独立的测试功能模块。我们认为将S盒分析作为一个独立模块比较合理。我们对S盒的规定也是只给出S盒的一个接口，至于S盒中输入输出之间的映射关系，由用户自己完成相应的实现代码。通过这种方式，可以使平台提供的s盒测试完成对任何一个S盒的安全性检测。可行性分析：首先我们需要对密码算法有深刻的本质理解，由于密码算法的不同构成方式，要求我们对不同种类的密码算法采用与其算法相适应的检测方法，这一点是根据密码算法构成组件安全性的特点提出的，因此我们应该大量查阅相关密码算法安全性分析的技术文档。由于现代密码学的发展，使得相关的资料、理论、思想等比较容易的从网络搜集到。关于这方面，我们进行了大量的资料搜集，找到了很多测试算法。我们已经搜集到流密码测试算法共计30多个，分组密码测试算法4个，S盒测试算法7项，等等，因此在算法的搜集上可以保证我们的测试软件具有较为全面的测试。其次是各个具体的测试算法，搜集到相关的资料后，我们应对算法的检测方法予以充分的理解，对算法的核心进行分析，完成我们需要的功能。虽然检测的算法众多，但是主要可以分为对序列随机性的分析、对S盒安全性的分析、对密码m测试十自措建方案及宴现整体结构的测试等几类。经过分析可知，同一类的密码算法所采用测试方法在核心思想t都是一样的，把握住这个基木的核心思想对我们理解相关的洲试算法有很大的好处。42平台框架实现l蒋f码算浊安个性能测试套件吲4-1密码算法安全性能测试套件分类框豳如图41所不，我们设计的测试平台的框架结构分为六个部分。整个框架采用windows向导模式进行处理，这样做的好处是使得测试具有针对性，并且用广在使用的时候，根据向导的指引，可以比较容易的选择相应的测试项目。有些测试，既可以用于流密码算法，也可以用于分组密码、杂凑函数等算法的安全性检测，故在选择页面上舔加了个专门用于这样一些组件的测试页面口。图42显示的是我们开发的测试平台框架的初始页面，其中的测试分类的安排就是按照图4-l中实现的。密码算法性能铡试及平台措建l制4-2测试甲行丰J始页而如l璺l43所示流崭码部分测试；由于输入的测试序列来源有多种方式，我们考虑到软件使用的J泛性兼容了文件输入和序列生成器输入两种主要方式，对于卜述两种丰要方式，又分为文本文件输入方式和_二进制文件输入方式。由于diehardbatteryj914试与非diehardbattery测试对序列的要求小相同(diehardbattery要求输入的测试序列的鲢度远远大于非diehardbattery测试所要求的)，所以将这两类测试分开处理。图4-4显示了测试软件流密码测试页的具体实现。圜囱图图图幽43流密码测试部分框图囱第叫章测试台措建方案蛮现圈4-4流密码测试页面嘲4-5流密码单项测试褫稚框幽图4-5所示的是流密码序列单项测试时的丰要流程。先是通过主控界l缸选择好要测试的序列，以及测试项目所需的其他辅助参数，将序列读入到输入缓冲区中，连同测试参数传递给测试单元，测试单元按照特定算法得到测试结果，井将结果写进输出缓冲区，返回给半控界面中的测试结果显示贝面。由于洲试算法众多，所以确定了我们必须采用尽可能具有共性的测试接u。不管怎么样测试序列是必不可少的。是我们测试的对象，因此这个参数，就成为我们必须保留的，并且密码算法性能测试厦平台拼建是公有的。还有一些辅助参数，他们是具体算法运行的时候，所需要确定的，因此这些参数作为具体算法的辅助输入不计入公有参数。针对上述的情况，我们选择采用动态链接库的方式进行平台与具体算法问的互联，以实现对平台中少许的改动，并结合动态连接库的增减，来调整测试软件的功能。图4-6分组密码测试流程框矧图4-6所示为分组密码测试框图，此框图也适用于S盒、P盒、以及共有组件测试。丰控界面选择相应的测试页面，确定输入测试参数，结合具体的密码算法(密码算法的输入输出关系、S盒的输入输出关系等)，送入用来实现测试算法的动态链接库，运算得到测试结果，然后，将结果写入到输出缓冲区，返回给主控界面的结果输出页面。具体的密码算法也采用的是动态链接库的方式嵌入系统，因为这样保证了测试接口的一致性，我们把算法的接口都定义好，留下密码算法的具体功能部分给密码算法发明者士实现具体的代码，只要密码算法的动态链接库司用，那么就可以通过我们的这个测试套件进行密码算法的测试。为了是测试软件自身具有更好的稳定性，避免m现不必要的错误，应该存测试软件中加入必要的检错功能。错误的来源有两方面，一是由于系统资源的缺失，造成测试软件的错误或不稳定：二是由于用户的错误操作，导致测试软件的异常。针对第一种情况，在保证运行该测试软件的系统有足够的系统资源外，为r防止软件的异常。应对其中对系统资源的使用中加入必要的保护措施，以及相应的错误相应，便于我们发现并解决其暴露出的缺陷。由用广错误揲作引起的异常，这种情况是可以通过规范用户的操作来避免的，这种操作不是通过髓明书等文档来规范使用者，应该在软件中给出必要的提示信息，引导用广进行正确的操作，从而避免软件的异常。当测试结束后，应该给出测试结果。这样的结果对使用者来说，应该包含足够的信息，以便日后调测。因此我们对测试软件的结果输出也给出了规定：首先应该包含测试的分类名称，如流密码安全性分析、分组密码安全性分析等：其次第四章测试平自搭建方案窘现应该包含具体的测试项