TW201005630A - Random number generation and management method, and device - Google Patents

Description

201005630 六、發明說明： 【發明所屬之技術領域】 本發明係-種有關於隨機數之技術領域，尤指一種隨機數產 生器及產生管理方法。 【先前技術】 目前產生用於像在計算機模擬時的短時間需要用大量的隨機 數的情況，也有產生像用於馳識別的ID (identificati〇n) 〇 與密碼的PW (password)，有限長（如128位元）的隨機㈣ 情況。儘管ID與PW需要有較強的安全管理但是實際上，還沒 有用裝置來實現的有效的管理方法。儲存著用戶的丨 的 記憶媒體被遺失的報導，從不間斷。 』 ^用來做ID與Μ的隨機數㈣的管雜_，現狀是保存在 體等的儲存15中而已。用戶$ 1]}等的訊息在無加密㈣ 下保存在記憶媒體中被遺失的情況，就說明了其管理的難度。 2機數是可以再生的。在計算機模擬時， ❹ =也=著產生此隨機數的初始值，就能產生同樣的 隨機數。也就疋’我們可以看作為 來管理此很長的隨機數列。 產生此隨機數的初始值 有一個能產生具有足夠長的週期性的2進位數列（Γ〇Γι.·. :二ίΓ管理系統。由秘密地管理的-個初始值和公 =Γ生和管理^的系統。在需要的時候，給 Γ 值和七，來產生所對應的ID或PW。但是，很明 ::樣的方法在很大的t所對應的隨機數列⑴ 生時所需要的時間將恨長，有時（*t = 264 )會使該系統失去作 3 201005630 為實用系統的機能。 在另一方面，由於混沌函數所產生的數值系列具有其特殊的 性質（非線性，初始值敏感性，計算的一方向性等），被期待著 有用於隨機數產生。其中，有許多是對用logistic map (式 1 )(以下稱作為LMAP)產生隨機數，及對產生的數列進行的考 察（例：非專利文獻1-3 ) 式1 ^+1 =4^0-^) (0 < X, < 1，t = 0,1,2,...) 非專利文獻1 U1 am, S. Μ · and Von Neumann，J · ，‘ ‘ On Combination of Stocastic Determi st i c Processes‘‘ ，Bull · AMS ·，Vol . 53，p . 1120 ( 1947 )) 在此文獻中，提議用式1來產生隨機數 非專利文獻2 香田徹•緒方栄次，彳試行七力才只1'，電子通信學會論文志A， Vol · J68-AN0 · 2pp · 146-152 (1985) 在此文獻中，顯示了用式1且將閾值定為0.5時所產生的2進位數數列為 良好的隨機數列。 非專利文獻3 莊野克房，”力才乂工 > 夕二T ”，シ二7° U >力、一7工7 今一"東京，東京，2002。 在此文獻中，作為利用式1來高速產生隨機數的有效方法，提出 201005630 了使用固定小數點計算法來實現硬體化。 混洗函數LMAP的計算具有一方向性，也就是從某一個初始值X。開

始’能逐個計算出xt (t=1，2，…），而從計算出來&Xt卻不能算出X 〇。這疋因為用2次函數LMAP的逆函數來進行xt的 •反向計算時’需要對2個可能的狀態作出其中之一的選擇（+或一符號的 選擇）^ 在本申請中的由LMAP來產生的2進位數數列是指對Xt取閾 〇值為〇· 5 ( X t 20. 5時輸出1，Xt<〇. 5時輸出〇)時所產生的 2進位數數列。而且’本發明還確認了 LMAp具有如下的特性。 在计算精度為N位元時’從t = 0到t=N-l，只要有著連續地 產生出來的N位元的2進位數數列（閾值〇. 5)，就能由LMAP 的逆函數來計算出產生此2進位數數列的此時的+, 一符號 的選擇是由相同的t所對應的2進位數的值來決定（1: +，〇: )^是由於在什算LMAP時，是依照lyapunov指數發散， 在汁算LMAP的逆函數時是依照iyapUnov指數收束所產生的結 © 果。 、" 报明顯，具有這樣的特性的LMAP所產生的2進位數數列， 作為訊息安全用隨機數是不合適的。對於一段报長的LMAp所產 生的2進位數列，只要知道最前面的比計算精度更長的位元數， 用這些位元的2進位數，透過計算LMAP的逆函數，就能得到χ 0，由X»來計算LMAP，就能計算出此很長的2進位數列的所有位 兀。但是，從LMAP所產生的2進位數數列的下位（較後產生 的）位元卻不能計算出上位（較前產生的）位元。 计算精度N位元時，在計算LMAP的過程中，可能產生的連 續的〇的數量，最多為N/2以下。此特性，限制了 LMAp所產生 5 201005630 的2進位數數列所持有的組合數的可能性，卻同時保證了從此2 進位數列取出N位元來作為新的初始值時，此初始值不會出現像 0，0. 2 5，0. 5，0. 7 5那樣的被稱為黑洞的值。 在用有限精度計算LMAP時，初始值敏感性可以用以下的形 式來觀察到。用只有最下位位元不一樣的兩個初始值，我們可以 確認從這兩個初始值，經過N次計算後的内部狀態xt，已經在完 全不同的軌道上（兩個内部狀態間找不出任何關係）（例：計算 精度128位元時的初始值0. 0…01和0. 0…010的128次計算後 的結果分別為0.0100…0100和0.1100…0110 (只表示了上位 4位元和下位4位元）。此事具有2個含義。 首先，由於在用有限精度計算時，下位位元隨時被捨去，在 N次的計算後，其狀態與初始狀態之間成為無關狀態。也就是說 不經過計算，就不能預測N次計算後的狀態。其次，即使是只有 最下位位元不同的兩個初始值，由這兩個初始值所產生的2進位 數數列是無相關關係的數列，從其中之一的數列不能推測出另一 數列的内容。以上的LMAP產生的2進位數列所具有的特性，在 此後所述的多維隨機數產生法中，具有重要的意義。由此可見， 習用的隨機產生器及產生管理方法仍存在諸多問題，實有改良之 必要。 【發明内容】 欲解決之技術問題點：目前產生用於像在計算機模擬時的短 時間需要用大量的隨機數的情況，也有產生像用於認証識別的 ID，密碼（PW)的，有限長（如128位元）的隨機數的情況。儘 管ID，PW需要有較強的安全管理，但是實際上，還沒有用裝置 來實現的有效的管理方法。儲存著用戶的ID等訊息的記憶媒體 被遺失的報導，從不間斷。用來做ID，PW的隨機數數列的管理 201005630 很困難，現狀是保存在記憶媒體等的儲存器中而已。用戶的ID 等的訊息在無加密狀態下保存在記憶媒體中被遺失的情況，就說 明了其管理的難度。 偽隨機數是可以再生的。在計算機模擬時，需要用到同樣的 ' 隨機數時，只要保存著產生此隨機數的初始值，就能產生同樣的 • 隨機數。也就是，我們可以看作為由管理產生此隨機數的初始值 - 來管理此很長的隨機數列。有一個能產生具有足夠長的週期性的 2進位數列（r 〇 r 1…r t…）（離散時間t = 0，1，2，…）為 前提，我們來考慮如下的.ID，PW的產生管理系統。由秘密地管 ® 理的一個初始值和公開地管理的t來產生和管理ID，PW的系 統。在需要的時候，給該系統輸入初始值和t，來產生所對應的 ID或PW。但是，很明顯，這樣的方法在很大的t所對應的隨機 數列（ID，PW )的產生時所需要的時間將很長，有時（如 t = 264 )會使該系統失去作為實用系統的機能。由此可見，習用的 隨機產生器及產生管理方法仍存在諸多問題。 解決問題的技術特點：提供一種隨機數產生器，係包括：一 隨機數產生與管理訊息輸入單元、一初始值與多維座標值變換單 Q 元、一暫存器、一混沌函數計算單元、一隨機數暫存器與一隨機 數產生控制單元。其中，該隨機數產生與管理訊息輸入單元係將 N (是2以上的整數）位元的2進位數數列R作為產生隨機數的 初始值訊息，將維數為K的多維座標i ( i 1，· · ·，i k，· · ·， iK) (ik是0以上的整數，K是1以上的整數）作為多維座標訊 息來接收；該初始值與多維座標值變換單元係將上述R作為非線 性函數 X t + 1 = 4 X t ( 1 — X t)(以下簡稱 LM ΑΡ，0 < X t < 1 ) 的初始值x〇的小數點以下的部分變換成x〇，並將i變換成多維 座標值il，· · ·，ik，· · ·，iK來為用計算LMAP來產生隨機數 作準備；該暫存器係將用來儲存該初始值與多維座標值變換單元 7 201005630

