公開(kāi)密鑰加密算法，也稱為非對(duì)稱算法，其主要特征為加密密鑰與解密密鑰不同，加密密鑰是可以公開(kāi)的，并且很難從加密密鑰計(jì)算出解密密鑰，所以，公鑰加密算法被廣泛應(yīng)用，接下來(lái)，我就給大家介紹一種基于環(huán)面自同構(gòu)的公鑰加密算法。

一、環(huán)面自同構(gòu)

環(huán)面自同構(gòu)（TorusAutomorphisms）是一種典型的混沌映射，其表達(dá)式如下：

其中，A是一個(gè)形如的2×2的矩陣；a，b，c，d皆為整數(shù)；且detA=1；mod1表示只取小數(shù)部分，即xi，yi∈（0，1）。

k=a+d為A的跡，則特征多項(xiàng)式為f（λ）=λ2-kλ+1，其較大的一個(gè)特征值為：

當(dāng)k2-4>0即k<2時(shí)（只考慮k為正），自同構(gòu)A具有強(qiáng)烈的混沌特性。環(huán)面自同構(gòu)的周期軌道，它由坐標(biāo)為ξ=p1/q1，η=p2/q2的有理點(diǎn)組成，其中pi，qi為整數(shù)。使pi，qi互素，g為q1，q2的最小公倍數(shù)。去分母，使M成為Z2（整數(shù)向量的網(wǎng)格）上的映射。

因此，將映射（1）擴(kuò)展到[0，N）×[0，N）上。設(shè)xi=Xi/N，yi=Yi/N，x≤Xi，Yi<N，且Xi，Yi為整數(shù)。則：

也即是：

所以，可以改寫(xiě)映射（1）為：

其中X，Y，N為整數(shù)，而其他參數(shù)與映射（1）要求相同。

將素?cái)?shù)分為3類。在映射（2）中N為素?cái)?shù)的情況下，它的周期根據(jù)這3類素?cái)?shù)，有著3種不同類型的周期軌道。確定方式如下：

定義整數(shù)d，

其中k2-4=n2D，D為square-free。

若L（d，N）=-1，素?cái)?shù)N為inert，映射（2）的周期為N+1的因子。若L（d，N）=1，素?cái)?shù)N為splits，映射（2）的周期為N-1的因子。若L（d，N）=0，素?cái)?shù)N為ramifies，若k≡2（modN），映射（2）的周期為N或1；若k≡-2（modN）則為2N或2。其中L（d，N）是勒讓德符號(hào)。

二、基于環(huán)面自同構(gòu)的公鑰加密算法

筆者提出的公開(kāi)密鑰加密算法與RSA相似，其安全性都是基于大數(shù)因式分解的難度，所不同的是利用混沌映射進(jìn)行迭代，并利用了該映射的周期性。

因?yàn)橛成洌?）是周期性的，所以：

即：

1、加密算法的描述

加密算法的描述主要分成3個(gè)部分，即密鑰產(chǎn)生，加密和解密。

密鑰產(chǎn)生：

（1）Alice隨機(jī)選取2個(gè)大素?cái)?shù)p和q，它們具有相同的長(zhǎng)度；

（2）計(jì)算N=pq，φ=（p3-p）（q3-q）；

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

（4）用歐幾里德擴(kuò)展算法計(jì)算d，以滿足ed≡1modφ。

此時(shí)，Alice的公開(kāi)密鑰為（N，e），私人密鑰（N，d）。加密：

1）Bob獲取Alice的公開(kāi)密鑰（N，e）；

2）將需要加密的信息表達(dá)成整數(shù)m1，m2，且0≤m1，m2<N；

3）計(jì)算，

4）將密文ca，cb，cc，cd傳送給Alice。

解密：

1）Alice接收到密文ca，cb，cc，cd；

2）計(jì)算，

3）則信息m1=pa，m2=pd。

值得注意的是，公式（4）中，矩陣中1和m1m2-1的位置是可以任意交換的，這不影響信息的加密和解密的效果。

2、加密算法的證明

設(shè)T為映射（2）的周期，即AkT+1=A（modN）。由上節(jié)可知，如果N為素?cái)?shù)，則映射（2）的周期T可以看成（N+1）（N-1）N即N3-N的因子：

若N=p，則映射（2）的周期Tp是p3-p的因子；因?yàn)棣?（p3-p）（q3-q），Tp也就必是φ的因子。又ed=1modφ，所以ed=1+k<=1+k1Tp。因此：

Aed=A1+kφ=A1+k1Tp=A（modp）。

同理可得:

Aed=A1+kφ=A1+k2Tq=A（modq）。

根據(jù)中國(guó)剩余定理，N=pq，所以Aed=A1+kφ=A1+k′T=A（modN）。

3、簡(jiǎn)單的例子

