TWI269222B - Random number generating method and its equipment with a multiple polynomial - Google Patents

Description

1269222 九、發明說明： 【發明所屬之技術領域】 本發明是有關於一種亂數產生方法及其裝置（Rancj〇m

Humber Generator)，特別是指一種使用複合多項式（Multiple Polynomial-based)之線性反饋位移暫存器技術的亂數產生方 法及其裝置。 【先前技術】 目前一般加密/解密（Encryption/ Decryption)系統之傳送 端在傳送一文件的過程中，常需要將該文件内容以一亂數 產生器產生之亂碼重新編排使資料傳輸時其内容不致於外 沒’因此如何產生無週期性之高隨機度（Rand〇m)的亂碼序 列（Sequence)便顯得格外重要。常見的亂碼產生方法有使用 例如熱雜訊（Thermal Noise)或相位/頻率之變動（Jitter)原理 來產生一真貫隨機序列（Truly Rand〇m Sequence)，或是利用 線性反饋位移暫存器（Linear Feedback Shift Registei ;簡稱 lfsr)、混沌模式（Chaos m〇del)等原理來產生一虛擬亂數序 列（Pseudo Random seqUence)。 如圖1所示，說明使用一線性反饋位移暫存器6的原 理’其中’位移暫存器6可視同使用—單次多項式方程式 ’所使用公式如公式1所示·· χ30+χ5+χ4+χ2+χ 公式 1 首先將輸入樣本（Input Pattern)61中填入一序列 b〇〜by ’並依公式j所示將序列的第3〗、632位元 輸出給- XOR運算子62作x〇R邏輯運算，最後蠢運 5 1269222 九、發明說明： 【發明所屬之技術領域】 本發明是有關於一種亂數產生方法及其裝置（Random Number Generator)，特別是指一種使用複合多項式（Multip]e

Polynomial-based)之線性反饋位移暫存器技術的亂數產生方 法及其裝置。 【先前技術】 目月il 一般加密/解密（Encryption/ Decryption)系統之傳送、 端在傳送一文件的過程中，常需要將該文件内容以一亂數籲 產生裔產生之IL碼重新編排使資料傳輸時其内容不致於外 茂’因此如何產生無週期性之高隨機度（Rand〇m)的亂碼序 列（Sequence)便顯得格外重要。常見的亂碼產生方法有使用 例如熱雜汛（Thermal Noise)或相位/頻率之變動（Jitter)原理 末產生真貝隨機序列（Truly Random Sequence)，或是利用 線性反饋位移暫存器（Lineai· Feedback Shift Register;簡稱 LFSR)、混龙模式（Cha〇s m〇del)等原理來產生一虛擬亂數序 列（Pseudo Rand〇m Sequence)。 鲁 如圖1所示，說明使用一線性反饋位移暫存器6的原 理’其中，位移暫存器6可視同使用一單次多項式方程式 ’所使用公式如公式1所示： x30+x5+x4+x2+x 公式 1 首先’將一輸入樣本（Input Pattern)61中填入一序列 b〇〜b3】，並依公式1所示將序列的第3 1、6、5、3、2位元 輸出給一 XOR運算子62作x〇R邏輯運算，最後x〇R運 1269222 算子62計算出一種子（Seed)位元6〇1，並將該種子位元6〇ι 重新輸入至輸入樣本61序列中的最小位元（Least signifkant BU; LSB)bG以該種子位元601取代。如此循環地將各位元 資料以串列（Serial)的方式作X0R邏輯運算，直到輸入樣本 61的序列内容被加密/解密完成。 就使用LFSR之技術來產生亂數而言，現今共有三種實 現方式：-、將單次多項式LFSR所產生之近似隨機之亂數 結果輸出給複雜的數位電路，用來自我測試（Bui]d_in seif Test)數位電路的輸出入結果是否符合設計需求。二、使用 細胞陣列（Cell Array; CA)的方式實現LFSR電路，用以產生 亂度較大的隨機亂數。三、使用類比式電路來實現lfsr電 路，此種方式相較於前述二種方式可產生較大乱度的乱數 ，然而類比式電路具有不易設計的缺點。 综上所述，目前的LFSR具有下述的缺點： 1.由於單次多項式LFSR以串列的方式作x〇R邏輯運 算只能輸出-位元，導致輸出f料的轉換速率（τ咖·_ Rate)低’無法應用在需要多位元輸出的高速系統之中。 2·如圖2所示，由於單次多項式的硬體邏輯電路並不 能任意更改’而在固定方程式的限制之下，使得I數序列7 將在-定週期内重複出現，因此其特性便容易被破解。 3.使用細胞㈣或類比式電路來實現[舰的方式， 必須花費較大的硬體成本才能達到不易被破解之乱數需求 ，而且電路不易設計。 【發明内容】 1269222 因此，本發明之目的，即在提供—種使用複合多項式 之LFSR技術的數位式亂數產生方法及其裝置。 於是，本發明複合多項式之亂數產生方法，係在一具 有複數位移暫存器之亂數產生器内進行運算以輸出一縫 ’該方法包含下述步驟：⑷在該亂數產生器中建立―複合 式查電路’且該複合式查表電路内建有複數輸入多項式 之對妝表，(B)輸入一選擇訊號以選取該對照表中對應數目 之-輸入多m⑹配合步驟（B)所選取之該輸入多項式 ，在該等位移暫存器中進行線性反饋位移暫存之運算。 本發明亂數產生器包含一選擇單元、一複合式查表電 路二：位移暫存電路及一邏輯閘電路，該選擇單元用以： 出一選擇訊號；該複合式查表電路耦接該選擇單元，且内 建有一具有複數輸人多項式之對照表；該位移暫存電路且 有複數位移暫存器，純該複合式查表電路；該邏輯問電 路耦接該等位移暫存器’在該邏輯閘電路中，是分別對各 X位私暫存益之輸出作邏輯運算，並將運算得到之一種子 序列回授至各該位移暫存器。 a ”猎此，该複合式查表電路接收該選擇單元輸出之選擇 可動態地選取該對照表之一輸入多項式，且該位移 :子Γ路可對應該所選取之該輸人多項式分別對各該位移 曰存器所輸出之該種子序列作邏輯運算。 本^明禝合多項式之亂數產生方法及其裝置可用於產 曰付夕合吳國聯#資訊處理標準（FIPS140-2)之亂數序列，若 卜接例如 AMBA(Advanced Micro-controller Bus 1269222

