有限域上Chebyshev映射的周期性分析

1、第28卷第2期石家庄铁道大学学报(自然科学版)Vol. 28 No. 22015 年 6 月 JOURNAL OF SHIJIAZHUANG T1EDA0 UNIVERSITY (NATURAI, SCIENCE) jun. 2015有限域上Chebyshev映射的周期性分析徐明(石家庄铁道大学数理系河北石家庄05()043)摘要：基于有限域上Chebyshev映射的公钥密码系统的安全性直接取决于Chebyshev映射 的周期性。利用矩阵变换讨论有限域Zn上Chebyshev映射的周期性问题，并给出一种快速的 寻找周期的方法从而使得对有限城上Cheyshev公钥加密方畫的攻击成为可能。关键词:

2、Chebyshev映射；公钥密码；周期分析；攻击中图分类号:TP309. 7 文献标志码：A 文章编号：2095 -0373(2015)02-0106 -050引言混沌变换所具有的混合、对参数和初值的敏感性等基本特性和密码学的天然关系早在Shannon的经 典文章中就已提到，混沌的轨道混合特性对应于传统加密系统的扩散特性，而混沌信号的类随机特性 和对系统参数的敏感性则对应于传统加密系统的混乱特性。混沌和密码学之间具有的天然的联系和结 构上的某种相似性，启示着人们把混沌应用于密码学领域。自从1989年A. Robert和J. Matthews在文 献2中明确提出“混沌密码”至今，涌现出了数目众多

3、的混沌密码学的研究成果。与基于混沌理论的对称密码的研究比较起来，利用混沌来构造公开密钥密码的研究成果就显得相对 较少3心。利用有限域Z”上的Chebyshv映射的半祥性质，文献3提出了基于有限域上Chebyshev映射 的公钥密码系统。但垒当Chebyshev映射产生的序列具有较强的周期性时，基于有限域上Chebyshev 映射的公钥密码系统会存在安全漏洞，容易受到攻击。本文首先介绍基于有限域上Chebyshev映射的 公钥加密方案以及当Chebyshev映射的周期性存在时对该公钥密吗系统的攻击方案。然后利用矩阵变 换讨论有限域Zn上Chebyshev映射的周期性问题，并给出一种快速的寻找周期

4、的方法，从而使得上述攻 击方案成为可能。1基于有限域上Chebyshev映射的公钥加密方案1.1有限域Zn上的Chebyshev映射定义1设灭Z，hG乙，N为一个大素数，有限域Z*上阶为”的Chebyshev映射记为：T”(h)：Zn fZ“，其定义的迭代形式为T(x) = 2工7_| (工)一 T2(x)mod N(1)其中,T0(x) = l, Tt(x)=xe1.2 基于有限域上Chebyshev映射的公钥加密方案该方案由3个算法构成，算法描述如下：(1) 密钥生成。为了安全传送，Alice首先采用如下算法生成其加密和解密密钥。随机选择一个大 的整数打随机选择一个hZn，然后计算T,(x

5、)；Alice公布(作为其公开密钥，而把s视为 其私有密钥。(2) 加密.Rob为了加密一条消息首先获取Alice经过认证的公开密钥Cr.TXr);把它魏 传递的消息表示成一个数字MGZ和随机生成一个大的整数r计算Tr(x),Tr(T4(x),以及X =收積日期：2014 - 09 - 01 责任编辑：车轩玉 DOI.10. 13319/j. enki. sjztddxxbzrb. 2015. 02. 21作者IW介：徐明1981-),女，讲师，主强从挙密码学的研究.E-mailsxuyong 1994xuming 126. com 徐明有限域上Chebyshev映射的周期性分析J.石家庄铁道

6、大学学报：自然科学版.2015.28(2),106-110.第2期徐明：有限域上Chebyshev映射的周期性分析107MTr(T,(x)>；将(Tr(x),X)作为密文传递给Alice。(3) 解密。Alice为了恢复明文，须作如下计算。利用它的私有密钥s计算T,(Tr(x) = T,Xr(x) = Tr(T,(x)；恢复明文 M=X/T,(Tr(x)K上面算法描述中加密和解密的一致性可以利用T,(Tr(x) = Tr(T/x),BP有限域上Chebyshev映 射所具有的半群性质来进行证明。该公钥密码方案并不安全，如果能找到Chebyshev序列在模N时的周期T,则可以进行下面的 攻

7、击。1.3 对基于有限域上Chebyshev映射的公钥加超方案的攻击设 T,(x)二 T*r,iT(x),Tr(x) = 7+寸(工)，则有Tr(T,()=(X)= 7气 +», 7)(*2 njT)(H)=5(工)=°YY其中丿+皿+虽山+心巾八 这样明文就可以恢复出来:= zr0本文主要讨论有限域上Chebyshev映射周期的存在性、周期的性质并给岀一种快速的寻找周期的算 法，从而使得上述攻击方案变得可行。在讨论的过程中，需要用到一些矩阵变换及环面自同构的知识。2矩阵变换及环面自同构2.1矩阵变换(2)定义2 般的模N时的矩阵变换的定义如下% mod N这里是一个整数矩

8、阵。文献8研究了矩阵变换的周期问题对矩阵变换在模N时周期是否存在给出了一个充分必要条件。 定理1。】 模N的僅数变换矩阵具有周期性的充要条件是IA |与模N互素，此处A是变换的矩阵,IAI是矩阵A的行列式。陈勇在文献9中进一步指出，上述矩阵变换的周期与模数有如下关系:考虑在域GF(qn)上的矩阵变换irX inmod q"(3)(4)第2期徐明：有限域上Chebyshev映射的周期性分析107(4)第2期徐明：有限域上Chebyshev映射的周期性分析107定理2 若gcdCdet Am.q) = 1,令怡是最小的下标使得(>2),则和模旷的周期是 这里g是素数，det九“表示A.x.的行列式，gcd(.表示最大公因子，P”， (”=1,2,)表示A”.模g"的周期。定理2告诉我们：随着模数的成倍增加，矩阵的周期也将成倍增加。推论 若gcd(det 4mx2) = 1,令&是最小的下标使得PaHP仏A2),则模2”的周期是 P2kPdn>kK这里det A.x表示A一的行列式,gcd(表示最大公因子>?.(