使用二进制粒子群优化破坏简化数据加密标准外文翻译资料

IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 3, No 1, May 2012

Breaking of Simplified Data Encryption Standard Using Binary Particle Swarm Optimization

by Lavkush Sharma , Bhupendra Kumar Pathak , Nidhi Sharma

Abstract：Cryptanalysis of cipher text by using evolutionary algorithm has gained so much interest in last few years. This paper demonstrates the use of Binary Particle Swarm Optimization with bit change mutation operator for cryptanalysis of S-DES and then compared the results with Genetic Algorithm. An experimental result shows that Binary PSO performs better than the genetic algorithms for such type of problem. Here the cipher text attack is considered and several keys are generated in the iteration of the Binary Particle Swarm Optimization algorithm on the basis of their cost function value which depends upon letter frequency. The results on the S-DES indicate that, this is a promising method and can be adopted to handle other complex block ciphers like DES, AES.

Keywords: Cryptanalysis, Cipher text attack, Simplified Data Encryption Standard, genetic algorithm, Binary Particle Swarm Optimization.

1. Introduction

A cipher is a secret way of writing in which plaintext is encrypted into cipher text by using a key. Those who know the key can easily decrypt the cipher text back into the plaintext. Cryptanalysis is the study of breaking ciphers, that is, finding the key or converting the cipher text into the plaintext without knowing the key. Optimization techniques have got a significant importance in determining efficient solutions of different complex problems. One such problem is to break S-DES. This paper considers cryptanalysis of S-DES. In the brute force attack, the attacker tries each and every possible key on the part of cipher text until desired plaintext is obtained. A brute force approach may take so much time to guess the real key which is used to generate a cipher text. On the other hand optimization technique can be used for the same purpose. Genetic algorithm is an evolutionary algorithm that works well and takes less time to break cipher as compared to Brute force attack. BPSO is also a population based optimization technique which could be applied to solve such optimization problems. Unlike GA, PSO has no evolution operations like crossover and mutation. In the beginning the PSO can handle only continuous optimization problem but Kennedy and Eberhart introduced a discrete binary version of PSO to handle discrete optimization problem. In Binary PSO, each particle represents its position in binary value which are 0 and 1. As an algorithm, the main strength of PSO is its fast convergence. The remaining paper is organized as follows: Section 2 discusses the earlier works done in this field. Section 3 presents overview of S-DES and Section 4 discusses the Cost function and Section 5 gives the over view of Genetic Algorithm and BPSO. Experimental results are discussed in Section 6. Conclusion is presented in section 7.

1. Related work

In the past years, so many papers have been published in the field of cryptanalysis. R. Spillman etc. showed that Knapsack cipher and substitution ciphers could be attacked using genetic algorithm. In the recent years Garg presented the use of memetic algorithm and genetic algorithm to break a simplified data encryption standard algorithm. Nalini used efficient heuristics to attack S-DES. In 2006 Nalini used GA, Tabu search and Simulated Annealing techniques to break SDES. Matusi showed the first experimental cryptanalysis of DES using an linear cryptanalysis technique. Clark also presented important analysis on how different optimization techniques can be used in the field of cryptanalysis. Vimalathithan also used GA and PSO to attack Simplified-DES. Lavkush also used Genetic Algorithm to break SDES. In 2011 Vimalathithan used Computational Intelligence for cryptanalysis of S-DES . In this paper, a Binary PSO with bit change mutation is used to break S-DES and then compare the results with Genetic Algorithm. A population of keys is generated and their fitness is calculated by using efficient fitness function. At the end, we will find the key in less time.

3. S-DES

In this section we will provide the overview of SDES Algorithm. Simplified DES, developed by Professor Edward Schaefer of Santa Clara University is an educational rather than a secure encryption algorithm. The S-DES encryption algorithm takes an 8-bit block of plaintext and a 10-bit key as input and produces an 8-bit block of cipher text as output. The S-DES decryption algorithm takes an 8-bit block of cipher text and the same 10-bit key used to produce that cipher text as input and produces the original 8-bit block of plaintext. The encryption algorithm involves five functions: an initial permutation (IP); a complex function labeled f_K, which involves both permutation and substitution operations and depends on a key input; a simple permutation function that switches (SW) the two halves of the data; the function f_K again; and finally a permutation function that is the inverse of the initial permutation (I^P–1).The function f_K takes as input not only the data passing through the encryption algorithm, but also an 8-bit key. S-DES uses a 10-bit key from which two 8-bit sub-keys are generated. In this, the key is first subjected to a permutation. Then a shift operation is performed. The output of the shift operation then passes through a permutation function that produces an 8-bit output for the first sub-key (K1).

