利用破壞自格函數(shù)的平滑性設(shè)計(jì)之亂數(shù)產(chǎn)生器

1、利用破壞自格函數(shù)的平滑性設(shè)計(jì)之亂數(shù)產(chǎn)生器曾正男1, 陳以德2*1中央研究院 基因體研究中心2高雄醫(yī)學(xué)大學(xué) 醫(yī)療資訊管理系電子郵件 : 1jengnan, 2.tw摘要自格函數(shù) (scaling function) 是建構(gòu)小波基底 (wavelet basis) 低頻空間的函數(shù)，該函數(shù)的特性是他可以被用函數(shù)本身的縮小和平移的線性組合將自己建構(gòu)回來(lái)，故名為自格函數(shù)。在小波理論的應(yīng)用上，要保證自格函數(shù)具有某種平滑度時(shí)，決定自格函數(shù)的係數(shù)，需要滿足一些特定的條件。給定一組自格係數(shù)，就唯一決定一自格函數(shù)，因此可以利用不滿足自格係數(shù)平滑度的係數(shù)當(dāng)作亂數(shù)產(chǎn)生的種子，來(lái)產(chǎn)生

2、不收斂的自格函數(shù)，進(jìn)而發(fā)展出一套無(wú)法預(yù)測(cè)的亂數(shù)序列。關(guān)鍵詞：亂數(shù)產(chǎn)生器、擬亂數(shù)、亂度驗(yàn)證、FIPS 140-2、FIPS 800-22 壹、前言小波理論(Wavelet theory) 最早是由 Morlet 和 Grossman 在1980年代提出。之後在Ingrid Daubechies 於1992年提出一系列的正交小波基底以及離散小波轉(zhuǎn)換之後，該理論在計(jì)算科學(xué)領(lǐng)域立即掀起一陣風(fēng)潮，許多對(duì)應(yīng)於傅氏理論(Fourier theory) 的應(yīng)用與論文不斷地被提出與討論。和傅氏轉(zhuǎn)換類似，小波轉(zhuǎn)換可以把時(shí)間域的資料轉(zhuǎn)換到頻率域，但由於小波的基底涵蓋是有限長(zhǎng)度的(compact supported)

3、，所以小波函數(shù)有同時(shí)精準(zhǔn)刻劃時(shí)間域和頻率域的特性，因此在某些應(yīng)用領(lǐng)域，小波轉(zhuǎn)換更優(yōu)於傅氏轉(zhuǎn)換。也由於小波是一個(gè)有限長(zhǎng)度的函數(shù)，相較於傅氏基底是無(wú)限長(zhǎng)的周期函數(shù)，小波因此被命名。小波理論最常被使用在訊號(hào)處理，特別是對(duì)於保有某種平滑度的資料來(lái)說，小波可以提供很精簡(jiǎn)的表示方法，因此該技術(shù)被大量使用在影像的壓縮以及去除雜訊。近年來(lái)常見的H.264檔案格式的動(dòng)態(tài)影像儲(chǔ)存技巧就是利用小波理論。在微分方程領(lǐng)域小波理論也佔(zhàn)有重要的地位，由於小波基底的涵蓋是有限長(zhǎng)度並且相互正交，因此應(yīng)用在有限元素法時(shí)，所求解的矩陣是一個(gè)對(duì)角矩陣，有別於使用其他基底的稀疏矩陣。詳細(xì)的情形不在此多作說明，有興趣了解更多關(guān)於小波理論

4、應(yīng)用的讀者請(qǐng)參考4 6。小波函數(shù)具有特定的平滑程度，那麼自格係數(shù)就必須滿足下列幾項(xiàng)條件。第一，；第二，。當(dāng)?shù)诙€(gè)條件成立時(shí)，剛好是一個(gè) m 階的多項(xiàng)式。若我們刻意讓 不滿足上述兩個(gè)條件，我們便無(wú)法造出一個(gè)屬於的自格函數(shù)，這樣的函數(shù)將不會(huì)是一個(gè)平滑的函數(shù)，甚至於連續(xù)性也會(huì)被破壞。因此，我們期待用這樣的一個(gè)觀點(diǎn)，來(lái)製造出一個(gè)怪異的，不平滑，不連續(xù)的函數(shù)。透過擷取函數(shù)值在二進(jìn)位表示法中的特定位元來(lái)製造出 0，1亂數(shù)序列。貳、小波函數(shù)建構(gòu)小波基底的一個(gè)重要函數(shù)我們稱為自格函數(shù)(Scaling function)，它的特性是函數(shù)本身可以被自己的縮小的平移函數(shù)的線性組合重組回來(lái)，故名自格函數(shù)。自格函數(shù)的數(shù)

