复合离散混沌动力系统与Hash函数

第26卷 第4期2003年4月

计 算 机 学 报

CH INESE JOURNAL OF COMPUT ERS

V ol. 26No. 4

A pr. 2003

复合离散混沌动力系统与Hash 函数

李红达 冯登国

(中国科学院研究生院信息安全国家重点实验室 北京100039)

摘 要 在对一般的复合离散混沌系统和一个由两个混沌映射构成的特殊复合离散混沌系统进行初步分析的基础上, 建立了一个基于复合离散混沌系统的带秘密密钥的Hash 算法. 算法以迭代初始点作为秘密密钥, 以粗粒化的迭代轨迹作为其Hash 值. 该带秘密密钥的Hash 函数满足一定的安全性要求, 并且算法简单快速. 关键词 Hash 函数; 混沌; 复合混沌系统; 不变分布中图法分类号T P301

Composite Nonlinare Discrete Chaotic Dynamical Systems

and Keyed Hash Functions

LI H ong -Da FENG Deng -Guo

(S tate K e y L aboratory o f Information S ecurity, Grad uate School o f Chinese A c ade my of S ciences, Beij ing 100039)

Abstract T he aim of this paper is to deal w ith com posite descrete chaotic dy nam ical systems and Keyed H ash based on it. The discrete chaotic dy nam ical systems is the iteration of a chaotic map. One

of its characteristics is that the trajectory is sensitive to initial conditions and seems to be random though it is really a determinate process. T he composite discrete chaotic dy nam ical system consists of some chaotic maps, and the iteration process is completely decided by one predetermined sequence called composite sequence. T he trajectory of the composite discrete chaotic dynam ical systems is not only sensitive to its initial conditions, but also relative w ith the composite sequence, which determines the choice of iterated function in the iterating process, so the trajectory is more com plex than that of g eneral discrete chaotic dynamical systems. After analyzing some basic properties of com posite sys -tems, w e study a special one, w hich uses two chaotic maps and has special invariant distribution dens-i ty function, and present a new approach to construct Keyed Hash function, w ith the composite se -quences obtained from the message to be hashed. T he approach uses the initial value of composite dis -crete chaotic dynamical system iteration as the secret key and the coarse -graining trajectory as H ash v alue. Because of the sensitivity and randomicity of the iteration process, there is a very complex non -linear relation between the Hash value and the corresponding message and secret key, and then every bit of the Hash value of the message M is relative w ith every bit of M . Furthermore, the algorithm is very fast and the Hash value is uniformly distributed in the Hash value space. T herefore, the keyed Hash function satisfies security requirem ents.

Keywords H ash function; chaos; composite chaotic systems; invariant disribution

收稿日期:2001-12-28; 修改稿收到日期:2002-05-13. 本课题得到王宽诚博士后工作奖励基金资助. 李红达, 男, 1966年生, 博士, 现从事博士后工作, 主要研究领域为密码学. 冯登国, 男, 1963年生, 研究员, 博士生导师, 主要研究领域为信息安全.

4期李红达等:复合离散混沌动力系统与Hash 函数

461

1 引 言

Hash 函数是从全体消息集合到一个具有固定长度的消息摘要集合的变换, 可分为两类[1]:带秘密密钥的Hash 函数(K -HF) 和不带密钥的H ash 函数. 带密钥的H ash 函数可用于认证、密钥共享和软件保护等方面

[2]

. 本文利用离散混沌系统, 提出一

种直接构造带密钥的Hash 函数的新方法.

离散混沌系统的迭代过程除了对初始条件敏感, 产生复杂的轨迹外, 迭代过程在一定意义上还具有单向性. 离散混沌系统的这一属性在密码学中可以得到很好应用, 如Habutsu 等人[3~

5]

=0, 1, , , k 为子系统.

复合迭代系统的动力行为与复合序列R 有关, 若从某个i 0开始, r i 为常数, 则复合系统退化为单一混沌系统. 一般地, 复合迭代系统保持了所有子迭代系统的混沌特性, 比单个其子系统的行为要复杂得多.

定理1. 若|f c q (x ) |>1, q =0, 1, , , k , 那么对任意复合序列R , 复合系统(1) 是混沌迭代系统.