iK 所變換的初始值叉0和多維座標值u，···，ik，·· ^ 該混Ά函數計算單元係依照該暫存器中儲存的初始值χ。和 多維座標值’對LMAP反覆進行計算精度為Ν位㈣蚊小數點 ..bk，N_1)組成，bk,〇 = [2xxNxik]，b 的"十算，來產生Ν位元的2進位數列Bik (Bik的各位元是由（b k · 0 b · ' ^ x * L^XXNxik + ll f ··· 5 T^i . 「八 ~ 1 — [2XXNxik + N- l]，[]是捨去 小數點以下的部分的計算），再將Bu作為LMAp的初始值 小數點以下的部分來將Bik變換成χ。，並且將上述的計算 反覆進行，來產生N位元的2進位數列I 以㈣机 卜…為Rn，…，k = K時r"， ^為尺"^ , R i u的各位元由（rk，…，m 組成，η 〇 = [2χχ

Ν] ，ΓΚ’1 = [2χΧν+1]，...，rk,N-i = [2xx2N-⑴來產 生混洗2進錄數列；該隨機數暫存難絲儲存該誠函數計 算卓續輸出的N位元的2進位數數列Rii ik ;該隨機數產 生控制單元剌該隨機數產生與管理訊息輸人單元的動作、初始 ^與多維絲變換單元的動作、科函數計算單元的計算以及將 11’=’^作為1^1^?的初始值乂()的小數點以下的部分來變換成 的計算，以k=1，2，···]的順序來執行（但是，當k=K R :::R" “向初始值x。的變換），來產生多維隨機數 Ri的隨機數。 =卜’本發明係提供—種隨機數產生管理方法，係依序包括 下列步驟： &對所給與的_是2以上的整數）位元的2進位數列R和維數為κ 的多維座標訊息1 01，.·.，ik，…，幻（设是0以上的整數，k=1 ’ 2’.W作為非線性函數〜= 4Xt(1-xt)(簡稱腑， 201005630 〇<Xt<l )的初始值XQ的小數點以下的部分，將i轉換為各維座標值 il，…’ ik，…，iK，並將X。和ii，...，ik，…，iK儲存於一暫存器。 b.依照該暫存器所存初始值叉〇和ik，透過一混沌計算單元對LMAP進 行計算精度N位元的固定小數點計算法的反覆計算，來產生N位元的2進 位數列 Β& (Bik的各位元由（bk，〇bk.i...t)k，N-i)組成，bk，〇 = [2xx

Nxik] > b k> l=[2XXNxik + l] > ·.. , bk.N-l=[2XXNxik+N-l] » 小數點以下的部分的計算）。 〇

