崔圓圓 北京郵電大學(xué)電子信息工程專業(yè) 100876

基于模式與熵的隨機(jī)序列研究

崔圓圓 北京郵電大學(xué)電子信息工程專業(yè) 100876

本文從雙色球開獎(jiǎng)結(jié)果出發(fā)，探討真隨機(jī)序列中暗含的“模式”：真隨機(jī)序列有時(shí)表現(xiàn)得并不那么“隨機(jī)”。這是因?yàn)槿藗冋J(rèn)為，隨機(jī)應(yīng)是無序的。事實(shí)證明，并非如此。另一方面，人為產(chǎn)生的偽隨機(jī)序列，大多經(jīng)過了消除重復(fù)的步驟以使序列本身較為“隨機(jī)”——看起來是無序的。本文使用Mersenne Twis算ter 法產(chǎn)生偽隨機(jī)序列，測(cè)試這種人為因素對(duì)隨機(jī)序列統(tǒng)計(jì)特性的影響。為了進(jìn)一步研究“無序”序列與隨機(jī)序列的差異，本文基于熵，提出了一種簡(jiǎn)便的偽隨機(jī)數(shù)發(fā)生器。通過對(duì)有序序列進(jìn)行次數(shù)可控的交換來逐步實(shí)現(xiàn)無序化。對(duì)無序化后的序列進(jìn)行均勻性和圖像加密測(cè)試。通過無序的方法產(chǎn)生的序列，其隨機(jī)性在一定范圍內(nèi)是可以信賴的。

真?zhèn)坞S機(jī)序列;模式;熵 ;Mersenne Twister算法;圖像加密

1.形形色色的隨機(jī)數(shù)

在自然界和人類社會(huì)中存在著兩類現(xiàn)象，確定性現(xiàn)象和非確定性現(xiàn)象。前者在一定條件下必然發(fā)生；對(duì)于后者，其結(jié)果的樣本空間非但并不唯一，大多數(shù)時(shí)候甚至難以計(jì)量。非確定性現(xiàn)象，或者說隨機(jī)現(xiàn)象，經(jīng)過大量的重復(fù)試驗(yàn)或觀察，總能表現(xiàn)出一定的統(tǒng)計(jì)規(guī)律性。隨機(jī)數(shù)根據(jù)其產(chǎn)生機(jī)理，可分為兩種：真隨機(jī)數(shù)與偽隨機(jī)數(shù)。前者由物理采樣方法得到，后者來自于數(shù)學(xué)計(jì)算。

2.隨機(jī)序列與模式

2.1 真隨機(jī)數(shù)及其特征

真隨機(jī)數(shù)源有很多，包括人為隨機(jī)源、設(shè)備隨機(jī)源、電路中的熱噪聲和散粒噪聲，等等。電腦的操作系統(tǒng)就能夠?qū)崿F(xiàn)對(duì)如鍵盤隨機(jī)性、鼠標(biāo)隨機(jī)性、中斷隨機(jī)性等的統(tǒng)一控制，以產(chǎn)生符合要求的隨機(jī)數(shù)。即使是真隨機(jī)數(shù)發(fā)生器的設(shè)計(jì)者，也不可能知道實(shí)際生成的隨機(jī)序列的內(nèi)容，生成的隨機(jī)數(shù)是真正無法預(yù)測(cè)的。

2.2 真隨機(jī)與假模式

2.2.1 預(yù)測(cè)的模式

隨機(jī)現(xiàn)象的本質(zhì)是不確定性。研究表明，“我們?cè)诓淮_定局面下進(jìn)行評(píng)估和選擇時(shí)，常常會(huì)依賴于直覺”。面對(duì)隨機(jī)序列，我們所要做出的判斷并不會(huì)威脅自身的安全，僅僅是個(gè)小小的判斷。這時(shí)候，模式的思維就占了上風(fēng)。

2.2.2 雙色球中的幸運(yùn)

在中國，目前雙色球是一種較流行的博彩方式：投注區(qū)分為紅球號(hào)碼區(qū)和藍(lán)球號(hào)碼區(qū)，紅球號(hào)碼范圍為01～33，藍(lán)球號(hào)碼范圍為01～16。雙色球每期從33個(gè)紅球中開出6個(gè)號(hào)碼，從16個(gè)藍(lán)球中開出1個(gè)號(hào)碼作為中獎(jiǎng)號(hào)碼，雙色球玩法即是競(jìng)猜開獎(jiǎng)號(hào)碼的6個(gè)紅球號(hào)碼和1個(gè)藍(lán)球號(hào)碼，順序不限?？紤]到16是2的四次冪，便于后文的二進(jìn)制計(jì)算，本文取每一期的藍(lán)球號(hào)碼作為真隨機(jī)序列。