证明. 设R ={r i }是任意复合序列, {x i }是由初始点x 0得到的迭代序列, 由Lyapunov 指数的定义[7]知

K =n lim log F f c r (x n ) >0, y ]n n

正的Lyapunov 指数意味着混沌, 所以式(1) 是离散混沌系统.

定理2. 设N (q) 表示复合序列R ={r i }前N

个元素中q 的个数, 若N lim =A (q ) , 则复合系y ]N

统(1) 的不变分布密度函数(invariant distribution density, 简称为不变分布) 就是Q (x ) =A (0) Q (1) Q (k ) Q 0(x ) +A 1(x ) +, +A k (x ) (2) 其中Q 0(x ) , Q 1(x ) , , , Q k (x ) 分别是子系统的不变分布密度函数.

证明. 设复合混沌系统的不变分布密度函数为Q (x ) . 根据假设, 我们可以认为P (r i =q ) =A (q ). 为方便, 迭代过程统一表示为x i =F (x i -1) , 那么对任意的x I [0, 1], 有P(F (t) I [0, x ]) =

==

于是

Q (x ) =

=

F (t) I [0, x ]) d x

r =0

r =0k

利用这一性

质提出的一些加密和随机数生成算法. 由多个离散混沌动力系统构造的复合离散混沌系统比一般离散混沌系统具有更好的密码学属性, 它不仅保证了迭代轨迹与初始条件之间的复杂且敏感的非线关系, 而且在迭代过程增加了函数选择的随机性, 这既可保证迭代轨迹的复杂和敏感性, 还可利用复合序列控制它的不变分布以得到均匀分布的迭代轨迹, 这使得复合离散混沌系统在密码学中可以得到更广泛的应用. 本文利用一个特殊的复合离散混沌系统, 构造了一个带秘密密钥的Hash 函数. 复合离散混沌系统对应的复合序列由消息M 产生, 而它的迭代初始点作为Hash 函数的秘密密钥. 算法利用复合离散混沌动力系统的敏感性和迭代过程中迭代函数选择的任意性, 将消息M 巧妙地调制在其迭代轨迹中, 而以迭代轨迹的某种粗粒化作为M 的Hash 值H (M ). 在很广泛的条件下, Hash 值H (M ) 的分布是均匀分布的. 算法保证了带秘密密钥的Hash 函数的安全性完全由秘密密钥的安全性决定, 满足对带秘密密钥的Hash 函数的安全性的要求.

文中的离散混沌动力系统都定义在[0, 1].

E P (f q (t)

k

k

I [0, x ], q =r )

I [0, x ])

r =0

E A (r ) P(f r (t)

-1r

r =0

Q r (t) d t. E A (r ) Q f (t) I [0, x ]

2 复合离散混沌系统

2. 1 复合离散混沌动力系统

定义1. 设x i =f q (x i -1) , q =0, 1, , , k 是一组离散混沌动力系统, 对任意序列为R =(r 1, r 2, , ) I {0, 1, , , k }, 称

x i =f r i (x i-1) , i =1, 2, ,

]

E A (r )

k

d x

f

-1

(r

t ) I [0, x ]

Q r (t ) d t,

由文献[8], 得

Q (x ) =A (0) Q (1) Q (k ) Q 0(x ) +A 1(x ) +, +A k (x ) . 定义2. 设x i =f q (x i -1) , Q =Q q (x ) , q =0, 1, , , k 是一组离散混沌动力系统和对应的不变分布, 若存在向量A =(A (0) >0, A (1) >0, , , A (k ) >0) , A (0) +A (1) +, +A (k ) =1, 使A (0) Q 0(x ) +A (1) Q (k ) Q 1(x ) +, +A k (x ) =1, 则称离散混沌动x i f q i -1) , q =, 1, , , .

(1)

