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

徐明

(石家莊鐵道大學(xué) 數(shù)理系， 河北 石家莊050043)

摘要：基于有限域上Chebyshev映射的公鑰密碼系統(tǒng)的安全性直接取決于Chebyshev映射的周期性。利用矩陣變換討論有限域ZN上Chebyshev映射的周期性問題，并給出一種快速的尋找周期的方法，從而使得對有限域上Cheyshev公鑰加密方案的攻擊成為可能。

關(guān)鍵詞：Chebyshev映射；公鑰密碼；周期分析；攻擊

中圖分類號：TP309. 7文獻(xiàn)標(biāo)志碼： A

收稿日期：2014-09-01責(zé)任編輯:車軒玉DOI:10.13319/j.cnki.sjztddxxbzrb.2015.02.21

作者簡介：徐明(1981-)，女，講師，主要從事密碼學(xué)的研究。E-mail:xuyong1994xuming@126.com

徐明.有限域上Chebyshev映射的周期性分析[J].石家莊鐵道大學(xué)學(xué)報:自然科學(xué)版,2015,28(2):106-110.

0引言

混沌變換所具有的混合、對參數(shù)和初值的敏感性等基本特性和密碼學(xué)的天然關(guān)系早在Shannon的經(jīng)典文章[1]中就已提到，混沌的軌道混合特性對應(yīng)于傳統(tǒng)加密系統(tǒng)的擴(kuò)散特性，而混沌信號的類隨機(jī)特性和對系統(tǒng)參數(shù)的敏感性則對應(yīng)于傳統(tǒng)加密系統(tǒng)的混亂特性?；煦绾兔艽a學(xué)之間具有的天然的聯(lián)系和結(jié)構(gòu)上的某種相似性，啟示著人們把混沌應(yīng)用于密碼學(xué)領(lǐng)域。自從1989年A.Robert和J.Matthews在文獻(xiàn)[2]中明確提出“混沌密碼”至今，涌現(xiàn)出了數(shù)目眾多的混沌密碼學(xué)的研究成果。

與基于混沌理論的對稱密碼的研究比較起來，利用混沌來構(gòu)造公開密鑰密碼的研究成果就顯得相對較少[3-6]。利用有限域ZN上的Chebyshv映射的半群性質(zhì)，文獻(xiàn)[3]提出了基于有限域上Chebyshev映射的公鑰密碼系統(tǒng)。但是，當(dāng)Chebyshev映射產(chǎn)生的序列具有較強(qiáng)的周期性時，基于有限域上Chebyshev映射的公鑰密碼系統(tǒng)會存在安全漏洞，容易受到攻擊[7]。本文首先介紹基于有限域上Chebyshev映射的公鑰加密方案以及當(dāng)Chebyshev映射的周期性存在時對該公鑰密碼系統(tǒng)的攻擊方案。然后利用矩陣變換討論有限域ZN上Chebyshev映射的周期性問題，并給出一種快速的尋找周期的方法，從而使得上述攻擊方案成為可能。

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

1.1有限域ZN上的Chebyshev映射

定義1設(shè)n∈Z+，x∈Zn，N為一個大素數(shù)，有限域ZN上階為n的Chebyshev映射記為：Tn(x):ZN→ZN，其定義的迭代形式為

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

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

該方案[3]由3個算法構(gòu)成，算法描述如下：

(1)密鑰生成。為了安全傳送，Alice首先采用如下算法生成其加密和解密密鑰。①隨機(jī)選擇一個大的整數(shù)s;②隨機(jī)選擇一個x∈ZN，然后計算Ts(x)；③Alice公布(x,Ts(x))作為其公開密鑰，而把s視為其私有密鑰。

(2)加密。Bob為了加密一條消息M。①首先獲取Alice經(jīng)過認(rèn)證的公開密鑰(x,Ts(x))； ②把它要傳遞的消息表示成一個數(shù)字M∈ZN；③隨機(jī)生成一個大的整數(shù)r；④計算Tr(x)，Tr(Ts(x)),以及X=MTr(Ts(x))；⑤將(Tr(x),X)作為密文傳遞給Alice。

(3)解密。Alice為了恢復(fù)明文，須作如下計算。①利用它的私有密鑰s計算Ts(Tr(x))=Ts×r(x)=Tr(Ts(x))；②恢復(fù)明文M=X/Ts(Tr(x))。

上面算法描述中加密和解密的一致性可以利用Ts(Tr(x))=Tr(Ts(x))，即有限域上Chebyshev映射所具有的半群性質(zhì)來進(jìn)行證明。

該公鑰密碼方案并不安全，如果能找到Chebyshev序列在模N時的周期T，則可以進(jìn)行下面的攻擊[7]。

