对一种基于logistic映射的分组加密机制的分析和改进.doc

第12期杨吉云等：对一种基于logistic映射的分组加密机制的分析和改进91对一种基于logistic映射的分组加密机制的分析和改进杨吉云，廖晓峰，肖迪，邓绍江（重庆大学 计算机学院，重庆 400044）摘 要：对一种改进的混沌分组密码机制分析后发现其本质上是流密码系统，并且密钥流与明文无关。通过选择明文攻击，在很小的计算代价下获得了密钥流。给出了选择明文攻击的算法，并通过实验进行了验证。为克服原加密算法的缺陷，采用密文反馈的形式使密钥流与明文相关。关键词：logistic映射；混沌；加密机制；选择明文攻击中图分类号：TP309.7 文献标识码：B 文章编号：1000-436X(2008)12-0086-05Cryptanalysis and improvement of a block cryptographic scheme based on logistic mapYANG Ji-yun, LIAO Xiao-feng, XIAO Di, DENG Shao-jiang(Department of Computer Science, Chongqing University, Chongqing 400044, China)Abstract: Through analyzed of an improved chaotic block cryptographic scheme, it was found that this scheme behaves as a stream cipher indeed and generated keystream is independent with plaintext. By means of chosen plaintext attack, the keystream used can easily be recovered with little computing. The algorithm a chosen plaintext attack was proposed and validated by experiment. In order to avoid the flaw, a remedy which makes keystream dependent with plaintext though ciphertext feedback was suggested while keeping all the merits of the original cryptosystem.Key words: logistic map; chaos; cryptographic scheme; chosen plaintext attack1 引言混沌现象是非线性确定系统中的一种类似随机的过程，这种过程具有对初值敏感、遍历等特性，这些固有的特性是一个好的密码系统所期盼的，因此将混沌系统应用到密码系统中的研究引起了广泛的关注，并先后提出了一些基于混沌系统的加密系统，如文献13。收稿日期：2007-05-02；修回日期：2008-11-11基金项目：重庆市自然科学基金资助项目(2007BB6168); 国家自然科学基金资助项目(60703035)Foundation Items: The Natural Science Foundation of Chongqing (2007BB6168); The National Natural Science Foundation of China (60703035)最近向涛等人提出了一种基于logistic映射的分组加密系统4（为描述方便，以下简称该加密系统为XBC），该密码系统针对一类Baptista密码系统57存在的些问题进行了改进。该密码系统首先通过logistic映射产生随机二进制序列，然后将所产生序列的一部分对明文进行置乱，最后将序列中剩余的部分与分组明文进行异或运算产生密文。该密码系统加快了加密的速度，同时使密文和明文的长度相等。XBC是一类混沌加密算法810的典型代表，它们的思路都是取混沌轨迹上的点进行变换后，直接参与明文的加密。在加密过程中，密钥流序列都与明文无关，类似于同步流加密机制。因此，本文对XBC的分析方法完全可以推广应用到其他相似的加密算法上。目前，混沌密码学的整体研究水平还不成熟，虽有大量具有良好性能的混沌加密算法的被提出，如XBC，但还未能在实际中广泛应用。然而，相信随着这些混沌加密算法的不断提出与改进，必将会极大地促进了混沌密码学的发展，为保障信息安全提供更多新颖的手段。虽然混沌密码系统相对于传统密码系统有一定的优势和不同，但如果在设计时违背了密码学的一些基本准则，其安全性将难以保证。通过对XBC的仔细分析后发现本质上是一个流密码系统11，而且只要密钥不变，每次新的加密过程都会有相同的密钥流序列，这就违背了流密码设计的基本准则。而正是这个缺陷导致了通过选择明文攻击能够找出密钥流，而获得密钥流就等同于获得了密钥，因此就能够破解密文。在本文中，首先介绍了向涛等人的加密机制，然后对该加密机制存在的问题进行详细分析，给出了通过选择明文攻击获取密钥流的方法以及实验验证，最后对XBC进行了改进。2 XBC的主要内容2.1 伪随机序列的产生在XBC中，首先利用logistic映射产生混沌轨道，如式（1）所示。(1)轨道上的每个点采用二进制的形式可以表示为(2)其中，bi(x)可以通过式（3）得出(3)式（3）中是一个门限函数，如式（4）定义(4)通过式（1）式（4）就可以得到具有独立均匀分布的伪随机序列，其中，n是二值序列的长度，是logistic映射第n次迭代时的值，该序列将在XBC中被多次用到。2.2 XBC加密算法XBC以logistic映射为基础，通过2.1节所描述的方法产生基本的伪随机序列，为了防止过渡效应，将丢弃logistic映射的前N0=250次迭代产生的数据。在加密的过程中，明文分组包含8个字母，因此每个明文组的长度为64bit。该算法的基本思想是利用2.1节产生的部分伪随机序列对明文组进行置乱，再利用另一部分伪随机序列与置乱后的明文异或运算产生密文，从而达到对明文加密的目的，其详细算法描述如下。step1 将logistic迭代N0次，得到logistic映射产生伪随机序列的起始点。step2 将明文m表示为长度为l字节长的明文组Pj（在XBC中l=8），(5)因此Pj可以表示为Pj = pl j + pl j+1 + pl j+7 step3 迭代logistic映射70次并得到70个数据x1，x2，x70。利用2.1节所描述的方法产生二值序列，计算序列的数值Dj，该值将在随后2次用到。step4 将Pj左移 Dj位，得。step5 根据式（6）利用和Aj产生密文C j组。(6)其中，表示异或运算。step6 如果所有的明文组都被加密，则加密过程结束。否则迭代logistic映射70+Dj次，然后转向step 2。解密过程与加密过程相似，只需要将式（6）替换为式（7）(7)然后将Pj右移 Dj位，即可得到明文组。关于XBC的详细描述请参阅文献4。3 选择明文攻击对加密算法的攻击在文献11给出了4个级别，按照从易到难的顺序排列分别是密文攻击、已知明文攻击、选择明文攻击、选择密文攻击。根据Kerckhoff原则11在密码分析知道所有加密算法的前提下，只有当一个加密算法能抵御所有的攻击才认为是安全的。通过对XBC的加密算法分析可知，该加密算法本质上是一个流密码加密算法。同时式（6）中的密钥流与明文无关，只要密钥固定，每新的一次加密过程都会使用相同的密钥流，并且在算法中对明文的置乱也是固定的。当使用该算法对同一加密位置的相同明文加密时，将会等到相同的密文。如果能够通过对加密算法进行密码分析得到加密密钥，则可完全破解该加密算法生成的密文。对于XBC，由于其密钥一定后，每次产生的密钥流以及对明文的置乱相同，因此如果能通过密码分析得到密钥流和明文置乱次数，也可完全破解其密文。通过进一步分析发现选择明文攻击对文献4的加密系统是非常有效的。假定拥有了在相同位置的2对明文以及相应的密文，分别用Pj1和Cj1，以及Pj2和Cj2来表示。由于Pj1和Pj2 都位于加密过程中的第j次加密，它们将被循环左移相同的Dj位，而且它们会与相同的密钥流Aj进行异或运算产生密文。由加密算法的step4(8)(9)其中，表示循环左移运算。由加密算法的step 5，可知(10)由式（8）和式9）可知(11)令，则可将式（11）写为Xj= Zj Dj。由于 Xj 和 Zj 是已知的，要得到Dj，只需要将进行Zj循环左移，直到Xj=Zj，此时Zj左移的位数即为Dj的值。如果Dj有解，即可成功破解，当然更希望Dj的解是惟一的。但是当Zj具有形如aaa的形式时，即表示Zj是由一些重复的二进制位构成的，这些重复的二进制位用a表示，此时就存在无数个解。因为Zj 左移n位和Zj 左移（n+kL）位的值相同，其中L是 a 的位数，k为自然数。例如Zj=1110111011101110，则a=1110，L=4。取n=1，此时循环左移n位后的Zj= 1101110111011101，循环左移（n+4k）位的Zj=1101110111011101。所以在选择明文时应避免具有aaaa形式的Zj。当得到了Dj 后，通过式（8）就能得到，或者通过式（9）得到。再通过式（10）即可得到或者(12)由以上分析可知，只需要几步简单的运算即可得到想要的密钥流，而得到密钥流与得到加密密钥的效果是一样的12，因此该加密算法在小的计算代价下就能够被破解。 4 实验验证为了说明上述攻击的有效性，首先根据XBC生成前10组密钥流，如表1所示。表1部分密钥流加密组过渡次数N0起始点x0Aj(H)Dj(H)12500.17775D53 69E3 8DBF 102B72770.930595C99 A6FB DE3E 78CE03700.243877BA B387 779F C04F24720.0311668FBE DA5D CE2F 992715710.29386075C 893D 217C 4FE936730.804062D2B D6A6 1729 9D0DF7850.38298AFD6 6002 DC15 527D28720.05932277C1 4AFB D072 FF0079770.88571A713 3B3D A4A6 673B810780.0026122C6C4 1483 0B64 FF65B然后随机产生2段长度为40个字符的明文，以十六进制表示41F1A69803D85D78FAC1C7A 4A1007DC247C97CDEDFE5436353A369EB6A0886560B45799B630F46FFH,DAF7A2D44A0CAFD3510183B033359F38E29BFEF66B990E5C92D06705484EDF6D 0294E707B8C45B9H，分别用P1和P2表示。根据XBC加密算法，对P1和P2的加密过程如表2和表3所示。表2P1的加密过程加密组明文Pj(H)Dj(H)(H)Aj (H)Cj(H)141F1A69803D85D787F8D34C01EC2EBC205D5369E38DBF102BA58025E26191AC0B2FAC1C7A4A1007DC20FAC1C7A4A1007DC25C99A6FBDE3E78CEA658615F7F3E050C347C97CDEDFE5436321F25F37B7F950D8D77BAB387779FC04F689F40FC080ACDC2453A369EB6A0886561A746D3D6D4110CAC8FBEDA5DCE2F992728F8098B1A3E958B50B45799B630F46FF35A2BCCDB187A37F8075C893D217C4FE95D7745E639067811表3P2的加密过程加密组明文Pj(H)Dj(H) (H)Aj (H)Cj(H)1DAF7A2D44A0CAFD377BD16A250657E9ED5D5369E38DBF102B268203C68BE8F9C62510183B033359F380510183B033359F385C99A6FBDE3E78CE0D98254BED0BE7F63E29BFEF66B990E5C28A6FFBD9AE64397377BAB387779FC04FFDD5485ED9FBF93C492D06705484EDF6D125A0CE0A909DBEDB8FBEDA5DCE2F9927AA1E14575EB227FC5F0294E707B8C45B93814A7383DC622DCF075C893D217C4FE98616FABEFD1E6226为验证选择明文攻击对XBC的有效性，分别从表2和表3中选择了位于第1组的2对明文，分别用P11和P12 表示，然后按照上述选择明文攻击的方法获得密钥流，详细过程如下。1) 从表2和表3，可以得到P11=41F1A 69803D85D78H，P12= DAF7A2D44A0CAFD3 H，C11= A58025E26191AC0B H以及C12= 268203C68B E8F9C6H。2) 现已知P11，P12，C11和C12，根据式（8）、式（9）和式（11），可以计算出Dj和Aj 来验证本文的结论。83022624EA7955CD H，用 X1表示。 9B06044C49D4F2AB H，用Z1表示。左移Z1直到X1=Z1，可以得到左移的次数D4=7H，该数值与表2和表3相同。根据XBC的step4，可以得到= F8D34C01EC2EBC20H和=7BD16A250657 E9ED H。根据式(12)，可以得到=5D5369E 38DBF102B H，与表2和表3中相同。从以上的过程可知，可以根据2对明密文对比较容易的得到密钥流以及置乱次数，在得到密钥流和置乱次数后，可以在密钥不变的情况下，通过破译密文就可得到明文，从而实现了加密系统的攻击。5 对XBC的改进XBC的致命缺陷在于其密钥流与明文无关，所以可以通过选择明文攻击获得密钥流。因此对XBC改进的关键是通过明文或者密文反馈的形式控制密钥流的生成，为保证加密和解密双方同步，采用密文反馈方式。实现的方法是对XBC算法中step5产生的8byte密文按序抽位，如式（13）所示，然后将抽位所得的值控制XBC算法中step6所需参数Dj的生成。为了更进一步使抽位随机化，每次抽位的起点由XBC算法中step3产生的Dj确定，如式（14）所示。将抽位得到的数据与通过式（15）产生，然后用替换XBC算法中step6的参数Dj。(13)(14)(15)式（13）中为与运算，c为密文组中的字节。由于改进后的算法中step6所需参数通过密文反馈与明文相关，不同的明文就会使logistic映射在加密的过程中进行不同次数的迭代，从而产生不同的密钥流，这样就避免了XBC中的安全漏洞。同时式（13）的抽位起点不固定，在抽位时还引入了明文组里字节间的顺序，这样可以避免利用明文组里的字节顺序进行攻击。为了测试改进算法对明文敏感性，随机产生2段长度为80byte的明文，分别为P3：58FF64F5B6DEB4E341305CCB11F3B8EFC14E18894C2ED3B721C4BD80AD6A730DEA9B2F72BC0209A632DDD27EE82FFAD4297A25238600644D06C7314D23DBAE043A8ABC751D94E90DF29455D1910D0196H，P4：A552A2F 620224056985F88F3DB 5A216E93B8D72E8A1074417C25F840FF99EF936FEBFB4D98D23447EF6401EF311F7AF2A646F432FB4F118F43092518BDA4E30C42812782B7EEA11284BBA8C7DB0EADH，利用改进后的XBC产生相应的密钥流，如表4和表5所示。表4P3对应密钥流（x0=0.1234）加密组过渡次数N0Aj(H)Dj(H)125003F8B1221FBE048C3C21147BC3BBDF37FD55E62A389D6502496091B4FA406480F548B00F8EA38D152B5129424B67ACFBB1BA591468139C2B6714538DB8E0E712965A9DD4B27A35E6501886DFF15E1024347D01039116BB55DCC2825F55E52E10115FF6E3CB91886E2DE34表5P4对应的密钥流（x0=0.1234）加密组过渡次数N0Aj(H)Dj(H)125003F8B1221FBE048C3C281D1D3EA2F3DE1DDEF263101CD4C36B28124B04836411091601F1D471A2B5A135783FE260DE119092D93A6777E8FD7DE2084E70A36774E665D964A7A7063D138948394A828881266F3349906F3E970075080AA11A10995796E647393F10FB0E由表4和表5可以看出，从第二组开始后密钥流Aj对就完全不同，同时过渡迭代次数也不同，所以改进后的算法对明文是敏感的。式（13）（15）仅改变了下轮过渡迭代次数，并且计算量小，所以在克服原算法的缺陷同时，保持了原算法的高效性和安全性。由于改进算法对密钥流的修改是从第二组开始的，所以在使用时应该从第二组开始加密有用信息。6 结束语基于混沌理论的密码学经过近些年的发展，已取得了很多的研究成果，也提出了很多新颖的混沌密码系统。但有的混沌密码系统在设计时，没有遵循传统密码学中的一些基本准则。因此即使混沌系统有很好的混乱和扩散特性，也不能抵御已知的攻击和安全性分析。通过对XBC的分析也正好验证了这点，这对设计新的混沌加密系统具有一定的参考意义。参考文献：1BAPTISTA M S. Cryptography with chaosJ. Physics Letters A, 1998, 240(1): 50-54.2WONG W K, LEE L P, WONG K W. A modified chaotic cryptographic methodJ. Computer Physics Communications, 2000, 138(3): 234-236.3PAREEK N K, PATIDAR V, SUD K K. Discrete chaotic cryptography using external keyJ. Physics Letters A, 2003, 309(1): 75-82.4XIANG T, LIAO X F. A novel block cryptosystem based on iterating a chaotic mapJ. Physics Letters A,