精確混沌迭代和近似混沌迭代的比較

張翔 陸正福

摘? ?要：對(duì)于浮點(diǎn)數(shù)（雙精度數(shù)）計(jì)算中混沌映射存在著比較明顯的有限精度效應(yīng)，文章設(shè)計(jì)了一種多精度計(jì)算方法，并使用多精度計(jì)算來進(jìn)行混沌迭代運(yùn)算，比較了精確混沌迭代和近似混沌迭代計(jì)算結(jié)果的差異。

關(guān)鍵詞：混沌映射;多精度計(jì)算;迭代

1? ? 混沌簡(jiǎn)要介紹

1989年英國數(shù)學(xué)家Matthews提出混沌加密方法以來，混沌系統(tǒng)陸續(xù)被應(yīng)用于保密通信領(lǐng)域?；煦缰阅軌虺蔀橐环N新的密碼體制，是因?yàn)橛幸韵聨讉€(gè)適合作為密碼系統(tǒng)的特性：遍歷性、混合性、非周期性以及對(duì)初值的敏感依賴特性。

然而，由于實(shí)際計(jì)算中存在著有限精度效應(yīng)，混沌序列在迭代過程中必將退化為周期序列且周期難以度量。此外，由于使用數(shù)值映射作為密碼流發(fā)生器，有限精度也限制了密鑰空間的大小。這使得混沌序列原本優(yōu)良的性能大打折扣，難以抵御統(tǒng)計(jì)分析和參數(shù)重構(gòu)等攻擊。

在這些方面有著許多的研究，Shujun等[1]中介紹了Baptista混沌密碼及其改進(jìn)的方法，也指出Baptista混沌密碼及其改進(jìn)的方法的缺陷和破解方法。周紅等[2-4]中為了提高混沌密碼的保密性，分別把m序列擾動(dòng)實(shí)現(xiàn)，反饋控制，前饋型設(shè)計(jì)的思想在有限精度下實(shí)現(xiàn)。

上面所提到的論文雖然提高了混沌序列的周期，但是由于使用的精度不高，混沌序列的周期也不會(huì)超過一定值，所以增加精度才是解決有限精度所帶來影響的根本辦法。

本文提出了一種多精度計(jì)算方法，可以有效地提高精度，從而減少混沌映射中的有限精度效應(yīng)。但是計(jì)算機(jī)中的空間和時(shí)間是有限的（尤其是時(shí)間），所以不可以無限制地提高精度。因此，本文提出了一種結(jié)合多精度計(jì)算生成混沌映射的方式，

2? ? 多精度數(shù)及其運(yùn)算

本文中的程序是在Java平臺(tái)下實(shí)現(xiàn)的，在這里沒有使用Java程序中的BigDecimal類，而是使用了一種類似于科學(xué)計(jì)數(shù)法的方式來保存數(shù)并進(jìn)行數(shù)的加減乘除運(yùn)算。

2.1? 多精度數(shù)的儲(chǔ)存方式

本文中定義了一個(gè)類來表示數(shù)，該類是這樣定義的：

varNumber

{

byte value[];

int exponent;

byte type;

}

包括value[]，exponent，type 3個(gè)元素，其中，value數(shù)組表示該數(shù)的每一位上的值，value[0]表示該數(shù)的最高位的值，value[1]表示該數(shù)的次高位的值，以此類推，value[len-1]（len為value數(shù)組的長度）表示該數(shù)的最低位的值;在這里定義數(shù)的形式為（0.value）*（256^exponent），exponent表示指數(shù);type用來標(biāo)識(shí)數(shù)的類型，用0表示正實(shí)數(shù)，1表示負(fù)實(shí)數(shù)。

在這里使用了256進(jìn)制，目的在于兩個(gè)方面：（1）可以充分利用存儲(chǔ)空間;（2）在把數(shù)轉(zhuǎn)化為二進(jìn)制時(shí)在程序上容易實(shí)現(xiàn)。

本文中所定義的數(shù)不但可以表示實(shí)數(shù)，同樣可以用來表示其他類型的數(shù)。比如可以用type=2表示實(shí)部為正的純虛數(shù)，用type=3表示實(shí)部為負(fù)的純虛數(shù)。

最后在本文中定義數(shù)的標(biāo)準(zhǔn)形式為value數(shù)組的前后第一位均不為0。特殊的定義0為：

varNumber

{

value[0] = 0;

exponent = - 2147483648;

type = 0;

}

其中，-2147483648為Java中最小的整型數(shù)。

2.2? 多精度數(shù)的計(jì)算

本文中的多精度計(jì)算包括正實(shí)數(shù)范圍內(nèi)的加減乘除計(jì)算，實(shí)數(shù)范圍內(nèi)的加減乘除計(jì)算。