C.該混洗計算單元再將^作為LMAp的初始值XQ的小數點以下的部 分’對LMAP進行反覆計算，來產生N位元的2進位數列Rq ,..., ik (k=l 時1111以為亿1，... ’ k=K 時R;1，···，以為尺"，…，iK > Rii，·.·，ik的各位 元由（ rk’〇rk，i..·。，”）組成 ’ rk，〇 = [2xxN]，rk’i = [2xXN+ 丄] Γ k ’ N-1 [ 2 XX 2N-1])並存入一隨機數暫存器。 d.將該隨機數暫存騎存Rii “料LMAp的初始值又。的小數點 以下的部分存入該暫存器。 e.將上述步驟b、 k=K時不做將Rq,..., 數R。 c、d的作業以k=l，2，...，κ的順序來實行（俱是’ iK&LMAP的初始值叉。的變換），來產生多雉隨機 ^，本發明的目的主要係提供_種在通用計算機和專用硬艘的雨方 面都地實顺’紅與管理像ID或雜的味短的隨機數數列 的隨機數產生與管理方法及裝置。 對照先前技術之功效： 201005630 本發月透過依照多維座標訊息所進行的初始值的反覆產生 ，能夠高速 產生（再生）置於多維座標空間中的大量的隨機數列中的位於任何 座標位置的隨機數列。因此，我們可以構築-_聽管理的2進位 數列R和有規則的多維座標訊息i (il，…，ik，…，iK )來產生 和管理2進位數列Ri (ID，pw)崎機數產生與管理系統。 -本發雜卿了魏函數（LMAp)，即使是时規則的多維座標訊息 1 ’ lK)來產生的Ri之間，也沒有線性相關關係。因此，從 某個隨機數列Ri和其多維座標訊息i (il，...，iK)不能推測出R 而且’也不能推測出由其财維座標訊息所產生的隨機數數列。 三、本發鶴賴定小數點計算絲計算腑，使得只要是能進行整數運 算的系統（乘法’加減法，邏輯運算等），不管是軟體還是硬體系 統’都能料地難本發贿提案的_數產生與#_統。而且使 隨機數產錢管__鋪魏變得可能，是料產紐術的一種 被期待的形態。 有關本發輯剌之麟、手段及其魏，錄齡實糊並配合圖 式詳細說明如后，相信本發明上述之目的'構造及其特徵，當可由之得一 深入而具體的暸解。 【實施方式】 请參閱第-圖至第五圖所示，本發明係提供—種隨機數產生 器該隨機數產生器係為一種隨機數產生與管理裝置（1 〇〇)，係 包括：一隨機數產生與管理訊息輸入單元（102)、一初始值與多 維座標值變換單元（104)、-暫存器（1G6)、—混先函數計算單 元（108)、一隨機數暫存器（11〇)與一隨機數產生控制單元 201005630 (112)。其中，該隨機數產生與管理訊息輸入單元（1〇2)係將n (是2以上的整數）位元的2進位數數列R作為產生隨機數的初 始值訊息，將維數為κ的多維座標i ( u，· · ·，ik，· · ·， ❹ iK) (ik是0以上的整數’ KU以上的整數）作為多維座標 訊息來接收；該初始值與多維座標值變換單元（104)係將上述R 作為非線性函數叉1 + 1=4又彳1—叉0(以下稱為1^^八15，（）< Xt<l )的初始值又。的小數點以下的部分變換成χ。，並將i變 換成多維座標值il，· · · ’ ik ’ · · ·，iK來為用計算LMAP來產 生隨機數作準備；該暫存器（106)係將用來儲存該初始值與多維座 標值變換單元所變換的初始值XG和多維座標值U，···，比，.. •，iK。 該混沌函數計算單元（108)係依照該暫存器（1〇6)中儲存的 初始值xQ和多維座標值，對LMAp反覆進行計算精度為n位元的 固定小數點的計算，來產生N位元的2雜數列gik (Bik的各位 兀是由（b k , 0 b k ,丄…b k，N-l )組成，b k，。= [ 2 χχ J bk-i = [2xXNxik + 1] , , bk，N-1 = [2xxNxik + N_ ❹ !]，□是捨去小數點以下的部分的計算），再將作為LMAp 的初始值Xq的小數點以下的部分來將Bik變換成X。，並且將上 述LMAP的计算反覆進行，來產生n位元的£進位數列r “ i k ( k 1 時1^ 1 1，…’ 4 >^為 R" ’ …，k=K 時R i !，_··，i k為 R i 丄，...，i K R]1 ’11"的各位元由（1)1，〇11^’1〜『1^,^-1)組成，1' [2χχΝ] , γκ.ι = [2χχν + ι]»···» Tk-N-i = [2xx 2H])來產生混沌2進位數數列；該隨機數暫存器（no)係用 來健存該混此函數計算單元（108)所輸出的N位元的2進位數數 列R 1 1 ’ ； k ;該隨機數產生控制單元（112)係對該隨機數產生 與管理訊息輸入單元（102)的動作 、初始值與多維座標變換單元 (104)的動作、混沌函數計算單元（1〇8)的計算以及將r u ^ 201005630 = 的初始值，。的小數點以下的部分來變換成χ ◦的計 =序來執行（但是，當w時，不做 _·’iK向㈣值x°的變換），來產生多賴機數R1的隨 機數。 理方、去，传：五圖所不’本發明係提供一種隨機數產生管 理方法，係依序包括下列步驟： ❻ a. 對所給與的_ 〇社數）位元的2進位數❹和維數為κ 的多維座標訊息i (U，...，ik，…，沉）（ik是0以上的整數，k=1， 2’.··’幻；將！作為非線性函數Xt + i = 4xt(1—xt)(簡稱薩， 〇<χχΐ)的初始值^的小數點以下的部分將土轉換為各維座標值 ik · ’沉，並將χ〇和U，·.· ’ ik，…，iK儲存於一暫存器。 b. 依照該暫存騎存初始值χ。和ik，透過—混綺算單元對⑽^進 行-十算精度n位tl的m定小數點計算法的反覆計算，來產生\位元的2進 位數列Βϋ (Β&的各位元由n i)組成，bk 〇 = [2χχ 小數點以下的部分的計算） ]b k , k + 1]，…，b k , N—i =[2xXNxi k + N—J，□是捨去 C.該屈0屯叶算單元再將Bac作為LMAP的初始值xq的小數點以下的部 刀’對LMAP進行反覆計算，來產生n位元的2進位數列Ru ,..., ik (k^ 時Ru，...也 η 、 .，1 k為 Rn ’ ...，k=K 時R ; ! i k為R i i，...’ iK，R i i，...，i k的各仇 元由（r t ’ork，i.”rk，N-i)組成，rk.〇 = [2xxN]’ rk，i = [2xXN+ l] ·” ’ r k’N-eUxxa-i])並存入一隨機數暫存器。 d.將該隨機數暫存器所存R i:,..., i k作為LMAP的初始值X。的小數點 以下的部分存人該暫翻。 ’’ 12 201005630 e.將上述步驟b、c、d的作業以k=l，2，...，κ的順序來實行（但是， k=K時不做將Rii ’...，以向LMAP的初始值X()的變換），來產生多維 數R。 、、’機 再者，我們參考圖式，來詳細說明本發明的實施形態及其效果。第 二圖係顯示了本發明的一實施例形態，即隨機數產生與管理裝置（1〇〇)。 此實施形態的隨機數產生與管理裝置（1〇0)，是透過將N位元的2進位數 列R變換成LMAP的初始值x。，依照X 〇和多維座標訊息i，用混沌函數計 算單元（108)來產生N位元的2進位數列Ru，.·.，ik，再將其變換成叉〇的 計算進行K次反覆，來產生（κ)維隨機數见。隨機數產生與管理裝置 (100)由隨機數產生與管理訊息輸入單元（102)、初始值與多維座標值變換 單元（104)、暫存器（1〇6)、混沌函數計算單元(108)、隨機數暫存器（11〇) 與隨機數產生控制單元(112)所組成。 該隨機數產生與管理訊息輸入單元（1〇2)將N位元的2進位數列R和 多維座標訊息i (i 1，…，i K)接收。 0 該初始值與多維座標值變換單元(1〇4)將輸入的2進位數列R或在多 維隨機數產生過程中所產生的2進位數列Ru，…，ik變換成叉。，也將輸入 的多維座標訊息i變換成各維的座標值i 1，...，i K以備用於用固定小 數點計算來產生多維隨機數。 該暫存器（106)將在初始值與多維座標值變換單元（1〇4)變換的X 〇和 i 1 ’…，i K儲存於其中。 該混沌函數計算單元（1〇8)用儲存在該暫存器（1〇6)的初始值，依次 依照多維座標ik (k=l ’ 2，…，K)來反覆計算LMAP，產生N位元的2進 位數列 R i 1，...，i k。 13 201005630 在此說明混沌函數計算單元（108)的作業的詳細内 目兀*，孩藏洗 函數計算單元⑽)用儲存在該暫存器⑽）中的初始值Xq和多維座標化 將LMAP計算Mxik次。 其次’在計算LMAP的同時’計算bkfKxxwk]，bki = [2x χΝ“ + 1] ’ ’ bk’N-FUxxNikw—!]([]是捨去小數點以下的部分 的計算），來產生况位元的2進位數列Bik (bk Gbk r. bkn) 再將心作為LMAP的初始值χ〇的小數點以下的部分來轉換成χ〇，將 LMAP計算Ν次。 而後在計算LMAP的同時，計算rk,0 = [2xXN] ，fk ι = [2><Χν+ 1 ^ ，Γ k ’ Ν-1 — [ 2XX ν+ν-ι ]來產生ν位元的2進位數列R i j_,. (Γ k'O Γ k»l**· Γ k*N-l) 0 如上述的計算，使得我們能夠切斷如上所述的由LMAp產生的2進位 數列所具有的上位位元對下位位元的推測可能性。 該隨機數暫存器（110)用來儲存該混沌函數計算單元(108)所輸出的2 進位數列。 該隨機數產生控制單元（112)控制各單元的動作來產生多維隨機數 列。 該隨機數產生控制單元（112)對維數Κ的多維訊息，按從k=l到k=K 的順序，利用多維座標訊息’反覆用混沌函數計算單元（1〇8)進行計算， 其輸出儲存於該隨機數暫存器（110)，當k<K時，將儲存於該隨機數暫存 器（110)的隨機數列經初始值與多維座標值變換單元G〇4)變換為x〇，並 201005630 儲存於該暫存II(1G6)，繼續上述計算，k=K時，將該隨機數暫存器⑽) 所存的N位元的2進位數列作為隨機數忆，並中止計算。 在此，對多維隨機數的含義及其效果進行說明。 我們來考慮由LMAP進行固定小數點計算，計算精度N位元，來產生 N位元的2進位數列。 輸入N位兀的初始值叉。來產生所需數量的2進位數列犷（『〇犷 i.·.)。設It機數產生器的產生速度為s bps (位元/秒），並且產生2進 ©位數列以外的作業時間非常小，不予計算。在此我們來看—下用賴數產 生器產生MxN (M是1以上的整數）位元的隨機數，分織M觸長n位 元的2進位數列時，用初始值χ〇來產生任意一個R所需的時間。 用像這樣的方法所產生的_ Ri可㈣料置於—條直線上（如第 三圖所示），因此，我們稱此產生法為一維隨機數列產生法。 由於是N位元的數列’很明顯，從XD產生第一列的數列_需要的 時間是N/Sm產生第二列的數列Ri所需的時間，由於其含有產生第一 列隨機數列的時間，所以應為2N/S。依此類推，從χ〇產生第土列的數列 Rh所需的時間為ixN/S。 由於能產生的隨機數列以多為好，因此期望能取較大的m值。但是， 像這樣的從一個初始值來連續產生賴數列的方法，無法將Μ值取得很大 的值’如像M=2M，即使是隨機數的產生速度為24。_時，—列n位元 的數列的平均產生時間即為（ 1+264) χΝ/2/24°> 2 23秒。 我們來考慮如下的隨機數產生法： 15 201005630 在此’設上述Μ為MixM2 (Μι ’ M2為1以上的整數），從N位元的初始值 x〇產生Μι列的N位元的隨機數列，再將所產生的吣列的N位元的數列， 作為新的初始值，各自產生吣列的N位元的隨機數列。所產生的N位元的 隨機數列用仏^來表示。 由於用上述方法產生的數列Ru,i2能夠想像為被置於2維平面（座 標）上一樣，我們稱此為2維隨機數產生法。 很明顯，Rile的總數為ΜιχίΜιί，從初始值X。產生任意的一個Rim 所需的時間T為如下所述。