5、學(xué)表示為 (1)，這個(gè)等式稱為自格等式，其中稱為自格係數(shù)。非零的自格係數(shù)個(gè)數(shù)決定自格函數(shù)的涵蓋。在小波理論中，的積分不為零，因此，我們也將自格函數(shù)視為一個(gè)低頻濾波器。觀察一下 (1)的定義，是的縮小一半並且向右平移n個(gè)單位，因此在低解析度的函數(shù)可以被高解析度的所展開。若我們定義，(2)則成為一組多重尺度分析空間序列。若我們希望的聯(lián)集是，並且讓小波函數(shù)具有特定的平滑程度，那麼自格係數(shù)就必須滿足下列幾項(xiàng)條件。第一，； (3)第二，。 (4)當(dāng)?shù)诙€(gè)條件成立時(shí)，剛好是一個(gè) m 階的多項(xiàng)式。為了取得發(fā)散的Wavelet，我們刻意讓 不滿足上述兩個(gè)條件，便無(wú)法造出一個(gè)屬於的自格函數(shù)，這樣的函數(shù)將不會(huì)是一

6、個(gè)平滑的函數(shù)，甚至於連續(xù)性也會(huì)被破壞。因此，我們用這樣的一個(gè)觀點(diǎn)，來(lái)製造出一個(gè)怪異的、不平滑、不連續(xù)的函數(shù)。並透過擷取函數(shù)值在二進(jìn)位表示法中的特定位元來(lái)製造出 0，1亂數(shù)序列。要求取自格函數(shù)的函數(shù)值其過程非常容易。在假定自格函數(shù)屬於時(shí)，假想在最高解析度的空間自格函數(shù)函數(shù)，這裡的函數(shù)指的是 Dirac delta 函數(shù)。透過自格函數(shù)自己可以把自己建構(gòu)回來(lái)的特性，裡的就是用自格係數(shù)的線性組合。在實(shí)際計(jì)算上，我們用衝激函數(shù)（impulse function）來(lái)代替函數(shù)。因此，從高解析度空間的計(jì)算低解析度空間的的精緻表示，只要使用高解析度的離散表示與自格係數(shù)的捲積（convolution）就可以得到。

7、一般來(lái)說，為了配合每增加一次疊代計(jì)算就得到多一倍的含數(shù)值，所使用的自格係數(shù)每疊代一次就要在係數(shù)與係數(shù)之間插入0值。配合所需要的解析度，經(jīng)過幾次疊代之後所得到的值需要作整體高度的修正。因?yàn)楫?dāng)屬於時(shí)，的積分值為1，我們可以利用這一個(gè)特性來(lái)調(diào)整函數(shù)的整體高度。下圖一是自格係數(shù)(1,3,3,1)/4所對(duì)應(yīng)的自格函數(shù)圖形，這組係數(shù)滿足屬於的條件，所以圖一的函數(shù)圖形是一個(gè)平滑的函數(shù)。圖一、以（1,3,3,1）/4 為自格係數(shù)所造成的自格函數(shù)圖二是由自格係數(shù)(9,-3,7,-1)/6所產(chǎn)生的函數(shù)圖形。由於此組係數(shù)不滿足屬於的條件，所以，對(duì)應(yīng)的函數(shù)不是一個(gè)平滑函數(shù)。我們就是要利用這種特性來(lái)製作一個(gè)亂數(shù)產(chǎn)生器。

