利用破坏自格函数的平滑性设计之乱数产生器

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

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

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

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

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

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

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

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

9、自格係數。二、 給定二位元亂數序列的長度N。亂數序列的長度以及種子的長度會決定要疊代的次數。三、 若不進行任何的疊代，那麼離散的序列其長度就是L。我們定義自格係數序列為，是序列在兩兩數值中插入0的新序列。舉例來說，假若是(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。每增加一個指標，序列的長度就是前一項長度的兩倍減一。因此，的長度就是。計算的方法非常簡單，就是，這裡的符號代表捲積運算。經過計算後可以得到序列長度是。當第二個步驟中所要求的亂數序列長度決定之後，就可以決定出需要疊代的次數k，使得k 滿足。四、 從序列中

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

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

12、個不重疊長度是m 的片段。因為每一個片段都是長度為m 的二位元序列，因此每一個片段都可以對應一個0到的整數，我們定義，依序為這個集合的元素。 Poker test 是檢驗這個數字出現的頻率是否一致。我們定義變數，則會依循階的卡方分配。當時，Poker test 剛好退化為先前介紹的Frequency test。四、 Runs Test定義是連續出現個1 的個數，大寫B 代表Block。是連續出現個0 的個數，大寫G 代表Gap。是或的期望值，對應長度為n 的亂數序列。假定k是最大的連續出現0或1的個數，並且假設k>5。那麼變數滿足2k-2 階的卡方分配。五、 Autocorrelatio

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

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

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

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

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

18、下第40至48個位元可以得到最佳的亂度序列。參考文獻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