为迭代系统组在序列R 下的复合系统, 记为(f 0,

f k , x i (x i -1, q

462

计 算 机 学 报2003年

由定义可以看出:互补的离散混沌动力系统组, 一定存在R , 使在R 下的复合系统具有均匀分布. 2. 2 一个特殊的复合离散混沌动力系统

我们在[0, 1]构造两个特殊的非线性离散混沌动力系统, 并对其性质进行分析. 在[0, 1]定义函数

f 0(x ) =f 1(x ) =1-|2x -1||2x -1|

(3) (4)

C f (n) =

R 2

Q

[0, 1]

(x -x ) (f (n) (x ) -x ) d x

(6)

对式(3) 及式(4) , x =(x ) , 经适当地变换得C f r (n ) =2

R

, 利用f 33

(n) r (1-x ) =f (r n)

x -3

f

(n) r (

x ) -

d x +3

由此可以得到两个迭代系统x n +1=f r (x n ) (r =0, 1) 及复合迭代系统(f 0(x ) , f 1(x ) , R ). 关于它们的基本性质, 有如下结论.

结论1. 由式(3) 与式(4) 定义的迭代系统满足:(1) x n +1=f r (x n ) (r =0, 1) 是混沌迭代系统. (2) 对应的不变分布密度函数分别是Q 0(x ) =2x 和Q 1(x ) =2-2x.

(3) 它们是互补的.

证明. (1) 由于在(0, 1) 上f c r (x ) >1, 由定理1可得结论.

(2) 同样, 由于在(0, 1) 上f c r (x ) >1, 存在唯一

[7]

的分布密度函数Q r (x ) 满足

¹Q r (x ) E 0.

1

1

x -

f (r n) (x ) -3

n

d x 3

=3C f r (n -1) =

C f r (0) .

(2) 由结论1, 存在R, 使在R 下的复合系统具有均匀分布. 为方便, 一次迭代统一表示为x i =F (x i -1). n 次复合简记为F n (x ) , 则由式(6) 得C (n) =R

Q

[0, 1]

x -

2

F (n) (x ) -

d x 2

.

若设n >0, 由于不论F 是f

或f 1, 总有F (1-x )

º[Q 0r , (1]x ) d x =1.

»Q -r (x ) =P Q r (x ). 其中P 是著名的Perron Frobenius 算子. 由Q r (x ) =Pf r (x ) =Q 0(x ) =

-d x

Q -1Q (t) d t 可得d x f r ([0, x ]) r

Q 0(t) d t +

Q

=F (x ) , 令y 1-x , , 得

(n)

C(n) =-[0, 1]y -2F (y ) -2d y

R

由此可得结论.

Q

,

3 用复合系统构造带秘密密钥的

Hash 函数

带秘密密钥的Hash 函数(K -HF) 在密码学中有广泛的应用, Berson 等人[9]首先提出了K -H F 安全性的一般要求, 给出了K -HF 的一个定义. Bakhtiari 等人[6]认为对于Keyed -H F 来说, Berson 等人给出的定义太强, 他们又给出了一个可满足实际要求的较弱的定义.

定义3. K -H ash 函数H (#) 是一个H ash 函数族{h k :k I K }, 对任意k I K , h k (M ) :E y V m 将消息集合E 中的任意长度的消息M 映射为长度为m 的消息摘要h k (M ) , 若

(1) h k (M ) 是密钥单向函数, 即

¹给定k I K 和M I E , 计算h k (M ) 是容易的.

º在没有k 的情况下, 给定h k (M ) , 求M 是困难的.

»在没有k 的情况下, 给定M, 求h k (M) 是困难的.

(2) h k (M ) 是密钥碰撞自由函数, 即若没有密钥M I M M c 且h k M ) k (1(1-x 2) 12

2

1(1+x 2) 1Q (t) d t

=Q 0

2x +Q 02

x .

不难验证Q 0(x ) =2x 正是满足条件的唯一解. 同理可得Q 1(x ) =2-2x.

式(3) 由式(2) 与定义2易得.

结论2. (1) 两个迭代系统x n +1=f r (x n ) , r =0, 1的迭代序列的自相关函数均满足C f r (n ) =3

n

C f r (0).

(2) 存在二进制系列R , 使他们在R 下的复合

系统的自相关函数满足C (n) =D (0).

证明. (1) 依文献[8], 迭代序列{x n =f (x n -1)}的自相关函数定义为

C f (n ) =2N lim

R y ]N

2

N-1i=0

E (x i -

x ) (x i +n - x ) (5)

其中x 与R 分别是它的均值和方差. 由Birkhoff 遍

[8],

4期李红达等:复合离散混沌动力系统与Hash 函数

463

是困难的.

(3) 给定一组M I E 及对应的h k (M ) , 求出其它消息M c 的h k (M c ) 或其它摘要h k (M c ) 的消息M c 是困难的. 则称H (#) 为安全的带秘密密钥的单向Hash 函数(Secure Keyed One -Way Hash Func -tion, SKOWHF).

Bakhtiari 等人指出, K -HF 应满足如下的安全性要求:

(1) 满足定义3;

(2) 秘密密钥的长度应不小于128bits , 以防止密钥穷尽搜索攻击;

(3) 消息的Hash 值的长度也应不小于128bits , 以防止生日攻击;

(4) 具有均匀分布的H ash 值, 抵御统计分析. 带秘密密钥的Ha sh 函数一般由已有的加密算法或Hash 函数来构造, 我们利用由式(3) 与式(4) 构成的复合系统(f 0(x ) , f 1(x ), R ) 建立一个带秘密密钥的

Hash 函数, 使其满足安全性要求(1) ~(4).

不失一般性, 假设消息M 是二进制序列, H ash 值的长度为N , 为抵御生日攻击, 要求N E 128. 若M 的长度|M |不是N 的整数倍, 可以给它连接适当的序列使其满足要求. 下面设|M |=sN , s E 1. 将M 按长度N 分组, M =(M 1, M 2, , , M s ) , 记M i =m i m i , m i . 取长为N 的0序列H 0为初始向量. 算法的基本思想是:给定密钥x 0, 即复合迭代系统的迭代初始点, 以H 0ÝM 1作为复合序列, 迭代得到复合混沌系统的轨迹{y i }1, 将其转化为一个二进制序列作为M 1的Hash 值H 1, 然后再以x 1=y N 作为迭代的初值, 以H 1ÝM 2作为复合序列, 得到H 2. 重复上述过程至消息结束, 得到M 的Hash 值H s . H ash 算法一般可以描述为(如图1)

(H i , x i ) =F (x i -1, H i-1ÝM i ) , i =1, 2, , , s;

H (M ) =H s

.

N

1

2

N

图1 H ash 算法

这里F (#, #) 表示求某一消息块的Hash 值的过程, 也是复合混沌系统的迭代过程. 在这个过程中, 需要一个将轨迹{y i }1转化为二进制序列的变换, 我们定义这个变换为T r (x ) =r

x mod 2, r 是自然数. F 实际上是一个由复合混沌系统列出的布尔函数, 可以描述如下:

(1) 从i =1到i =s, 完成下列各步:¹y 0=x i -1.

ºq =H j i -1Ým j i , y j =f q (y j -1) , H j i =T r (y j ) , j =1, 2, , , N .

»y 0=y N .

¼q =H j i , y j =f q (y j -1) , H j i =T r (y j ) , j =1, 2, , , N .

2N

(2) H i =H 1i H i , H i , x i =y N .

由于复合混沌系统的敏感性和迭代过程的随机性, H ash 值与消息有着复杂而敏感性的非线性关系, 而且两次迭代使Hash 值的任一bit 与消息的所有, N

引起H ash 值H i 的极大变化. 若密钥x 0发生微小改变, 复合混沌系统迭代过程将使差异不断放大和扩散, 最终会得到完全不同的H ash 值. 基于复合混沌系统的Keyed -HF 的安全性完全依赖于密钥, 即迭代的初始点x 0, 复合系统迭代轨迹的复杂性可以保证算法满足定义2. 对H (M ) 在GF (2) (N) 上的均匀分布性, 有如下定理.

定理3. 若复合序列R 满足P (r i =1) =,

2

则(f 0(x ) , f 1(x ) , R ) 的迭代轨迹{x i }的离散化轨迹{T r (x i ) }的各bit 为独立同分布, 即对任意的二进制序列P (a 1, a 2, , , a n ) , 有

p {T (x i ) =a i , i =1, 2, , , n}=2n . 证明. 为叙述方便, n 次复合迭代简记为x n

=F (n) (x 0) . 对r =1, 若n =1, P (s j 1=a 1) =P (s j 1

=a 1, r 1=0) +P(s j 1=a 1, r 1=1) =. 现假设n =

2

k 时成立, 当n =k +1时,

(=i , 1, , , , k 1)

464

计 算 机 学 报2003年

=p (s i =a i , i =1, 2, , , k +1, r i+1=0) +p (s i =a i , i =1, 2, , , k +1, r i+1=1) . 记E (n , R k ) ={x 0:s i =a i , i =1, 2, , , k }, 其中R k =(r 1, r 2, , , r k ) , E (0) ={x 0:T j (F (n) (x ) ) }, 则

p (s i =a i , i =1, 2, , , k +1) =L (E (n, R k ) H E (0) ) +2L (E (n, R k ) H ([0, 1]-E (0) ) ) 2=L (E (n, R k ) ) 2=p (s i =a i , i =1, 2, , , k ) . 2

由此得结论. 对任意的r , 可类似证明.

对任意的二元序列的消息M, 可以认为0与1的分布是均匀的, 故对全体消息集合E , Hash 值H (M ) 具有均匀分布, 这可以有效地抵抗统计攻击.

关系可以有效地抵御线性分析. 由于具有很大的密钥空间, 可以抵抗密钥的强力攻击.

参

1

考文献

Feng Deng -Guo, Pei Ding -Yi. Introduction to Cryptography. Be-i ji ng:Scien ce Press, 1999(in Chines e)

(冯登国, 裴定一. 密码学导引. 北京:科学出版社, 1999)

23

Bakhti ari S, Safav-i Naini R, Pieprzyk J. Keyed Hash functions. Lecture Notes i n Com puter Science, 1996, 1029:201~204H abutsu T , Nishio Y, Sasase I, M ori S. A secret key cryptsystem by iterating a chaotic map. In:Proceedings of EOROCRYPT c 91, Berlin, 1991. 127~136

4Goce Jaki moski, Lj upc %o Kocarev. Chaos and cryptography:Block encrypti on ciphers based on chaotic maps. IEEE Trans Circuits System I, 2001, 48(2) :163~169

5

%o Kocarev. Chaos Toni S tojanovski, Lj upc -based random number

generators ) ) ) part I:Analysis. IEEE T ransactions on Circuits System I, 2001, 48(3) :281~2886

Toni Stoj anovski, Johnny Pi hl, Ljupc %o Kocarev. Chaos -based ran -dom number generators ) ) ) part II:Practical realization. IEE E Transactions on Circui ts System I, 2001, 48(3) :382~3857