3.1 Initial and Final Permutations

The input to the algorithm is an 8-bit block of plaintext, which we first permute using the IP function IP= [2 6 3 1 4 8 5 7].This retains all 8-bits of the plaintext but mixes them up. At th

剩余内容已隐藏，支付完成后下载完整资料

IJCSI国际计算机科学问题，卷9，第3期，1期，2012年5月

使用二进制粒子群优化破坏简化数据加密标准

通过使用进化算法的密文安全性分析在过去的几年里已经引起了许多的关注。本文演示了为S-DES的安全性分析用位的变化变异操作的二进制粒子群优化的使用，然后与遗传算法的结果进行比较。实验结果表明，对这种类型的问题二进制PSO比遗传算法效果更好。在这里，密文攻击被认为是和几个在其取决于信频率的成本函数值的基础上的二进制粒子群优化算法的迭代产生关键问题。S-DES的结果表明，这是一种有前途的方法，可以采用，以处理其他复杂块密码像DES，AES。

关键词：密码分析，密文攻击，简化数据加密标准，遗传算法，二进制粒子群优化。

1．引言

密码是一个神秘写入方式，其中明文是通过使用密钥加密成密文，知道密钥可以轻松解密密文回明文。密码分析是打破密码的研究，即，找到密钥或不知道密钥的情况下把密文变换成明文。优化技术已经得到对确定不同的复杂问题的有效解决方案的显著重要性。有个这样的问题是要打破S-DES。本文考虑到S-DES的安全性分析。在蛮力攻击下，攻击者尝试密文的一部分中的每一个可能的密钥直到得到所需的明文。蛮力方法可能要花很长时间去猜测是用来生成密文的真正密钥。另一方面优化技术可以用于同样的目的。遗传算法是一种进化算法，相比暴力攻击，运作良好，并花费较少的时间来破解密码。 BPSO也是基于优化技术的一个受欢迎的方式，该技术可以适用于解决这种优化问题。不像GA，PSO没有一个像交叉和变异的进化操作。在开始PSO只能处理连续优化问题，但肯尼迪和埃伯哈特提出PSO的离散二进制版本来处理离散优化问题。在二进制PSO中，每个粒子代表其二进制值的位置是0和1。作为一个算法，PSO的主要力量是它的快速收敛。其余本文安排如下：第2节讨论在这个领域所做的早期工作。第3节介绍S-DES的概述和第四部分讨论成本函数和第5节给出了遗传算法和BPSO的过度视图。实验结果在第6讨论结论是在第7给出。

2.相关研究

过去这些年，很多在密码分析领域的论文已发表。R.Spillman等表明，背负式密码和替换密码可以使用遗传算法攻击。近年来，加尔格提出采用模因算法和遗传算法打破简化数据加密标准算法。娜莉妮用高效启发式攻击S-DES。 2006年娜莉妮使用GA，禁忌搜索和模拟退火技术突破SDES。 Matusi 展示了DES的第一个采用线性分析方法实验密码分析。克拉克也提出了关于如何可以在密码分析的领域中使用不同优化技术的重要的分析。 Vimalathithan 也用遗传算法和PSO攻击简化-DES。 Lavkush也用遗传算法打破SDES。 2011年Vimalathithan对S-DES的安全性分析用计算智能 。在本文中，二进制PSO与位变化突变是用来打破S-DES，然后与遗传算法的结果比较。密钥形成和他们的适应值是通过使用高效的适应度函数来计算。最后，我们在更短的时间内找到密钥。

3.S-DES

