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

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

徐明

(石家庄铁道大学 数理系， 河北 石家庄050043)

摘要：基于有限域上Chebyshev映射的公钥密码系统的安全性直接取决于Chebyshev映射的周期性。利用矩阵变换讨论有限域ZN上Chebyshev映射的周期性问题，并给出一种快速的寻找周期的方法，从而使得对有限域上Cheyshev公钥加密方案的攻击成为可能。

关键词：Chebyshev映射；公钥密码；周期分析；攻击

中图分类号：TP309. 7文献标志码： A

收稿日期：2014-09-01责任编辑:车轩玉DOI:10.13319/j.cnki.sjztddxxbzrb.2015.02.21

作者简介：徐明(1981-)，女，讲师，主要从事密码学的研究。E-mail:xuyong1994xuming@126.com

徐明.有限域上Chebyshev映射的周期性分析[J].石家庄铁道大学学报:自然科学版,2015,28(2):106-110.

0引言

混沌变换所具有的混合、对参数和初值的敏感性等基本特性和密码学的天然关系早在Shannon的经典文章[1]中就已提到，混沌的轨道混合特性对应于传统加密系统的扩散特性，而混沌信号的类随机特性和对系统参数的敏感性则对应于传统加密系统的混乱特性。混沌和密码学之间具有的天然的联系和结构上的某种相似性，启示着人们把混沌应用于密码学领域。自从1989年A.Robert和J.Matthews在文献[2]中明确提出“混沌密码”至今，涌现出了数目众多的混沌密码学的研究成果。

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

1基于有限域上Chebyshev映射的公钥加密方案

1.1有限域ZN上的Chebyshev映射

定义1设n∈Z+，x∈Zn，N为一个大素数，有限域ZN上阶为n的Chebyshev映射记为：Tn(x):ZN→ZN，其定义的迭代形式为

其中，T0(x)=1,T1(x)=x。

1.2基于有限域上Chebyshev映射的公钥加密方案

该方案[3]由3个算法构成，算法描述如下：

(1)密钥生成。为了安全传送，Alice首先采用如下算法生成其加密和解密密钥。①随机选择一个大的整数s;②随机选择一个x∈ZN，然后计算Ts(x)；③Alice公布(x,Ts(x))作为其公开密钥，而把s视为其私有密钥。

(2)加密。Bob为了加密一条消息M。①首先获取Alice经过认证的公开密钥(x,Ts(x))； ②把它要传递的消息表示成一个数字M∈ZN；③随机生成一个大的整数r；④计算Tr(x)，Tr(Ts(x)),以及X=MTr(Ts(x))；⑤将(Tr(x),X)作为密文传递给Alice。

(3)解密。Alice为了恢复明文，须作如下计算。①利用它的私有密钥s计算Ts(Tr(x))=Ts×r(x)=Tr(Ts(x))；②恢复明文M=X/Ts(Tr(x))。

上面算法描述中加密和解密的一致性可以利用Ts(Tr(x))=Tr(Ts(x))，即有限域上Chebyshev映射所具有的半群性质来进行证明。

该公钥密码方案并不安全，如果能找到Chebyshev序列在模N时的周期T，则可以进行下面的攻击[7]。

1.3对基于有限域上Chebyshev映射的公钥加密方案的攻击

设Ts(x)=Tk1+n1T (x)，Tr(x)=Tk2+n2T (x)，则有

Tr(Ts(x))=Trs(x)=T(k1+n1T)(k2+n2T) (x)=Tk1k2+lT (x)=Tk1k2(x)。

本文主要讨论有限域上Chebyshev映射周期的存在性、周期的性质并给出一种快速的寻找周期的算法，从而使得上述攻击方案变得可行。在讨论的过程中，需要用到一些矩阵变换及环面自同构的知识。

2矩阵变换及环面自同构

2.1矩阵变换

定义2一般的模N时的矩阵变换的定义如下

这里Am×m是一个整数矩阵。

文献[8]研究了矩阵变换的周期问题，对矩阵变换在模N时周期是否存在给出了一个充分必要条件。

定理1[8]模N的整数变换矩阵具有周期性的充要条件是|A|与模N互素，此处A是变换的矩阵，|A|是矩阵A的行列式。

陈勇在文献[9]中进一步指出，上述矩阵变换的周期与模数有如下关系：

考虑在域GF(qn)上的矩阵变换

定理2[9]若gcd(detAm×m,q)=1，令k是最小的下标使得Pk≠Pk+1(k≥2)，则Am×m模qn的周期是Pn=qn-kPk(n>k)。这里q是素数，detAm×m表示Am×m的行列式，gcd(.,.)表示最大公因子，Pn,(n=1,2,…)表示Am×m模qn的周期。

定理2告诉我们：随着模数的成倍增加，矩阵的周期也将成倍增加。

推论若gcd(det Am×m,2)=1，令k是最小的下标使得Pk≠Pk+1(k≥2)，则Am×m模2n的周期是Pn=2n-kPk(n>k)。这里detAm×m表示Am×m的行列式，gcd(.,.)表示最大公因子，Pn(n=1,2,…)表示Am×m模2n的周期。

2.2环面自同构

定义3环面自同构是一种特殊的矩阵变换，其表达式如下

