自從看了電影〝駭客任務(MATRIX)〞後，就深深為其動人的劇情所吸引，震撼之深非筆墨所能言喻。故事內容大約如下:二十二世紀的地球已被電腦進化成有生命的電腦人(agent)所控制主宰，人類大部分都活在agent設計的虛擬夢幻世界中，而實際上是熟睡在保育箱中，成為agent所飼養的〝動物〞，只有一小部份人類是清醒並躲入地下伺機而動，在女主角崔妮蒂的帶領下，男主角尼歐結識了一群抵抗agent電腦王國的自由鬥士，那時活在地底下的人類生活行動是依賴一部〝錫安〞電腦主機來掌控，〝錫安〞電腦主機是由人類所操控，藉著其強大的密碼系統抵抗保衛agent的入侵，最後終因密碼系統的強固以及密碼(password)沒有外洩的情形下，爭取到時間使得尼歐領悟電腦電子世界的奧秘，進而消滅了電腦人。
這部令人想一看再看的電影深深吸引著我，因而有個念頭也想設計出強大而無法被人破解的密碼系統，可以抵抗未來agent的入侵。

二、研究目的

機緣巧合下在接觸到天下文化出版社所發行的〝渾沌(chaos)〞以及楊吳泉先生所著的〝現代密碼學入門與程式設計〞兩本書，反覆熟讀思索，發現在現在熱門的非線性科學〝渾沌(chaos)〞中，有一種稱為邏輯映射圖(Logistic map)的一元二次方程式，其形式非常簡單，適當的參數控制下，其迭代軌跡會出現渾沌現象，所以想利用電腦程式演算此軌跡圖形，利用數論中的模運算來取得加解密所需要的亂數，配合密碼學中串流加密的方式(Stream Ciphers)，是可以發展出一套安全性高的加解密軟體系統，媲美〝錫安〞電腦主機密碼系統來抵抗agent的入侵。

三、研究設備器材：

(一)pentium(ｋ) 450 個人電腦，Win98作業平台：1台；

(二)Visual C++6.0 版軟體:1套;

(三)Matlab5.1 版軟體:1套;

(四)PUTeX 論文編輯軟體:1套;

四、研究過程或方法:

(一)研究過程:

1.渾沌理論:

邏輯映射圖(Logistic map)方程式:

        Xn+1 =μ *Xn(1-Xn),Xn   [0,1]，                                                (1)

邏輯映射圖在 米=3.569946 開始出現渾沌，其分析圖形如下:

圖(2):

Xn+1=0.4 Xn (1- Xn )，X0=0.8 ，幾次迭代後很快進入固定點0不再改 變，屬於週期數為1的邏輯映射圖。

圖(3): 

Xn+1=2 Xn (1- Xn )，X0=0.2，幾次迭代後很快進入固定點0.5不再改變，屬於週期數為1的邏輯映射圖。

圖(4):

Xn+1=3.3 Xn (1- Xn )，X0=0.2幾次迭代後很快進入兩個固定點0.48和0.83，屬於週期數為2的邏輯映射圖。

圖(5):

Xn+1=3.53 Xn (1- Xn )，X0=0.37幾次迭代後很快進入四個固定點0.37、0.52、0.83、0.88，屬於週期數為4的邏輯映射圖。

圖(6):

Xn+1=3.9 Xn (1- Xn )，X0=0.2很多幾次迭代後仍無法進入固定點，屬於週期數為∞的邏輯映射圖，此時已出現渾沌現象。

圖(7):

μ  = 1 ∼ 4，倍週期分叉到混沌映射圖，其中μ  = 3.5699456 ∼ 4的黑色區域表示渾沌現象。

圖(8):

 ,μ  = 3 ∼ 4倍週期分叉到混沌映射圖，其中黑色區域中三條白紋表示再次出現穩定倍週期現象。

2.密碼學:

串流加密方式如下，今有明文(plaintext)P:八個位元;亂數(random number)R:八個位元;欲產生密文(ciphertext)C:八個位元，如下所示，方程組(2)為互斥運算:

Ｐ♁Ｒ≡Ｃ

Ｃ♁Ｒ≡Ｐ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(２)

(二) Return map 檢測:

Return map(遞迴映射)是一種可以測量出亂數序列週期性的測量方法，舉例說明:今有一數字序列為(X1,X2,… ,Xn),遞迴映射檢測方式為:Xi對Xi+1作圖，其中1≦ i ≦(n-1)，若數字序列是週期性，則遞迴映射將出現一些固定點圖，若數字序列是非週期性，則遞迴映射圖將出現一些複雜的圖形。

(三) FIPS PUB 140-1亂數檢測方式:

FIPS PUB 140-1是美國聯邦資訊處理標準公告(Federal Information Processing Standards Publication)對密碼模組的秘密安全規定(Security Requirements for Cryptographic Modules)，其中所包含對密碼模組亂數檢測方式如下:

1.單一位元測試(Monobit Test):

