我們利用RSA公鑰加密算法和EIGamal公鑰加密算法的算法結(jié)構(gòu)，提出基于有限域離散Chebyshev多項式的公鑰加密算法。該算法結(jié)構(gòu)類似于RSA加密算法，其安全性基于大數(shù)因式分解的難度或者與ElGamal的離散對數(shù)難度相當，能夠抵抗對于RSA的選擇密文攻擊，并且易于軟件實現(xiàn)。

一、實數(shù)域擴展離散Chebyshev多項式

1、Chebyshw多項式及其性質(zhì)

Chebyshev多項式是由Tn(x)= cos(n*arccosx)，（-1≤x≤1）所定義的n次多項式，其遞推關(guān)系為：

且有T0(x)=1，T1(x)=x。

可以證明Cbebyshev多項式具有以下的重要特性。

(1)半群特性

(2)混沌特性

當n>1時，n次Chebyshev多項式映射Tn[-1，1]→[-1，1]的Lyapunov指數(shù)λ=In n>0，所以它是混沌映射，其分布函數(shù)為：

2、實數(shù)域擴散離散的Chebyshw多項式

由于Chebyshev多項式是代數(shù)多項式，因此可以很容易地把式(1)擴展到實數(shù)域，得到實數(shù)域擴散離散Chebyshev多項式Fn(x)的定義如下：

設(shè)n∈N，實數(shù)|x| >1。P為非零實數(shù)且|p|>1。實數(shù)域擴散離散Chebyshev多項式迭代關(guān)系表達式為：

且有Fo(x)=1 mod p，F(xiàn)1（x）=x mod p，本文有關(guān)Chebyshev多項式Fn（x）的討論和計算都在實數(shù)域上進行。

實數(shù)域擴散離散的Chebyshev多項式還保留著其原來作為加解密基礎(chǔ)算法的半群特性。根據(jù)半群特性在實數(shù)域中的定義，可知其在有限域上可表示為：

由于半群特性的存在，使得有限域Chebyshev多項式可以用來構(gòu)造公鑰體系。

二、實數(shù)域擴散離散的Chebyshey多項式的公鑰算法

提出的公開密鑰加密算法與RSA加密算法相似，其安全性都是基于大數(shù)因式分解的難度，所不同的是它利用混沌映射進行迭代，并利用實數(shù)域擴散離散的Chebyshev多項式的半群特性。加密算法的描述主要分成3個部分，即密鑰產(chǎn)生、加密和解密。

1、密鑰產(chǎn)生

①Alice隨機選取2個大素數(shù)p和q，它們具有相同的長度；

②計算N=bq和φ=(p2-1)(q2-1)；

③隨即選取整數(shù)e，使得1<e<φ聲并且gcd(e，φ)=1；

④用歐幾里德擴展算法計算d，以滿足ed-1 modφ；

⑤隨機選擇一個整數(shù)x0，且x0>1，計算Fd（x0）= Fd（x0）mod N。

此時，Alice的公開密鑰為（N，e，x0，F(xiàn)d（x0），私人密鑰為(N，d)。

2、加密

Bob為了加密消息M。須完成以下步驟：

①獲得經(jīng)過認證的Alice的公鑰（N，e，x0，F(xiàn)d（x0）；

②將消息變換成一個整數(shù)M；

③計算Fed（x0）=Fe(Fd (xo)）mod N．X=M．Fed（x0）和Fe（x0）=Fe（x0）mod N；

④發(fā)送密文C→（Fe（x0），X）給Alice。

3、解密

①Alice收到密文C=（Fe（x0），X）；

②使用密鑰(N，d)計算Fde（x0）=Fd（Fe（x0））mod_N;

③求M=X/Fd．e（xn）。

整數(shù)e和整數(shù)d在傳統(tǒng)的RSA加密算法里面稱為加密指數(shù)和解密指數(shù)，相應(yīng)的N為模數(shù)。與RSA相比，我們提出的算法有兩個步驟與RSA算法是不同的。在步驟(2)③中，我們使用實數(shù)域擴散離散的Chebyshev多項式的迭代來加密明文，即Fde（x0）=Fd（Fe（x0））modN和M=X/Fd*e(x0)而RSA加密算法使用C=Me (mod N)進行加密；在步驟(3)②中，我們同樣使用實數(shù)域擴散離散的Chebyshev多項式的迭代來解密密文，即Fde（x0）=Fd（Fe（x0））modN和M=X/Fd*e(x0)，而傳統(tǒng)的RSA使用M=D(mod N)來解密密文。

三、加密算法性能分析

1、合理性分析

Chebyshev多項式迭代公式為：

由n維Chebyshev多項式的半群特性，得：

式中，R∈Z，s∈Z。

將上式取模為任一個大于1的整數(shù)N得：

盡管x的取值范圍有所變化，但是這不改變上述的半群特性，正因為這樣，上述新算法顯然是正確的。因為：

所以M= X/Fd (Fe(x0)mod N。

2、安全性分析

加密算法與RSA有著相同的結(jié)構(gòu)，要破解提出的算法，首先要得到私鑰(N，d)，因此其安全性與RSA相當。理論上，RSA的安全性取決于因式分解模N的困難性，這從技術(shù)上來說是不正確的，因為在數(shù)學上至今還未證明分解模數(shù)就是攻擊RSA的最佳方法，也來證明分解大整數(shù)就是NP問題，而事實上，人們設(shè)想了一些非因子分解的途徑來攻擊RSA體制，但這些方法都不比分解N來得容易。因此，所提加密算法的安全性是可靠的。

同時根據(jù)Chebyshev多項式迭代關(guān)系，F(xiàn)n(x)的多項式又表達為：

EIGamal公鑰加密算法的安全性是基于有限域上離散對數(shù)難解這一性質(zhì)。同理地，本文提出基于實數(shù)域擴散離散Chebyshev多項式的公鑰加密算法中，已知z，F(xiàn)n(x)，其中Fn(x）mod p是一個關(guān)于x的n次多項式，在多項式時間內(nèi)計算是不可行的。

3、加密算法的可行性分析

快速算法如下：

設(shè)整數(shù)s可分解為：

則由Chebysbev多項式的半群特性得：

為了計算Fs(x) (mod p)，只需進行k1+k2+…ki次迭代即可。s的取值的因子越多，其效率就越高，確切地講，在2048bit精度下，s和r的上界是2的970次方。

4、加密算法效率和復雜性分析

上述加密算法由于需要類似RSA、EIGamal等加密算法選擇一個大素數(shù)，有實數(shù)域離散多項式文件加密算法的時間復雜度為0(log2n)，其空間復雜度為0(log2n)，因此基于實數(shù)域離散多項式的公鑰算法的效率與RSA、EIGamal加密算法相同。

admin

收藏 海報分享