rfi〇,〇 =(\xN + \xN)/S = 2N/S

=(lxN + 2xN)/S = 3N/S

=(ΙχΝ + (/2 + \)xN)/S = (/2 + 2)N/S TRIW = ((1 + ϊΟ ^N + (i2 + \)xN)/S = (il + /2 + 2)N/S 也就是，產生一列隨機數列所需的時間為，最短2N/S，最長 (ΜΗ·Μ2) N/S，與一雉產生法時的最長時間MxN/S=(沁潘）N/S相比，其 不同之處不言而喻。 將維數設為K，且Μ=Μιχ···χΜκ，從N位元的初始值xq產生Μι列的N 位元的隨機數列。而後，將所產生的沁列的N位元的數列作為新的初始 值，各自產生M2列的N位元的隨機數列。與上述同樣地轉換為新的初始值 的處理到Μκ為止進行K-1次，來產生數列匕。由於能夠將數列忆想像為置 於K維空間中的座標為（i : i 1，i 2，…，i K) 一樣，我們稱此產 生法為多（K)維隨機數產生法。我們可以知道，置於K維座標空間中的 201005630 任意一列數列的產生所需的昧pq 4 1 而叫間為（κ+i 1 + i 2+...+ iK)N/S，最 短為屬’最長為（_2+..爲）N/S，平均時間為（Κ+Μι+Μ2+·..+Μ K) N/ (2S)。 ❹ ❹ 我們來說明多維隨機數產生法中的各個參數N K(k)的 含義N U算精度。目此’可轉初始制麵（初雑㈣）為除去 N 位元數列為 0···◦，^0...^10...0,^..0(0,0.25, GD的2 4種。但是’由於某__初始值X。所能產生的混池狀態 的長度為近似於2，_可轉働非聊狀_ Μ的大小為2Ν/2/ν。實 際上’取Ν為32〜64之間的值，用數值計算來對Μ的非週期狀態的長度 進行檢索赌果為近錄2气這是由於反覆進初雜的產生使得多 維隨機數產生騎具有的職性變得比絲的腑更長。 座標量Μ是從初始值χ。所能產生的數列的總數。一般其大小受到隨 機數產生器所具有的週雛的_。但是，如果允許在錄空間中置有相 同的隨機數列（不知道置於何處）的話，將不受此限制。 決定各維座標的空間大小（Μ，2 , ...，κ)。並且，影響r的產 生速度。1取較大值時可使Ri的平均產生速度變得很低。1與k 一起對亿 具有分類機能。就是，能持有具雜定含義的訊息（如_，名稱，組織 (部門）等）。亦即是，適當的％的大小的決定，不僅取決於隨機數的產 生速度’還要綜合考慮到分類上是否料。比較有效的表示座標空間的方 法為取M=2e ’ m=mi+."+mK，（仙，…服是〇以上的整數）。 K作為維數’持有分類機能。Μ為一定值時，K取得較大，仏的平岣 值將變得較小，㈣平均產生速錢得減。但是俯m 14的值極端地取 17 201005630 較大值時’Ri的產生速度極端地變慢的情況也會發生。這是因為，同在一 維產生法所看到的-樣，將某—維的鋪數設定得過於大時，在此維中的 平均產生時間將變得很長。因此，κ的設定既要依從分類機能，同時也要 使個別的M,不要過於大^亦就是說，即使是屬於同類也沒有必制同—維 的座標來表示。在分類上如果個別的Mk的值太大時，對此類可用複數個的 維數來表示。 可以對K (k)進行分割。 我們來考慮計算精度N位元，初始值Xd，綠〖，各賴大小為①，❹ Μ2’ ·，.，ΜΚ的多維隨機數產生系統。我們來考察一下中間過程維k時的狀 態。k=l時，我們能夠從初始值以產生Ml個的N位元的2進位數列^。 k=2時，我們可以從初始值X()產生出Ml個的N位元2進位數列Rn (中間 過程初始值），再從中間過程初始值各產生出吣個的N位元的2進位數列 Rue。即，能夠從初始值Χ()產生總數ΜιχΜζ個n位元的2進位數列。同樣 地’在中間過程維k ’能夠產生出MixMzx…xMk個的中間過程初始值。 在這裡’使k=Ku，K=Ku+Kd，則Kd=K-Ku。即，成為由初始值χ〇維數 〇

Ku，各維數的大小為Μι，Μ2 ’ ...，MkU的上位維所組成的多維隨機數產生系 統。如’由維數Ku的上位維所組成的系統所產生的Μ!χΜ2χ…xMku個的N位 元的2進位數列（中間過程初始值）作為各個初始值的由下位維所組成的 多維隨機數產生系統（維數Kd，各維的大小為，…，Μκ) 如上所述，2個K (Ku，Kd)對應於原來的一個多維隨機數產生系 統，透過分割K，可以將多維隨機數產生系統分割，並且，在分割多維隨 機數產生系統時，以維Ku為界並不是必須把所有的下位維從多維隨機數 18 201005630 產生系統分割出來。只要將處於任意的中間過程座標η，i2，…，土⑽ 的It機數Rm ..，iku輪出，作為新的下位多維隨機數產生系統的初始值，即 可將任意的下位多維隨機數產生系統從原來的多維隨機數產生系統中分離 出來。 並且’顯然作為系統分割的逆作業，可以將分割出來的系統再進行連 接（統合）。但是，必須將分割時的各自的中間過程維的座標訊息保存起 來。換而s之’對有必要進行再連接的分割系統必須保存其中間維座標 €)訊’。巾對於不需要進行再連接的，完全獨立的分割系統可以將其中間 過程座標消除。 以上對K進行Ku和kd的2分⑽行了說明，當然，朋樣的方法， 根據需要進行更多的分割也是可能的。 由初始值X°，多維座標1⑴，i2，…，iK)產生的Ri和由初始值