8、圖二、以(9,-3,7,-1)/6為自格係數(shù)所造成的自格函數(shù)一個(gè)決定性的二位元亂數(shù)產(chǎn)生器是指若給定相同的亂數(shù)種子，便可以得到同樣的二位元亂數(shù)序列。給定自格係數(shù)便唯一決定自格函數(shù)的函數(shù)值的特性，正好可以被利用到製作決定性的亂數(shù)產(chǎn)生器。要確認(rèn)此方法可以用在決定性的二位元亂數(shù)產(chǎn)生器上，我們還需檢查所產(chǎn)生的二位元亂數(shù)序列是否通過二位元亂數(shù)序列的檢驗(yàn)。下列章節(jié)我們會(huì)更詳細(xì)的介紹利用破壞自格函數(shù)平滑度來(lái)製作二位元亂數(shù)的過程，並且展示他通過二位元亂數(shù)檢驗(yàn)的能力。參、演算流程一、 給定一有限長(zhǎng)度L 的亂數(shù)向量，例如長(zhǎng)度是10從高斯分佈中擷取的亂數(shù)。此亂數(shù)用來(lái)當(dāng)作我們二位元亂數(shù)產(chǎn)生器的種子，也是製造自格函數(shù)值的

9、自格係數(shù)。二、 給定二位元亂數(shù)序列的長(zhǎng)度N。亂數(shù)序列的長(zhǎng)度以及種子的長(zhǎng)度會(huì)決定要疊代的次數(shù)。三、 若不進(jìn)行任何的疊代，那麼離散的序列其長(zhǎng)度就是L。我們定義自格係數(shù)序列為，是序列在兩兩數(shù)值中插入0的新序列。舉例來(lái)說，假若是(1,3,3,1)/8那麼就是(1,0,3,0,3,0,1)/8，是(1,0,0,0,3,0,0,0,3,0,0,0,1)/8。每增加一個(gè)指標(biāo)，序列的長(zhǎng)度就是前一項(xiàng)長(zhǎng)度的兩倍減一。因此，的長(zhǎng)度就是。計(jì)算的方法非常簡(jiǎn)單，就是，這裡的符號(hào)代表捲積運(yùn)算。經(jīng)過計(jì)算後可以得到序列長(zhǎng)度是。當(dāng)?shù)诙€(gè)步驟中所要求的亂數(shù)序列長(zhǎng)度決定之後，就可以決定出需要疊代的次數(shù)k，使得k 滿足。四、 從序列中

10、依序取出前N 個(gè)序列來(lái)，將此實(shí)數(shù)的子序列用二進(jìn)位科學(xué)記號(hào)來(lái)表示，取小數(shù)點(diǎn)以下第T 個(gè)位數(shù)來(lái)代表我們的二位元亂數(shù)序列的，即為所求。圖三是計(jì)算二進(jìn)位亂數(shù)的流程圖。以上四個(gè)步驟是我們所提出產(chǎn)生決定性二位元亂數(shù)序列的方法。我們用 B 表示我們的亂數(shù)產(chǎn)生器，則所產(chǎn)生的亂數(shù)序列 b 可表示成的函數(shù)。接下來(lái)我們要討論種子S 與取位T 對(duì)亂數(shù)序列b 的影響。圖三，計(jì)算亂數(shù)序列的流程肆、亂度驗(yàn)證為了要驗(yàn)證我們的二位元亂數(shù)產(chǎn)生器所生產(chǎn)的亂數(shù)序列是否真的滿足亂度的驗(yàn)證，我們需要對(duì)亂數(shù)序列作一些基本的檢驗(yàn)。檢驗(yàn)亂度的方法與標(biāo)準(zhǔn)有很多，在此我們僅引用15文章中所提到的五個(gè)驗(yàn)證標(biāo)準(zhǔn)來(lái)檢驗(yàn)我們的亂數(shù)序列。以下是這五個(gè)驗(yàn)證法