亂數產生器產生20,000個連續位元(0或1)，將20,000個連續位元相加總數定義為X，若9,654 < X < 10,346 ，則此項亂數測試通過。

2.樸克測試(Poker Test):

亂數產生器產生20,000個連續位元，將此20,000個位元切割成連續5,000個4位元整數，此整數之數值範圍為0-15。定義f(i)為整數i出現之次數，而i的範圍為0 ≦ i ≦ 15，計算下列數值:

 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(3)

若1.03 <  X < 57.4，則此項亂數測試通過。

3.位元重複值測試(Runs Test):

〝位元重複值〞定義為連續20,000亂數位元中所出現的連續為1的長度或連續為0的長度，統計累積此數值，不論是1或是0的位元，〝位元重複值〞的長度對統計數值大小需符合下表(1)累積數之範圍，共計12項測試(包含1和0的測試)，若不符合其中一項，則此項亂數測試不通過。

位元重複值	累積數
1	2,267－2,733
2	1,079－1,421
3	502－748
4	223－402
5	90－223
≧6	90－223

4.長位元重複值測試(Long Run Test):

〝長位元重複值〞定義為連續20,000亂數位元中所出現的連續為1的長度為34或34以上，或連續為0的長度為34或34以上，統計累積此〝長位元重複值〞，共計2項測試(包含1和0的測試)，若此兩項統計值其中一項不為0，則此項亂數測試不通過。

五、研究結果

以實際例子來說:輸入密碼為: chaos

輸入明文為: Quantum mechanics is the basis for all modern descriptions of the structure and behaviour of matter.

(一)加密:

假設尼歐欲加密一段明文m(k) = (m1,m2,…,mk)給崔妮蒂，並且輸入密碼h(i) = (h1,h2,…,hk)， 在此5 ≦ i ≦ 200 ; hi代表 ASCII 電腦字元碼，進入電腦LSC密碼系統，其運算過程如下:

1.取得初值:

password=〝chaos〝，h1 代表 c(99)， h_2 代表 h(104)， h3代表 a(97)， h4代表 o(111) ， h5代表s(115)。

((((99)¹⁰⁴)⁹⁷)¹¹¹)¹¹⁵ ≡ 64492 (mod 65537)
99 * 104 * 97 * 111 * 115 ≡ 39292 (mod 65537) 
64492 * 39292 ≡ 90 (mod 109)
99 + 104 + 97 + 111 + 115 ≡ 109 (mod 139)
64492 + 39292 ≡ 5 (mod 13)

2.取得明文m(k) 和明文長度k=800。

3.取得邏輯映射初值條件。

X0 = 0.1 + 0.00001 * 64492 = 0.74492 (0.1∼ 0.75537 )
Y0 = 0.1 + 0.00001 * 39292 = 0.49292 (0.1 ∼ 0.75537 )

μx = 3.63 + 0.001 * 90 = 3.72 (3.63∼ 3.74 )
μy = 3.86 + 0.001 * 109 = 3.969 (3.86 ∼ 4.0 )
t0 = 10 + 5 = 15 (10 ∼ 22 )

如圖(9):

Xn+1=3.72 Xn(1-Xn)，X0=0.74492很多幾次迭代後仍無法進入固定點，屬於週期數為∞的邏輯映射圖，此時出現渾沌現象。

如圖(13):

Yn+1=3.969Yn(1-Yn)，Y0=0.49292很多幾次迭代後仍無法進入固定點，屬於週期數為∞的邏輯映射圖，此時出現渾沌現象。

4.得到亂數序列。讓邏輯映射軌跡從t=0開始演化直到 t ≧ 15，開始取出x,y變數值。亂數序列表示為 U(800)=U1,U2, … U800。

                       10⁷*Xn ≡ Tx(n) (mod 2⁸ )
                       10⁷*Yn ≡ Ty(n) (mod 2⁸ )
Tx(n)♁  Ty(n) ≡ H(n)
                        H(1) ≡ U1,U2,… U8
                        H(2) ≡ U9,U10,… U16                                               (4) U1,U2…U800為產生的亂數序列。

5.產生密文 Ck.

 m^k ♁ Uk ≡ Ck

(二)解密:如上述加密的步驟。

六、討論

(一)FIPS PUB 140-1亂數檢測:

1.邏輯映射圖Xn+1=μXn(1-Xn)，X0=0.2在經由FIPS PUB 140-1亂數檢測，如圖(17)，μ=3.5到 4，共16項亂數測試全部通過為T=16或T=-16(一項測試通過為1，二項測試通過為2,…,T=-16和T=16意義相同，方便圖形對稱比較)，明顯看出有四區可以通過測試， 米=3.55 到4三條測試不過範圍，表示再次出現穩定倍週期現象，故無法通過亂數測試。

2.邏輯映射圖在單一位元總和亂數測試，如圖(18): μ=3.5 到4，明顯看出有三條測試不過範圍，表示再次出現穩定倍週期現象，故無法通過亂數測試， 9,654 < X < 10,346。