Ril i2，..，ikU ’多維座標 1 (i (ku+1)，i (㈣），...，iK)產生的 Ri 具有 相同的值。也就是’從初始值X()能得_始值& 2 ★，但從& …’卻不能得到初始值X°。對於持有上述_的初始值，我們稱初始 值X。為上位初始值，初始值心·^.如，為下位初始值。 用持有上述雛❹賴機數產生方法，細可以構細具有等級構 造的隨機數產生祕。即，上位秘值h和下位初始值所具有 的權限不同，持有初始值X#比持有Rii，i2 ★者具有更大的權限。 第五圓係顯示多維隨機數產生與管理裝置⑽)的動作的流程圖的一 例。根據義數產生命令，此_騎稍隨驗產生鮮理裝置(⑽） 開始動作。 201005630 將輸入到隨機數產生與管理訊息輸入單元的N位元的2進位數列R 和多維座標訊息i接受，將變數k設為k=〇。然後初始值與多維座標值變 換單元使k=k+l，並將接受到的N位元的2進位數列R變換成X。與多維座 標訊息（il，i2，…，iK ) 一起’存入暫存器(1〇6)。混沌函數計算單元 ' (108)再依據儲存在暫存器(106)中的X。和多維座標訊息汝，產生N位元的2 * 進位數列，存入隨機數暫存器(11〇)當k小於維數κ時，將N位元 的2進位數列Rue…，*輸入到初始值與多維座標值變換單元(1〇4)，並進行 重複計算。當k=K時’將N位元的2進數列Rn.n，作為隨機數輸 ◎ 出，本流程圖所示隨機數產生裝置的動作終止。 在此用產生和管理隨機數的系統的具體例，從初始值敏感性，近傍座 標的無相關性，產生速度，系統的分割等方面來確認本發明的效果。 工業產品附有能確認此產品的記號（號碼）^如機種號碼，製造號 碼，批號，製造年月等。這些號碼在管理此產品的有關訊息及售後服務 時，是必須的。當然，這些號碼必須被管理。這些產品的號碼大都是有規 則的連號。由於有規則，因此具有的訊息量較少，容易管理。但是，其反 0 面，容易從某個號碼推測出其他的號碼，容易被非法利用（在複製品上附 上真品的號碼來偽裝成真品）^要使產品號碼無法推測，只要對有規則的 號瑪加上無規則的識別Π)號碼（隨機數）即可。但是使用了無規則的隨 機數，將使近於無限的工業產品的號碼的管理變得困難。本申請所提議的 多維隨機數產生法對於這樣的看不出規則的識別ID (隨機數列）的管理問 題是有效的。 20 201005630 我們可以設想，對應於多維隨機數產生法的3個元素（R，i , Ri)， 將能夠識別產品（獨特的）的產品號碼變換成多維座標，將產生的產品識 別Π)(隨機數Ri)加入到產品號碼巾，使產品號碼無法推測。此時的初始 值X。（R)成為管理產品識別ID的管理鑰匙。正確的初始值L和產品號 碼能夠產生（再生）所對應的產品識別ID。有規則的產品號碼能夠被推 測，但是附加的產品識別ID是無法推測的。亦就是，不持有初始值h者 無法得到正確的產品號碼和產品識別比的組合。 〇 以下是經過簡單化的產生持有如機種號碼為MC780，製造號碼為 C042875的產品的識別ID的系統的例。 產生識別ID，需要將產品號碼變換成多維座標。在這裡將機種號碼 和製造號碼進行如表一所示的變換（英文字母用ASCn碼的16進位數表 示，1〇進位的數字用16進位表示，該表一主要係為說明將工業產品所 具有的產品號碼變換成多維座標的表。 ®表一

使維數K=14 ’各維的大小為Μι=Μ2=…=Mi4=16，管理輪匙為128位_ 初始值（16進位數）χβ=〇.··〇1，則由多維隨機數產生法所計算的亿用π 21 201005630 進位數表示則成為B44768B06B7A25D464F3523552BD0DFB。其對應的多維座 標用 16 進位數表示則為（i=4, d，4，3, 2, c，4, 4, 3, 0, A，7, 7, B) 首先’將多維座標i固定’給與X。以微小的變化，來確認所產生的