11、的簡(jiǎn)介：一、 Frequency(Monobit) Test這個(gè)測(cè)試是驗(yàn)證亂數(shù)序列中，0出現(xiàn)的個(gè)數(shù)與1出現(xiàn)的個(gè)數(shù)是否接近。若我們假設(shè)是亂數(shù)序列的長(zhǎng)度，是出現(xiàn)0的個(gè)數(shù)，是出現(xiàn)1的個(gè)數(shù)，當(dāng)我們定義時(shí)，在大於10的條件下，會(huì)接近一階的卡方分配。二、 Serial test(two-bit-test)這個(gè)測(cè)試是驗(yàn)證亂數(shù)序列中， 00，01，10和11數(shù)對(duì)出現(xiàn)的頻率是否接近。我們定義變數(shù)，其中是數(shù)對(duì)00出現(xiàn)的個(gè)數(shù)，是數(shù)對(duì)01出現(xiàn)的個(gè)數(shù)，是數(shù)對(duì)10出現(xiàn)的個(gè)數(shù)以及是數(shù)對(duì)11出現(xiàn)的個(gè)數(shù)。當(dāng)大於21的條件下，會(huì)接近二階的卡方分配。三、 Poker test假設(shè)m 是一個(gè)滿足的正整數(shù)，並且。我們把亂數(shù)序列切成k

12、個(gè)不重疊長(zhǎng)度是m 的片段。因?yàn)槊恳粋€(gè)片段都是長(zhǎng)度為m 的二位元序列，因此每一個(gè)片段都可以對(duì)應(yīng)一個(gè)0到的整數(shù)，我們定義，依序?yàn)檫@個(gè)集合的元素。 Poker test 是檢驗(yàn)這個(gè)數(shù)字出現(xiàn)的頻率是否一致。我們定義變數(shù)，則會(huì)依循階的卡方分配。當(dāng)時(shí)，Poker test 剛好退化為先前介紹的Frequency test。四、 Runs Test定義是連續(xù)出現(xiàn)個(gè)1 的個(gè)數(shù)，大寫B(tài) 代表Block。是連續(xù)出現(xiàn)個(gè)0 的個(gè)數(shù)，大寫G 代表Gap。是或的期望值，對(duì)應(yīng)長(zhǎng)度為n 的亂數(shù)序列。假定k是最大的連續(xù)出現(xiàn)0或1的個(gè)數(shù)，並且假設(shè)k>5。那麼變數(shù)滿足2k-2 階的卡方分配。五、 Autocorrelatio

13、n test這個(gè)測(cè)試主要在檢查一個(gè)亂數(shù)序列和他本身平移後所成的序列的相關(guān)性。假設(shè)d 是一個(gè)正整數(shù)，其中。在亂數(shù)序列s 中不同於平移後的位元組個(gè)數(shù)為，其中運(yùn)算符號(hào)代表XOR運(yùn)算。我們定義變數(shù)，在n-d>10 的條件下，變數(shù)滿足N(0,1) 分佈。以上介紹的五種亂度的驗(yàn)證方法是1所提出的基本驗(yàn)證方法，驗(yàn)證的方法並不只限定於這幾種方式，若是提出的亂數(shù)產(chǎn)生器滿足這五種驗(yàn)證條件，也不代表亂數(shù)序列真的無(wú)法被預(yù)測(cè)5。這只是提供我們信心，來(lái)反應(yīng)亂數(shù)序列的亂度有達(dá)到一定程度的方式。其他驗(yàn)證亂數(shù)序列亂度的方法，請(qǐng)參見2 3。伍、亂度模擬測(cè)試我們使用 Matlab 來(lái)產(chǎn)生我們的亂數(shù)產(chǎn)生器所模擬出來(lái)的亂數(shù)，對(duì)於

14、每一個(gè)測(cè)試我們重複1000個(gè)模擬，自格係數(shù)的產(chǎn)生是由 N(0,1) 亂數(shù)選取，亂數(shù)序列的長(zhǎng)度，我們定在長(zhǎng)度為20000的長(zhǎng)度。我們分別對(duì)下列幾點(diǎn)做出討論。第一，自格係數(shù)的長(zhǎng)度是否對(duì)亂度產(chǎn)生影響；第二，使用自格函數(shù)值的第幾個(gè)二進(jìn)位表示來(lái)產(chǎn)生亂數(shù)可以得到最好的亂度。首先，我們探究第一個(gè)問題。我們固定取自格函數(shù)小數(shù)點(diǎn)以下第46個(gè)位元來(lái)作為我們的亂數(shù)。作為種子的自格係數(shù)長(zhǎng)度從2 到11。產(chǎn)生出來(lái)的亂數(shù)我們計(jì)算他們對(duì)上述五種測(cè)試的表現(xiàn)程度，圖四表示對(duì)應(yīng)五種測(cè)試的測(cè)試變數(shù)平均值（即的平均值）。我們把五種測(cè)試表現(xiàn)在同一張圖上，由左至右分別是Frequency test，Serial test，3-bit P

