1、毕业设计 英文翻译译文 一种混沌图像加密并行算法 英译中附英文原文指导教师评定成绩(五级制):指导教师签字:附件C:译文基于离散混沌映射的图像加密并行算法摘要:最近,针对图像加密提出了多种基于混沌的算法。然而,它们都无法在并行计算环境中有效工作。在本文中,我们提出了一个并行图像加密的框架。基于此框架内,一个使用离散柯尔莫哥洛夫流映射的新算法被提出。它符合所有并行图像加密算法的要求。此外,它是安全、快速的。这些特性使得它是一个很好的基于并行计算平台上的图像加密选择。1.介绍最近几年,通过计算机网络尤其是互联网传输的数字图像有了快速增长。在大多数情况下,传输通道不够安全以防止恶意用户的非法访问。因
2、此,数字图像的安全性和隐私性已成为一个重大问题。许多图像加密方法已经被提出,其中基于混沌的方法是一种很有前途的方向1-9。总的来说,混沌系统具有使其成为密码系统建设中重要组成部分的几个属性:(1)随机性:混沌系统用确定的方法产生长周期、随机的混沌序列。(2)敏感性:初始值或系统参数的微小差异导致混沌序列的巨大变化。(3)易用性:简单的公式可以产生复杂的混沌序列。(4)遍历性:一个混沌状态的变量能够遍历它的相空间里的所有状态,通常这些状态都是均匀分布的。除了上述性能,有些二维(2D)的混沌映射是图像像素置换天生的优良替代者。Pichler和Scharinger提出一种在扩散操作1,2之前使用柯尔
3、莫哥洛夫流映射的图像排列方式。后来,Fridrich将此方法扩展到更广义的方式3。陈等人提出基于三维猫映射的图像加密算法4l。Lian等人提出基于标准映射的另一种算法5。其实,这些算法在相同的框架下工作:所有的像素在用密码分组链接模式(CBC)模式下的加密之前首先被用离散混沌映射置换,当前像素密文由以前的像素密文影响。上述过程重复几轮,最后得到加密图像。这个框架可以非常有效的实现整个图像的扩散。但是,它是不适合在并行计算环境中运行。这是因为当前像素的处理无法启动直到前一个像素已加密。即使有多个处理元素(PE),这种计算仍然是在一个串行模式下工作。此限制了其应用平台,因为许多基于FPGA / C
4、PLD或者数字电路的设备可以支持并行处理。随着并行计算技术的应用,加密速度可以大大加快。基于混沌的图像加密方案的另一个缺点是运算速度相对较慢。主要原因是基于混沌的密码通常需要大量的实数乘法和除法运算,计算成本巨大。加密算法在并行处理平台上执行计算效率将大幅提升。在本文中,我们提出了一个并行图像加密的框架。在这样的框架下,我们设计了一个安全快速算法满足并行图像加密所有要求。本文的其余部分安排如下:第2部分介绍了并行的操作模式和其要求。第3节给出加密解密中四个转换的定义和属性。在第4节,加密、解密的过程和密钥调度会加以详细说明。第5和第6节,提供实验结果与理论分析。最后,我们总结本文 。2.并行模
5、式2.1.并行模式及其要求在并行计算模式下,每个PE是负责图像数据的一个子集,并拥有自己的内存。在加密时,可能会有一些PE之间的通信(见图1)。要允许并行图像加密,传统CBC样的模式必须予以打破。然而,这将导致新的问题,即如何实现不在这种模式下的扩散要求。此外,也出现了一些额外针对并行图像加密的要求:1.计算负载平衡 并行图像加密方案的总时间是由最慢的PE决定,因为其它PE不得不等待直至这个PE完成其工作。因此,良好的并行计算模式可以平衡分配给每个PE的任务。2.通信负载平衡 通常存在有大量的PE之间的通信。基于和计算负载同样的原因,通信负载应认真平衡。PE PEPE图1 图像加密并行计算模式
6、3.临界区管理在并行模式计算时,许多的PE可以同时读取或写入相同的内存区域(即临界区),这往往会导致意想不到的执行程序。因此,有必要在关键区域使用一些并行技术管理。2.2.并行图像的加密框架为了满足上述要求,我们提出了一个并行图像加密的框架,这是一个四个步骤的过程:步骤1:整个图像被划分成若干块。步骤2:每个PE负责确定数量块。一个区域内的像素可以充分使用有效的混乱和扩散进行操作加密。步骤3:通过PE之间的通信交换加密数据块从块到更大范围的扩散。步骤4:转到第2步,直到加密图像达到所需的安全级别。在第2步,已经实现扩散,但只有一个块的一个小部分。但在第3步的帮助下,这样的扩散效应被扩大。请注意
7、,从加密的角度,在步骤3中的数据交换本质上是一个置换。经过多次迭代步骤2和3,扩散效应蔓延到整个图像。这意味着在一个普通的图像像素的微小变化会波及到了大量的加密图像的像素。为了使框架足够安全,两个要求必须被满足:1.第2步中的加密算法混乱和扩散的特点应该是足够安全的,而且对明文和密钥敏感。2.在步骤3中的置换在几个回合变化中必须从局部蔓延到所有部分。 结合不同的加密元素可以满足第一个要求,如S-盒,Feistel 结构,矩阵乘法和混沌映射等,或者我们可以只使用一个传统的加密标准,如AES或IDEA。然而,第二个是由于这一框架而产生的一个新课题。此外,这样的置换应有助于实现2.1节中提出的三个附
8、加目标。因此,置换操作是本文的重点之一,应认真研究。 这种并行图像加密框架下,我们提出了一种新的算法,这是基于四个基本的转换。因此,我们将描述我们的算法之前,先介绍这些转换。3.转换3.1.A-转换在A转换中,A代表加,能被形式化的定义如下:a+b=c (1) 加法被定义为按位与操作转换A有三个基本性质:(2.1)a+a=0 (2.2)a+b=b+a (2)(2.3)(a+b)+c=a+(b+c)3.2 M-转换在M转换中,M代表混合数据首先,我们介绍和转换:sum:定义sum(I): (3)sum(I)=然后给出M转换的定义M:让M(I)=C 让I= C= (4)容易证明M转换有如下性质:(
9、5.1)M(M(I)=I (5)(5.2)M(I+J)=M(I)+M(J)(5.3)M(kj)=kM(I),where kI=,k需要指出的是,从所有从(3)(5)的加法运算其实是A转换。3.3 S-转换在S-变换中,“S”代表S盒置换。有很多方法来构造S盒,其中混沌的做法是一个很好的选择。例如,唐等人提出了一个基于离散逻辑映射和Baker映射10的设计S-盒的方法。之后,陈等人提出另一种方法来构造S盒,具有更好的性能11。该过程描述如下:步骤1:选择一个Chebyshev映射的初始值,然后迭代映射生成初始的S-盒表。步骤2:把二维表加载到三维表上。步骤3:多次应用离散化的三维Baker映射使
10、表格混乱。最后,把三维表转换成二维,以获得所需的S-盒。实验结果表明,由此产生的S-盒是加密应用程序的理想选择。该方法也被称为“动态”的,当Chebyshev映射的初始值被改变时得到不同的S-盒。然而,为了简化和性能,我们使用一个固定的S-盒,即在11给出的例子见表1。3.4 K-转换在K-转换中,“K”代表柯尔莫哥洛夫流,通常被称为广义Baker映射3。图像加密应用程序的Kolmogorov流由Picher和Scharinger首次提出 1,2。 离散形的K-流如(6):(x,y)=(x-)+(y mod ),+(y div ) (6)其中=(n1,n2,.nk),是一个正整数=N,划分把s
11、和N分开,=一个垂直的s的范围:=需要注意的是(6)可以用图2中的几何变换来解释。N*N图像可以划分为高N和宽度Ns的垂直矩形。然后又进一步分为箱子每一个垂直的矩高度Ps宽度Ns。 K -映射后,从同一个盒子的像素实际上是映射到一个单行的。表(1)提及的s盒是11中给出的例子161851292241765020717748205686011601174613012420358145141151892351424431351521915215383968613322813617523109252236491679210694811391511342457217217162797723182322
12、382263998021716417801542401881501572152321801191661814120179725418118447146233113120542118311815114362531972916513220422664107885582216518523416221025017961202248247213891011081024556521210122432162428411114367931231113724917027223186951691161632517413591104196208148242513940311621921474140211112751
13、9073187244182122193131194149121761561682223424170255229246905322510030372371031263820044209422941218711557812517328128872393191158199138227596922019566192230198261596127201144206983335710514757110图2 每个盒子里的像素都要被k流划分成单行4MASK-一个并行的图像加密体系4.1加密方案的概要假设的NN图像是由n个 PE同时加密的,我们描述并行加密方案如下:1.每个PE负责图像中像素的一些固定行。2.每
14、行的像素分别使用M,A,S进行加密。3.根据置位转型K进一步扩散的所有像素。4.转到第二步进行另一轮的加密,直到密文足够安全。 如上所述,在第3步中的置换是非常重要的,因为它有助于满足安全性和速度要求。因此,置换的映射和它的参数,一定要慎重选择。在我们的算法中,是常数向量其长度为q,其中q = N / n。向量的每个元素都等于n: =(n,n,.n)1q (7)每个PE负责q个连续的行,或者更具体地说,第i个PE行负责从(i-1)*q 到i*q-1的行。该算法可以实现并行加密的所有要求,分析如下。1.整个图像的扩散效应假设在第2步的操作有足够的安全。第2步后,明文像素的微小变化会扩散到整行的N
15、个像素。如果我们根据Eq(7)选用,很容易证明,这N个加密的像素会在第3步K变换中会置换到不同的q行。同样,另一轮加密过后,改变会扩散到q行,第3轮后,整个加密图像已经改变。因此,在我们的方案中,任何单个像素的最小变化会在3轮后扩散到整个图像。2.通讯负载平衡如果参数(6)中的参数(7)那样选择,很容易证明,两个PE之间的数据交换是不变的,即等于图像的像素总数的1/q2。对于每个PE,这个数量变为(q-1)/ 。因此,在我们的方案中,每个PE的通信负载是等效的,并没有任何通讯负载不平衡。3.平衡负载的计算每个PE将要加密的数据都是像素q行,因此计算负载平衡自然实现。4.临界区管理在我们的体制中
16、,不会发生两个PE读取或写入到相同的内存。因此,我们不必像其他并行计算体制经常做的一样需要施加任何关键领域的管理技术。上述讨论表明,该方案能实现并行图像加密的所有要求,这主要归因于混沌柯尔莫哥洛夫映射和其参数的选择。4.2.加密密文经过数轮加密才能产生。然而,在第一轮中,图像预先经过K置换处理。然后在每一轮中,分别进行M,A,S,K的变换。最后一轮与前面不同之处在于S-变换故意遗漏。M,A,S变换通过PE操作一行中的每个像素,而这K操作对整个图像的运作必然涉及到PE之间的通信。加密过程是由伪代码在图3中列出所描述的。4.3轮密钥生成在四个置换中,只有置换A需要一个轮密钥。对于8位灰度图像的N*
17、N像素,一个包含N个字节的轮密钥应在每一轮为置换A产生。 一般来说,轮密钥应该是伪随机和敏感的。从这个角度来看,一个混沌映射是一个很好的选择。在我们的体系中,我们使用斜帐篷映射生成所需的轮密钥。= (8) 图3.MASK的伪代码混沌序列由系统参数和混沌映射的初始状态确定,它们是0和1之间的实数。虽然混沌映射方程很简单,它生成的伪随机序列对系统参数和初始状态敏感。这个属性使得映射是密钥生成的理想选择。 在数字计算机实施时,映射状态存储为一个浮点数。第一个轮状态的8位被提取作为一个字节的轮密钥。因此,我们每一轮需要N次迭代斜帐篷映射。4.4.解码一般情况下,解密程序是由一个相反的顺序执行加密转换组
18、成。此性质也在我们的体系中。然而,经过精心的设计,我们体系中解密过程是相同的,而不是反转,转换为密码。这个令人印象深刻的特征属性归功于以下变换的两个属性:(1)置换-S和置换 - K可交换。置换-S只替换每个像素的值而独立于它的位置。另一方面,置换 - K只改变一个像素的位置其值不变。因此,两者之间的转换关系可表示为(9):K(S(I)=S(K(I) (9)(2)根据(5)置换-M是一个线性操作。此外,(5.2)中定义的加实际上是置换-A。因此, 两者之间的转换关系可表示为(10): M(A(I,J)=A(M(I),M(J) (10)总之,无论是置换S和K时,还是置换M和A,可以互换计算顺序对
19、最终结果没有影响。表2说明了这两个属性如何影响置换的顺序,应用简单的2轮加密例子加以证明。很容易观察到多轮加密组成的密码,解密过程中仍然具有和加密过程相同的序列。因此,密码和解密共享相同的框架。但是加密和解密过程之间仍然有一些细微的差异:(1)在解密中使用的轮密钥是加密过程的倒序,这些密钥应首先应用在置换M。(2)在解密中K和S的置换应使用其逆变换。然而,由于置换K和S都可以实现查找表操作,其逆变换不同的只是在查找表的内容。因此,所有在计算上述差异可以转换到数据差异。对称的特性使得我们的方案非常简洁。它也减少了很多计算机系统实施代码用于加密和解密。如果硬件实现,这个属性使两种设备的使用成本降低
20、。表2在2轮加密过程相当于解密我们的方案结构看起来更简洁,并在实施过程中节省了很多的代码。这绝对是一个与其他基于混沌的密码的比较优势。5.实验结果在本节中,举例说明该算法的有效性。在实验中,灰色水平图像“莉娜”的大小为256 * 256,如图所示,Fig.4a为原始图片。PE数量为4个。我们系统的关键点,即初始状态和存储系统参数以浮点方式储存,具有56位精度。这里介绍的例子, = 0.12345678,和L = 1.9999。 当加密过程完成后得到如图所示 Fig.4b。通常情况下,我们建议对原始图像进行9轮加密。5.1.直方图原始图像和加密图像的直方图的描绘图分别是Fig.4c和Fig.4d
21、。这两个数字表明:加密图像具和原始图对比具有均匀分布的特点。5.2.两个相邻像素的相关性分析 相关分析是由随机选择1000对纵向,横向和对角线方向两个相邻像素,分别从原始图像和加密图像。然后,一对像素的相关系数计算结果见表3。图5显示了两个水平相邻关系像素。这是显而易见的,加密图像的相邻像素的相关性不大。5.3.NPCR分析 NPCR意味着当只有一个原始图像的像素改变引起的加密图像的像素数的变化率。在我们的例子中,选定的像素是原始图像的最后一个像素。它的值从(01101111)2改为(01101110)2。然后经过不同轮NPCR计算和表4中列出。数据显示,经过3轮的加密性能是令人满意的。经过9
22、轮的两个密码的图像不同的像素绘制在图6中表示。图4(a) (a)原始形象,(b)加密图像,(c)原始图像的直方图,(d)加密图像的直方图。表3临近两个像素在原始图像和加密图像中的相关系数 图5水平两个像素的相关系数(a)是原始图像(b)是加密图像,x,y分别代表两个相邻像素的灰度水平。表4两个加密图像在不同轮的NPCR5.4.UACI分析统一平均变化强度(UACI)指数衡量的是两个图像平均强度差异。同样,我们做与5.3节中相同的变化并计算两个加密图像之间的UACI。结果如表5所示。经过三轮的加密UACI被汇聚到1/3。应当注意到,如果它们完全与对方无关,两个随机序列的平均误差均匀分布在0,1之
23、间的平均误差为1/3。图6.经过九轮加密过后两个不同加密图像之间的差异。白色的点(约占整个图像像素的的1/256)表示这两个加密图像在这个位置的值相等。表5两个加密图像的UACI6.安全性和性能分析6.1.扩散 NPCR分析显示,当原始像素只有1位改变时,几乎所有的加密像素都变得不一样,两个加密像素相等的可能性只有1/256。这种扩散到置换S,因为任何的S盒的输入位变化会影响所有输出位变化,概率为50。然后,扩散传播到置换M的整个行,置换K有助于扩散放大至2轮的图像25,并在3轮达到整个图像。6.2.混淆 相邻像素的直方图和相关分析都表明,我们的方案具有良好的混淆属性。这主要是由于伪随机性的关
24、键时间表和置换M和A。他们共同工作,引进随机的效果来加密图像。 K置换也有利于摧毁本地原始图像的相似性。6.3.蛮力攻击 建议方案使用的密钥即初始状态X0和系统参数的位数是112。这是迄今为止非常安全以应用于适合普通商业应用程序。因此,我们的方案是强大的,足以抵御蛮力攻击。此外,也很容易增加X0和的位数。6.4.其他安全问题有人可能会争辩说,在我们的方案中,置换K 不属于任何密钥管辖。然而,这样对我们的方案的安全性影响很小。事实上,最传统的加密算法如DES和AES使用公共排列。它至少有两个原因。首先,受密钥支配的序列使加密速度减慢,因为它花费时间来产生关键的序列。其次,也是最重要的,不可靠的序
25、列可能会产生一些密钥,危害到系统的安全性。其实,一个有助于实现扩散和混乱置换是一个更好的选择。更具体地说,在一个并行的加密系统中,如果置有助于实现计算和通信负载平衡就是一个很好的选择。从这点来看,选择置换K是一个正确的选择。6.5.性能分析 该算法的运行速度非常快,只有逻辑XOR加密查表操作和解密过程。虽然置换K中要进行乘法和除法运算,但PE一旦确定转换也随之确定。因此,他们可以预先计算并存储在查找表中。更准确地说,在每一轮中的每个像素有只有3个 XOR操作(2个在置换M和1个在置换A)和2个查找表操作(1个在置换S和另一个在置换K中)。相反,最简单的具有56位精度状态变量的逻辑映射,乘法平均
26、增加约28倍成本。我们的主要方案中,还需要在斜帐篷映射中应用乘法。然而,在每一轮只有N多乘法还有平均每轮每个像素的1 / N乘法运算。此外,当算法在并行平台运行,其性能可以比普通的序列图像加密方案提高近n倍。因此,考虑到可实现的性能,我们的方案是比现有的优越。7.结论 在本文中,我们介绍了并行图像加密的概念,并提出了几项要求。然后在并行图像加密的框架中,提出了一个基于这个框架设计的新算法。该算法在柯尔莫哥洛夫离散映射的帮助下成功满足并行图像加密算法的所有要求。此外,实验结果和理论分析表明,该算法具有较高的安全性。该算法运算速度也快;只有一对每个像素的异或运算和查表操作。最后,解密过程相对于加密
27、是相同的。考虑到上述所有的特性,该算法是在并行计算平台上进行图像加密不错的选择。译文原文出处:Qing Zhou , Kwok-wo Wong , Xiaofeng Liao , Tao Xiang , Yue Hu :Parallel image encryption algorithm based on discretized chaotic map,Chaos, Solitons and Fractals 38 (2008) 10811092. Parallel image encryption algorithm based on discretized chaotic map Abs
28、tractRecently, a variety of chaos-based algorithms were proposed for image encryption. Nevertheless, none of themworks efficiently in parallel computing environment. In this paper, we propose a framework for parallel image encryption.Based on this framework, a new algorithm is designed using the dis
29、cretized Kolmogorov flow map. It fulfills all therequirements for a parallel image encryption algorithm. Moreover, it is secure and fast. These properties make it a goodchoice for image encryption on parallel computing platforms.1. IntroductionIn recent years, there is a rapid growth in the transmission of digital images through computer networks especially the Internet. In most cases, the transmission channels are not secure enough to prevent illegal access by malici