下面舉一個(gè)例子來(lái)進(jìn)行說(shuō)明：Alice隨機(jī)選取2個(gè)大素?cái)?shù)p=3391和q=3793，計(jì)算N=12862063，φ=2127805021604586885120。Alice選取的e=65537，通過(guò)歐幾里德擴(kuò)展算法計(jì)算d=36493169420076531713。Alice的公開(kāi)密鑰就是（N，e），私人密鑰就是（N，d）。

為了加密消息m=12345674567890，Bob將消息表示為m1=1234567，m2=4567890，再使用Alice提供的公鑰（N，e），根據(jù)公式（4）運(yùn)算，得出ca=10495137，cb=8311873，cc=5249972，cd=10914291。Bob將密文ca，cb，cc，cd傳給Alice。Alice則根據(jù)公式（5）和私人密鑰（N，d）來(lái)計(jì)算出m1=1234567，m2=4567890，再將其組合成為m=12345674567890。

4、軟件實(shí)現(xiàn)

我們所說(shuō)的公鑰算法步驟簡(jiǎn)潔，運(yùn)算簡(jiǎn)單，與RSA相似，容易軟件實(shí)現(xiàn)。但是需要注意的是，本加密算法的安全性基于因式分解2個(gè)大素?cái)?shù)的乘積，在運(yùn)算中需要涉及大整數(shù)的存儲(chǔ)和運(yùn)算。程序語(yǔ)言中提供的整數(shù)類型是不能滿足需求的，所以需要單獨(dú)定義。

其次，本加密算法最主要的運(yùn)算就是矩陣的乘方。采用快速矩陣乘法算法將大大加快運(yùn)算速度。

計(jì)算矩陣A的n次方：X=I；

for（i=n.bitsnumber（）；i>0；i--）

{

X=X2；

if（n.bitat（i）==1）

X=XA；

}

其中：n.bitsnumber（）表示取n的二進(jìn)制的位數(shù)；n.bi2tat（i）則表示n的第i位的值。

三、加密算法的安全性

我們提出的叫曖昧算法與RSA有著相同的結(jié)構(gòu)，因此其安全性與RSA相當(dāng)。理論上，RSA的安全性取決于因式分解模n的困難性。雖然從技術(shù)上來(lái)說(shuō)這是不正確的，因?yàn)樵跀?shù)學(xué)上至今還未證明分解模數(shù)就是攻擊RSA的最佳方法，也未證明分解大整數(shù)就是NP問(wèn)題。而事實(shí)上，人們?cè)O(shè)想了一些非因子分解的途徑來(lái)攻擊RSA體制，但這些方法都不比分解n來(lái)得容易。因此，RSA加密算法以及筆者提出的加密算法的安全性是可靠的。

在特定的條件下，RSA的實(shí)現(xiàn)細(xì)節(jié)的漏洞會(huì)導(dǎo)致對(duì)算法的攻擊：選擇密文攻擊，公共模數(shù)攻擊，低加密指數(shù)攻擊以及低解密指數(shù)攻擊。

RSA的選擇密文攻擊對(duì)筆者提出的基于環(huán)面自同構(gòu)的算法是無(wú)效的。這種攻擊方式主要有3種形式：明文破譯、騙取仲裁簽名和偽造合法簽名。這3種形式都利用了指數(shù)運(yùn)算保持了輸入的乘積結(jié)構(gòu)，也即是：

但是對(duì)于我們的加密算法，X和Y都是二階矩陣，顯然（XY）dmodN=XdYdmodN是不成立的，因?yàn)榫仃嚨某朔ㄊ遣痪哂锌山粨Q性的。

公共模數(shù)攻擊依然有效。設(shè)M為含有消息m1，m2的矩陣，2個(gè)加密密鑰為e1，e2，公共模數(shù)N。經(jīng)過(guò)加密運(yùn)算得出密文矩陣為C1，C2。由于e1，e2互素，可以找到r和s，滿足re1+se2=1。假設(shè)r為負(fù)，則：（C-11）-r×Cs2=MmodN。因此。在一組用戶之間共享模數(shù)N是不安全的。

采用小的e，d可以加快加密和解密的速度，而且所需的存貯空間??；但是如果e，d太小，則容易受到低指數(shù)攻擊，包括低加密指數(shù)攻擊和低解密指數(shù)攻擊。例如，對(duì)于加密密鑰e，如果消息相同，利用e個(gè)消息就可以進(jìn)行低加密指數(shù)攻擊。因此，一定要選擇較大的e，d，且保證MemodN≠M(fèi)e。

因此通過(guò)精心考慮基于環(huán)面自同構(gòu)的公鑰加密算法實(shí)現(xiàn)的細(xì)節(jié)是可以避免這些安全漏洞的。

admin

收藏 海報(bào)分享