15、oker test，4-bit Poker test，Run test 以及Autocorrelation test。Autocorrelation test 中我們所呈現(xiàn)的數(shù)值是沒有通過測(cè)試的個(gè)數(shù)除以10，這樣的調(diào)整是為了方便將六種結(jié)果清楚的表示在同一個(gè)圖表上。圖形最上方的一條線代表自格係數(shù)長(zhǎng)度是二的種子所產(chǎn)生的測(cè)試平均。在下面一條是自格係數(shù)長(zhǎng)度是三的種子所產(chǎn)生的測(cè)試平均。數(shù)值越低，表示亂數(shù)序列的亂度越佳。再來(lái)的線條是自格係數(shù)長(zhǎng)度是四以上的圖形，由於表現(xiàn)的程度非常相近，我們不特別標(biāo)示在圖形上。我們進(jìn)一步使用T-test 來(lái)確認(rèn)到底自格係數(shù)長(zhǎng)度需要多少才能確保亂度的品質(zhì)。經(jīng)過比較，自格係數(shù)長(zhǎng)度

16、至少大於等於6 可以得到較好的通過率。圖四、不同長(zhǎng)度的自格係數(shù)，對(duì)應(yīng)六種亂度測(cè)試的通過程度比較。接著，我們探討第二個(gè)問題。給定一個(gè)自格係數(shù)長(zhǎng)度（例如，長(zhǎng)度是10），我們利用他對(duì)應(yīng)的自格函數(shù)值的不同位元位置，產(chǎn)生不同的亂數(shù)序列。我們紀(jì)錄小數(shù)點(diǎn)以下第43到第53個(gè)位元，並且計(jì)算他們通過上述五種測(cè)試的表現(xiàn)程度。圖五表示他們對(duì)應(yīng)測(cè)試的平均值。最上面的線條代表用二進(jìn)位表示法取小數(shù)點(diǎn)以下第53個(gè)位元所成的亂數(shù)，接下來(lái)的線條代表取小數(shù)點(diǎn)以下第52個(gè)位元所成的亂數(shù)，再來(lái)是取第51個(gè)位元所成的亂數(shù)。我們看到圖形有下降的趨勢(shì)。在第50個(gè)位元之後的圖形就幾乎混在一起無(wú)法分辨。我們用T-test方法來(lái)測(cè)試，建議使用在

17、40到48個(gè)位元之間所成的亂數(shù)都可以得到不錯(cuò)得亂度。約有96%左右的亂數(shù)序列可以通過每一項(xiàng)測(cè)試。圖五、固定長(zhǎng)度為10的自格係數(shù)，取不同位元組對(duì)應(yīng)六種亂度測(cè)試的通過程度比較。陸、結(jié)論亂數(shù)產(chǎn)生方式分為兩大類：真亂數(shù)產(chǎn)生器(True Random Number Generator, TRNG)及虛擬亂數(shù)產(chǎn)生器(Pseudo Random Number Generator, PRNG)。本文利用破壞自格函數(shù)平滑性的特性，我們可以造出不屬於 的函數(shù)，將這些函數(shù)值的二進(jìn)位表示法抽出，便可成為亂數(shù)序列亦屬PRNG的一種。經(jīng)過實(shí)驗(yàn)觀察我們建議使用自格係數(shù)長(zhǎng)度大於5的種子來(lái)製作亂數(shù)，並且建議取二進(jìn)位表示小數(shù)點(diǎn)以

18、下第40至48個(gè)位元可以得到最佳的亂度序列。參考文獻(xiàn)1 Handbook of Applied Cryptography. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. CRC Press. October 16, 1996. ISBN: 0849385237. pp. 169-190.2 National Institute of Standards and Technology, NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms, January 31, 2005.3 NIST, “For Random and Pseudorandom Number Generator for Cryptographic Application”, Federal Information Processing Standards Pub