基于Chebyshev多項式的公鑰密碼算法安全性及貓映射周期分布分析.pdf

1、本論文討論兩個問題：第一，分析NZ上基于Chebyshev多項式的公鑰密碼算法的安全性；第二，分析貓映射的周期分布，該問題直接來源于第一個問題的深入研究。
　　對于第一個問題，本論文通過NZ上一維線性遞歸序列對該密碼算法進行建模，分析了Chebyshev多項式迭代序列的周期分布。研究結(jié)果表明：若密碼算法的參數(shù)選擇不合適，對于素數(shù)N以及一般的合數(shù)N，該序列都存在較小的周期。較小的周期意味著該算法存在安全弱點，基于此，本論文給出了對該

2、算法的一種窮舉攻擊，該攻擊可以發(fā)現(xiàn)等效的私鑰，即該密碼算法被攻破。為有效地防止這種攻擊，本論文建議了一些合適的參數(shù)選擇方法，在合適的參數(shù)下，證明了該密碼算法在選擇明文攻擊下的安全性介于離散對數(shù)問題（DL）及計算Diffie-Hellman問題（CDH）之間。同時，本論文對該算法進行了一些改進，使得該算法可以應用于真實的世界，但改進后的算法在IND-CCA2下的安全性是今后待解決的問題。
　　對于第二個問題，本論文通過NZ上二維線性

3、遞歸序列對貓映射迭代進行建模，將貓映射周期分布問題規(guī)約為其迭代序列的周期分布問題，進一步將該問題規(guī)約為其最小多項式的周期分布問題。首先，對于一般的合數(shù)N，本論文討論了其周期結(jié)構(gòu)，研究結(jié)果表明其周期為貓映射在其素數(shù)分解的因子上周期的最小公倍數(shù)。然后，本論文分析了N為素數(shù)、2eN=及Npp=>為素數(shù)時貓映射的周期分布，e,3獲得了精確的解析解。N為素數(shù)時解決方法的核心是將有限域上多項式的周期分布分析規(guī)約為其根的階的分布分析；2eN=時解決方

4、法的核心是將Galois環(huán)上多項式的周期規(guī)約為有限域上該多項式的周期，然后通過Hensel提升將有限域上的結(jié)果提升至Galois環(huán)，進而得出周期分布結(jié)果；Npp=>時解決方法的核心是將e,3Galois環(huán)上多項式的周期分布分析規(guī)約為其根的階的分布分析；后兩種情況較復雜，且周期分布問題不總能規(guī)約到多項式的周期分布分析。此時，本論文將貓映射矩陣進行p進制展開，然后利用Hensel提升得出了較滿意的結(jié)果。至此，貓映射周期分布的核心問題獲得了圓