1.3對基于有限域上Chebyshev映射的公鑰加密方案的攻擊

設(shè)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映射周期的存在性、周期的性質(zhì)并給出一種快速的尋找周期的算法，從而使得上述攻擊方案變得可行。在討論的過程中，需要用到一些矩陣變換及環(huán)面自同構(gòu)的知識。

2矩陣變換及環(huán)面自同構(gòu)

2.1矩陣變換

定義2一般的模N時的矩陣變換的定義如下

這里Am×m是一個整數(shù)矩陣。

文獻(xiàn)[8]研究了矩陣變換的周期問題，對矩陣變換在模N時周期是否存在給出了一個充分必要條件。

定理1[8]模N的整數(shù)變換矩陣具有周期性的充要條件是|A|與模N互素，此處A是變換的矩陣，|A|是矩陣A的行列式。

陳勇在文獻(xiàn)[9]中進(jìn)一步指出，上述矩陣變換的周期與模數(shù)有如下關(guān)系：

考慮在域GF(qn)上的矩陣變換

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

定理2告訴我們：隨著模數(shù)的成倍增加，矩陣的周期也將成倍增加。

推論若gcd(det Am×m,2)=1，令k是最小的下標(biāo)使得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環(huán)面自同構(gòu)

定義3環(huán)面自同構(gòu)是一種特殊的矩陣變換，其表達(dá)式如下

文獻(xiàn)[10]利用戴德金關(guān)于代數(shù)整數(shù)環(huán)的算術(shù)基本定理仔細(xì)研究了環(huán)面自同構(gòu)的周期軌道，指出：可把有理素數(shù)分為三類：惰性(inert)素數(shù)、分裂(split)素數(shù)和分歧(ramified)素數(shù)，在映射(4)中N為素數(shù)的情況下，它的周期根據(jù)這三類素數(shù)，有著不同類型的三種周期軌道，確定方式如下：

(1)若L(d,N)=-1，素數(shù)N為惰性素數(shù)，變換(4)的周期為N+1的因子；

(2)若L(d,N)=1，素數(shù)N為分裂素數(shù)，變換(4)的周期為N-1的因子；

(3)若L(d,N)=0，素數(shù)N為分歧素數(shù)，若k≡2(modN)，變換(4)的周期為N或1；若k≡-2(modN)，變換(4)的周期為2N或2。

其中，L(d,N)是勒讓德符號。

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

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

通過研究發(fā)現(xiàn)，有限域上的Chebyshev映射與矩陣變換之間具有密切關(guān)系，可以通過如下公式把Chebyshev映射(1)改寫成矩陣變換的形式

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

對于一般的矩陣變換式(2)，容易推出下面的結(jié)論：

定理3設(shè)矩陣Am×m對于模數(shù)N1和N2都存在周期，Am×m模N1的最小正周期記為T1，Am×m模N2的最小正周期記為T2，若N1

證明由條件可知

式中，I表示單位矩陣。

對式(6)左右兩邊同時模N1，則有

AT2modN2modN1=I modN2modN1，

因?yàn)镹1

AT2mod N1=ImodN1，

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

在基于上述分析的基礎(chǔ)上，給出一種尋找Chebyshev映射周期的快速算法。

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

算法描述：

(2)對于Chebyshev公鑰加密方案中指定的模數(shù)N，確定整數(shù)n，使得2n

若L(d, N)=-1，轉(zhuǎn)(5)；若L(d, N)= 1，轉(zhuǎn)(6)；若L(d, N)= 0，轉(zhuǎn)(7)。

(5)在Pn與Pn+1之間尋找滿足t|N+1的整數(shù)t，如果滿足At=ImodN，則返回T=t。

(6)在Pn與Pn+1之間尋找滿足t|N-1的整數(shù)t，如果滿足At=ImodN，則返回T=t。

3.3算法的有效性分析

4結(jié)論

在基于有限域上Chebyshev映射的公鑰密碼方案中，如果能求得Chebyshev映射產(chǎn)生的序列的周期，明文就能被恢復(fù)出來，該密碼方案就是不安全的。利用矩陣變換及環(huán)面自同構(gòu)的相關(guān)理論討論了有限域ZN上Chebyshev映射的周期性問題，并給出一種快速的尋找周期的方法，從而使得對有限域上Cheyshev公鑰加密方案的攻擊成為可能，經(jīng)過實(shí)驗(yàn)分析，可知該算法是快速有效的。

參考文獻(xiàn)

[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多項(xiàng)式的公鑰系統(tǒng)[J]，鐵道學(xué)報,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]陳勇. 對幾類混沌加密系統(tǒng)的分析和改進(jìn)[D]. 重慶：重慶大學(xué), 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