Ri的變化。如下顯示多維座標i為（4, D，4,3, 2, C，4,4,3, 0, A，7, 7, β)時的 ， 例。初始值xd為〇...〇1和0...02(16進位數32位）時的吣各為 · C β44768Β06Β7Α25Ι)464Ρ3523552ΒΙ)ΟΡΡΒ )和 (8849A5994E6b861F6298CFB4C7C71E9F) ^我們能夠確認到初始值敏感 性。 美 ❹ 然後，將初始值固定，給與多維座標i以微小的變化，來確認所產生 的亿的變化。以下顯示使初始值χ。為〇“.〇1時的例。使多維座標i為 (4，d，4,3’2，c，4,4,3,0，A，7,7，B)和（4，d，4,3,2，c，4,4,3,0，A，7,7，C) 時，得到的 Ri各為（B44768B06B7A25D464F3523552BD0DFB)和 (BA1359675D951215D6F14411426D1E13) »我們能夠確認到近傍多維座標 的非相關性。 從以上的結果我們可以確認到如下的效果；用多維隨機數產生法構築❹ 的隨機數產生器，即使系統構成一樣，由不同的初始值和相同的多維座標 產生的隨機數之間無法找出相關關係。也就是說即使是構成為相同的系 統也無法從相同多維座標的隨機數來推測出初始值。而且，從具有某一 多維座標的_朗無法細㈣近旁彡輸標上峨機數列。 由上述可知’當給與了 2進位數列的產生速度時，某-多維座標上的 隨機數列的產生所需要的時間。此時，我們設定2進位數列產生以外的作 業時間非f小，不料算。在此，如上由近似計算所得到的產生時間為推 22 201005630 測時間t，而實際產生所需的時間為實例時.，2進位數列的產生速度 為4. 9_時的兩者的結果如表二所示。我地確認其為相近的結果，並 且是可以魏應⑽產生速度。該表二主要係魏·多祕餘產生法 來產生隨機數所需時間的表。