毫無疑問，每一次的藍(lán)球數(shù)字都是隨機(jī)產(chǎn)生的?，F(xiàn)在，讓我們?cè)賮砜纯辞耙还?jié)所提到的ABCDE五個(gè)數(shù)字序列。印象中最為隨機(jī)不可預(yù)測(cè)的序列，竟然表現(xiàn)出了驚人的“模式”。不得不相信，這些模式，僅僅是湊巧的結(jié)果。一方面，概率學(xué)的知識(shí)告訴我們，產(chǎn)生任何一種排列，都是有可能的，而這些模式，只是無數(shù)可能排列中的一種而已；另一方面，真隨機(jī)序列，原來有時(shí)候看起來并不那么“隨機(jī)”。

2.2.3 統(tǒng)計(jì)性驗(yàn)證

用于描述隨機(jī)序列的兩個(gè)主要指標(biāo)就是期望和方差。數(shù)學(xué)期望體現(xiàn)了隨機(jī)變量的真正平均，而方差則代表隨機(jī)變量的取值與其方差的偏離程度。

對(duì)于理想的從1～16等可能取值的隨機(jī)序列，其數(shù)學(xué)期望和方差分別為：

取最近200期的藍(lán)球開獎(jiǎng)結(jié)果，計(jì)算其平均值與方差：

可見，即使沒有數(shù)量龐大的樣本（只取了200個(gè)），真隨機(jī)序列在統(tǒng)計(jì)特性上的表現(xiàn)，仍是十分優(yōu)越的。真隨機(jī)序列中暗含的“模式”，讓它看起來不那么隨機(jī)了。

2.3 偽隨機(jī)序列

與真隨機(jī)序列相對(duì)的，就是假隨機(jī)序列。一般計(jì)算機(jī)中使用的偽隨機(jī)序列，都是通過遞推公式計(jì)算得來。這種生成裝置，稱為偽隨機(jī)數(shù)發(fā)生：由一個(gè)初始狀態(tài)（種子）開始，通過一個(gè)確定的算法來生成隨機(jī)數(shù)。

另一種廣泛使用的PRNG，是Mersenne Twister算法（馬特賽特旋轉(zhuǎn)演算法）。

1997 年，松本和西村開發(fā)了這一基于有限二進(jìn)制字段上矩陣線性再生的偽隨機(jī)數(shù)算法。它的算法隨機(jī)性好，易實(shí)現(xiàn)，占用內(nèi)存少，產(chǎn)生隨機(jī)數(shù)的速度快、周期長(zhǎng)，且具有623維均勻分布的性質(zhì)。 在MATLAB v7.7 及以上版本中，通過調(diào)用RandStream類，就能產(chǎn)生基于MT的偽隨機(jī)數(shù)。

2.4 兩種隨機(jī)數(shù)的比較

將Matlab自帶的隨機(jī)序列生成器設(shè)為“mt19937ar”，便可以得到基于MT算法的偽隨機(jī)序列。為了與雙色球的真隨機(jī)數(shù)作比較，產(chǎn)生多組200個(gè)同區(qū)間均勻分布的偽隨機(jī)數(shù)。計(jì)算數(shù)學(xué)期望與方差，可得：

可以看到，Matlab產(chǎn)生的偽隨機(jī)數(shù)偏離理想均值8.5的程度比雙色球大，其波動(dòng)卻相對(duì)較小。

使用隨機(jī)數(shù)生成算法連續(xù)生成的2 0 0個(gè)隨機(jī)數(shù)，耦合成199個(gè)像素坐標(biāo)值。Dn表示第n個(gè)像素點(diǎn)，以此衡量數(shù)據(jù)的均勻性。作圖后可見，兩者的均勻性相似。如果取值空間更大，而不是1至16，應(yīng)當(dāng)會(huì)出現(xiàn)一定的差異。

3.基于熵的偽隨機(jī)序列發(fā)生器

3.1 物理熵

