[doc格式] 一种基于混沌的带密钥hash函数的碰撞问题及分析

[doc格式] 一种基于混沌的带密钥hash函数的碰撞问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 及分析 一种基于混沌的带密钥hash函数的碰撞问 题及分析 第57卷第5期2008年5月 1000..3290/2008/57(05)/2737..06 物理 ACTAPHYSICASINICA Vo1.57,No.5,May,2008 ?2008Chin.Phys.Soc. 一 种基于混沌的带密钥hash函数的碰撞问题及分析* 王继志王美琴王英龙 1)(山东省计算中心,济南250014) 2)(山东大学密码技术与信息安全教育部重点实验室,济南250100) (2007年6月26日收到;2007年9月17日收到修改稿) 指出了一类基于混沌映射构造带密钥单向hash函数算法的碰撞问题,并对其产生的机理进行了初步分析,给 出了数字化混沌序列非奇异的定义,证明了数字化混沌序列非奇异的充要条件,并分析了变参数离散混沌动力系 统数字化后序列的周期性.分析结果表明这类算法产生碰撞的原因是其对混沌映射的数字化导致混沌序列的奇异 性,因此必须谨慎选择混沌映射的数字化方法以保证混沌序列的非 奇异性. 关键词:混沌,带密钥散列函数,碰撞,非奇异性 PACC:0545 1.引言 混沌是一种动力学行为,混沌现象表面上看起 来是随机的,不可预测的,但实际上却是按照严格而 且常常是简单的规律发生变化的一种自然现象,可 以利用简单的数学表达式产生复杂的混沌行为.因 此,混沌的这种性质在现代密码学中具有重要的应 用价值.目前,已有很多文献提出了基于混沌映射构 造带密钥的单向hash函数的算法?.其中文献[1] 提出了一种基于混沌神经网络的带密钥的单向 Hash函数构造方法.该方法通过使用以混沌分段线 性函数作为输出函数的神经网络和基于时空混沌的 密钥生成函数实现明文和密钥信息的混淆和扩散. 然而,通过仔细考察,发现该算法比较容易构造明文 对,使得明文对的hash值在同一密钥下发生碰撞, 不满足hash函数的抗碰撞性;也比较容易构造密钥 对,使得对同一明文的hash值发生碰撞,不满足对 密钥的敏感性. 本文首先指出该算法所存在的问题,对产生该 问题的原因进行了初步分析,给出了混沌序列非奇 异的定义,分析结果表明保证数字化混沌序列的非 奇异性是避免该问题产生的方法. *山东省自然科学基金(批准号:Y2006A27)资助的课题 2.碰撞问题 2.1.原算法概述 文献[1]中的算法将256位的明文块映射为128 位的Hash值,其中密钥为128位.映射采用混沌神 经网络,具有输入和输出两层结构,输入层具有8个 节点,输出层具有4个节点.具体算法如下: 1)256位的明文块分成32个8比特的数据,其 中每4个8比特的数据为一组,记为P...P...P P0.3…P7,0 P7,l P7,2 P7,3共8组. 2)每组4个8比特数据PP?Pf.2Pf.30, 1,…,7,通过固定权值[1/2.1/21/21/2],即 P=P.0 /2.+P ,1 /2+Pf.2 /224+P ..3 /2 转化为[0,1]之问的小数. 3)将Pi=0,1,…,7分别输入8个输入层节 点,其节点的传递函数为 f(,Q) /Q,0?<Q, (—Q)/(o.5一Q),Q?<0.5 (1一Q—)/(o.5一Q),0.5?<1一Q, (1一)/Q,1一Q??1, (1) 物理57卷 其中p取1/3,迭代次数取40. 4)128位密钥分为4个32位整数,除以2量化 为[0,1]之间的小数后.后:后后,按下式进行迭代: 1(+1)=(1一,)g((i))+,g((i)), :(i+1)=(1一,)g(:(i))+,g(.(i)), 3(+1)=(1一,)g(3())+,g(2(i)), (i+1)=(1一,)g(())+,g(3(i)), 其中,=1/3,g为Logistic映射(+1)=4x(i)(1 一 (i)). 连续取10个每隔30步迭代的系统状态值,其 中前8个4维状态值作为输入层神经元到输出层神 经元的连接权值,其后的2个4维状态值分别作 为阈值矢量@和控制参数矢量p. 5)输出层4个节点的输出按下式计算: c=f(rood(wU+0,1),Q), 其中,U为输入层的输出,迭代40次. 得到的hash值相等. (2)式很容易满足,例如,..=64,..=.::.= 0,b.=192,b.=b:=b:0,满足(2)式. 2.3.构造密钥对碰撞 首先考察Logistic映射的性质. 对于映射g()=4x(1一),显然有 命题3g()=g当0?<Q时,显然1一IQ<1一?1, 所以 f(,Q)=x/Q, f(1一,Q)=(1一(1一))/Q=x/Q, 因此 f(,Q)=f(1一,Q). 当Q?<0.5,0.5?<1一Q,1一Q?<1 时,同样可证f(,Q)=f(1一,Q). 因此命题1得证. 命题2若有两组4个8比特的数据口.口.口: 口3和boblb2b3,满足 O,o/2.+口1/2+0,2/224+0,3/23 =1一(6o/2+61/2+62/224+63/23),(2) 则明文对口0口1口2口3P1,oP1.1Pl,2P1, 3…P7.o P7,1 P7. 2 P7. 3和bob】b2b3P】10P】IJP】I2P】I3…P7,oP7,】 P.: P. 在同一密钥K下得到的hash值相等. 该命题的证明是显然的.根据命题1,两个明文 在步骤3)中得到的一次迭代值是完全相同的,因此 40次迭代值也是完全相同的,由于输出层的输出只 与密钥,输入层的输出有关,显然在同一密钥K下 从上文的分析可以看出,原算法不满足抗碰撞 性和密钥敏感性,主要是在从二进制数向小数的转 换过程中,由于混沌映射的对称性,导致不同的二进 制数映射为同一小数,从而产生hash值的碰撞. 下面推广到一般情况,分析该问题是如何产生 的以及如何避免. 3.1.前提条件 下面主要研究形如(3)式的一维离散混沌系统 +1=f(,),n=0,1,2,…, ?R且?[口,b],(3) 其中,为参数,R为实数集. 如果在迭代过程中,参数恒定不变,则称(3) 式为定参数离散混沌动力系统;否则,称(3)式为变 参数离散混沌动力系统. 在基于(3)式构造密码算法时,需要将明文的二 进制数转换为有限精度的实数,反过来说也就是离 散混沌系统的数字化,以生成混沌序列.一般的方法 是采用线性变换,如用mbit二进制数表示实数, 即在区间[.,b]上等间隔的选择2个离散点,分别 用0,1,2,…,2一1表示.例如,用0表示口,用1表 示口+(b一口)/2,用2表示口+2(b一口)/2,以此 类推,用2一1表示口+(2一1)(b一口)/2.若用 5期王继志等:一种基于t昆沌的带密钥hash函数的碰撞问题及分析 Y表示数字化后的数值,则 =0+Y(b一0)/2.(4) 将(4)式代入(3)式得 Y=g(Y,/z) : [+,)一.)],(5 其中,[]表示取整运算. 由于Y,Y+.是mbit二进制整数,而(5)式右 边一般是浮点运算,因此计算的最后结果需要取整 (如果直接用浮点数进行运算,取有限精度就相当于 这里的取整运算). 观察(5)式可以看出,其产生序列的方法与一级 q元反馈移位寄存器的结构是类似的,如图1所示. 图1一级反馈移位寄存器 下面,以反馈移位寄存器的观点来考察(5)式 3.2.非奇异性 对于数字化定参数离散混沌动力系统 Y+l=g(Y,/z),n=0,1,2,…, Y?{0,1,2,…,2一1},(6) 从任何一个初值Y.出发,通过(6)式的迭代运算,可 以得到序列Y.,Y.,Y,…,因此至多迭代2次, 必有 yf+Yi? 这样,从Yi到Y+?就构成了一个循环序列,其周期 为k.如果把Y的每一个取值看作一个状态,可得到 如图2所示的状态转移图. 图2状态转移 从图2可以看出,文献[1]中算法之所以存在碰 撞问题,就是因为它所产生的数字化混沌序列的状 态图存在分枝点,即对于Y,存在两个先导节点Y 和Y+,使得 g(Y一.,tz)=g(Y+一.,tz), 从而导致最后的hash值存在碰撞. 显然,对于某一离散混沌映射来说,其全部状态 转移可能是由几个类似图2的状态转移图构成的. 那么是否存在状态转移是由有限个彼此没有公共顶 点的圈所构成的情况,也就是说状态图中不存在分 枝节点;如果存在,满足这一要求的充要条件是什 么,下面来讨论这一问题. 首先类似于反馈移位寄存器非奇异的定义], 给出离散混沌映射数字化序列非奇异的定义. 定义1如果一个离散混沌映射数字化后的序 列状态图是由有限个彼此没有公共顶点的圈所构 成,则称此离散混沌映射数字化后的序列是非奇异 的,否则称之为奇异的. 定理1一个离散混沌映射数字化后序列非奇 异的充要条件是对于?Y,,Y?{0,1,2,…,2一 1},定参数数字化离散混沌映射g(,),方程 g(,/z)一g(Y,/z)=0 无解. 证明必要性. 根据非奇异的定义,状态图是由有限个圈构成 的,即状态图不存在分枝点,也就是说不存在两个点 ,Y,且?Y,使得g(,/z)=g(Y,/z),即方程 g(,/z)一g(Y,/z)=0无解. 充分性. 由于方程g(,/z)一g(Y,/z)=0无解,也就是 说不存在两个不同的离散点,使得他们映射到同一 个点,也就是状态图中不存在分枝节点,所以序列是 非奇异的. 证毕. 推论1如果一个离散混沌映射f(,/z)数字 化时,所取的离散点中存在,,i?,使得(, /z)=f(,,tz),则该离散混沌映射数字化后是奇 异的. 该推论的证明是显然的.因为若存在,,i? J.,使得f(,tz)=f(,tz),则必有数字化后的函数 g(,tz)=g(X,),因此该函数产生的序列是奇.itz 异的. 再回到文献[1]的算法.根据推论1,显然存在 不相等的离散点,使得神经元的传递函数f(,Q)相 等,即该离散混沌映射数字化后是奇异的.因此可以 2740物理57卷 把数字化混沌序列是否奇异作为一个判定条件,即 若数字化混沌序列是奇异的,则比较容易构造不同 的明文,使得它们的迭代值相等. 下面以一个简单的分段线性映射为例来说明如 何选择离散点以保证数字化混沌序列的非奇异性. 分段线性映射 +=f(,)= 取参数=2,?[一1,1] 结果,可以看出在区间[一1 发生. <0, ?0, (7) 3所示的迭代 显的混沌现象 下面对该离散混沌映射进行数字化. 首先采用线性变换. 假设用7bit二进制数表示%,用Y表示,则Y ?{0,1,2,…,127},也就是说需要在区间[一l,1]之 间选择128个离散的点.如果按下式等间隔进行选 取: =2y/128—1, 则存在Y=1和Y=127,使得 f(2×1/128—1,2)=1+2(2×1/128—1) =一124/128, f(2×127/128—1,2)=1—2(2×127/128—1) =一124/128, 即 f(2x1/128—1,2)=,(2x127/128—1,2). 根据推论1,可得该映射数字化后的序列是奇异的. 因此该方法是不可行的. 图3分段线性映射 由于该函数是关于=0对称的,下面给出另 外一种取点的方法: :一1,y<64,128一一’,u-r’ = -l’yn?64 该方法采用分段线性变换,避开了使,(,)= f(,)的点,因此是可行的.如图4所示,(b)是(a) 的局部放大. 图4数字化映射取点 根据(5)式,由于最后结果要进行取整运算,如 果只是在选取离散点时避开了使厂(,)=f(, )的点,仍不能保证数字化后的序列是非奇异的. 例如,如图4(b)所示的,Y两点,如果这两点的函 数值之差小于(b—o)/2=1/64,则取整运算后,这 两个点可能取整为同一个整数,导致序列奇异.因此 要保证类似这两点的函数值之差大于选取离散点的 间隔距离,才能保证取整运算后,取整为不同的整 数,即需满足 l厂’(,)l?2, 其中.厂’表示.厂的一阶导数. 那么对于导数的绝对值小于2的分段线性映射 函数,是不.是数字化后的序列肯定是奇异的? 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 是否定的,因为可以选择. 厂的多次迭代作为一次迭 代.例如,假设If’(,)I=k<2,取n次迭代作为 一 次迭代,即 ““图明 如有 +一到中 ?? 得=1 5期王继志等:一种基于混沌的带密钥hash函数的碰撞问题及分析 f(f(…f(f()))),—————一 求其一阶导数 厂(/(…f()))?厂(f(…f()))?…?厂(1l,)=,—— n个 对于>1,则总可以找到一个n,使得?2. 但是在具体的数字计算中发现,分段线性映射 函数本身满足该条件,多次迭代作为一次迭代,可能 会导致原先不相等的离散点反而相等,情况比较 复杂. 另外,对于不是分段线性的情况,如抛物线映射 + = 1—4(一0.5),El0,1J, 在=0.5时,无论迭代多少次,其一阶导数都等于 0,这时可以采用不等间隔取点,即斜率厂大的地方 取的间隔小,斜率厂小的地方取的间隔大,只要函 数值的区间距离大于1/厂个选取离散点的区间距 离,仍可以保证取整运算后不会取整为同一整数. 根据上述结论,(7)式采用(8)式的取点方法,经 计算(最后取整运算采用四舍五入)可得,其状态图 是由2个周期为36的圈,1个周期为35的圈,1个 周期为18的圈,1个周期为3的圈,共5个圈构成 的,如下: 1)0,1,3,7,15,31,63,127,2,5,11,23,47,95, 66,124,8,17,35,71,114,28,57,115,26,53,107,42, 85,86,84,88,80,96,64(周期35). 2)4,9,19,39,79,98,60,121,14,29,59,119,18, 37,75,106,44,89,78,100,56,113,30,61,123,10,21, 43,87,82,92,72,112,32,65,126(周期36). 3)6,13,27,55,111,34,69,118,20,41,83,90,76, 104,48,97,62,125(周期18). 4)12,25,51,103,50,101,54,109,38,77,102,52, 105,46,93,70,116,24,49,99,58,117,22,45,91,74, 108,40,81,94,68,120,16,33,67,122(周期36). 5)36,73,110(周期3). 这说明上述方法是有效的,数字化后的混沌序 列是非奇异的. 然而上述方法仍然可能存在短周期现象,这对 密码算法来说是有害的,最好是能生成全字长的 序列,以避免算法陷入到短周期.如何生成序列 还需要进一步研究. 3.3.变参数离散混沌映射的周期 文献[1]中的算法是将明文作为迭代初值,密钥 作为控制参数,而文献[5]中的算法采用相反的做 法,即将密钥作为迭代初值,明文作为控制参数,因 此有必要考察变参数离散混沌映射的周期性,以防 止混沌序列陷入到短周期序列中. 考察下述变参数离散混沌动力系统: +1=f(,),n=0,1,2,… +=g(), , 如果是周期为P的序列,对于任意,定参数 离散混沌序列+=f(,)均为非奇异的,周期 均为P,且对于任意两个参数,其数字化序列皆不 是移位等价的,则有下述定理. 定理2根据上述前提条件,对于变参数离散 混沌动力系统数字化后序列的周期P,有 P=mP,m为自然数且1?m?Pf. 证明对于变参数离散混沌映射可以转化为 P个定参数离散混沌映射函数,如下式所示: +1=f(,0),nmodP=0, +1=f(,1),nmodP=1, +1=f(,2),nmodP=2, +1=f(,P一1),nmodPg=Pg一1. 下面先证P=mP,m为自然数.用反证法. 假设PmodP=尼,尼?O,则不失一般性 0=P’ 1P+1’ 所以 f(.,.)=f(,)=f(.,). 由于?0,.?,上式与条件中对于任意两个参 数,其数字化序列皆不是移位等价矛盾. 所以=0. 下面证明m的范围为1?m?P. m?1是显然的. 对于任意,定参数离散混沌序列+= /(,)只有P个状态,那么从初值.出发,最 理想的情况就是把P个状态遍历一遍,再回到., 也就是m=P. 所以1?m?Pf. 证毕. 从定理2可以看出,变参数混沌序列的周期主 要是由控制参数序列的周期性决定的,这表明应用 该方法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 密码算法时,关键的是参数序列的迭代 函数,而不是初始状态的迭代函数. 物理 4.结论 本文对文献[1]中的算法进行了仔细地考察,指 出其中存在的碰撞问题,并从一般情况出发,得出了 一 个判定条件,即若数字化后的混沌序列是奇异的, 则比较容易构造明文对,使得它们的迭代值相同. 同时对定参数混沌映射的数字化及变参数混沌 映射的周期进行了讨论.对于定参数离散混沌映射, 其数字化时需要注意两个问题:一是要避开使得映 射函数值相等的离散点;一是所选取的离散点中函 数值接近的任意两个点,取整运算后不能取整为同 一 个整数,如果映射函数不满足这个条件,可以把多 次迭代作为一次迭代,使得该条件满足.但也可能出 现映射函数本身满足该条件,多次迭代作为一次迭 代反而不满足该条件,情况比较复杂,需要具体 分析. 对于变参数离散混沌映射函数,其数字化后的 序列周期,主要是由参数序列的迭代周期决定的,因 此在设计密码算法时要重点关注于参数序列迭代函 数的选取. LiuGJ,ShanL,DaiYW,SunJS,WangZQ2006ActaPhys. Sin.555688(inChinese)[刘光杰,单梁,戴跃伟,孙金生,王 执铨2006物理555688] LiuJD,YuYM2007ActaPhys.Sin.561297(inChinese)【刘 建东,余有明2007物理561297] WeiPC,ZhangW,LiaoXF,YangHQ2006JournalOn Conunun/cations27(9)27(inChinese)[韦鹏程,张伟,廖晓峰, 杨华千2006通信27(9)27] [4]LiHD,FengDG2003ChineseJournalofComputer2646O(in ChineSe)[李红达,冯登国2003计算机26460] [5]ShengLY,IAGQ,IAzw2006ActaP.Sin.555700(in Chinese)[盛利元,李更强,李志炜2006物理555700] [6]XiaoGZ,LiangCJ,WangYM1985Thetheoryandapplications ofpseudo-randomsequence(Beliing:Nationaldefenceindustry press)39(inChinese)[肖国镇,梁传甲,王育民1985伪随机序 列及其应用(北京:国防工业出版社)第39页] Thecollisionofonekeyedhashfunctionbasedon chaoticmapandanalysis WangJi.Zhi?WangMei.Qin2)WangYing.Long 1)(ShandongComputerScienceCenter,J/nan250014,China) 2)(KeyLaboratoryofCryptography&InformationSecurityMinistryofEducation,J/nan250100,China) (Received26June2007;revisedmanuscriptreceived17September2007) Abstract Thecollisionofakeyedhashfunctionbasedonchaoticmapispointedout.Itsprincipleisanalyzedintheory.The definitionofthenonsingularityispresentedbasedonanalyzingdigitaldiscretechaoticsequence.ThenecessaryandSufficient conditionsforthenonsingularityisdeduced.Theperiodofdigitaldiscretechaoticsequencewithvariableparameterisdiscussed. Theresultshowsthatthesingulartiyofchaoticsequenceleadstothecollisionofthehashfunction.Sothedigitalmethodof chaoticmapmustbechosencarefullytoensurethenonsingularityofchaoticsequence. Keywords:chaos,keyedhashfunction,collision,nonsingularity PACC:0545 *ProjectsupportedbytheNaturalScienceFoundationofShangdongPro~nee,China(GrantNo.Y2006A27)