Architecture)中的 AHB(AdVanced High-Perf0rmance Bus：^ 準Arbiter訊號，亦可由該外接之訊號改變其亂數產生規則 ’更可達到亂度之增加及不可預測性。 【實施方式】 有關本發明之前述及其他技術内容、特點與功效，在 以下配合參考圖式之一較佳實施例的詳細說明中，將可清 楚的呈現。 在說明本發明複合多項式之亂數產生方法之前，先將 本發明亂數產生器1的作用說明如下： 如圖3所示，配數產生器i具有一控制/分配電路u、 一複合式查表電路12、-位移暫存電路（LFSR)13、一邏輯 閘電路14及一選擇單元15。其中，選擇單元Η用以輸出 一選擇訊號15〇;複合式查表電路12内建有複數輸入多項 式之對照表（P〇ly_ial LUT);位移暫存電路13用以執行 位移暫存功能；邏輯閘電路14是對位移暫存電路13之輸 出作邏輯運算，並將運算得到之_種子序们41回授至位 移暫存電路13。 ^中抆制/刀配包路11可輸入一時脈訊號（CLK)1〇1， —重置（Reset)訊號102及一亂數輸出要求（r叫⑽雜號 。該等訊號之作用在於：時脈訊?虎1〇1之每次脈衝是心 使位移暫存電路13之訊號往右移及對於序列之最小位^ ⑽B)進行漁，·重置訊號1G2則是线設定线使其㈣ 錢原先的預設狀態；亂數輸出要求訊號ι〇3則用以設灵 控制/分配電路π輸出端是否產生_乳數輸出訊號1〇4」 1269222 亂數輸出訊號104輸出完成，則控制/分配電路u以輸出一 狀態訊號105顯示完成亂數輸出訊號104之輸出。 而在選擇單元15共有三輸入訊號，分別是一多項式/種 子值致能訊號152(Load Polynomial & Seed)、一真實礼數、身 訊號（Truly Random Source;以下簡稱TRS)154和一取消真 貫亂數源說號（Disable Truly Random Source;以下巧稱 DTRS)156 ’該等訊號之作用說明如下： 多項式/種子值致能訊號152的目的是讓選擇單元15按 照訊號選取多項式，以及選取種子值^⑼句輸入至位移暫存 電路13。當使用者輸入亂數輸出要求訊號1〇3至亂數產生 器1時，若是第一次運算，種子序列141尚未有值（均為〇) 之時，多項式/種子值致能訊號152會把系統預設的一初始 種子值輸入至位移暫存電路丨3中。 TRS訊號154致能時是表示選用一外部訊號產生源， 本實施例是使用AMBA中的AHB標準Arbher訊號，而 DTRS汛唬156之目的是取消以真實亂數源來當作決定多項 式的因子；假設亂數產生器丨是致能TRS訊號154作為決 疋夕項式的因子時，TRS訊號！ 54便接到選擇訊號〗5〇，並 乂 "玄外邛Λ號產生源所提供之訊號隨機地選取多項式；若 疋DTRS訊號156致能的情況下，則隨機分配起始訊號153 便接到選擇訊號150，以亂數產生器1本身所產生之隨機亂 數來選擇多項式（作用容後再述）。 如圖4所不，本實施例中，複合式查表電路12具有複 數查表單凡121〜125，位移暫存電路Η具有位移暫存器 1269222 131〜135，其中，在各查表單元121〜125中各内建複數多項 式之對照表（LUT)如表一所示： 表一 -----— " ~"~ -- 查表單元 121 122 123 124 125 x7 + x3 + x2 + x+1 x7 + x5 + x3 + x+1 x7 + x3 + l x7 + x5 + x4 + x3 + l x7+ x5+ x4 + x3+x2 + x+1 x7 + x+ 1 x7+ x5+ x4 + x3 + x2 + x+l x7 + x6 + x5 + x4 + l x7 + x6 + x5+ x4 + x3 + x2 + x + l x7 + x3+l ^ 癱 x7 + x5 + x3 + x+l x7 + x3+l x7 + x5 + x4 + x3 + l x7 + x3 + x2 + x+l --W- x7 + x3 + x2 + x+l x7+ x5 + x4 + x3 + x2 + x + l X7 + X6 + X5 + X4+l x7 + x6 + x5+ x4 + X3 + X2 + X+1 x7 + x+l x7 + x+l x7 + x3+l x7 + x5 + x4 + x3+l X7 + X3 + X2 + X+1 x7 + x5 + x3 + x+1 x7 + x5 + x3 + x+1 x7 + x6 + x5+ X4 + 1 x7 + x6 + x5+ X、 X3 + X2 + X+l x7 + x+l x7 + x5+x4 + x3 + x2 + x+1 X7 + X6 + X5 + X4+l x7 + x5-fx4+ x3 + 1 X7 + X3 + X2 + X+1 x7 + x5 + x3 + x+l x7 + x3 + l X7 + X5 + X4 + X3’+l x7 + x6 + x5+ x4 + x3 + x2 + x+1 x7 + x + l ---~-- x7+ x5+ x4 + x3 + x2 + x+l ---—-- x7+x6 + x5 + x4 + l —- x7+x6 + x5+ x3+x2 + l 本實施例中，該等位移暫存器131〜135可為d型正反 器（FnP-F1〇P) ’各查表單元121〜125係對應地連接各位移暫 #|§ 131〜135 ’而經過多次測試後，發現該等輸人多項式為 7位元不可再分解之多項式（7-bh Primitive Polynomial)時， ,、所產生序列之亂度為最佳，且可通過Fipsi.2的測試標 10 1269222 準。因此，令各該位移暫存器131〜135之位元數為7,該等 查表單元之數目為M=5 ,總位元之輸出共為M*N=35位元 ，如此，可從總位元M*N=35之輸出中抽取出k=3位元作 為隨機分配起始訊號153之來源；而各查表單元i2i〜125 中的輸入多項式數量為2k=8 因此，若是DTRS訊號156 致能的情況下，則隨機分配起始訊號153便接到選擇訊號 150，k=3位元之選擇訊號15〇可對應地選擇各查表單元 121〜125中8個不同多項式的任一輸入多項式。 此外，若判斷輸入至位移暫存器131〜135之種子序列 s〇〜s4其中有任_值為Q時，則使用㈣的初始種子值加入 種子序列值為〇的該位移暫存器131〜135巾，如此便可避 免王〇的種子值讓位移暫存電路η計算時落入死值(D— alue)而無法使用，若判斷輸人至位移暫存器⑶〜⑴之種 序列s0 S4中有值（不為〇)時，則是將新的種子序列Μ} 值輸入至位移暫存電路13中。 -己。圖3〜5所不，將本發明複合多項式之亂數產生方 法說明如下： 乂 ^ 3G1 ·在該亂數產生器1中建立如表1之該等輸入 多項式於各查表單元121〜12·5之中。 少驟302 ·選擇單元15載入多項式/種子值致能訊號 15 2以作為進杆％ ?旻a夕項式之亂數計算處理及進行隨機分配 種子訊號之判斷。 本貫施例Φ，夕#丄、， B 夕項式/種子值致能訊號152是用以決定 才工制7刀配電路11所分配之隨機起始訊號153作為 1269222 該選擇訊號15〇,其分配方式便是在邏輯間電路i4先排除 3位元，以該3位元作為隨機起始訊號i 53之輸出之後，再 將排除3位元後的剩餘位元作為輪出結果】6。 150以選取複 步驟303 :由選擇單元15輸入選擇訊號 合式查表電路12中查表單A 121〜125中對應數目之一輸入 多項式。 ’、卩，右疋接收控制/分配電路U所分配之隨機分配起 始訊號153，則是輸人k=3 ^之選擇訊號予各查表單元 121 125，例如·遙擇訊號之輸入為〇〇〇，則為選取如表j 所不的各查表單元121〜125同一列位址為〇⑻之多項式： X74-X3+X2+X+1 . χ7+χ5+χ3+χ+1 . χ7+χ3 + 1 . χ7+χ5+χ4+χ3 + 1 及 x7+ χ5+ χ4+χ3+χ2+χ+1 。 "步驟304 ··配合步驟303所選取之各輸入多項式，在該 等位私θ存裔131〜135及邏輯閘電路Μ進行線性反饋位移 暫存（LFSR)之運算。 本貝苑例之计异方式，主要是對各位移暫存器131〜I% 的輻出結果16之字元0〜字元4進行X〇R計算，為方便說 明起見’將字元〇〜字元4分別命名wQ、wi、w2、w3、w4 ，而在邏輯閘電路14中，是分別作WO㊉wl、W_W3、w2 ㊉Μ ' W3®W4 ' w4®w2之邏輯運算（㊉表示XOR運算子） I刀別侍到種子序列s0〜s4，並將各種子序列s〇〜S4回授至 〇位私曰存為131〜135以取代各位移暫存器131〜135各序 列的最小位元。 本貝化例中’原本輸出結果16之位元數應為5*7=35 12 1269222 位7L ’但是實際輪出僅取出32位元’主要是以該3位 為選擇《 150之來源，例如設定將輸出結果16之字元2 的第3位元、字元3的第2位元’以及字元4的第1位元2 為選擇訊號15〇,則聽上述3位元之輸出即為32位元之 亂數輸出訊號104。 如圖6所不，概括地說明了使用複數多項式可打破週 期性重複的情況，由於本發明之亂數產生方法綜合了複數 輸入多項式之設計，並可隨機地選取選取任一輸入多項式 ，因此可大幅提昇輸出結果之亂度，例如··狀態一〜狀態八 分別為多項式1〜8所產生的亂數序列，由於可隨機選取多 項式的結果，相較於單次方程式的將在一定週期内重複出 現，隨機且動態地選取各輸入多項式的結果，打破了週期 的限制，使得不可預測性將可增加。必須說明的是，圖6 並未真貫王現系統貫際的亂數產生結果，因為本發明產生 之亂數序列的實際情況將更為複雜。、 歸納上述，本發明之亂數產生方法及亂數產生器具有 下述優點： 1 ·本發明克服了目前單次多項式LFSR以串列的方式 導致輸出資料的轉換速率過低的缺點，一次便可輸出多位 元（32-bit)的亂數，可符合高速系統的需求。 2·本發明綜合了多數輸入多項式之設計，並可隨機地 選取選取任一輸入多項式，不似目前單次多項式的亂數序 列容易被破解。 3·本發明可以使用容易實現的數位式電路設計，有利 13 1269222 於保密系統 之用途。 片測試系統及通訊系統中的任一種產業上 & f隹以上所述者’僅為本發明之較佳實施例而已，當不 =以此限定本發明實施之，即大凡依本發明中請專利 =圍及發明說明内容所作之簡單的等效變化與修饰，皆仍 屬本發明專利涵蓋之範圍内。 【圖式簡單說明】 圖1是—示意圖，說明使用單次多項式概念之線性反 饋位移暫存器的原理； ^圖2是一示意圖，說明固定方程式的限制之下，使得 亂數序列將在一定週期内重複出現； 圖3疋电路方塊圖，說明本發明亂數產生器之一較 佳實施例； S 4疋黾路方塊圖，說明該較佳實施例中，複合式 查表電路、位移暫存電路及邏輯閘電路之連接關係； 圖5是一流程圖，說明本發明複合多項式之亂數產生 方法；及 圖6是一示意圖，概略說明使用複合式多項式的情況 ’使得I數序列不會在固定週期内重複出現。 14 1269222 【主要元件符號說明】 1………… 亂數產生器 101 時脈訊號 102 * 重置訊號 1 0 3 ‘… 亂數輸出要求訊 號 1 0 4 ♦，，… 亂數輸出訊號 1 0 5…… 狀態訊號 11 3； < ^ ^ * * + 控制/分配電路 12……… 複合式查表電路 121〜125 查表單元 ] * 令。ί k : < 位移暫存電路 131〜135 位移暫存器 t ♦ ϊ + r ψ ϊ + i 邏輯閘電路 141……種子序列 15………選擇單元 150 <……選擇訊號 1 5 2…‘…多項式/種子值致 能訊號 1 5 3 •……隨機分配起始訊 號 154……‘真實亂數源訊號 156………取消真實亂數源 訊號 1 6………輸出結果 301〜304步驟 15