由于在Java程序中byte型數(shù)進(jìn)行加減乘除運(yùn)算的結(jié)果為int型數(shù)，因此，在中間計(jì)算時(shí)使用的數(shù)據(jù)類型是int型數(shù)，最后，再把結(jié)果轉(zhuǎn)化為byte型數(shù)。所以，本文中使用了byte數(shù)組的全空間來存儲(chǔ)數(shù)位的方式并不會(huì)在計(jì)算中造成數(shù)據(jù)溢出。

3? ? 混沌映射

3.1? Logistic映射

Logistic映射又被稱為蟲口問題，其映射形式為：

Xn+1=Xn（1-Xn），0

其中，1≤μ≤4，μ∈（0，4）稱為分形參數(shù)。當(dāng)0<μ≤3時(shí)，迭代后的值為穩(wěn)定不動(dòng)點(diǎn)，μ逐漸增大，出現(xiàn)倍周期分岔現(xiàn)象，當(dāng)3.569 945 972…<μ≤4時(shí)，系統(tǒng)工作于混沌狀態(tài)。此時(shí)所產(chǎn)生的序列{Xn，n=0，1，…}具有非周期、非收斂以及對(duì)初始值十分敏感等特性。

3.2? 分段線性映射

分段線性映射最常見的是帳篷映射和移位映射。帳篷映射的迭代公式如下：

其中，Xn，p∈（0，1）分別為系統(tǒng)的狀態(tài)和參數(shù)。

移位映射的迭代公式如下：

Xn+1=aXn（mod1），Xn∈（0，1）

其中，Xn為系統(tǒng)的狀態(tài)，a>1為系統(tǒng)的參數(shù)。

4? ? 精確混沌迭代和近似混沌迭代的比較

本文選取Logistic映射進(jìn)行研究，在Logistic映射中取參數(shù)μ=4，初值，x0在程序中表示為：

varNumber

{

value[0]= 32;

exponent=0;

type=0

}

實(shí)驗(yàn)步驟如下：

（1）對(duì)該映射進(jìn)行n次的迭代計(jì)算，并在迭代中保留小數(shù)的所有位數(shù)。

（2）對(duì)經(jīng)過迭代計(jì)算得到的數(shù)進(jìn)行取舍（四舍五入），保留其前10位，得到精確迭代計(jì)算的結(jié)果。

（3）把初值代入混沌映射中進(jìn)行計(jì)算，得到x1的值，對(duì)x1的標(biāo)準(zhǔn)形式進(jìn)行取舍，在byte數(shù)組中只保留前10位（不足10位的全部保留）。

（4）按照（3）的方法計(jì)算x2，x3，…xn，xn為近似迭代計(jì)算的結(jié)果。

（5）對(duì)精確迭代計(jì)算的結(jié)果和近似迭代計(jì)算的結(jié)果進(jìn)行比較。

5? ? 實(shí)驗(yàn)結(jié)果和總結(jié)

在實(shí)驗(yàn)中分別取迭代次數(shù)n為10，15，20次，并進(jìn)行比較，比較結(jié)果如表1所示。

從表1可知，在迭代次數(shù)不高的時(shí)候，精確混沌迭代和近似混沌迭代的結(jié)果差別不大，但是不同的位數(shù)增加了。在無法在精確計(jì)算的條件下進(jìn)行高次迭代（比如300次）時(shí)，可以推斷只要迭代次數(shù)足夠，近似計(jì)算所產(chǎn)生的擾動(dòng)對(duì)混沌映射有很大的影響。

[參考文獻(xiàn)]

[1]SHUJUN L，GUANRONG C，KWOK-WO W，et al.Baptista-type chaotic cryptosystems problems and countermeasures[J].Physics Letters，2004（338）：368-375.

[2]周紅，凌燮亭.有限精度混沌系統(tǒng)的m序列擾動(dòng)實(shí)現(xiàn)[J].電子學(xué)報(bào)，1997（7）：95-97.

[3]周紅，羅杰，凌燮亭.混沌非線性反饋密碼序列的理論設(shè)計(jì)和有限精度實(shí)現(xiàn)[J].電子學(xué)報(bào)，1997（10）：57-60.

[4]周紅，俞軍，凌燮亭.混沌前饋型流密碼的設(shè)計(jì)[J].電子學(xué)報(bào)，1998（1）：98-101.

Comparison of exact chaos iteration and approximation chaos iteration

Zhang Xiang1， 2， Lu Zhengfu2

（1.Puer University， Puer 665000， China; 2.Department of Mathematics， Yunnan University， Kunming 650091， China）

Abstract：There are some problem in chaos because of finite precison. It is obvious when calculating chaos by floating-point numbers（double precision number）. This paper presents a more accurate method（multi-precision arithmetic）and calculate chaos by this method， comparing the result between in exact chaos iteration and approximation chaos iteration.

Key words：chaos; multi-precision arithmetic; iteration