3.邏輯映射圖在樸克亂數測試，如圖(19): μ=3.5 到4， 明顯看出有四區可以通過測試，三條測試不過範圍，表示再次出現穩定倍週期現象，故無法通過亂數測試，1.03 < X < 57.4。

4.亂數映射遞迴圖如圖(12)，混亂而無法辨別軌跡，可以確保LSC系統的安全性。

(二)邏輯映射圖固定點穩定性分析及倍週期分叉圖米範圍計算:

1.邏輯映射圖方程式及微分後斜率m方程式如下:

                    f(Xn) = Xn+1  = μ *Xn(1-Xn), Xn  [0,1] ,μ [0,4]
                    f(Xn)' = Xn+1' = μ-2μXn                                               (5)

2.固定點穩定性分析:

定義固定點為Xf

所以圖(4),屬於週期數為2的邏輯映射圖(xf=0.48和0.83)。倍週期分叉μ出現範圍分析:

4.定義倍週期斜率m,兩個固定點為p, q:
  

   m=μ2(1-2p)(1-2q)                                                                                                               (12)                             

將方程式(17)之固定點帶入方程式(19),可得
                   m=μ²(1-2p)(1-2q)= μ²[1-2(p+q)+4pq]
                   m= -μ²+2μ+ 4
                  |m| ≦ 1, |-μ²+2μ+ 4| ≦ 1
                   3 ≦μ≦ 1+  
                   3 ≦μ≦ 3.4494897                                                (13)
由上可知,2倍週期分叉米出現範圍為3≦米≦3.4494897,如圖(8): 2倍週期分叉出現在μ=3 ∼ 3.45,且固定點有兩個。

(三)邏輯映射串流加密系統(LSC)加解密速度分析:

如下表,加解密速度最快約為19456bytes/s,也就是155648 bites/s,也等於152 kbits/s。

CPU	作業平台	加密	解密
Pentium(ｋ)450	Windows98	152	152

(四)Return map 檢測:

１．圖(11):

代表方程式 Xn+1=3.72 Xn(1-Xn),X0=0.74492之Xn遞迴映射圖,由圖形可知Xn序列會分布在拋物線上。

２．圖(12):

代表在上述方程式下,R(n) ≡ X(n) (mod 256),在經過模運算後所得亂數序列R(n)遞迴映射圖,由圖形可發現亂數序列R(n)沒有一定之週期。

３．圖(15):

代表方程式yn+1=3.969 yn(1-yn),y0=0.49292之yn遞迴映射圖,由圖形可知yn序列會分布在拋物線上。

４．圖(16):

代表在上述方程式下,R(n) ≡ y(n) (mod 256),在經過模運算後所得亂數序列R(n)遞迴映射圖,由圖形可發現亂數序列R(n)沒有一定之週期。

(五)LSC密碼系統抵抗〝暴力攻擊法〞數值值域範圍:

以輸入密碼字數而言,LSC可輸入密碼字數為5 ∼200個字(猜出password:機率約1/2¹⁶⁰⁰,顯然優於傳統4 ∼ 6字元機率約1/2⁴⁸,而以輸入起始值參數範圍為五次模運算中質數相乘之乘積65537*65537*109*139*13,猜出起始值機率約為1/2⁵⁰,一般來說LSC加解密系統是已經編譯成電腦執行檔,所以使用者使用時並須先面對輸入密碼的檢測,是以LSC仍優於傳統密碼系統加解密的方式。

七、結論

一個渾沌系統意謂著在相空間中的數值軌跡演化會展現非週期性、複雜、和對初值敏感的現象。根據邏輯映射圖的渾沌性質,我們詳述一個簡單的亂數產生器,利用適當的模運算,乘法運算,截掉小數處理,LSC系統所產生之亂數可用來當作加解密金鑰(key)。在本文中,我們示範遞迴運算(return map)分析邏輯映射圖並了解其無週期性,再利用FIPS PUB 140-1亂數檢測方式證明亂數具有高度的安全性。LSC加解密系統可適用於任何文件之加解密,如各式中英文檔案,圖形檔,執行檔等,使用LSC加解密系統有容易完成、高隱密性、高效率、安全性高可抵抗竊密者等優點。

八、參考資料及其他

(一)參考資料:

(1)楊吳泉.現代密碼學入門與程式設計.全華出版社.1996

(2)James Cleick , 林和　譯.渾沌.天下文化.1997

(3)閔嗣鶴,嚴士健.初等數論.凡異出版社.1993

(4)美國密碼模組(FIPS 140-1)檢驗認證講習會手冊.中華民國資訊安全學會.1999年四月.

(5)劉秉正,非線性動力學與渾沌基礎},徐氏基金會.1994

(6)E. Ott  Chaos in Dynamical Systems}. Cambridge Univ. Press. 1993.

(7)Brauce Schneier  Applied Cryptography:Protocols,Algorithms, and Source Code in C,seconded. John Wiley \& Sons, Inc. 1994.

(8)R.A. Rueppel  Analysis and Design of Stream Ciphers. Springer--Verlag Berlin, Heidelberg. 1986.

評語