Claims (1)

1269222 十、申請專利範圍： 1· 一種複合多項式之亂數產生方法，係在一具有複數位移 暫存器之亂數產生器内進行運算以輸出一亂數，該方法 包含下述步驟： (A) 在该亂數產生器中建立一複合式查表電路，且該 複合式查表電路内建有複數輸入多項式之對照表，· (B) 輸入一選擇訊號以選取該對照表中對應數目之一 輸入多項式；及 (C)配合步驟（B)所選取之該輸入多項式，在該等位 私暫存中進行線性反饋位移暫存之運算。 2 依據申請專利範圍第丨項所述之亂數產生方法，其中， 步驟（A)中，該複合式查表電路具有複數查表單元Y且各 该查表皁兀係對應地連接—位移暫存器，而該等位移暫 存器之數目A M，該等查表單元之數目》n，總位元之 輸出共為M*N位元，步驟（b)中 出中抽取出k位元作為選擇訊號 ，係從總位元之輸 之來源。 其中， AMBA 3·依據申請專利範圍第丨項所述之亂數產生方法， 步驟（B)中，該選擇訊號之來源可為外接—符合 AHB 之 Arbiter 訊號。 4· 一種亂數產生器，包含： 一選擇單元，用以輪出一選擇訊號； 一複合式查表電路，叙接該 軍 , 坏早兀，且内建右 具有複數輸入多項式之對B、g表· 一位移暫存電路，星古获奴“ 具有複數位移暫存器，轉接該 16 1269222 合式查表電路；及 :邏,間電路，•接該等位 路中，疋分別對各該位 …在該邏輯間 並將運算得到之曰子之私出作邏輯運算， 藉此，該複至各該位移暫存器’· ^ 5工~表電路接收該選摆印一 擇Λ號，可私能±丄 、擇早元輪ΐ夕、阳 你 動恶地選取該對照表之—轸Α二之忠 位移暫存電路可對廊嗦 知入夕項式，且該 該位移暫存器所輪出:思以輪入多項式分別對各 5.依據申請專利範：第種子序列作邏輯運算。 寻才J摩巳圍$ 4項所述之就數 稷合式查表電路屋生。。，其中，該 毛峪具有複數查表單元，且夂 對應地連接一位移* D ^ —表單元係 Μ，該等杳表單元Vr’而該等位移暫存器之數目為 开^ 之輸出共為WN位 …從總位元之輸出中可抽取 之來源。 U仆马埯擇訊號 6.依據申:專利範圍第5項所述之乳數產生器，其中，各 表單兀中的輸入多項式數量為2、該選擇訊號係& 位元可對應地選擇各該查表單元中的任一輸入多項式。 該 7·依據申請專利範圍f 4項所述之亂數產生器，其中， 等輸入多項式係7位元不可再分解之多項式。 8·依據申請專利範圍帛4項所述之亂數產生器，可用於產 生符合美國聯邦資訊處理標準（FIPS140-2)之亂數序列。 17