1850 年，德國物理學(xué)家魯?shù)婪颉た藙谛匏故状翁岢鲮氐母拍?，用來表示任何一種能量在空間中分布的均勻程度。一個(gè)體系的能量完全均勻分布時(shí)，這個(gè)系統(tǒng)的熵就達(dá)到最大值。系統(tǒng)的熵，只能逐漸增大或保持不變，而不可能逐漸減小。在物理學(xué)中，熵代表著系統(tǒng)的無序性。越是均勻無序的系統(tǒng)，其熵值越大。

3.2 信息熵

信息論的創(chuàng)始人香農(nóng)，率先將熵的概念進(jìn)行了泛化，引入信息熵。對(duì)于有限離散隨機(jī)變量集合，當(dāng)集合中的等概率發(fā)生時(shí)，熵達(dá)到最大值。對(duì)于隨機(jī)序列，當(dāng)取值均勻分布時(shí)，熵達(dá)到最大值。熵標(biāo)志著系統(tǒng)的無序性，當(dāng)序列變得無序，熵也不斷增大，逼近均勻分布。

3.3 基于熵的發(fā)生器

構(gòu)建一個(gè)序列，由四個(gè)從0到255的連續(xù)升序排列（0,1,2,...255）組成。顯然，這一序列是非常有序的。根據(jù)前一小節(jié)的分析，如果不斷打亂其排序，序列的熵就會(huì)不斷增加，逼近最大值。這時(shí)，就有可能得到了一個(gè)偽隨機(jī)序列。

在原序列基礎(chǔ)上，每次隨機(jī)選取兩個(gè)序號(hào)，交換其值，進(jìn)行實(shí)驗(yàn)。根據(jù)期望和方差的定義，由于打亂后的序列，其各個(gè)數(shù)字的數(shù)量維持在4不變，因此均值和方差與理想序列相同。

3.3.1 均勻性測(cè)試

按照第二部分中介紹過的均勻性衡量方法，取序列的前256個(gè)值作圖。記k為交換的次數(shù)，分別做出k=0,100,200,300, 400,500時(shí)的均勻性分布圖。

未做交換時(shí)，原圖是一條直線。隨著k的值不斷增大，點(diǎn)越來越分散。k=500時(shí)，仍能看出原圖的痕跡。對(duì)于使用這種擾亂的方法構(gòu)造的1024個(gè)數(shù)字組成的序列，在交換500次時(shí)，隨機(jī)性仍不理想。

當(dāng)交換次數(shù)達(dá)到600時(shí)，點(diǎn)的分布已找不到原始的規(guī)律；隨著交換不斷增加，均勻性狀況不再改變。對(duì)于一個(gè)長(zhǎng)度為2n的序列，交換n次時(shí)，可基本無序。

3.3.2 無序程度測(cè)試

在未進(jìn)行交換時(shí)，1024個(gè)點(diǎn)，每個(gè)都在自己的初始位置。現(xiàn)每交換100次后，測(cè)試仍在初始位置的點(diǎn)的個(gè)數(shù)，它表現(xiàn)出了明顯的下降趨勢(shì)，并且在3200次之后開始波動(dòng)，不再單一遞減?？梢酝茰y(cè)，對(duì)于長(zhǎng)為n的序列，當(dāng)交換3n次時(shí)，無序狀況基本穩(wěn)定。

3.3.3 圖像加密測(cè)試

以大小為256×256的256級(jí)灰度的Lena圖像為例，明文為是一個(gè)256×256的8bit的2進(jìn)制矩陣，通過reshape整合運(yùn)算，將算法生成的隨機(jī)數(shù)轉(zhuǎn)換成為一個(gè)256×256的密鑰矩陣，然后再將明文矩陣與密鑰矩陣按位異或。當(dāng)交換次數(shù)改變時(shí)，加密效果有所不同。交換400次后，仍能看出原圖的痕跡；交換800次后，逐漸變得模糊；交換1200次后，已經(jīng)完全看不出Lena的樣子了。對(duì)于一個(gè)長(zhǎng)度為n的序列，進(jìn)行n次交換后，已達(dá)到較好的圖像加密效果。

[1]胡細(xì)寶,孫洪祥,王麗霞.概率論·隨機(jī)過程·數(shù)理統(tǒng)計(jì).北京郵電大學(xué)出版社.2004年2月,第一版

[2]列納德·蒙洛迪諾[英]著；郭斯羽譯.醉漢的腳步——隨機(jī)性如何主宰我們的生活.湖南科學(xué)技術(shù)出版社.2010年6月,第一版

10.3969/j.issn.1001-8972.2011.11.012

崔圓圓，北京郵電大學(xué)電子信息工程專業(yè)本科生，在讀。