文献翻译——基于离散混沌映射的图像加密算法

第1页外文文献资料ImageencryptionalgorithmbasedondiscretechaoticmapsRecently,avarietyofchaos-basedalgorithmswereproposedforimageencryption.Nevertheless,noneofthemworksefficientlyinparallelcomputingenvironment.Inthispaper,weproposeaframeworkforparallelimageencryption.Basedonthisframework,anewalgorithmisdesignedusingthediscretionKolmogorovflowmap.Itfulfillsalltherequirementsforaparallelimageencryptionalgorithm.Moreover,itissecureandfast.Thesepropertiesmakeitagoodchoiceforimageencryptiononparallelcomputingplatforms.1.IntroductionInrecentyears,thereisarapidgrowthinthetransmissionofdigitalimagesthroughcomputernetworksespeciallytheInternet.Inmostcases,thetransmissionchannelsarenotsecureenoughtopreventillegalaccessbymaliciouslisteners.Thereforethesecurityandprivacyofdigitalimageshavebecomeamajorconcern.Manyimageencryptionmethodshavebeenproposed,ofwhichthechaos-basedapproachisapromisingdirection.Ingeneral,chaoticsystemspossessseveralpropertieswhichmakethemessentialcomponentsinconstructingcryptosystems:(1)Randomness:chaoticsystemsgeneratelong-period,random-likechaoticsequenceinadeterministicway.(2)Sensitivity:atinydifferenceoftheinitialvalueorsystemparametersleadstoavastchangeofthechaoticsequences.(3)Simplicity:simpleequationscangeneratecomplexchaoticsequences.(4)Ergodicity:achaoticstatevariablegoesthroughallstatesinitsphasespace,andusuallythosestatesaredistributeduniformly.Inadditiontotheaboveproperties,sometwo-dimensional(2D)chaoticmapsareinherentexcellentalternativesforpermutationofimagepixels.Pichlerand第2页ScharingerproposedawaytopermutetheimageusingKolmogorovflowmapbeforeadiffusionoperation.Later,Fridrichextendedthismethodtoamoregeneralizedway.Chenetal.Proposedanimageencryptionschemebasedon3Dcatmaps.Lposedanotheralgorithmbasedonstandardmap.Actually,thosealgorithmsworkunderthesameframework:allthepixelsarefirstpermutedwithadiscretionchaoticmapbeforetheyareencryptedonebyoneunderthecipherblockchain(CBC)modewherethecipherofthecurrentpixelisinfluencedbythecipherofpreviouspixels.Theaboveprocessesrepeatforseveralroundsandfinallythecipher-imageisobtained.Thisframeworkisveryeffectiveinachievingdiffusionthroughoutthewholeimage.However,itisnotsuitableforrunninginaparallelcomputingenvironment.Thisisbecausetheprocessingofthecurrentpixelcannotstartuntilthepreviousonehasbeenencrypted.Thecomputationisstillinasequentialmodeevenifthereismorethanoneprocessingelement(PE).ThislimitationrestrictsitsapplicationplatformsincemanydevicesbasedonFPGA/CPLDordigitalcircuitscansupportparallelprocessing.Withtheparallelcomputingtechnique,thespeedofencryptionisgreatlyaccelerated.Anothershortcomingofchaos-basedimageencryptionschemesistherelativelyslowcomputingspeed.Theprimaryreasonisthatchaos-basedciphersusuallyneedalargeamountofrealnumbermultiplicationanddivisionoperations,whichcostvastofcomputation.Thecomputationalefficiencywillbeincreasesubstantiallyiftheencryptionalgorithmscanbeexecutedonaparallelprocessingplatform.Inthispaper,weproposeaframeworkforparallelimageencryption.Undersuchframework,wedesignasecureandfastalgorithmthatfulfillsalltherequirementsforparallelimageencryption.Therestofthepaperisarrangedasfollows.Section2introducestheparalleloperatingmodeanditsrequirements.Section3presentsthedefinitionsandpropertiesoffourtransformationswhichformtheencryption/decryptionalgorithm.InSection4,theprocessesofencryption,decryptionandkeyschedulingwillbedescribedindetail.ExperimentalresultsandtheoreticalanalysesareprovidedinSections5and6,respectively.Finally,weconcludethispaperwithasummary.第3页2.Parallelmode2.1.ParallelmodeanditsrequirementsInparallelcomputingmode,eachPEisresponsibleforasubsetoftheimagedataandpossessesitsownmemory.Duringtheencryption,theremaybesomecommunicationbetweenPEs(seeFig.1).Toallowparallelimageencryption,theconventionalCBC-likemodemustbeeliminated.However,thiswillcauseanewproblem,i.e.howtofulfillthediffusionrequirementwithoutsuchmode.Besides,therearisesomeadditionalrequirementsforparallelimageencryption:1.ComputationloadbalancethetotaltimeofaparallelimageencryptionschemeisdeterminedbytheslowestPE,sinceotherPEshavetowaituntilsuchPEfinishesitswork.ThereforeagoodparallelcomputationmodecanbalancethetaskdistributedtoeachPE.2.CommunicationloadbalancethereusuallyexistslotsofcommunicationbetweenPEs.Forthesamereasonasofcomputationload,thecommunicationloadshouldbecarefullybalanced.Fig.2-1.Parallelcomputingmodeforimageencryption.3.CriticalareamanagementWhencomputinginaparallelmode,manyPEsmayreadorwritethesameareaofmemory(i.e.criticalarea)simultaneously,whichoftencausesunexpectedexecutionoftheprogram.Itisthusnecessarytousesome第4页paralleltechniquestomanagethecriticalarea.2.2.AparallelimageencryptionframeworkTofulfilltheaboverequirements,weproposeaparallelimageencryptionframework,whichisafour-stepprocess:Step1:Thewholeimageisdividedintoanumberofblocks.Step2:EachPEisresponsibleforacertainnumberofblocks.Thepixelsinsideablockareencryptedadequatelywitheffectiveconfusionanddiffusionoperations.Step3:Cipher-dataareexchangedviacommunicationbetweenPEstoenlargethediffusionfromablocktoabroaderscope.Step4:Gotostep2untilthecipherimagereachestherequiredlevelofsecurity.Instep2,diffusionisachieved,butonlywithinthesmallscopeofoneblock.Withtheaidofstep3,however,suchdiffusioneffectisbroadened.Notethatfromthecryptographicpointofview,dataexchangeinstep3isessentiallyapermutation.Afterseveraliterationsofsteps2and3,thediffusioneffectisspreadtothewholeimage.Thismeansthatatinychangeinoneplain-imagepixelwillspreadtoasubstantialamountofpixelsinthecipher-image.Tomaketheframeworksufficientlysecure,tworequirementsmustbefulfilled:1.Theencryptionalgorithminstep2shouldbesufficientlysecurewiththecharacteristicofconfusionanddiffusionaswellassensitivitytobothplaintextandkey.2.Thepermutationinstep3mustspreadthelocalchangetothewholeimageinafewroundsofoperations.ThefirstrequirementcanbefulfilledbyacombinationofdifferentcryptographicelementssuchasS-box,Feistel-structure,matrixmultiplicationsandchaosmap,etc.orwecanjustuseaconventionalcryptographicstandardsuchas.AESorIDEA.Thesecondone,however,isanewtopicresultedfromthisframework.Furthermore,suchpermutationshouldhelptoachievethethreeadditionalgoalspresentedinSection2.1.Hence,thepermutationoperationisoneofthefocusesofthispaperandshouldbecarefullystudied.Underthisparallelimageencryptionframework,weproposeanewalgorithmwhichisbasedonfourbasictransformations.Therefore,wewillfirstintroducethosetransformationsbeforedescribingouralgorithm第5页3.Transformations3.1.A-transformationInA-transformation,Astandsforaddition.Itcanbeformallydefinedasfollow:a+b=cwherea,b,cG,G=GF(28),andtheadditionisdefinedasthebitwiseXORoperation.ThetransformationAhasthreefundamentalproperties:(2.1)a+a=0（3-1）(2.2)a+b=b+a（3-2）(2.3)(a+b)+c=a+(b+c)（3-3）3.2.M-transformationInS-transformation,SstandsforS-boxsubstitution.TherearelotsofwaystoconstructanS-box,amongwhichthechaoticapproachisagoodcandidate.Forexample,TangetalpresentedamethodtodesignS-boxbasedondiscretionlogisticmapandBakermap.Followingthiswork,CposedanothermethodtoobtainanS-box,whichleadstoabetterperformance.Theprocessisdescribedasfollows:Step1:SelectaninitialvaluefortheChebyshevmap.TheniteratethemaptogeneratetheinitialS-boxtable.Step2:Pileupthe2Dtabletoa3Done.Step3:Usethediscretized3DBakermaptoshufflethetableformanytimes.Finally,transformthe3Dtablebackto2DtoobtainthedesiredS-box.ExperimentalresultsshowthattheresultantS-boxisidealforcryptographicapplications.TheapproachisalsocalleddynamicasdifferentS-boxesareobtainedwhentheinitialvalueofChebyshevmapischanged.However,forthesakeofsimplicityandperformance,weuseafixedS-box,i.e.theexamplegivenin(seeTable1).4.MASKaparallelimageencryptionscheme4.1.OutlineoftheproposedencryptionschemeEachPEisresponsibleforqconsecutiverows,ormorespecifically,theithPEisresponsibleforrowsfrom(i-1)*qtoi*q-1.Thisalgorithmcanfulfilalltherequirementsforparallelencryption,asanalyzed第6页below.1.DiffusioneffectinthewholeimageAssumethattheoperationsinstep2aresufficientlysecure.Afterstep2,atinychangeoftheplainpixelwilldiffusetothewholerowofNpixels.IfwechoosedaccordingtoEq.(7),itiseasytoprovethatthoseNcipherpixelswillbepermutedtodifferentqrowswiththehelpofK-transformationinstep3.Inthesameway,afteranotherroundoftencrypt,thechangeisspreadtoqrows,andafterthethirdround,thewholecipherimageischanged.Consequently,inourscheme,thesmallestchangeofanysinglepixelwilldiffusetothewholeimagein3rounds.2.BalanceofcommunicationloadIftheparameterdof(6)ischosenas(7),itiseasytoprovethatthedataexchangedbetweentwoPEsareconstant,i.e.equalto1/q2ofthetotalnumberofimagepixels.ForeachPE,thisquantitybecomes(q_1)/q2.Therefore,inourscheme,thecommunicationloadofeachPEisequivalent,andthereisnounbalanceofcommunicationloadforthePEsatall.3.BalanceofcomputationloadThedatatobeencryptedbyeachPEisequallyqrowsofpixels;hencecomputationloadbalanceisachievednaturally.4.CriticalareamanagementInourscheme,undernocircumstanceswouldtwoPEsreadfromorwritetothesamememory.Therefore,wedonotneedtoimposeanycriticalareamanagementtechniqueinourschemeasotherparallelcomputationschemesoftendo.Theabovediscussionshaveshownthattheproposedschemefulfillalltherequirementsforparallelimageencryption,whichismainlyattributedtothechaoticKolmogorovmapandthechoiceofitsparameters.4.2.CipherThecipherismadeupofanumberofrounds.However,beforethefirstround,theimageispre-processedwithaK-transformation.Thenineachround,thetransformationM,A,S,Kiscarriedout,respectively.ThefinalrounddiffersslightlyfromthepreviousroundsinthattheS-transformationisomittedonpurpose.ThetransformationsM,A,SoperateononerowofpixelsbyeachPE,whilethetransformationKoperatesonthewholeimagewhichnecessarilyinvolvescommunicationbetweenPEs.Thecipherisdescribedbythepseudo-codelistedinFig.4-1.Chipher(I)第7页BEGINK(I)Fori=1torounds-1M(I)A(I)S(I)K(I)ENDFig.4-1.Theencryptionprocess4.3.RoundkeygenerationAmongthefourtransformations,onlytransformationAneedsaroundkey.Foran8-bitgreylevelimageofNNpixels,aroundkeycontainingNbytesshouldbegeneratedfortransformationAineachround.Generallyspeaking,theroundkeysshouldbepseudo-randomandkey-sensitive.Fromthispointofview,achaoticmapisagoodalternative.Inourscheme,weusetheskewtentmaptogeneratetherequiredroundkeys.4.4.DecipherItiseasytoobservethatforaciphercomposedofmultiplerounds,thedecipherprocessstillhasthesamesequenceoftransformationsasthecipher.Hence,boththecipheranddeciphersharethesameframework.However,therearestillsomeslightdifferencesbetweentheencryptionanddecryptionprocesses:(1)Theroundkeysusedindecipherisinareversedorderofthatincipher,andthosekeysshouldbefirstappliedthetransformationM.(2)ThetransformationKandSindeciphershouldusetheirinversetransformations.However,sincetransformationKandScanbothbeimplementedbylook-uptableoperations,theirinversetransformationsdifferjustincontentoflook-uptables.Consequently,allabovedifferenceincomputationscanbetranslatedintodifferenceindata.Thesymmetricpropertymakesourschemeveryconcise.Italsoreduceslotsofcodesforacomputersystemimplementingboththecipheranddecipher.Forhardware第8页implementation,thispropertyresultsinareductionofcostforbothdevices.5.ExperimentalresultsInthissection,anexampleisgiventoillustratetheeffectivenessoftheproposedalgorithm.Intheexperiment,agreylevelimageLenaofsize256*256pixels,asshowninFig.4a,ischosenastheplain-image.ThenumberofPEsischosenas4.Thekeyofoursystem,i.e.theinitialstatex0andthesystemparameterlarestoredasfloatingpointnumberwithaprecisionof56-bits.Intheexamplepresentedhere,x0=0.12345678,andl=1.9999.Whentheencryptionprocessiscompleted,thecipher-imageisobtainedandisshowninFig.5-1.and.Typically,weencrypttheplain-imagefor9roundsasrecommended.(a)Theoriginalimage(b)EncryptionimageFig.5-1.Thesimulationimage5.1.HistogramHistogramoftheplain-imageandthecipher-imageisdepictedinFigs5-2(a)and(b),respectively.Thesetwofiguresshowthatthecipher-imagepossessesthecharacteristicofuniformdistributionincontrasttothatoftheplain-image.(a)histogramofplain-image(b)histogramofcipher-image第9页Fig.5-2.HistogramtestInthispaper,weintroducedtheconceptofparallelimageencryptionandpresentedseveralrequirementsforit.Thenaframeworkforparallelimageencryptionwasproposedandanewalgorithmwasdesignedbasedonthisframework.TheproposedalgorithmissuccessfulinaccomplishingalltherequirementsforaparallelimageencryptionalgorithmwiththehelpofdiscretionKolmogorovflowmap.Moreover,boththeexperimentalresultsandtheoreticalanalysesshowthatthealgorithmpossesseshighsecurity.Theproposedalgorithmisalsofast;thereareonlyacoupleofXORoperationsandtablelookupoperationsforeachpixel.Finally,thedecryptionprocessisidenticaltothatofthecipher.Takingintoaccountallthevirtuesmentionedabove,theproposedalgorithmisagoodchoiceforencryptingimagesinaparallelcomputingplatform.5.2.CorrelationanalysisoftwoadjacentpixelsThecorrelationanalysisisperformedbyrandomlyselect1000pairsoftwoadjacentpixelsinvertical,horizontal,anddiagonaldirection,respectively,fromtheplain-imageandthecipheredimage.ThenthecorrelationcoefficientofthepixelpairiscalculatedandtheresultislistedinTable1showsthecorrelationoftwohorizontallyadjacentpixels.Itisevidentthatneighboringpixelsofthecipher-imagehaslittlecorrelation.Table5-1Correlationcoefficientofadjacentpixelsinplain-image原始图像加密图像垂直0.9803-0.0124对角0.9853-0.0273水平0.94200.00746.ConclusionInthispaper,weintroducedtheconceptofparallelimageencryptionandpresentedseveralrequirementsforit.Thenaframeworkforparallelimageencryptionwasproposedandanewalgorithmwasdesignedbasedonthis第10页framework.TheproposedalgorithmissuccessfulinaccomplishingalltherequirementsforaparallelimageencryptionalgorithmwiththehelpofdiscretionKolmogorovflowmap.Moreover,boththeexperimentalresultsandtheoreticalanalysesshowthatthealgorithmpossesseshighsecurity.Theproposedalgorithmisalsofast;thereareonlyacoupleofXORoperationsandtablelookupoperationsforeachpixel.Finally,thedecryptionprocessisidenticaltothatofthecipher.Takingintoaccountallthevirtuesmentionedabove,theproposedalgorithmisagoodchoiceforencryptingimagesinaparallelcomputingplatform.第11页中文翻译稿基于离散混沌映射的图像加密算法最近，针对图像加密提出了多种基于混沌的算法。然而，它们都无法在并行计算环境中有效工作。在本文中，我们提出了一个并行图像加密的框架。基于此框架内，一个使用离散柯尔莫哥洛夫流映射的新算法被提出。它符合所有并行图像加密算法的要求。此外，它是安全、快速的。这些特性使得它是一个很好的基于并行计算平台上的图像加密选择。1.介绍最近几年，通过计算机网络尤其是互联网传输的数字图像有了快速增长。在大多数情况下，传输通道不够安全以防止恶意用户的非法访问。因此，数字图像的安全性和隐私性已成为一个重大问题。许多图像加密方法已经被提出，其中基于混沌的方法是一种很有前途的方向。总的来说，混沌系统具有使其成为密码系统建设中重要组成部分的几个属性：（1）随机性：混沌系统用确定的方法产生长周期、随机的混沌序列。（2）敏感性：初始值或系统参数的微小差异导致混沌序列的巨大变化。（3）易用性：简单的公式可以产生复杂的混沌序列。（4）遍历性：一个混沌状态的变量能够遍历它的相空间里的所有状态，通常这些状态都是均匀分布的。除了上述性能，有些二维（2D）的混沌映射是图像像素置换天生的优良替代者。Pichler和Scharinger提出一种在扩散操作之前使用柯尔莫哥洛夫流映射的图像排列方式。后来，Fridrich将此方法扩展到更广义的方式。陈等人提出基于三维猫映射的图像加密算法。Lian等人提出基于标准映射的另一种算法。其实，这些算法在相同的框架下工作：所有的像素在用密码分组链接模式（CBC）模式下的加密之前首先被用离散混沌映射置换，当前像素密文由以前的像素密文影响。上述过程重复几轮，最后得到加密图像。这个框架可以非常有效的实现整个图像的扩散。但是，它是不适合在并行计算环境中运行。这是因为当前像素的处理无法启动直到前一个像素已加密。即使有多个处理元素（PE），这种计算仍然是在一个串行模式下工作。此限制了其应用平台，因为许多基于第12页FPGA/CPLD或者数字电路的设备可以支持并行处理。随着并行计算技术的应用，加密速度可以大大加快。基于混沌的图像加密方案的另一个缺点是运算速度相对较慢。主要原因是基于混沌的密码通常需要大量的实数乘法和除法运算，计算成本巨大。加密算法在并行处理平台上执行计算效率将大幅提升。在本文中，我们提出了一个并行图像加密的框架。在这样的框架下，我们设计了一个安全快速算法满足并行图像加密所有要求。本文的其余部分安排如下：第2部分介绍了并行的操作模式和其要求。第3节给出加密解密中四个转换的定义和属性。在第4节，加密、解密的过程和密钥调度会加以详细说明。第5和第6节，提供实验结果与理论分析。最后，我们总结本文。2.并行模式2.1.并行模式及其要求在并行计算模式下，每个PE是负责图像数据的一个子集，并拥有自己的内存。在加密时，可能会有一些PE之间的通信（见图1）。要允许并行图像加密，传统CBC样的模式必须予以打破。然而，这将导致新的问题，即如何实现不在这种模式下的扩散要求。此外，也出现了一些额外针对并行图像加密的要求：1.计算负载平衡并行图像加密方案的总时间是由最慢的PE决定，因为其它PE不得不等待直至这个PE完成其工作。因此，良好的并行计算模式可以平衡分配给每个PE的任务。2.通信负载平衡通常存在有大量的PE之间的通信。基于和计算负载同样的原因，通信负载应认真平衡。图1PE之间的通信3.临界区管理在并行模式计算时，许多的PE可以同时读取或写入相同的内存区域（即临界区），第13页这往往会导致意想不到的执行程序。因此，有必要在关键区域使用一些并行技术管理。2.2.并行图像的加密框架为了满足上述要求，我们提出了一个并行图像加密的框架，这是一个四个步骤的过程：步骤1：整个图像被划分成若干块。步骤2：每个PE负责确定数量块。一个区域内的像素可以充分使用有效的混乱和扩散进行操作加密。步骤3：通过PE之间的通信交换加密数据块从块到更大范围的扩散。步骤4：转到第2步，直到加密图像达到所需的安全级别。在第2步，已经实现扩散，但只有一个块的一个小部分。但在第3步的帮助下，这样的扩散效应被扩大。请注意，从加密的角度，在步骤3中的数据交换本质上是一个置换。经过多次迭代步骤2和3，扩散效应蔓延到整个图像。这意味着在一个普通的图像像素的微小变化会波及到了大量的加密图像的像素。为了使框架足够安全，两个要求必须被满足：1.第2步中的加密算法混乱和扩散的特点应该是足够安全的，而且对明文和密钥敏感。2.在步骤3中的置换在几个回合变化中必须从局部蔓延到所有部分。结合不同的加密元素可以满足第一个要求，如S-盒，Feistel结构，矩阵乘法和混沌映射等，或者我们可以只使用一个传统的加密标准，如AES或IDEA。然而，第二个是由于这一框架而产生的一个新课题。此外，这样的置换应有助于实现2.1节中提出的三个附加目标。因此，置换操作是本文的重点之一，应认真研究。这种并行图像加密框架下，我们提出了一种新的算法，这是基于四个基本的转换。因此，我们将描述我们的算法之前，先介绍这些转换。3.转换3.1.A-转换在A转换中，A代表加，能被形式化的定义如下：a+b=c（3-1）a,b,cG,G=GF加法被定义为按位与操作转换A有三个基本性质：(2.1)a+a=0(3-2）(2.2)a+b=b+a(3-3)(2.3)(a+b)+c=a+(b+c)(3-4)第14页3.2.S-转换在S-变换中，“S”代表S盒置换。有很多方法来构造S盒，其中混沌的做法是一个很好的选择。例如，唐等人提出了一个基于离散逻辑映射和Baker映射的设计S-盒的方法。之后，陈等人提出另一种方法来构造S盒，具有更好的性能。该过程描述如下：步骤1：选择一个Chebyshev映射的初始值，然后迭代映射生成初始的S-盒表。步骤2：把二维表加载到三维表上。步骤3：多次应用离散化的三维Baker映射使表格混乱。最后，把三维表转换成二维，以获得所需的S-盒。实验结果表明，由此产生的S-盒是加密应用程序的理想选择。该方法也被称为“动态”的，当Chebyshev映射的初始值被改变时得到不同的S-盒。然而，为了简化和性能，我们使用一个固定的S-盒。4.MASK-一个并行的图像加密体系4.1.加密方案的概要假设的NN图像是由n个PE同时加密的，我们描述并行加密方案如下：1.每个PE负责图像中像素的一些固定行。2.每行的像素分别使用M，A，S进行加密。3.根据置位转型K进一步扩散的所有像素。4.转到第二步进行另一轮的加密，直到密文足够安全。如上所述，在第3步中的置换是非常重要的，因为它有助于满足安全性和速度要求。因此，置换的映射和它的参数，一定要慎重选择。在我们的算法中，是常数向量其长度为q，其中q=N/n。向量的每个元素都等于n：=（n，n，.