在本节中，我们将提供SDES算法的概述。简化DES是由圣克拉拉大学的爱德华bull;谢弗教授开发的是一种教学性质的而不是一个安全加密算法。S-DES 的加密算法采用一个8位块明文的和10位密钥作为输入，并产生一个8位块密文作为输出。S-DES解密算法将一个8位块密文和用于产生相同的10位密钥的密文作为输入并且产生明文的原始8位块。加密算法包括五大功能：一个初始置换（IP）;标记F_k一个复杂的函数，这既包括置换和替换操作，并且取决于密钥输入;一个简单的置换函数，开关（SW）中的数据两部分;再次功能F_k;最后一个置换函数即逆初始置换（IP^-1）。函数f_k作为输入不仅通过加密算法的数据，也有8位的密钥。 S-DES使用一个10位的密钥并从其产生两个8位的子项的。在此，密钥首先进行置换（P10）。然后进行转换操作。移位操作的输出通过产生用于第一子项（K₁）的8位输出（P8）的置换函数传递。

3.1初始和最终置换

输入到算法是明文的一个8位块，这是我们使用IP功能IP= [26 3 14 8 57]的第一次重排，保留了明文的所有8位，但把它们混合起来了。在算法结束时，逆置换是通过，IP^-1= [4 1 35 7 28 6]其中，我们有IP^-1（IP（X））= X完成的。

3.2函数f_k

函数f_k，是SDES的复杂组成，包括置换和替换功能的组合。功能如下给出。

设L，R为左4位和输入的右4-位，那么，

F_K（L，R）=（L XOR F（R，key），R）

其中异是异或运算和密钥是一个子 密钥。F（R，key）计算如下进行。

1.应用扩展/置换E / P= [4 1 2 32 3 41] 输入4位。

2.添加8位密钥（XOR）。

3.传递通过S-box S0左4位和通过S-Box S1的右4位。

4.应用置换P4= [2 4 31]。

S-box的操作如下：在第一和第四输入指定的一行的被视为2位数字的位而第二和第三输入指定的S-box的一列。在2的基础上该行和列中输入的项是2位输出。

图1.S盒的工作

3.3切换功能

函数f_k仅改变输入的最左边的4位。开关功能（SW）互换左，右的4位，使F_K的第二个实例在不同的4位进行操作。在此第二实例中，E / P，S0，S1，和P4功能是相同的。密钥输入是K₂。

4.成本函数公式

（1）是用于确定假定密钥（K）的适宜的总体的适应度函数。在这里，A表示语言字母（即英语，[A...... Z，_]，其中_代表空格符号），K和D分别表示已知的语言统计和解密的消息统计，u，b和t分别表示单字，双字母组合和卦统计; alpha;，beta;和gamma;是加权以每三个统计的分配不同的权重，其中alpha; beta; gamma;= 1。鉴于卦的计算复杂性，仅使用单字组和两字组的统计数据。

5.方法

5.1遗传算法

遗传算法是一种基于自然选择和“优胜劣汰”的搜索算法，其主要思想是，为了使个体的群体适应某些环境，它应该像一个自然系统。这意味着一个个体的生存和繁殖通过无用性状消除和通过奖励有用行为而促进。遗传算法属于家族的进化算法。一种进化算法保持为现存问题的方案群。群体通过一组随机运营商的迭代应用演变。遗传算法的最简单形式有以下三种类型的运算符：选择，交叉和变异。选择算子首先被应用。

选择：这种选择算子选择用于复制群体的染色体。越好染色体，次数越多，更有可能被选择以复制。交叉：交叉选择从父染色体的基因，并创建一个新的后代。要做到这一点最简单的方法是随机选择一些交叉点和在此之前从第一个父辈复制的一切，然后，从第二父复制交叉点之后的一切。变异：交叉后，进行变异。这是为了防止在群体中所有的解决方案落入解决的问题的一个局部最优。变异随机变化新后代。在二进制GA，我们可以切换几个随机选择位从1到0或从0到1。在遗传算法中，我们采用环形交叉算子。在环交叉两个亲戚如parent1和parent2被认为是交叉过程，然后以环的形式相结合，如图所示。图3（b）。然后，在环的任何一点决定随机切割点。子代根据合并的两个亲本染色体的长度在环的任何点产生的随机数创建。参照切割点，当其中一个子代在顺时针方向被创建，另一个是在逆时针的方向上产生，如图所示。图3（c）。然后交换和反转过程在环交叉算子执行，如图所示。图3（d）。