文献[10]利用戴德金关于代数整数环的算术基本定理仔细研究了环面自同构的周期轨道，指出：可把有理素数分为三类：惰性(inert)素数、分裂(split)素数和分歧(ramified)素数，在映射(4)中N为素数的情况下，它的周期根据这三类素数，有着不同类型的三种周期轨道，确定方式如下：

(1)若L(d,N)=-1，素数N为惰性素数，变换(4)的周期为N+1的因子；

(2)若L(d,N)=1，素数N为分裂素数，变换(4)的周期为N-1的因子；

(3)若L(d,N)=0，素数N为分歧素数，若k≡2(modN)，变换(4)的周期为N或1；若k≡-2(modN)，变换(4)的周期为2N或2。

其中，L(d,N)是勒让德符号。

3有限域上Chebyshev映射的周期性

3.1有限域上Chebyshev映射周期的存在性

通过研究发现，有限域上的Chebyshev映射与矩阵变换之间具有密切关系，可以通过如下公式把Chebyshev映射(1)改写成矩阵变换的形式

易知，在式(5)中矩阵A的周期恰为由式(5)产生的序列{Tn(x)}的周期加1，因此，为了求序列{Tn(x)}的周期，只需求出式(5)中矩阵A的周期再加1即可。

对于一般的矩阵变换式(2)，容易推出下面的结论：

定理3设矩阵Am×m对于模数N1和N2都存在周期，Am×m模N1的最小正周期记为T1，Am×m模N2的最小正周期记为T2，若N1

证明由条件可知

式中，I表示单位矩阵。

对式(6)左右两边同时模N1，则有

AT2modN2modN1=I modN2modN1，

因为N1

AT2mod N1=ImodN1，

而T1是Am×m模N1的最小正周期，所以必有T1≤T2。证毕。

在基于上述分析的基础上，给出一种寻找Chebyshev映射周期的快速算法。

3.2寻找Chebyshev映射周期T的算法

算法描述：

(2)对于Chebyshev公钥加密方案中指定的模数N，确定整数n，使得2n

若L(d, N)=-1，转(5)；若L(d, N)= 1，转(6)；若L(d, N)= 0，转(7)。

(5)在Pn与Pn+1之间寻找满足t|N+1的整数t，如果满足At=ImodN，则返回T=t。

(6)在Pn与Pn+1之间寻找满足t|N-1的整数t，如果满足At=ImodN，则返回T=t。

3.3算法的有效性分析

4结论

在基于有限域上Chebyshev映射的公钥密码方案中，如果能求得Chebyshev映射产生的序列的周期，明文就能被恢复出来，该密码方案就是不安全的。利用矩阵变换及环面自同构的相关理论讨论了有限域ZN上Chebyshev映射的周期性问题，并给出一种快速的寻找周期的方法，从而使得对有限域上Cheyshev公钥加密方案的攻击成为可能，经过实验分析，可知该算法是快速有效的。

参考文献

[1]ShannonCE.Communicationtheoryofsecrecysystems[J].BellSystemTechnologyJournal, 1949, 28: 656-715.

[2]RobertA,MatthewsJ.Onthederivationofa“chaotic”encryptionalgorithm[J].Cryptologia, 1989,XIII(1):29-42.

[3]KocarevL,MakraduliJ,AmatoP.Public-keyencryptionbasedonChebyshevpolynomials[J].CircuitsSystemsandSignalProcessing, 2005, 24(6):497-517.

[4]ZhangYP,LinX,WangQ,etal.Arapidcryptographyalgorithmbasedonchaosandpublickey[J].Journalofsoftware, 2012, 4(7): 856-860.

[5]YoonE,JeonI.AnefficientandsecureDiffie-HellmankeyagreementprotocolbasedonChebyshevchaoticmap[J].CommunNonlinearSciNumberSimulat. 2011,16:2383-2389.

[6]陈小松，孙一为. 基于Chebyshev多项式的公钥系统[J]，铁道学报,2013, 35(1):77-79.

[7]LiaoXF,ChenF,WongKW.Onthesecurityofpublic-keyalgorithmsbasedonChebyshevpolynomialsoverthefinitefieldZN[J].IEEETransactionsonComputers, 2010, 59(10): 1392-1401.

[8]QiD,ZouJ,HanX.Anewclassofscramblingtransformationanditsapplicationintheimageinformationcovering[J].ScienceinChina(SeriesE), 2000, 3:304-312.

[9]陈勇. 对几类混沌加密系统的分析和改进[D]. 重庆：重庆大学, 2006:96-101.

[10]PercivalI,VivaldiF.Arithmeticalpropertiesofstronglychaoticmotions[J].PhysicaD. , 1987, 25:105-130.

ThePeriodicAnalysisofChebyshevMapOvertheFiniteField

XuMing

(Departmentofmathematicsandphysics,ShijiazhuangTiedaoUniversity,Shijiazhuang050043,China)

Abstract:The security of public-key cryptosystem based on Chebyshev map is determined by the periodicity of Chebyshev map. In this paper, the period problem of Chebyshev map over the finite field ZN is analyzed, and a fast algorithm for period search is proposed, thus making the attack to the Chebyshev public-key cryptosystem possible.

Keywords:Chebyshevmap;public-keycryptosystem;periodicanalysis;attack