基于四圈DES蚁群算法密码分析.docx
《基于四圈DES蚁群算法密码分析.docx》由会员分享，可在线阅读，更多相关《基于四圈DES蚁群算法密码分析.docx（15页珍藏版）》请在冰点文库上搜索。
基于四圈DES蚁群算法密码分析
基于四圈DES蚁群算法密码分析
作者：
SalabatKhan,WaseemShahzad,FarrukhAslamKhan
Email:
{salabat.khan,waseem.shahzad,farrukh.aslam}@nu.edu.pk
摘要：
密码专家很难运用传统的方法和暴力攻击的手段来攻击型密码由于其内在结构的高度非线性和低自相关。
在本文中,我们为四圈密码分析提出一个基于二进制蚁群（BACO）数据加密标准（DES）。
一个简单的测试攻击用作弥补DES密码的密钥安全。
蚁群是一个有向图,我们称之为搜索空间,构建有效的搜索密钥。
我们也开发一种启发式函数的措施一个建造质量的解决方案。
几个最佳密钥是在不同运行计算的基础上通过蚁群路线完成的。
然后使用这些最佳密钥找到个人的56位DES密钥。
结果，我们的实验结果表明,蚁群算法是一种四圈DES密码分析的有效方法。
具我们所知，BACO被使用解决具体问题是第一次。
关键字：
密码分析,四圈DES,蚁群优化、启发式、适应度函数。
I.简介
任何一个机构有必要维持他们的数据安全以防止任何有害的攻击。
主要有两个类别的数据或信息攻击;一个是被动攻击,另一个是主动出击。
在一个被动攻击,攻击者得到进入通讯系统并发现秘密信息中包含的数据。
这些攻击是困难的,因为攻击者不会拦截任何情况下更改课程内容的原始数据。
另一方面,主动攻击,攻击者不仅能数据的存取原始数据可以通过调整。
活跃的攻击很容易检测困难的恢复。
因此,任何一个组织都不能信任秘密数据其原来的形态,他们甚至不希望任何攻击者发动被动攻击（主动攻击更有害的）反对他们的沟通/信息系统。
因此,他们用通常被称为密码加密方案（加密算法）领域的加密。
一些密码例句。
数据加密标准（DES）,前进加密标准（AES）等使用秘密钥匙加密秘密数据或明文。
密码分析涉及技术试图恢复原始讯息或明文使用的加密方法。
它包括研究数学技术如线性密码分析对微分密码分析私密数据或攻击信息。
密码分析不是一个糟糕的活动,而是估计了复杂性和相当难度的一个加密方案在使用反攻击能够打破一个组织的私密信息。
型设计DES是基于分组的密码。
分组密码算法是现代密码基于密文替代排列。
由于是替代密码容易破坏他们的诙谐加密过程[13]。
在这里,在这个密码分析时,我们的主要目标是发现这个秘密的钥匙用在加密的明文。
长度的关键主要指标是很难会破解密码。
与一个56位DES密钥长度使暴力攻击不可行,因为它将把大量的时间才能找到密钥即使原始明文是众所周知的。
原因是,有总有256种可能的排列方式的密钥。
在最坏的情况下,找到了密钥将参与DES运行在已知明文为每个可能的安排键,然后匹配这个候选人密文（加密的文本使用猜到键）和原来的作品密文（加密的文本使用初始关键）显然不能作为DES的一个合理的密码分析时间。
群体智能和演化技术被吸引来用作密码分析学领域已经有一段时间了。
这些优化方案能很好的解决复杂的大型、动态问题。
最近,研究人员用这些优化技术自动攻击。
包括DES密码方法的基础上,提出了基于蚁群优化算法的二进制版本局限于它的搜索空间。
蚁群算法是一个元启发式算法为组合优化问题。
主要的想法蚁群算法是利用人工蚂蚁重复,产生新的解决方案。
蚂蚁使用收集的资料通过环境和修改过去的直接判断他们搜索的信息是否为可用的。
接下来的文章结构如下:
在第二部分,我们提出了相关的工作做这方面的工作。
DES的工作过程在第三部分呈现。
在第四部分,我们呈现基础和背景的蚁群准启发式。
在第五部分,提出建筑、设计及其它方案的细节。
第VI部分实验研究了该方法。
最后,总结整篇论文在VII部分。
II.相关研究
分组密码分析算法在密码学领域内是研究人员感兴趣的问题。
密码分析从古典和现代分组密码算法两个方面进行分析可以对很多的密码破解。
Spillmanetal.[1]andCastroet
al.[2]在他们的实验中使用遗传算法攻克了不同的密码。
相当数量的具体分析如何使用不同的方法破解密码在[3]中作了详细的介绍。
更深层次上，ClarkandDawson[4]对传统自动密码分析作了深入的研究。
在[5]中，作者也对模拟退火算法做了深入的研究。
禁忌搜索和密码分析遗传算法等替换密码。
GariciandDrias[6]使用著名的方法对自动密码分析的替换密码进行了分析。
文章中所描述的方法对传统的密码都是行之有效的[7]，因为它们的密码复杂度比较低并且有一些继承的关系容易被攻击者发现并利用。
现代密码一般比较复杂并且具有抗攻击型。
DES密码就经历过雪崩效应；对于任何加密算法来说，明文中的小小的变化或者是密钥的变化都会对密文产生巨大的影响。
DES的强度将在[8]中做详细的阐述。
Matsui[9]首先提出了一种改进的线性密码分析技术对DES进行密码分析。
Bafghietal.[10]提出了权重模型使用蚁群算法根据最短路径找到了不同快密码的特征。
Laskarietal.[11]使用粒子群优化技术来分析DES的简化模型。
Songetal.[12,7]使用遗传算法对2和3圈DES进行密码分析。
Shahzadetal.[13]使用二进制粒子群优化对四圈DES进行密码分析。
本文作者成功的找到解决这一问题的最优解。
在这篇文章中，我们使用二进制蚁群算法（BACO）来对四圈DES进行分析。
计划使用一堆蚂蚁又叫蚁群来找寻问题的解决办法。
在我们的实验中，每一只蚂蚁都构成了一个候选方案；这是一个64bit的密钥。
一个适宜函数会被用作一只蚂蚁加快解决问题的工具。
这些最优的解会被用作查找或是猜猜真是密钥的每一个bit。
III.四圈DES加密
在斯特密码中，通常进行转变来讲替代和排列结合在一起。
一个映射函数包括反复几次迭代。
一次迭代过程通常被叫做一圈。
DES是一个著名的斯特密码并且在近几十年中被广泛的应用在各个方面。
它总共包括16圈使用56bit的密钥对64bit的快进行加密。
DES是对称密码即加解密使用相同的密钥。
四圈DES是一个受限制的加密因为在加解密的过程中只进行了四圈。
在DES中，64bit的数据被分为左右两半。
密钥是64bit的大小但是通过排列表后变成了56bit。
这56bit的数据被分成两段每一段包含28bit。
16个密钥范围根据应用left-shifts和排列给定位移和排列表分别产生。
在DES的每一圈，都会对右边部分应用一个主函数和一个48bit的密钥空间。
在这个过程中，八个盒子会将6bit的数据块转换成4bit的数据总共产生一个32比特的数据。
最后左边的数据和这32比特的数据抑或。
在每一圈中如下的公式会被应用到上述的描述运算中去：
其中i表示圈数，代表抑或运算。
Li和Ri分别代表左右两部分。
Ki是密钥空间在第i圈的密钥。
在四圈DES中，i的最大值为四。
图1中展示了整个DES的构造过程。
更加详细的关于DES的描述可以再[14,15]中找到。
图一：
DES的工作流程
蚁群算法（ACO）是一种受到蚂蚁的习性激发的启发性算法。
ACO是一种多重代理的系统；一个蚂蚁的行为等同于一个代理在系统中的意义。
第一个蚁群算法是由Dorigo[16]提出来。
并在[17,18]中得到发展。
自然中的蚂蚁可以根据时不时的分泌一种叫做pheromone的物质来改变环境。
同时这种物质被用作一种直接的蚂蚁交流方式并且指引蚂蚁找到离食物所在地最近的路径。
如果有很多条通往食物的路径，蚂蚁会根据pheromone来慎重的选择一条。
在图二中，一个蚂蚁可以很自然的找到一条最短路径由于高剂量的pheromone可以帮助它们按照原来的路径迅速的返回。
图二：
蚂蚁找到最短路径。
A）没有障碍物。
B）有障碍物。
C）蚂蚁找寻最短路径。
D）蚂蚁找到最短路径[19]
A.简单的ACO算法
假设有一个连通图G=（V,E）其中V代表节点，E代表图的任意一条边。
这个简单的蚁群算法可以启发式的用来找到图G中从起点Vs到终点Vd的最短路径。
这条路径的长度或者通过节点的数量来定或者根据所有边的权值来确定。
图的每一条边连通节点Vi和Vj都有一个值（人工的pheromone），根据蚂蚁访问节点时改变。
从一个节点，当一只蚂蚁决定接下来将移动到哪个节点时，它可以使用两个参数来计算它将移动到一个独特的节点的可能性；第一：
从这个节点到第二个节点的距离，每一条连接边的pheromone的量。
不妨使用Dij来表示节点i和节点j之间的距离，则当蚂蚁移动到了i时这只蚂蚁接下来将要移动到j的概率可以通过下面的一个公式给出，其中S表示没有被访问过的节点集。
其中τij表示边e（i，j）的pheromone值ηij表示1/dij.α和β是影响pheromone值的变量。
每条边的Pheromone值初始为小的随机值。
一个完整的从起始节点到终节点的蚂蚁路径叫做一个解决问题的可行方案。
可以通过一个合理的公式来对这个方案进行优化。
一些有好的解决方案的蚂蚁或者所有的改变它们路径上的pheromone的量来记住它们的旅途。
一个可行的改变pheromone量的方法如下：
其中Q表示常量L表示路径的总长度。
减小L的值，就可以增大前一个pheromone的值。
随着时间的流逝，由于扩散的原因pheromone的浓度越来越小；这是一种被称做蒸发的自然现象。
这也就可以确保那些原有的pheromone不会对将来的蚂蚁造成太大的影响。
因此，随着蒸发的进行，最后pheromone的值到达ACO算法的最小值。
这种蒸发过程可以通过如下公式表示出来：
V.可行策略
A、查找空间构架
为了使用ACO算法来对四圈DES进行密码分析，一个查询空间需要首先从一个直观图中构造出来。
一只蚂蚁的路径通常是需要一些限制的。
进而，公式
（1）中的一些变量就会改变。
我们方法的核心主要是这个查找空间的结构和计算公式的诱导值。
这个查找空间包括两次。
第一次在上第二次在下，每一层都包括图（3）中包含的64个顶点。
上层的顶点用“1”来标记下层的用“0”来标记，因此这个算法又叫做二分蚁群算法。
图三：
DES密码分析的查询空间
查询空间中的顶点可以使用一个2层64列的网格来存储。
每一列的顶点都通过直接的边与所有的顶点连接除了最后一个顶点。
因此，所有边的数量是4*（63）。
一只蚂蚁从最左边列的一个通过选择0或是1的随机顶点开始它的旅程。
限定蚂蚁只可从左到右的移动并且终止于最后一列。
在任何一列中，一只蚂蚁只能选择一个顶点。
因此，这只蚂蚁的路径就会包括64个顶点标签从而构成一个64bit的二差串。
这个二差串可以用来对明文到密文的加密密钥。
B、初始化
开始，查询空间里的每条边被初始化为小值。
通常，这些值会随机的选取，但在我们的实验中pheromone的初始值并不是随机的。
可以通过公示（4）给出，然后被用作初始化pheromone的值。
其中k是明文M第kbit的值和它相应的密文C。
其中衍生值的产生是基于随机的多样明-密文配对。
对一个明文和它相应的密文进行抑或运算。
这样可以加快运算的推进过程[7]该公式是通过线性近似表达密码分析推导出来的[20,9]。
为了保证查询空间的多样性，我们定义衍生空间的值为100。
公式（4）最终得出来一个64bit的二进制串。
这个二进制串能够推导出图四所示边的pheromone值的密度。
同样运算会重复99次得出剩下的99个二进制串作为衍生值。
我们用四只蚂蚁和变量α（影响pheromone值的因素）初始值为1.5和变量β（诱导因素）初始值设为1。
图四：
pheromone值的初始化
C．适应函数
合适的函数与初始的使用了初始密钥的密文Cs和候选的使用了试验密钥的密文Ct具有完全相同的比特数，试验密钥是一只蚂蚁的完整旅程[13]。
这个合适的公式如下:
这里α表示与Cs和Ct完全相同的比特数，那么可能的值只可能是0或者1。
这是一个蚁群算法的近似公式。
同时这个公式也可以用作一般的公式来进行其他的密码分析过程。
一只蚂蚁的旅程往往代表着一个推测的密钥，而那个最接近实际密钥的那个路径往往被认为最适合的值[13]。
D.诱导值的计算
蚂蚁一般会决定接下来它将移动到哪个节点上去。
而它的可能的移动过程是通过公式
（1）来计算出来的。
为了更加接近结果启发值的计算需要改变。
往往启发值的计算过程决定着蚁群算法的算法效率。
我们的方法包括多次迭代过程（下一章讨论）。
在第一次迭代过程中，启发值初始为对结果没有什么影响的值1。
在第一次迭代结束后，四个蚂蚁就可以得出四个候选的密钥。
最好的那个候选值w.r.t.被存在一个全局最大的蚂蚁中。
现在开始，在每一次迭代过程中的任意一个需要决定的要点时，这只蚂蚁都会应用如下的启发值算法：
1）截取局部的二进制串使其长度为L。
2）决定接下来的一列中是“0”时是否继续，用0连接局部二进制串如果是“1”的话就使用1来连接，然后长度加1变为L+1.
3）从上述的最优的蚂蚁中从第L+1+1bit开始连接上述二进制串使之成为64bit的二进制串。
4）现在可以根据最优算法来计算出最适合的二进制串来并且将这个最优的值除去10，结果被用作一个诱导值。
例如，我们假设最优蚂蚁旅程（64bits）为“0100011100100010000101000010000000101000000000000001111111111101”
现在蚂蚁在查询空间的第四列的节点0上如图五所示。
因此，蚂蚁局部的旅途为“1000”。
接下来蚂蚁需要决定下一列是移动到1还是0。
这只蚂蚁需要判断接下来两个选择哪一个会更好一些。
如果是“1”，它会根据以上的四个步骤来连接二进制串如下：
1000111100100010000101000010000000101000000000000001111111111101（S1）
如果是“0”我们可以得到：
1000011100100010000101000010000000101000000000000001111111111101（S2）
现在我们根据“S1”和“S2”来计算适度值并出去10来作为一个诱导值为了下一步是去1还是去0分别来决定。
这个诱导值通常会被公式
（1）用到。
E．改进算法
在蚁群算法开始的时候，衍生值在V-B部分被关联并且初始化。
蚂蚁们会根据公式
（1）来决定它们的整个旅程。
Pheromone的量会根据公式（6）来实时的更新并且只有最优的那只蚂蚁在特殊的迭代过程中被允许更新构成蚂蚁旅程的每条边的pheromone的量。
蚂蚁们也可以根据它们旅程的适度值来更新最优蚂蚁的信息。
Pheromone量的消失迭代过程会根据公式（3）来表现出来。
图五：
启发值的计算过程
改进算法
1.从多个明密文对中产生seedingpopulation并且初始化。
2.通过公式
（1）来完成蚂蚁的整个旅程的决定过程。
3.根据公式（5）来计算出适合蚂蚁的旅程。
4.更新最优蚂蚁的信息。
并且通过公式（6）来更新连接旅程中每条边的pheromone的值。
5.通过公式（3）进行pheromone的消失过程。
6.重复进行这些步骤直到一个最优的密钥被找到或者达到了迭代的最大次数（N）。
如果找到了最优的解，如果可能则推断出这些bits并且将这些bits固定在seedingpopulation中。
7.重复1-6步（R）次。
我们每次定义（R）为500次，其中每一次要进行（N）为1000次迭代过程。
在一次迭代的过程中，如果我们找到了最优蚂蚁的适宜值大于或等于阈值‘γ’,我们就称这64bits的二进制串为最优的密钥，一旦这个最优的密钥被找到，接下来的一轮就开始了。
几个最优的密钥在交叉多次过程中生成，我们分别统计1和0的总量然后通过R[13]把它们分开。
如果总数多于‘Ϛ’（用户设置的阈值）的值，这些bits可以通过0或者1推导出来。
我们可以将这些bits固定在seedingpopulation中并且开始下一轮的过程。
这个算法一轮一轮的进行下去直到得出所有的比特。
例如，假设我们有三个最优的密钥，“R”=3其值‘Ϛ’为0.80。
假设密钥1：
（11010101），密钥2：
（11001000）密钥3：
（10001110）因此
（1）的统计量为（3,2，0,1,2,2,1,1,）（0）的统计量为（0,1,3,2,1,1,2,2）。
接下来:
Count
（1）/R=（1,0.67,0,0.33,0.67,0.67,0.33,0.33）
Count（0）/R=（0,0.33,1,0.67,0.33,0.33,0.67,0.67）
所有的bit位置都可以通过矢量Count
（1）/R和矢量Count（0）/R表示，如果值大于等于‘Ϛ’，它们会分别的被固定为1或者0。
在上述的例子中seedingpopulation中的1被定为1，3被定为0.在接下来的进程中，这些推导出来的bit将要用高浓度的pheromone值初始化每条边并且帮助猜猜其他有价值的完整密钥的bits。
这个改进的算法一次次的运行知道所有的密钥bits被找到。
VI.模拟结果
我们在VisualStudio2008C#和InterlP-IV处理器中实现改进算法。
我们用最优的比特率（密钥的最佳比率解决方案），成功位的数量（猜测密钥与初始密钥的匹配bit数）作为表现的标准。
表1：
实验结果
表1给出了实验过程中的参数值。
同时也总结出了运算过程中的一些中间值。
在实验中固定的N值为1000，运行圈数R为500。
参数‘γ’和‘Ϛ’值的多样性也在表1中体现出来。
参数‘γ’和‘Ϛ’都是用户定义其值。
其中变量‘γ’被用作找到最优密钥的阈值。
如果在一个运行过程中，一只蚂蚁的旅程中找到的候选密钥大于等于参数‘γ’的值，那么它就会被选作为最优解。
参数‘Ϛ’被用作猜测下一bit走向的阈值。
对于所有的最优解中，我们会在所有bit位中统计1的数量和0的数量并除去R。
这些bits就可以使用0或是1推导出来并且固定在seedingpopulation中。
然而这些注解推导过程可能对也可能错；如果是正确的，那么在接下来的运算过程中就会得出正确的结果和更多的有价值的密钥bits。
然而，蚂蚁们会经常因为一些具有迷惑性的推导过程而被局部的最优值吸引。
如果我们设置小的γ值，那么我们就会得到更多数量的最优解；作为蚂蚁的目标很容易被发现。
我们可以从表1中发现当γ值为0.80且Ϛ值为0.70时，我们可以得到最多数量的成功位总共19位。
如果这个算法使用这些参数值运行四圈的话，就会得到密钥的所有bit位。
在表2中，这些结果也可以在1,2和3圈DES中得到。
为了尽可能的在一次过程中尽可能的得到最优解我们使用了小值R并且把N的值设定为10，000。
实验中参数‘γ’和‘Ϛ’的值设定为能更好更快的得出结果。
从结果中，我们可以清晰的看出1，2和3圈DES加密很容易被攻击。
每一圈DES加密都会增加明密文对的复杂性。
因此我们使用这种方法对四圈以上的DES加密进行分析就会显得不那么高效了。
表2:
1，2和3圈DES结果
VII．总结和接下来的工作
本文中提出了一种新的对四圈DES数据加密的蚁群密钥分析的途径。
我们实验的结果表明这是一种密钥分析的比较高效的方法。
结果的分析是在最优比特率和成功位的获取为前提的。
有一些重要的指导提出来可以为将来这一领域的研究起很大的作用。
查询空间的结构和诱导值的计算肯能优化以获得更好的结果。
使用混合式的解决方案或许是一个好的方法例如将遗传算法和ACO算法结合起来（如果可能的话）进行一些实验。
有一些参数需要被设置为适当的值以获得更好的结果。
例如，参数α和β的值可以被调整来获得比我们实验中所使用的α和β的值（α=1.5，β=1）更加高效的值。
Pheromone的消失速率ρ可以考虑进一步的改进。
最优适度方程也有很大的改进空间。
也有很多不同种类的ACO算法可以获得更加优质的结果。
同时这些方法可以被用作其他密码分析的过程中去。
感谢
作者感谢高等教育委员会（HEC），巴基斯坦，感谢他们长久以来对本土博士研究协会的支持。
参考文献
[1]R.Spillman,M.Janssen,B.Nelson,andM.Kepner。
“Useofageneticalgorithminthecryptanalysisofsimplesubstitutionciphers”。
Cryptologia,April1993,Vol.17
（1）,pp.31-44.
[2]J.CésarHernándezCastro,J.M.Sierra,P.IsasiandA.Ribagorda。
“GeneticcryptoanalysisoftwotoundsTEA”.ICCS2002.LectureNotesInComputerScience;Vol.2331
2002.pp.1024-1031.
[3]A.Clark.“ModernOptimizationAlgorithmsforCryptanalysis”.ProceedingsofSecondIEEEAustralianandNewZealandConferenceonIntelligentInformationSystems。
1994.pp.258-262.
[4]A.ClarkandE.Dawson。
“OptimizationHeuristicsfortheAutomatedCryptanalysisofClassicalCiphers”.InJournalofCombinatorialMathematicsandCombinatorialComputing,1998,vol.28,pp.63-86.
[5]A.Clark.“OptimizationHeuristicsforCryptology”.PhDthesis,QueenslandUniversityofTechnology,1998。
[6]M.A.Garici,H.Drias.“Cryptanalysisofsubstitutionciphersusingscattersearch”。
IWINAC2005。
LectureNotesinComputerScienceVol.3562pp.31-40.
[7]J.Song,H.Zhang,Q.Meng,Z.Wang.“CryptanalysisoffourroundedDESbasedongeneticalgorithm”.InternationalConferenceonWirelessCommunications,NetworkingandMobileComputingWiCom200。
Issue。
21-25Sept.2007pp.2326–2329。
[8]D.Coppersmith.“TheDataEncryptionStandard（DES）anditsstrengthagainstattacks”.IBMJournalofResearchandDevelopment。
Vol.38Issue3。
May1994.pp.243–250。
[9]M.Matsui.“ThefirstexperimentalcryptanalysisoftheDataEncryptionStandard”.AdvancesinCrypto
升级会员 