该程序进行使用GA密码分析为了打破密钥，如下：1.输入：密文，和语言的统计数据。 2.随机产生的初始池解决方案。 3.计算每个池中使用等式（1）的解决方案的适应值。 4.重复下面的步骤，直到新的群体完整的来创建一个新的种群。从根据他们自己的适应值（更好的适应值，更大的机会被选中）从目前的群体中选择父辈（密钥）。这里使用锦标赛选择。B,用交叉概率交叉父母，形成新的后代（子代）。在我们的遗传算法，我们使用的是环交叉算子C，对于每一个子代，进行一些变异概率产生新的后代的变异操作。 D,将新的后代放置到新的群体5.使用新的群体产生为算法的进一步运行。6，如果结束条件得到满足，停止，并返回当前种群的最佳解决方案

5.2二进制粒子群优化

粒子群优化（PSO）是由肯迪尼和哈伯特开发的一个基于优化算法的群体。它是由鸟类群体对粮食搜索时的社会行为的启发。在PSO算法中，每种方法被称为粒子，每个粒子在根据颗粒本身的值（溶液）和粒子的邻居的值不断更新的超维搜索空间的速度飞来飞去。每个粒子跟踪迄今取得的最佳值（溶液），这个值被称为个体极值。此外，每个粒子都知道该组中迄今取得的最好的值被称为群体极值。各颗粒的下一步是通过一个速度矢量控制，受个体极值和群体极值影响。在搜索空间，每一个粒子的速度V_n（t）和位置X_N（t）的更新是基于以下公式。

C1和C2是正加速度常数，R1和R2是0和1之间的随机数，和w为惯性重量。 PSO的二进制版本被肯尼迪和埃伯哈特提出。但粒子群优化二进制版本有跳出好局部最优的问题。这个问题可以通过二进制PSO用位变化变异进行处理。在二进制PSO中，粒子的个体最佳值和全局最佳值被连续的PSO更新。二进制PSO和具有连续PSO的主要区别在于颗粒的速度使用一个取0或1为的可能性。利用该定义，一个速度必须是受到[0，1]的范围限制。在BPSO的等式（2）更新速度保持不变，但对于更新的位置上的方程（3）由下面的公式（4）重新定义。

其中S（.）是一个S形函数,此功能用于转化速度，以约束到间隔[0，1]的概率 ，rand()是从[0，1]区间中选择随机数。当二进制粒子群优化开始迭代找到一个最佳的解决方案，速度趋向于进入V_MAX或-v_max通过速度更新方程（2），根据分别作为相应的目标位置是1或0。如果速度收敛接近V_MAX或 - v_min，很难去改变有速度微小变化的相应位置，使得它很难从BPSO的一个良好的局部最优逃脱出去。为了处理这种不理想的位置，速度的大的移动是必需的，这是不相关的的p_best和g_best。为了实现上述目的，在BPSO过程中在速度更新和位置更新之间插入下面的操作

其中r_mute是一个概率。如果在执行此操作时，速度接近V_max和-v_max，则位置将分别被从1变为0或0到1。使用BPSO进行密码分析的算法突破密钥如下。

算法：

步骤1。初始化随机粒子，形成群和PSO的参数。

第2步。计算每个粒子根据公式（1）给出的适应度函数的适应值。适应度函数决定解决方案好坏。

第三步。根据等式（2），（4）和等式（5）更新速度和粒子的位置。

第四步。更新局部最优和全局最优值。

Step4. 如果没有超过最大迭代就停止迭代或者如果低适应值被找到，然后转到步骤5否则转到步骤2。

Step5. 显示是到目前为止的最佳key，然后退出

6.结论

我们在本文的目的是比较有位的变化突变的二进制粒子群优化算法与遗传算法的结果。实验是在Core 2 Duo系统上进行的。有各种各样的由以往其它研究人员使用的成本函数。最常见的成本函数使用克的统计数据，有的用大量克而其他人只用了很少。等式（1）是用于确定一个已提出的密钥的通式。许多实验已经通过不同的投入和运用遗传算法和二进制PSO进行打破简化数据加密标准。

遗传算法参数

遗传算法参数使用的：

群体规模：100

选择：选择算子竞赛

交叉：环装交叉

交叉：.85

变异：.02

后代数：50

BPSO参数

自我识别参数C1 2

社会参数C2 2

惯性权重 0lt; W lt;0.99

初始群体 100

迭代号 50

r_mute .004

表1：遗传算法和二进制粒子群算法的比较