冗余方程对基于Minisat的代数攻击影响

第３６卷　第１期　计算机工程　２０１０年１月　ＶｏＬ３６　Ｎｏ．１　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｊａｎｕａｒｙ　２０１　０　・安全技术・　文章编号：１０００－－３４２８（２０１０）０１－－－－０１７７—－０４　文献标识码：Ａ　中图分类号：ＴＮ９１８．１　冗余方程对基于Ｍｉｎｉｓａｔ的代数攻击影响　卜凡　（解放军信息工程大学电子技术学院，郑州４５０００４）　摘要：分析基于Ｍｉｎｉｓａｔ软件的代数攻击方法，发现由该代数攻击方法对某些密码算法所建立的方程组中存在冗余方程，研究去除所有　冗余方程的预处理方法，基于该方法提出先去除冗余方程，再利用Ｍｉｎｉｓａｔ软件求解无冗余方程组的代数攻击方法。实验结果表明，对ＣＴＣ　算法，新的攻击方法的攻击时间平均缩短了ｌ／２，冗余方程的存在降低了基于Ｍｉｎｉｓａｔ软件的代数攻击的效率。　关键词：代数攻击；非线性方程组；冗余方程；ＣＴＣ算法　Ａｆｆｅｃｔｉ０ｎ　ｏｆ　Ｒｅｄｕｎｄａｎｔ　Ｅｑ　ｕａｔｉｏｎｓ　ｔｏ　Ａｌｇｅｂｒａｉｃ　Ａｔｔａｃｋ　Ｂａｓｅｄ　０ｎ　Ｍｉｎｉｓａｔ　ＢＵＦａｎ　（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｔｅｃｈｎｏｌｏｇｙ，ＰＬＡ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ　４５０００４）　［Ａｂｓｔｒａｃｔ］Ｔｈｉｓ　ｐａｐｅｒ　ａｎａｌｙｚｅｓ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆ　ａｌｇｅｂｒａｉｃ　ａｔｔａｃｋｓ　ｂａｓｅｄ　ｏｎ　Ｍｉｎｉｓａｔ．Ｉｔ　ｆｉｎｄｓ　ｔｈａｔ　ｔｈｅ　ｆｈｎｃｔｉｏｎｓ　ｗｈｉｃｈ　ａｒｅ　ｂｕｉｌｔ　ｆｒｏｍ　ｔｈｉｓ　ｍｅｔｈｏｄ　ａｒｅ　ｒｅｄｕｎｄａｎｔ　ｆｏｒ　ｓｏｍｅ　ｃｉｐｈｅｒｓ，ｇｉｖｅｓ　ａ　ｐｒｅｔｒｅａｔｍｅｎｔ　ｍｅｔｈｏｄ　ｔｏ　ｔｈｒｏｗ　ｏｆｆ　ｔｈｅｓｅ　ｒｅｄｕｎｄａｎｃｙ　ｆｕｎｃｔｉｏｎｓ　ａｎｄ　ａ　ｍｅｔｈｏｄ　ｏｆ　ａｌｇｅｂｒａｉｃ　ａｔｔａｃｋ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｐｒｅｔｒｅａｔｍｅｎｔ　ａｎｄ　ｕｓｉｎｇ　Ｍｉｎｉｓａｔ　ｔｏ　ｓｏｌｖｅ　ｆｕｎｃｔｉｏｎｓ．Ｕｓｉｎｇ　ｔｈｉｓ　ｉｍｐｒｏｖｅｄ　ｍｅｔｈｏｄ，ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｃａｎ　ｃｕｔ　ｄｏｗｎ　ｈａｌｆｔｉｍｅ　ｏｆ　ｏｎｅ　ａｔｔａｃｋ　ｏｎ　ａｖｅｒａｇｅ　ｏｎ　ＣＴＣ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅｓｅ　ｒｅｄｕｎｄａｎｔ　ｆｕｎｃｔｉｏｎｓ　ｍａｋｅ　ｔｈｅ　ａｌｇｅｂｒａｉｃ　ａｔｔａｃｋ　ｂａｓｅｄ　ｏｎ　Ｍｉｎｉｓａｔ　ｂｅｃｏｍｅｓ　ｉｎｅｆｉｆｃｉｅｎｔ．　［Ｋｅｙ　ｗｏｒｄｓ］ａｌｇｅｂｒａｉｃ　ａｔｔａｃｋ；ｎｏｎ－ｌｉｎｅａｒ　ｓｙｓｔｅｍ　ｏｆ　ｅｑｕａｔｉｏｎｓ；ｒｅｄｕｎｄａｎｔ　ｅｑｕａｔｉｏｎ；ＣＴＣ　ａｌｇｏｒｉｔｈｍ　１概述　２基于Ｍｉｎｉｓａｔ软件的代数攻击方法　代数攻击是采用基于代数思想的方法与技巧，将一个密　２．１方法介绍　码算法的输入输出及其各中间状态变量的关系归结为一个超　文献［１］提出利用Ｍｉｎｉｓａｔ软件求解方程组的代数攻击方　定的多元高次方程组（即方程个数远大于未知量个数），使得　法，具体过程如下：　该密码算法的安全性完全依赖于求解多元高次方程组的困　（１）建立以算法中变换环节输入输出的各比特位为未知　难性。　量的方程组，其中算法的线性变换环节可直接建立以输入输　代数攻击首先是建立关于算法输入输出及各中间状态变　出的各比特位为未知量的线性方程，非线性变换环节仅建立　量之问关系的方程组，而后解出方程组中所有变量的值从而　以输入输出的各比特位为未知量的低次非线性方程。　恢复密钥。在建立关于算法的方程组的方法中，既有利用以　（２）将求解方程组的问题转化为ＳＡＴ问题，进而利用　算法中变换环节输入输出的各比特位为未知量来建立方程的　Ｍｉｎｉｓａｔ软件求解ＳＡＴ问题从而解得方程组。　方法ｌ　ｌＪ，也有利用以算法中变换环节输入输出比特块为未知　该方法已经对６圈ＤＥＳｌ　１、ＫｅｅＬｏｑ…、ＣＴＣ　和ＣＴＣ２　量来建立方程的方法ｌｊ　；既有建立算法中变换环节的输出未　等算法进行了攻击实验。由于这些攻击实验建立的非线性方　知量关于输入未知量关系的显示表示的方法ｌ４Ｊ，也有建立关　程均是低次非线性方程并且方法类似，因此本文仅以ＣＴＣ算　于算法中变换环节的输入输出未知量关系的隐式表示的方　法为例分析基于Ｍｉｎｉｓａｔ软件的代数攻击方法所建立的非线　法ｌ　】Ｊ。求解方程组的方法主要有线性化方法（包括直接线性　性方程中存在的冗余方程问题。　化　、扩展线性化【叫等）、求Ｇｒ６ｂｎｅｒ基（Ｆ４　Ｊ、Ｆ５［８－９］算法等）　２．２方法分析　的方法和转化为可满足性问题（ＳＡＴ问题）利用ＳＡＴ　Ｓｏｌｖｅｒ软　ＣＴＣ算法是Ｃｏｕｒｔｏｉｓ为了验证所提出的代数攻击方法的　件求解ＳＡＴ问题从而求解方程组的方法ｌＪ’　Ｊ。　正确性和有效性而提出的一个玩具分组密码算法。该算法采　目前，利用以算法中变换环节输入输出的各比特位为未　用ＳＰＮ结构，分组长度３　（１≤Ｂ≤１２８）、密钥长度３　和迭　变量来建立方程组，再将求解方程组的问题转化为ＳＡＴ问题，　代圈数Ｊｖ　均是可变的，圈函数包括圈密钥加、混乱变换和扩　进而利用Ｍｉｎｉｓａｔ软件求解ＳＡＴ问题从而解得方程组的代数　散变换，其中圈密钥加是将圈函数的输入与圈密钥逐比特“异　攻击方法已经实现对低圈的ＤＥＳｌＪ　和ＫｅｅＬｏｑ…　算法的攻击。　或”，混乱变换是由Ｂ个３比特Ｓ盒并置构成，扩散变换是　本文介绍基于Ｍｉｎｉｓａｔ软件的代数攻击方法，分析该代数　｛ｏ，１　到｛０，１　上的线性变换。圈密钥仅是通过算法密钥循　攻击方法所建立的方程组中存在的冗余方程的问题，给出去　环移动若干比特位得到。　除方程组中所有冗余方程的方法，提出对基于Ｍｉｎｉｓａｔ软件的　代数攻击的新方法，并通过实验说明该新方法的效果及冗余　作者简介：ｂ）￣（１９８２一），男，硕士研究生，主研方向：密码学　方程对基于Ｍｉｎｉｓａｔ软件的代数攻击方法的影响。　收稿日期：２００９—０６—０８　Ｅ—ｍａｉｌ：ｂｕｆａｎ１９８２＠ｙａｈｏｏ．ｃｎ　１７７—　在ＣＴＣ算法的圈函数中，圈密钥加变换和扩散变换都是　线性变换，因此可以很容易得出这些变换的以输入输出比特　位为未知量的线性方程；而混乱变换是由Ｂ个３比特Ｓ盒并　，　，…，　）。若存在多项式　，使　，　，…，　。，　一，　）＝，　【　，　，…，　），则称　＝０是方程组　＝　一一　＝０的冗　余方程。　根据上述定义可直接得出判定方程组１≤ｉ≤　＝置构成的非线性变换，其中代替表Ｓ盒为｛７，６，０，４，２，５，１，３｝，　即若ｓ盒输入的３比特为Ｘ３Ｘ２Ｘ１，输出的３比特为Ｙ３Ｙ，Ｙ．，则　Ｙ，Ｙ：ｙ，是Ｓ盒中第４ｘ３＋２　：＋　个值对应的二进制数，文献［２］　＝０中　０是否为冗余方程的方法：穷举Ｘｔ，　，…，　得到方程组　１≤ｉ≤ｒ，　＝０的解集　（　，　，…，　）；穷举　，　：，…，Ｘ　得到方　程组１≤ｉ≤，，ｉ≠ｆ，　＝０的解集　（　，　，…，　果　（　，　，…，　）≠　（　，　，…，　中基于Ｍｉｎｉｓａｔ软件的代数攻击方法建立了１４个以　Ｘ３，Ｘ　，Ｘ１，Ｙ　，Ｙ　，Ｙｌ为未知量的二元域上的二次非线性方程，并　基于这些方程利用Ｍｉｎｉｓａｔ软件对ＣＴＣ进行了代数攻击实验。　这些方程具体为　０＝ＸｌＸ２０Ｙ１０Ｘ３０Ｘ２０Ｘ１０１　０＝Ｘ１Ｘ３０Ｙ２０Ｘ２０１　＋．，…，　），如　…，　），则　＝０不是冗　余方程，否则　＝０是冗余方程。该方法每判定方程组中的　１个方程就需要对Ｘ　，Ｘ２，…，Ｘ　穷举一次，下面给出仅需对　Ｘ　，Ｘ　一，Ｘ　穷举一次就能判定并去除方程组中所有冗余方程　０＝ｘｌＹｌ０Ｙ２０　２０１　０＝ｘｌＹ２　０Ｙ２　０Ｙｌ　０Ｘ３　　ｌ０＝　０Ｙ３０Ｙ２０Ｙｌ０Ｘ２０Ｘｌ０１　　Ｊ０＝ｘｚＹｌ０Ｙ３０Ｙ２０Ｙｌ０Ｘ２０Ｘ１０１　　１０＝　２０　０Ｘ１　１　０＝　乃０ＸｌＹ３０Ｙ１０Ｘ３０　２０１　　ｌ０＝ｘ３ｙｌ０ｘｌｙ３０Ｙ３０Ｙｌ　１０＝ｘ３ｙ２０Ｙ３０Ｙ１０Ｘ３０Ｘ１　　ｌ０＝　乃０　乃０Ｙ２０　２０Ｘ１０１　　ｌ０＝Ｙ１Ｙ２０Ｙ３０Ｘｌ　　ｌ０＝Ｙ１Ｙ３０Ｙ３０Ｙ２０Ｘ２０　ｌ０１　【０＝Ｙ２Ｙ３０Ｙ３０Ｙ２０Ｙｌ０Ｘ３０Ｘｌ　容易验证，方程组（１）的解为　｛（　，　，　，　，　，　）：４儿十２　十　＝　：４　＋２　＋　，　，　∈｛ｑ１｝｝　如果将方程组（１）的ｌ４个方程从上到下依次编号为　（１．１）～（１．１４），则发现（１．２）～（１．１４）构成的方程组的解与方程　组（１）的解相同，这说明方程（１．１）对于求解方程组（１）没有提供　任何信息量，即（１．１）是冗余方程。事实上，我们发现仅由（１．２），　（１．４）和（１．１２）构成的方程组的解与方程组（１）的解相同，这说明　方程组（１）中除了（１．２），（１．４）和（１．１２）外的１１个方程相对于　（１．２）、（１．４）和（１．１２）这３个方程来说都是冗余方程。　另一方面，基于Ｍｉｎｉｓａｔ软件的代数攻击方法在得到关于　算法的方程组后，将求解方程组的问题转化为ＳＡＴ问题，进　而利用Ｍｉｎｉｓａｔ软件求解ＳＡＴ问题从而解得方程组。在这个　过程中，方程组中的方程数量越多，转化为ＳＡＴ问题的规模　就越大（包括变量个数、语句个数、语句总长度），即Ｍｉｎｉｓａｔ　软件运行时的输入规模就越大。由于冗余方程对于求解方程　组不提供任何信息量并且去除冗余方程使得Ｍｉｎｉｓａｔ软件运　行时的输入规模减小，因此笔者期望在得到关于算法的方程　组后，通过去除方程组的冗余方程的方法来提高基于Ｍｉｎｉｓａｔ　软件的代数攻击的速度。　３冗余方程对基于Ｍｉｎｉｓａｔ代数攻击的影响　本文首先给出去除冗余方程的压缩查表法，基于压缩查　表法给出基于Ｍｉｎｉｓａｔ软件的无冗余方程的代数攻击方法，最　后通过对ＣＴＣ算法的实验说明新的代数攻击方法的性能，进　而分析冗余方程对代数攻击的影响。　３。１去除冗余方程的压缩查表法　首先引入下面的概念：　定义设　，　，…，　是二元域上的　多元多项式，则称使　得　＝　一一　＝０成立的未知量　，Ｘ：，…，　的所有可能值　构成的集合为　，　，…，　构成的方程组的解集，记为　ｌ７８一　的方法。　定理１设　，　，…，　是二元域上的，ｚ多元多项式，则有　（１）　（　，　，‘。。，　）＝ｎ　（　）；　ｉ＝１　（２）如果｛ｇ　，ｇ　，…，ｇ，｝　｛ｆｌ，　，…，　｝，则　（　，　，…，　）　（蜀，ｇ２，…，ｇ，）。　定理１中的（１）说明方程组的解集可以通过先分别求出方　程组中各方程的解集，再求它们的交集得到。具体地，对于　方程　＝０，开辟２　个存储单元ｔａｇ［２　］，依次穷举　ｌ，　，…，　，如果ＸＩ，　２，…，Ｘｎ是ｆｉｅ：０的解，令ｔａｇ［￣２　］＝１；　ｉ＝１　否则令ｔａｇ［￣２　ｘｉ］＝０。对于由，个方程构成的方程组，则需　ｉ＝１　要开辟ｒｘ２　个存储单元ｔａｇ［ｒ］［２　］来标记ｒ个方程各自的解　集。显然，　方程组的解集就是｛（　，Ｘ　一，　）：　＂　＾ｔａｇ［ｔ儿∑２　Ｘ　］＝１｝。　１＝１　ｉ＝１　去除方程组中所有冗余方程的思想为：对于１≤ｉ≤，，　穷举计算方程　＝０的解并标记在数组ｔａｇ［ｉ］［】中；对于　０≤Ｊ≤２”一１，令ｖ［ｊ】＝＾　［ｆ］［　，则ｖ［ｊ］标记出方程组　ｆ　Ｉ　１≤ｉ≤ｒ，　＝０的解集；记集合，＝｛１，２，…，，｝，将去除，中　１个元素后的集合记为，　，对于０≤Ｊ≤２　一１，计算　＝Ａｔａｇ［ｔ］［ｊ］，则　］标记出方程组ｆ∈，’，　＝０的解集；　如果对于０≤Ｊ≤２　１，己　＝　力均成立，则令，＝，’，继续　去除』中１个元素得到，’后按同样的方法检验；只要　］＝　】　对于０≤，≤２”一１中的一个，不成立，则继续去除，中未曾检　验过的１个元素得到，’后按同样的方法检验；最终，如果，中　元素经检验均不能去除，则说明以，中元素为下标的方程构　成的方程组为无冗余方程组。　在具体实现时，由于标记方程解集的数组ｔａｇ［ｒ］［２　］，　ｖ［２　］和Ｕ［２”］中各存储单元的取值仅为０或１，因此可以将　它们进行压缩存储，即利用３２比特整型变量数组ｔａｇｌ［ｒｌ［２　】　来存储２　ｘ３２＝２　个比特，其中ｔａｇ［ｔ］［ｊ１＝（ｔａｇＩ［ｔ］［ｕ】＞　ｖ）ｏｒｏｄ２，“Ｘ＞＞　”表示Ｘ右移Ｙ比特位，　＝ｆｌｏｏｒ（ｊ￣３２），　ｌｆｏｏｒ（ｘ）为下取整函数，ｖ＝３１一（ｊｒｏｏｄ３２）。这种方法不仅降　低了算法所需的存储空间，还大大降低了算法的计算量。　综上所述，去除冗余方程的压缩查表算法如下：　输入ｒ个方程　＝　一一　＝０，其中　，　，…，　是二　元域上的ｔ／＇元多项式　输出方程组１≤ｉ≤ｒ，　＝０的无冗余方程组　（１）开辟ｒ×２　的３２比特无符号整型变量存储空间　和本文所提出的新方法对ＣＴＣ算法做了大量实验。已有的基　于Ｍｉｎｉｓａｔ软件的代数攻击方法『Ｊ　’ⅢＪ是指建立了关于算法的　ｔａｇｌ［ｒ］［２　］，２　的３２比特无符号整型变量存储空间ＶＩ［２　］　和　［２　］，并将ｔａｇｉ［ｒ］［２　】、ＶＩ［２　］和　［２　］均初始化为　０，令集合，＝｛１，２，…，ｒ｝。　方程组后直接转化为ＳＡＴ问题，利用Ｍｉｎｉｓａｔ软件求解的方　法，而新方法是指建立了关于算法的方程组后先去除冗余方　程再将无冗余方程组转化为ＳＡＴ问题，利用Ｍｉｎｉｓａｔ软件求　解的方法。　（２）计算方程组中每个方程的解集。对于１≤ｉ≤　，依次　执行：穷举Ｘ　，　，…，Ｘ　的所有可能取值，记“＝∑２　ｉ＝６　，　实验环境为Ｐｅｎｔｉｕｍ　４　ＰＣ，主频２．５　ＧＨｚ、内存２５６　ＭＢ，　Ｍｉｎｉｓａｔ　２．０。实验情况总结如下：　ｖ＝∑２　Ｘｉ，　如果　，　，…，Ｘｎ是　＝０的解，　则令　ｉ＝１　ｔａｇＩ［ｉｌ［ｕ］：＝ｔａｇｌ［ｉ］［ｕ］＋２　～。　（３）计算方程组的解集。对于０≤ｉ≤２　１，计算ｖｉｉｉ］＝　ｆｌｔａｇｌ［ｔｌ［ｉ］。　（４）检测并去除冗余方程。令ｋ＝１，，　＝｛１≤ｉ≤，：ｉ≠　｝。　对于０≤ｉ≤２　一１，计算　［小＝／ＸｔａｇＩ［ｔ］［ｉ］。当ＵＩ［ｉ】＝ｖｌｔｉ】对　０≤ｆ≤２　一１均成立时，说明　＝０是冗余方程，此时令　，＝，’，并将ｋ增１。如果ｋ≤ｒ，则返回步骤４检测下个方　程　＝０是否为冗余方程，否则输出以，中元素为下标的方　程构成的方程组，算法终止；　定理２去除冗余方程的压缩查表算法的存储复杂性为　ｆ　＋２）ｘ２　～。　证明：去除冗余方程的压缩查表算法需要的存储空间为　ｔａｇｌ［ｒ］［２　］，Ｖｌ［２　］和ｕｉ［２　］，故算法的存储复杂性为　ｆｒ＋２）ｘ２”。　说明：如果直接利用冗余方程的定义去除冗余方程，则　在检验方程　＝０是否为冗余方程时，需要穷举Ｘ１　Ｘ　，…，　，　并检测Ｘ１，Ｘ２，…，　是方程组的解是否等价于它是去掉方程　＝０后的方程组的解，此时最大的穷举量是２”。但是，如　果采用本文提出的压缩查表算法，只需穷举／，ｔ＝（　，　，…，　），　并检测Ｕ／［ｕ］＝Ｖ／Ｉ，，］是否对所有“成立即可，此时最大的穷举　量是２　。因此，压缩查表算法也将计算复杂性降低为原来　的１／３２。　３．２基于Ｍｉｎｉｓａｔ软件的无冗余方程的代数攻击方法　在去除荣誉方程的压缩查表法基础上，基于Ｍｉｎｉｓａｔ软件　的无冗余方程的代数攻击方法如下：　（１）建立以算法中各变换环节的输入输出的各比特位为　未知量的方程组，其中算法的线性变换环节可直接建立以输　入输出的各比特位为未知量的线性方程，非线性变换环节仅　建立以输入输出的各比特位为未知量的低次非线性方程；　（２）对于算法中每个非线性变换环节对应的低次非线性　方程构成的方程组，调用去除冗余方程的压缩查表法来去掉　其中的冗余方程，其中去除冗余方程的压缩查表法尽量去除　项数多的冗余方程，保留项数少的方程构成无冗余方程组，　以进一步降低后续转化为ＳＡＴ问题时产生的语句个数；　（３）将排除冗余后的方程组的求解问题转化为ＳＡＴ问题，　进而利用Ｍｉｎｉｓａｔ软件求解ＳＡＴ问题从而解得方程组。　说明：对密码算法进行实际的代数攻击时，上述新方法　的前两步均可作为整个代数攻击的预处理过程提前进行，再　将无冗余方程组转化为ＳＡＴ问题，这样就可以在得到１个或　若干个明密对时，仅需将涉及到明密文的方程转化为ＳＡＴ问　题从而大大提高攻击效率。　３．３性能评测　本文分别利用已有的基于Ｍｉｎｉｓａｔ软件的代数攻击方法　（１）迭代圈数　＝４、每轮含Ｂ＝４０个ｓ盒的ＣＴＣ算法，　则密钥长度和分组长度均为１２０　ｂｉｔ。在已知１个明密对和　８５个密钥比特的条件下，对剩余３５　ｂｉｔ进行攻击。选取　５０个密钥及各密钥对应的１个明密对，分别利用已有方法和　新方法进行攻击实验：使用已有方法时Ｍｉｎｉｓａｔ的平均求解时　问为９９．４４　Ｓ；使用新方法时Ｍｉｎｉｓａｔ的平均求解时间为　３９．４７　Ｓ；但是，其中２组实验中，使用已有方法时Ｍｉｎｉｓａｔ　的求解时间小于使用新方法时Ｍｉｎｉｓａｔ的求解时间。新方法将　攻击时间缩短了１／２。　（２）迭代圈数　＝６、每轮含Ｂ＝８５个Ｓ盒的ＣＴＣ算法，　则密钥长度和分组长度均为２５５　ｂｉｔ。在已知１个明密对和　２３７个密钥比特的条件下，对剩余１８　ｂｉｔ进行攻击。选取　５Ｏ个密钥及各密钥对应的１个明密对，分别利用已有方法和　新方法进行攻击实验：使用已有方法时Ｍｉｎｉｓａｔ的平均求解时　间为２０８．７４　Ｓ；使用新方法时Ｍｉｎｉｓａｔ的平均求解时间为　１４７．１　Ｓ。新方法将攻击时间缩短了１／３。　（３）迭代圈数Ｎｒ：６、每轮含Ｂ＝８５个Ｓ盒的ＣＴＣ算法，　则密钥长度和分组长度均为２５５　ｂｉｔ。在已知１个明密对和　２３４个密钥比特的条件下，对剩余２１比特进行攻击。选取　２０个密钥及各密钥对应的１个明密对，分别利用已有方法和　新方法进行攻击实验：使用已有方法时Ｍｉｎｉｓａｔ的平均求解时　间为１　６０１．４３　Ｓ；使用新方法时Ｍｉｎｉｓａｔ的平均求解时间为　７６５．１４　Ｓ。新方法将攻击时间缩短了１／２。　（４）迭代圈数Ｎｒ＝６、每轮含Ｂ＝８５个ｓ盒的ＣＴＣ算法，　则密钥长度和分组长度均为２５５　ｂｉｔ。在已知１个明密对和　２３３个密钥比特的条件下，对剩余２２　ｂｉｔ进行攻击。选取　２Ｏ个密钥及各密钥对应的１个明密对，分别利用已有方法和　新方法进行攻击实验：使用已有方法时Ｍｉｎｉｓａｔ的平均求解时　间为３　２０９．７６　Ｓ；使用新方法时Ｍｉｎｉｓａｔ的平均求解时间为　１　５８１．５７ｓ。新方法将攻击时间缩短了１／２。　说明：新方法中去除冗余方程的时间在上述实验中都不　超过２秒。在相同实验条件下，Ｍｉｎｉｓａｔ的求解时间对不同的　明密对差异很大，例如在实验（２）的５０例实验中利用新算法　时Ｍｉｎｉｓａｔ的求解时间最短为２０．６　Ｓ，最长为２９２．７　Ｓ；同时虽　然新方法在平均时间上比原有方法快，但针对个别明密对，　使用新方法的求解时间比原方法求解时问长，如在实验（１）的　５０例中，有２例使用新方法的求解时间没有旧方法的快。实　验（２）～实验（４）都未出现这种情况，即使用新方法的求解速度　都比原有的方法快。　对ＣＴＣ算法来说，本文所提出的新方法平均将攻击时间　缩短了１／２，这也说明新方法的合理性和有效性。因此，冗余　方程的存在降低了基于Ｍｉｎｉｓａｔ软件的代数攻击方法的效率。　４结束语　本文对基于Ｍｉｎｉｓａｔ软件的代数攻击方法进行分析时发　现由该代数攻击方法对某些密码算法所建立的方程组中存在　冗余方程，提出了去除所有冗余方程的压缩查表法，基于该　压缩查表法提出了先去除冗余方程再用Ｍｉｎｉｓａｔ软件求解无　冗余方程组的代数攻击方法，利用新方法对Ｃｏｕｒｔｏｉｓ　Ｔｏｙ　Ｃｉｐｅｒ（ＣＴＣ）做了大量实验，实验结果表明对ＣＴＣ算法来说，　新方法的攻击时间平均缩短了１／２，冗余方程的存在降低了基　于Ｍｉｎｉｓａｔ软件的代数攻击方法的效率。　【６］Ｋｉｐｎｉｓ　Ａ，Ｓｈａｍｉｒ　Ａ．Ｃｒｙｐｔａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ＨＦＥ　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｃｒｙｐｔｏｓｙｓｔｅｍ　ｂｙ　Ｒｅｌｉｎｅａｒｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．　ｏｆ　Ｃｒｙｐｔｏｌｏｇｙ—　Ｃｒｙｐｔｏ’９９．Ｓａｎｔａ　Ｂａｒｂａｒａ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，１９９９：　１９—３０．　［７］Ｆａｕｇｅｒｅ　Ｊ　Ｃ．Ａ　Ｎｅｗ　Ｅｆｉｃｉｆｅｎｔ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｃｏｍｐｕｔｉｎｇ　Ｇｒ６ｂｎｅｒ　Ｂａｓｉｓ（Ｆ４）［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｐｕｒｅ　ａｎｄ　Ａｐｐｌｉｅｄ　Ａｌｇｅｂｒａ，１９９９，１３９（１）：　６１－８８．　参考文献　［１］Ｃｏｕｒｔｏｉｓ　Ｎ　Ｌ　Ｂａｒｄ　Ｇ　Ｖ　Ａｌｇｅｂｒａｉｃ　Ｃｒｙｐｔａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　Ｄａｔｅ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｔａｎｄａｒｄ［Ｚ］．（２００６—０１—０４）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／　２００６／４０２．　［８］Ｆａｕｇｅｒｅ　Ｊ　Ｃ．Ａ　Ｎｅｗ　Ｅｆｉｃｉｆｅｎｔ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｃｏｍｐｕｔｉｎｇ　Ｇｒ６ｂｎｅｒ　Ｂａｓｉｓ　Ｗｉｔｈｏｕｔ　Ｒｅｄｕｃｔｉｏｎ　ｔｏ　Ｚｅｒｏ（Ｆ５）［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＩＳＳＡＣ’０２．Ｌｉｌｌｅ，　Ｆｒａｎｃｅ：［ｓ．ｎ．］，２００２：７５—８３．　［２］Ｃｏｕｒｔｏｉｓ　Ｎ　Ｈｏｗ　Ｆａｓｔ　ｃａｎ　ｂｅ　Ａｌｇｅｂｒａｉｃ　ＡＲａｃｋｓ　ｏｎ　Ｂｌｏｃｋ　［９］Ｓｅｇｅｒ　Ａ　Ｊ　Ｍ．Ａｌｇｅｂｒａｉｃ　Ａｔｔａｃｋｓ　ｆｒｏｍ　ａ　Ｇｒ６ｂｎｅｒ　Ｂａｓｉｓ　Ｐｅｒｓｐｅｃ—　ｔｉｖｅｓ［Ｚ］．　ｆ２００４—０７—０６）．ｈｔｔｐ：／／ｗｗｗ．ｗｉｎ．ｔｕｅ．ｎｌ／－ｈｅｎｋｖｔ／ｉｍａｇｅｓ／　Ｒｅｐｏ￣一ＳｅｇｅｒｓＧＢ２—１　１—０４．　Ｃｉｐｈｅｒｓ？［Ｚ］．（２００６—０５—２０）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１　６８．　［３】Ｃｏｕｒｔｏｉｓ　Ｎ　Ｔ，Ｐｉｅｐｒｚｙｋ　Ｊ．Ｃｒｙｐｔａｎａｌｙｓｉｓ　ｏｆ　Ｂｌｏｃｋ　Ｃｉｐｈｅｒｓ　ｗｉｔｈ　Ｏｖｅｒｄｅｆｉｎｅｄ　Ｓｙｓｔｅｍｓ　ｏｆ　Ｅｑｕａｔｉｏｎｓ［Ｚ］．（２００２—１　１－１２）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．　ｉａｃｒ．ｏｒｇ／２００２／０４４．　［１０］Ｂａｒｄ　Ｇ、‘Ｃｏｕａｏｉｓ　Ｎ　Ｇｒｅｇｏｒｙ　Ｃ　Ｊ．Ｅｆｉｃｉｆｅｎｔ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｃｏｎｖｅｒｓｉｏｎ　ａｎｄ　Ｓｏｌｕｔｉｏｎ　ｏｆ　Ｓｐａｒｓｅ　Ｓｙｓｔｅｍｓ　ｏｆ　Ｌｏｗ—ｄｅｇｒｅｅ　【４］Ｃｏｕｒｔｏｉｓ　Ｎ　Ｔ．Ｆａｓｔ　Ａｌｇｅｂｒａｉｃ　Ａｔｔａｃｋｓ　ｏｎ　Ｓｔｒｅａｍ　Ｃｉｐｈｅｒｓ　ｗｉｔｈ　Ｌｉｎｅａｒ　Ｆｅｅｄｂａｃｋ［Ｃ］／／Ｐｒｏｃ．ｏｆ　Ｃｒｙｐｔｏｌｏｇｙ—Ｃｒｙｐｔｏ’０３．Ｓａｎｔａ　Ｂａｒｂａｒａ，　Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ：Ｓｐｒｉｎｇｅｒ　Ｖｅｒｌａｇ，２００３：１７６—１９４．　Ｍｕｌｔｉｖａｒｉａｔｅ　Ｐｏｌｙｎｏｍｉａｌｓ　ｏｖｅｒ　ＯＦ（２）ｖｉａ　ＳＡＴ－Ｓｏｌｖｅｒｓ［Ｚ］．　（２００７—１　１—１２）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃＬ０ｒｇ／２ｏｏ７／０２４．　［１１］Ｃｏｕｒｔｏｉｓ　Ｎ　Ｌ　Ｂａｒｄ　Ｇ　Ｖ　Ｗａｇｎｅｒ　Ｄ．Ａｌｇｅｂｒａｉｃ　ａｎｄ　Ｓｌｉｄｅ　Ａａａｃｋｓ　ｏｎ　ＫｅｅＬｏｑ［Ｚ］．ｆ２００７—１２—１ｏ）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／０５５．　［５］Ｃｏｕｒｔｏｉｓ　Ｎ　Ｔ，Ｋｌｉｍｏｖ　Ａ，Ｐａｔａｒｉｎ　Ｊ．Ｅｆｉｃｉｆｅｎｔ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｓｏｌｖｉｎｇ　Ｏｖｅｒｄｅｆｉｎｅｄ　Ｓｙｓｔｅｍｓ　ｏｆ　Ｍｕｌｔｉｖａｒｉａｔｅ　Ｐｏｌｙｎｏｍｉａｌ　Ｅｑｕａｔｉｏｎｓ［Ｃ］／／　Ｐｒｏｃ．ｏｆ　Ｃｒｙｐｔｏｌｏｇｙ—Ｃｒｙｐｔｏ’００．Ｎｅｗ　Ｙｏｒｋ，ＵＳＡ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，　［１２］Ｃｏｕｒｔｏｉｓ　Ｎ　ＣＴＣ２　ａｎｄ　Ｆａｓｔ　Ａｌｇｅｂｒａｉｃ　Ａｔｔａｃｋｓ　ｏｎ　Ｂｌｏｃｋ　Ｃｉｐｈｅｒｓ　Ｒｅｖｉｓｉｔｅｄ［Ｚ］．（２００７—０９－０２）．ｈｔｔｐ：／／ｗｗｗ．ｅｐｒｉｎｔ，ｉａｃｒ．ｏｒｇ／２００７／１５２．　２０００：３９２—４０７　编辑金胡考　（上接第１７３页）　参考文献　［１］Ｅｓｃｈｅｎａｕｅｒ　Ｌ，Ｇｔｉｇｏｒ　Ｖ　Ｄ．Ａ　Ｋｅｙ—ｍａｎａｇｅｍｅｎｔ　Ｓｃｈｅｍｅ　ｆｏｒ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　９ｔｈ　ＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｅｃｕｒｉｔｙ．Ｗａｓｈｉｎｇｔｏｎ　Ｄ．Ｃ．，　［４］Ｌｅｅ　Ｊ　Ｓ，Ｃｈａｎｇ　Ｃ　Ｃ．Ｓｅｃｕｒｅ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｆｏｒ　Ｃｌｕｓｔｅｒ－ｂａｓｅｄ　Ａｄ　ｈｏｃ　Ｎｅｔｗｏｒｋｓ　Ｕｓｉｎｇ　Ｎｏｄｅ　Ｉｄｅｎｔｉｔｉｅｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｎｅｔｗｏｒｋ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，３Ｏ（４）：１　３７７－１　３９６．　［５］Ｋｏｂｌｉｔｚ　Ｎ，Ｍｅｎｅｚｅｓ　Ａ　Ｊ，Ｖａｎｓｔｏｎｅ　Ｓ　Ａ．Ｔｈｅ　Ｓｔａｔｅ　ｏｆ　Ｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅ　ＣｒｙｐｔｏｇｒａｐｈｙｆＪ１．Ｄｅｓｉｇｎ，Ｃｏｄｅｓ　ａｎｄ　Ｃｒｙｐｔｏｇｒａｐｈｙ，２０００，１９（２／３）：　１７３—１９３．　ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ，２００２：４１—４７．　［２］Ｃｈａ　Ｗ，Ｗａｎｇ　Ｇ，Ｃｈｏ　Ｇ．Ａ　Ｐａｉｒ—ｗｉｓｅ　Ｋｅｙ　Ａｇｒｅｅｍｅｎｔ　Ｓｃｈｅｍｅ　ｉｎ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ．ｏｆＩＣＣＳ’０４，Ａｌａｂａｍａ，ＵＳＡ：［ｓ．ｎ．］，２００４．　［６］Ｓｃｈｎｅｉｅｒ　Ｂ．Ａｐｐｌｉｅｄ　Ｃｒｙｐｔｏｇｒａｐｈｙ　Ｐｒｏｔｏｃｏｌｓ　Ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　Ｓｏｕｒｃｅ　［３］Ｗａｎｇ　Ｇ，Ｃｈｏ　Ｇ，Ｂａｎｇ　Ｓ．Ａ　Ｐａｉｒ—ｗｉｓｅ　Ｋｅｙ　Ｅｓｔａｂｌｉｓｈｍｅｎｔ　Ｓｃｈｅｍｅ　ｗｉｔｈｏｕｔ　Ｐｒｅｄｉｓｔｒｉｂｕｔｉｎｇ　Ｋｅｙｓ　ｆｏｒ　Ａｄ—ｈｏｃ　Ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＩＣＣ’０５．Ｓｅｏｕｌ，Ｋｏｒｅａ：ｆｓ．ｎ．］，２００５．　Ｃｏｄｅ［Ｍ］．２ｎｄ　ｅｄ．［Ｓ．１．］：Ｊｏｈｎ　Ｗｉｌｅｙ　ａｎｄ　Ｓｏｎｓ　ｌｎｃ．，１９９６．　编辑金胡考　（上接第１７６页）　（３）在推荐因子的计算中，融入了分类结果。当出现恶意　推荐时，通过信任向量的更新来降低推荐节点的某些属性值　参考文献　［１］郭　成，李明楚，姚红岩，等．Ｐ２Ｐ网络下基于推荐的信任模　（如可靠性、历史推荐信誉度），从而在下次推荐分类时，该　类节点会从可信度高的分组中剔除，从而避免了恶意节点的　再次影响（通常情况下，节点不会轻易放弃通过大量交互积累　型［Ｊ１．计算机工程，２００８，３４（２４）：１　５７—１　５９．　［２］Ｔｅａｃｙ　Ｗ　Ｔ　Ｌ，Ｐａｔｅｌ　Ｊ，Ｊｅｎｎｉｎｇｓ　Ｎ　Ｒ．ＴＲＡＶＯＳ：Ｔｒｕｓｔ　ａｎｄ　Ｒｅｐｕｔａｔｉｏｎ　ｉｎ　ｔｈｅ　Ｃｏｎｔｅｘｔ　ｏｆ　Ｉｎａｃｃｕｒａｔｅ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｏｕｒｃｅｓ［Ｊ］．Ａｕｔｏｎｏｍｏｕｓ　Ａｇｅｎｔｓ　ａｎｄ　Ｍｕｌｔｉ－Ａｇｅｎｔ　Ｓｙｓｔｅｍｓ，２００６，１２（２）：１８３－１９８．　起来的多方面的信誉值，否则有可能得不偿失）。限于篇幅，　此问题将在后续的研究中展开。　【３］赵铁柱，杨秋鸿，梅登华．基于模糊集和灰色关联的Ｐ２Ｐ信任模　型［ＪＪ．计算机工程，２００９，３５（６）：１７３—１７５．　４结束语　本文基于社会网络人际交互的特征，提出了基于动态推　荐的信任评估模型。在获取推荐信任前，较为全面地考察了　推荐节点的可信度，并根据不同交互目的动态选择推荐节点，　从而可有效地避免推荐选择的盲目性，提高推荐的可靠性。　［４］唐　文，陈　钟．基于模糊集合理论的主观信任管理模型研　究【ＪＪ．软件学报，２００３，ｌ４（８）：１４０１－１４０８．　［５］｝ｆｊ慧蓉，邹仕洪，王文东，等．Ｐ２Ｐ网络层次化信任模型［Ｊ］ｌ电子　与信息学报，２００７，２９（１　１）：２５６０—２５６３．　编辑张正兴