iCil,"177, Π4) 〇, ···，〇(最小值）

4, D，4, 3, 2, C，4,4, 3, 0, A, 7,7, B Τ' (#) 〇. 000388 t (秒）

F，"sF(最大值） 002441 (Genuine Intel(R)CPU 1.5GHz 0.99GB RAM) 0. 000421 0. 002781 ❹ 在產生產品識別ID系統中，產品號碼由機種號碼和製造號碼組成， 也就是產品朗分絲理機種_分（機種號碼）和管理此機種的產品的 部分製造號瑪。在這裡將產品號碼分割為機種號碼和製造號碼，來確認分 割和不分割的兩種情況下所產生的隨機數。初始值卜仍，多維座標 1為（4’d’4’3’2’c’4,4’3，G’A，7,7，B)時所產生的隨機數列b上述所 不。首先’將多維座標分割為（4 d，4,3 2，c,4)(機種管理）和 (4’3,0，A，7’7’B)(該機種的產品）。而後由初始值^⑶…⑴和多維 座標1 (4，D，4,3,2，C，4)來產生賴數列Ri,。再以由Ri,變換的初始值 和多維座標1 (4,3,0，A，7,7，B)來產生隨機數列Ri.，與不分割時所產 生的隨機糊& _。我們賴顧其絲是一樣的。 再看由分割後的多維座標產生Ri，和R所需要的時間，各為 0· 001437秒和〇·觀21秒，其合計料分騎的Q ·781秒基本一致。 23 201005630 如上所述，不改變計算方法等’而只是改變初始值和多維座標，就能 容易地將子系統從母系統中分離出來。而經過分割，減少了系統的計算 量，隨機數的產生速度也變得更快。 另外’由於分割，下位系統沒有必要持有有關上位系統的訊息從訊- 息安全的觀點來看，可以說上㈣統也變得更安全。如本產品管理祕的· 情況’某-產品的生產部門遷移到料去時，這制管理系統的分割是有 效的。 此外，本發明的隨機數產生與管理方法可以用一列N位元的2進位❹ 數列R (初始值）和Μ個有規則的多維座標訊息i來產生與管理m列無規 則的N位元的2進位數列记（如第一圖所示）。 本發明的隨槪產生是由R和有規職丨來產生R，並具有無法用某 鋪疋的i和R來推測其麵M R雜冑。持有這樣職冑峨機數產 生器，能應用於訊息安全等廣泛的領域。 用本發明的隨機數產生法，可以構築起只用一次的m，pw的認註系 統。就是’將系統-側和用戶一側所持的秘密的（m，pw)作為r，在每❹ 次認註時，用戶-側用R和新的i來產生R (認湖瓜，則將i和免 送給系統-側。系統一侧用收到的i和該用戶的R來產生R，與送來的Ri 對照進行認証。由於-個i只用—次，即使被竊聽也不會產生什麼問題。 又由於秘密的R不用外出（經通信網等），也就更安全。如果用從身體上 所採取的訊息（指紋，靜脈等）來做成R，也就不用記憶R。 24 201005630 將本發明的賴數產生方法應用於加 ”眚ϊθ^ Μ _料產生與管理系統， 就月匕實現被稱為最強的加密方法’就是密鑰只用一次的加密方法由於一 個多維座標訊幻僅用-次，因此不會使用相同的密輪。 、 將本發明的隨機數產生法應用於共 _ 访壻加在通仏，能夠在持有相同 的密鑰R者之間，實現僅用一次的密 …· 辑將訊息加密。只要將加密後的 訊心和！送給對方，而沒有必要送R。取得加密的訊息和i崎方用所 持獅R和i來產生祕加密的訊息複元。由於R⑽現於通訊途中所以 更加安全。 由於本發明在賴數產生上是對數式丄進行固定小數點計算法的計 算，因此可以用整數的運算來實現計算。又由於整數能容易地實行分判計 算，所以即使是不同的計算系統（通用計算機（各種〇s)，專用硬體， 微型計算機等），只要能進行最基本的整數運算（加，乘，位元移位，位 元間邏輯運算）’就能糊由相同的輸人來得到相同的輸出。 ❹ 目此，本發餐隨機數產生裝置具有能適應多種需要的「性能_費 用」的組合，富有擴展性’能應用於以訊息安全領域為中心的廣泛的產業 領域。 以上，用實施形態對本發明進行了說明，但本發明的技術手段不限於 上述實施形態所記載的範圍。能對上述實施形態進行變更或改良。上述發 明疋用數式1來產生2進位數列，但用其它的方法來產生2進位數列也是 可能的。並且，也可以用隨機數的產生效率和品性的低下為代價來對上述 實施形態進行變更。很明顯，像這樣的變更，改良後的形態也包含在本發 明的技術的範圍内。 25 201005630 . 線纤而+ . « ，首先，本發明透過依照多維座標訊息所進行的初始值的 反覆產生’能夠高速產生（再生）置於多維練空間中的大量的隨機數列 中的位於任何座標位置的隨機數列。@此，我們可以構築—個由用來管 理的2進位數列只和有規則的多維座標訊息i (ii，…，ik，···，iK ) ' 來產生和管理2進絲列Ri (ID，pw)峨機數產生與管理錢。其次，* 本發明係利用了混洗函數⑽p)，即使是用有規則的多維座標訊息i (1 1，…’ i K)來產生的R之間，也沒有線性相關關係。因此，從某 個隨機數列R和其多維座標訊息i ( i工，…，i κ)不能推測出r。而❹ 且’也不能推測出由其他多維座標訊息所產生的隨機數數列。再者，本發 明係用固定小數點計算法來計算LMAP，使得只要是能進行整數運算的系統 (乘法，加減法，邏輯運算等），不管是軟體還是硬體系統，都能容易地 構築本發明所提案的隨機數產生與管理系統。而且使隨機數產生與管理系 統的低價格化變得可能，是作為產業技術的一種被期待的形態。 前文係針對本發明之可行實施例為本發明之技術特徵進行具體說明； 惟’熟悉此項技術之人士當可在不脫離本發明之精神與原則下對本發明進 0 行變更與修改，而該等變更與修改，皆應涵蓋於如下申請專利範圍所界定 之範疇中。 【圖式簡單說明】 第一圖：係本發明可行實施例之生產管理系統概念示意圖。 第二圖：係本發明可行實施例之實施狀態架構示意圖。 第三圖：係本發明可行實施例之一維隨機數產生方法示意 圖。 26 201005630 第四圖：係本發明可行實施例之二維隨機數產生方法示意 圖。 第五圖：係本發明可行實施例隨機數產生器之流程示意圖。 【主要元件符號說明】 Λ (100)隨機數產生與管理裝置 (102)隨機數產生與管理訊息輸入單元 (104)初始值與多維座標值變換單元 (106)暫存器 (108)混沌函數計算單元 (110)隨機數暫存器 (112)隨機數產生控制單元 27