Wu Xiang -Xing, Chen Zhong et al . An Introductiot to Chaos. Shanghai :Shanghai Sci ence and T echnology Press, 2001(in Ch-i nese)

(吴祥兴, 陈 忠等. 混沌学导论. 上海:上海科学技术文献出版社, 2001) 8

Baranovsky A, Daems D. Desi gn of one -dimensional chaoti c maps w i th prescribed statistical properties. International Journal Bifurca -tion and Chaos, 1995, 5(6) :1585~15989

Berson T A, Gong L. Secure, keyed, and colli sionful Hash func -tions . T echnical Report, SRI International Laboratory, M enlo Park, Californ i a, 199310

Parry W. Topic in Ergodic Th eory. London:Cambridge Univers -i ty Press, 1981. 25~

26

4 结 论

基于离散混沌系统的带秘密密钥的H ash 函数的算法简单、速度快, 而且算法利用了离散混沌系统

对初始条件的敏感性和迭代过程的单向性, 使Hash 值的每个bit 都与消息M 有关, 并且这种关系对消息M 及x 0的微小改变很敏感. 实验结果表明:当消息的1bit 发生变化时, 它们的Hash 值平均有近一半的bit 位发生了变化; 而当初始点(密钥) 在精度允许的范围内发生微小的改变时, 由于迭代过程将使初始值之间的差异不断放大, 经过第一轮的迭代将会使差异大到足以影响H ash 值, 因此, 对同一个消息用不同的密钥, 将得到完全不同的H ash 值. Hash 值与消息之间的这种复杂而敏感性的非线性

LI Hong -Da , male, born in 1966, Ph. D. . His research interests are in cryp -tology.

FENG Deng -Guo , male, born in 1963, r esearcher, P h. D. supervisor. His research interests focus on information secur ity.