2008 08
44(4)
北京师范大学学报(自然科学版)
Journal of Beijing Normal University (Natural Science)
]1
基 于 二 维 混 沌 系 统 的 Hash 函 数 构 造 算 法
倡
姜 楠
1 ,2)
杨德礼
1)
鲍明宇
3)
袁克杰
2)
( 1)大连理工大学系统工程研究所 ,116021 ,大连 ;
2)大连民族学院计算机科学与工程学院 ,116600 ,大连 ;3)东北大学信息学院 ,110004 ,沈阳)
摘要 在分析带有正弦因子的类 Hénon 混沌系统基础上 ,提出了一种混沌 Hash 函数的构造算法 .该算法在二维
Hénon 混沌系统中引入正弦因子进行迭代 ,产生混沌序列 ,然后通过混沌调制方式将明文信息注入均匀分布的混沌轨迹
中 ,以轨迹的量化结果作为明文的 Hash 值 .这种混沌 Hash 函数不仅具有不可逆性 、很好的单向性 ,而且 Hash 结果的每
一比特都与明文和初始条件有着敏感而复杂的非线性关系 .仿真实验与结果分析表明 ,该 Hash 函数满足一定的安全性
要求 ,构造算法简单易于实现 .
关键词 混沌 Hash 函数 ;类 Hénon 映射 ;正弦因子
倡 国家自然科学基金资助项目 (70672092)
收稿日期 :2008‐00‐00
0 引言
在信息时代 ,人们的工作和生活都离不开数据 ,而
网络上数据的完整性时刻都会受到威胁 .为了确保收
到的信息在传输的过程中没有被攻击者插入 、篡改 、删
除 、重排等 ,目前采用的主要技术手段是使用 Hash(散
列)函数 .密码学中 Hash 函数是一种将任意长度的消
息压缩成某一固定长度的消息摘要的函数 .它可用于
数字签名 、消息的完整性检测 、消息的起源认证检测
等 .安全的 Hash 函数应满足单向性 、弱抗碰撞 、强抗
碰撞 .也就是说 ,已知 Hash 函数值 ,进行碰撞性攻击
应具有计算复杂性意义下的不可行性 .
产生单向散列函数的方法很多 ,最典型的有 M Dx
系列和 SHA 系列 .这两大系列算法一直是国际电子
签名及许多其他密码应用领域的关键技术 ,广泛应用
于金融 、证券等电子商务领域 .最近 ,山东大学王小云
教授等人已经设计出对这两类算法快速而有效的碰撞
攻击算法 .研究结果表明 ,从理论上讲 ,基于 M D5 和
S HA‐1 的电子签名可以伪造 ,因此 ,必须重新设计更
安全的单向 Hash 函数 ,以保证电子商务的安全 .
由于上述原因 ,人们在不断探索构造新的 Hash
函数方法 .混沌系统具有初值敏感性 、遍历性等特点 ,
因此构造混沌 Hash 函数成为 Hash 函数的一个新的
研究方向 .文献[1]提出一种基于 Hénon 混沌映射的
单向 Hash 函 数 构 造思 想 .文 献 [2 ]提 出 通 过 采 用
Logistic 混沌映射构造单向散列函数来生成散列值 .
文献[3]提出基于 Logistic 混沌映射构造 Hash 算法
的一种改进算法 .以上 3 种算法的特点是参数空间较
小 ,易于实现穷举攻击 .本文提出用类 Hénon 混沌系
统构造单向散列函数 ,算法利用离散混沌动力系统的
敏感性和遍历性 ,将明文消息注入迭代轨迹中 ,而以迭
代轨迹 的 某 种 粗 粒 化 量 化 作 为 消 息 M 的 散 列 值
H (M) .该算法比文献 [1‐3]中的算法增大了参数空
间 ,具有了更高的安全性 ,而且该算法满足了单向散列
函数的各项性能要求 ,保证了 H (M)值的混乱性和散
布性 ,运行速度快易于软硬件实现 .
2 Hénon 混沌动力系统性质分析
混沌系统对初值和系统参数极端敏感 ,相同的混
沌系统在具有微小差别的初始条件下 ,系统的长期行
为将发生巨大的变化 ,混沌系统长期行为不可预测 ,这
样的特性使得混沌序列加密系统能够抵抗基于频谱分
析和进行穷尽搜索的攻击 .只要系统参数和初始条件
给定 ,混沌现象本身可以重复 ,混沌现象具有伪随机
性 、类噪声性 .由于混沌序列有如此优良的特性 ,从 80
年代末 ,混沌系统开始被应用于保密通信领域 .
2畅1 Hénon 混沌动力系统 Hénon 吸引子是最著名
的简单动力学系统之一 .其动力学方程为
[4]
x
n
+
1
=
1
-
ax
2
n
+
y
n
,
y
n
+
1
=
bx
n
.
(1)
该系统当参数 a = 1畅4 ,b = 0畅3 ,系统成为混沌的 .
一个系统是否混沌可以用它的 Lyapunov 指数是
否大于 0 来衡量 ,Lyapunov 指数可通过映射函数的导
数计算 ,而不仅仅是根据轨道本身计算 ,从而能反映动
力系统的混沌运动 .在一个 n 维的离散动力系统中 ,存
在 n 个 Lyapunov 指数
λ
i
(i = 1 ,… ,n) .如果其中最大