Claims (1)

1. 201005630 七、申請專利範圍： 1.一種隨機數產生器，係包括： …隨機數ϋ解魏魏概理訊息輸入單 讀、將Ν (疋2以上的整數）位元的2進位數數列r作為產生隨機數的初 始值訊息，峨為Κ的多維座標1 (U，…，也，···，iK) (lk是〇以 的整數K疋1以上的整數）作為多維座標訊息來接收； 一初始值與多維座標值變換單元，該初始值與多維座標值變換單元係 將上述R作騎線性函數χ _ 4 χ (丨—χ )(以下稱為臟，〇< 、'。值Xo的小數點以下的部分變換成X。，並將i變換成多維 標值11 止’ ···，lK來為用計算LMAP來產生隨機數作準備； 暫存器該暫存器係將用來健存該初始值與多維座標值變換單元所 變換的初始值χο和多維座標值il，···，ik，…，lK; ❹ I屯函數„十算單疋，該混死函數計算單元係依照該暫存器中儲存的 初始值X。和多維座標值，對LMAp反覆進行計算精度為Ν位汹固定小 數點的计算’來產生1^位元的2進位數列&(㈣各位元是由（匕〇b 組成，bk，0 = [2xxN㈣，bk i = [2xxNx k+i]，…， k N i UXXlk + N]]，□是捨去小數點以下的部分的計算），再將榀 為LMAP的初始值又0的小數點以下的部分來將&變換成，並且將 上述腑的計算反覆進行，來產生N位元的2進位數列R ;’ ik (k=1 時 R i 1，··· ’ i k 為兄丨，· · ·，γ 性 D K ^Kil，為RQ — a，Rh — u的各 ^ (rk'〇rk'1，，，rk-N-i) ^ > rk.〇=[2xxN]，rk.i=[2xx 叫]’ ...，m叫2xx2n_iD來產生混泡2進位數數列，· 28 201005630 一隨機數暫存器，該隨機數暫存器係用來儲存該混沌函數計算單元所 輸出的Ν位元的2進位數數列Ru. — ik ;以及， 一隨機數產生控制單元，該隨機數產生控制單元係對該隨機數產生與 管理訊息輸入單元的動作、初始值與多維座標變換單元的動作、混沌函數 計算單元的計算以及將Rii，…以作為LMAp的初始值χ〇的小數點以下的 部分來變換成χ〇的計算’以k=i，2，··· ’ Κ的順序來執行（但是，當 Ο k=K時’不做將R"，..·，以向初始值X。的變換），來產生多維隨機數亿的 隨機數。 2 . —種隨機數產生管理方法，係依序包括下列步驟： a. 對所給與的N(N是2以上的整數）位元的2進位數列r和維數為κ 的多維座標訊息i (il ’ ...，ik，…，iK) (ik是0以上的整數，k=i， 2,…，K);將R作為非線性函數xt + 1 = 4xt(1 —χ〇 (簡稱LMAp， 〇<xt<l )的初始值叉。的小數點以下的部分，將丨轉換為各維座標值 il，…，ik，…’ iK，並將以和^ ’…，ik ’…’ iK儲存於一暫存器； b. 依照該暫存器所存初始值叉〇和汝，透過一混沌計算單元對^八卩進 行計算精度N位元的固定小數點計算法的反覆計算，來產生^^位元的2進 位數列Β* (B*的各位元由（bk.obkfbk.N-i)組成，b k, 〇 = [2χχ Nxik] bk’：L—[2xXNxik + 1] ’ ’ bk’N—Fl^XXNxik+Nf-l] ’ □是捨去 小數點以下的部分的計算）； C.該混沌計算單元再將&作為LMAp的初始值^^的小數點以下的部 分’對LMAP進行反覆計算，來產生n位元的2進位數列Rq ,..., ik (k==1 時1^1’“為 Ri ’ …’ k=K 時R" ikaR“，…，iK，R"，…，ik的各位 29 201005630 元由（rk，〇rk,i...rk’N-i)組成，rk’〇 = [2xxN]，rk’i = [2xxN+ 1]，…，Γ k , N_1 = [2xx 2N-1 ])並存入一隨機數暫存器； d. 將該隨機數暫存器所存Rii,...ik作為LMAP的初始值X。的小數點 以下的部分存入該暫存器；以及， e. 將上述步驟b、c、d的作業以k=l，2，…，K的順序來實行（但 是，k=K時不做將Rm，….iK向LMAP的初始值X。的變換），來產生多維 隨機數R。 八、圖式： 如次頁 30